操作系统之进程同步

转专业至今课表还没出来，先去上了节田老师的操作系统课，好评，最喜欢这种课上都是代码的课了。

转专业来之不易，今后更加好好珍惜机会，努力学习。

今天下午这节课讲的是进程同步，也算是并发程序启蒙课吧，听起来这有趣，打算将老师 ppt 上写的几个并发程序伪代码实现下，体会下并发程序的开发。

因为老师给出的例子是关于进程间共享资源产生的问题，以及如何去解决，我打算用线程（pthread库）来实现，因为线程的资源可以共享（共享全局区域、堆），容易写，和并发的进程大同小异，且思想是一样的。

争夺临界资源

下面第一个例子是并发程序争夺 临界资源 会出现的问题，这里的临界资源是 栈。

/*************************************************************************
	> File Name: parallel.cpp
	  > Author: Netcan
	  > Blog: http://www.netcan666.com
	  > Mail: 1469709759@qq.com
	  > Created Time: 2016-09-13 二 19:13:5 CST
 ************************************************************************/

#include <iostream>
#include <cstdio>
#include <pthread.h>
#include <unistd.h>
using namespace std;

int top = -1; // 栈顶指针
const int n = 256; // 栈的空间大小
int stack[n]; // 栈

void printStack(int size) {
	for(int i=0; i<size; ++i)
		printf("%d", stack[i]);
	printf("\n");
}

void *funA(void*) {
	while(true) {
		top = (++top) % n;
		usleep(10);
		stack[top] = 1;
		usleep(10);
	}
	return NULL;
}

void *funB(void*) {
	while(true) {
		top = (++top) % n;
		usleep(10);
		stack[top] = 2;
		usleep(10);
	}
	return NULL;
}


int main() {
	pthread_t t1, t2;
	pthread_create(&t1, NULL, funA, NULL);
	pthread_create(&t2, NULL, funB, NULL);
	while(top < 255);
	printStack(255);
	return 0;
}

输出结果：

0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 1 1 0 1 0 1 0 2 0 2 0 2 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 2 1 2 1 2 0 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1

这里我用了 usleep 函数，它能让程序暂停微秒级，即(1000us = 1ms)。这样做是为了让程序程序浪费掉 cpu 执行的时间片，从而更容易调到另一个线程执行。

现在解释下运行的结果，当函数 A 执行 ++top 的时候，正好 cpu 调到函数 B 执行++top，从而跳过了一个位置，这样就产生了并发程序对临界资源共享的问题。

下面我们来解决这些问题。

临界区访问控制模型

在临界区代码前后分别加上进入区、退出区，即临界区的一般访问模型。比如（引用 ppt 内容）：

repeat                           repeat
	critical section;            	entry section;
	remainder section;   =>        		critical section;
until false;                     	exit section;
	                              		remainder section;
                                 until false;

下面给出老师 ppt 的几个解法的实现，以及其中隐含的问题。

软件解法 1：按需访问

在程序加个变量 free 来标记资源是否空闲，很容易得出一下解法：

/*************************************************************************
	> File Name: parallel.cpp
	  > Author: Netcan
	  > Blog: http://www.netcan666.com
	  > Mail: 1469709759@qq.com
	  > Created Time: 2016-09-13 二 19:13:5 CST
 ************************************************************************/

#include <iostream>
#include <cstdio>
#include <pthread.h>
#include <unistd.h>
using namespace std;

int top = -1; // 栈顶指针
const int n = 256; // 栈的空间大小
int stack[n]; // 栈
bool free = false; // 资源空闲标志

void printStack(int size) {
	for(int i=0; i<size; ++i)
		printf("%d", stack[i]);
	printf("\n");
}

void *funA(void*) {
	while(true) {
		// entry section
		while(free);
		free = true;
		// critical section
		top = (++top) % n;
		usleep(10);
		stack[top] = 1;
		usleep(10);
		// exit section
		free = false;
		// remainder section
	}
	return NULL;
}

void *funB(void*) {
	while(true) {
		// entry section
		while(free);
		free = true;
		// critical section
		top = (++top) % n;
		usleep(10);
		stack[top] = 2;
		usleep(10);
		// exit section
		free = false;
		// remainder section
	}
	return NULL;
}

int main() {
	pthread_t t1, t2;
	pthread_create(&t1, NULL, funA, NULL);
	pthread_create(&t2, NULL, funB, NULL);
	while(top < 255);
	printStack(255);
	return 0;
}

程序看上去似乎是正确的，没什么大问题，我们来看看结果：

2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

嘛，看上去没什么大问题啊，那不妨多试几次吧。。。

2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 2 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0

果然经不起考验，3 次就露出马脚了。

这段代码出现的错误在于，当我 A 函数执行到 while(free)，这时候free 为false自然不会循环，但是会出现 cpu 调到 B 函数执行，这时候 while(free) 也不会循环，结果到后面就会出现同时 ++top 的情况了。这段代码违背了 忙则等待 的原则。

软件解法 2：轮询

来看看第二个解法。

/*************************************************************************
	> File Name: parallel.cpp
	  > Author: Netcan
	  > Blog: http://www.netcan666.com
	  > Mail: 1469709759@qq.com
	  > Created Time: 2016-09-13 二 19:13:5 CST
 ************************************************************************/

#include <iostream>
#include <cstdio>
#include <pthread.h>
#include <unistd.h>
using namespace std;

int top = -1; // 栈顶指针
const int n = 256; // 栈的空间大小
int stack[n]; // 栈
int turn = 1; // 轮流标记

void printStack(int size) {
	for(int i=0; i<size; ++i)
		printf("%d", stack[i]);
	printf("\n");
}

void *funA(void*) {
	while(true) {
		// entry section
		while(2 == turn);
		// critical section
		top = (++top) % n;
		usleep(10);
		stack[top] = 1;
		usleep(10);
		// exit section
		turn = 2;
		// remainder section
	}
	return NULL;
}

void *funB(void*) {
	while(true) {
		// entry section
		while(1 == turn);
		// critical section
		top = (++top) % n;
		usleep(10);
		stack[top] = 2;
		usleep(10);
		// exit section
		turn = 1;
		// remainder section
	}
	return NULL;
}

int main() {
	pthread_t t1, t2;
	pthread_create(&t1, NULL, funA, NULL);
	pthread_create(&t2, NULL, funB, NULL);
	while(top < 255);
	printStack(255);
	return 0;
}

跑几下看看，没什么大问题：

1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1

是的，这段代码是正确的，但是它限制了资源访问顺序，所以你看到的结果永远是1 2 1 2...，这是没有必要的（限制访问顺序），PASS。

软件解法 3：访前先看

show you the code:

/*************************************************************************
	> File Name: parallel.cpp
	  > Author: Netcan
	  > Blog: http://www.netcan666.com
	  > Mail: 1469709759@qq.com
	  > Created Time: 2016-09-13 二 19:13:5 CST
 ************************************************************************/

#include <iostream>
#include <cstdio>
#include <pthread.h>
#include <unistd.h>
using namespace std;

int top = -1; // 栈顶指针
const int n = 256; // 栈的空间大小
int stack[n]; // 栈
bool Aturn = false;
bool Bturn = false;

void printStack(int size) {
	for(int i=0; i<size; ++i)
		printf("%d", stack[i]);
	printf("\n");
}

void *funA(void*) {
	while(true) {
		// entry section
		Aturn = true;
		while(Bturn);
		// critical section
		top = (++top) % n;
		usleep(10);
		stack[top] = 1;
		usleep(10);
		// exit section
		Aturn = false;
		// remainder section
	}
	return NULL;
}

void *funB(void*) {
	while(true) {
		// entry section
		Bturn = true;
		while(Aturn);
		// critical section
		top = (++top) % n;
		usleep(10);
		stack[top] = 2;
		usleep(10);
		// exit section
		Bturn = false;
		// remainder section
	}
	return NULL;
}

int main() {
	pthread_t t1, t2;
	pthread_create(&t1, NULL, funA, NULL);
	pthread_create(&t2, NULL, funB, NULL);
	while(top < 255);
	printStack(255);
	return 0;
}

猜猜结果是多少？我不知道，因为我至今没看到结果，如果你仔细看代码的话，你会发现很容易进入 Aturn 和Bturn都为 true 的情况，所以 2 个函数都死循环了。

这段代码违背了 空闲让进 的原则。

面包坊算法（Peterson算法）

这个代码名叫 Peterson 算法，于 1981 年提出，这里给出只有 2 个线程并发的简化代码。毋庸置疑，我看到标题就不用怀疑其正确性了 = =

/*************************************************************************
	> File Name: parallel.cpp
	  > Author: Netcan
	  > Blog: http://www.netcan666.com
	  > Mail: 1469709759@qq.com
	  > Created Time: 2016-09-13 二 19:13:5 CST
 ************************************************************************/

#include <iostream>
#include <cstdio>
#include <pthread.h>
#include <unistd.h>
using namespace std;

int top = -1; // 栈顶指针
const int n = 256; // 栈的空间大小
int stack[n]; // 栈
bool turn; // 轮到谁？线程个数为 2
bool interested[2]; // 兴趣数组，初值为 false
void enter_region(bool thread) {
	bool other = ~thread;
	interested[thread] = true;
	turn = thread;
	while(turn == thread && interested[other] == true);
}

void leave_region(bool thread) {
	interested[thread] = false;
}

void printStack(int size) {
	for(int i=0; i<size; ++i)
		printf("%d", stack[i]);
	printf("\n");
}

void *funA(void*) {
	while(true) {
		// entry section
		enter_region(0);
		// critical section
		top = (++top) % n;
		stack[top] = 1;
		// exit section
		leave_region(0);
		// remainder section
	}
	return NULL;
}

void *funB(void*) {
	while(true) {
		// entry section
		enter_region(1);
		// critical section
		top = (++top) % n;
		stack[top] = 2;
		// exit section
		leave_region(1);
		// remainder section
	}
	return NULL;
}

int main() {
	pthread_t t1, t2;
	pthread_create(&t1, NULL, funA, NULL);
	pthread_create(&t2, NULL, funB, NULL);
	while(top < 255);
	printStack(255);
	return 0;
}

运行结果：

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1

如果你仔细看的话，会发现我去掉 usleep 了，这样做是为了让结果更加明显，否则得到的结果几乎和轮询的结果一样的。

之所以也叫面包坊算法，老师的介绍是因为算法源于老外，老外喜欢吃面包，这个算法和面包坊加工一样，先进先出。

我觉得这个代码的精髓在于 turn = thread，当初第一次看到这个代码的时候，我在想这个应该可以化简去繁，但是仔细一想，这个turn 是全局变量，很巧妙，很可能因为其他线程而改变，第二个精髓的地方在于判断 if(turn == thread，由于线程的id 不一样，所以总能保证有一个在执行，其他线程就绪。

硬件解法 1：TSL 指令

因为 TSL 指令是一条原语（即不可中断），所以不好实现，这里略过，可看看书。

硬件解法 2：SWAP 指令

略过，理由如上。

以上几种解法，虽然有些满足同步要求，但是都违背了这样的原则：让权等待 ，据说 信号量 能很好解决这个问题，让我们拭目以待吧 = =

参考资料

• Linux/Unix 系统编程手册（上册）第 30 章：线程同步
• 合肥工业大学田老师操作系统课件：进程