信号量机制解决经典同步互斥问题

生产者 / 消费者问题、读者 / 写者问题和哲学家问题是操作系统的三大经典同步互斥问题。本文将介绍这三个问题的基本特点以及如何用信号量机制进行解决。

在分析这三个问题之前，我们首先需要了解用信号量机制解决同步互斥问题的一般规律： 实现同步与互斥的P、V操作都是成对出现，但互斥问题的P、V操作出现在同一个进程中；同步问题的P、V操作出现在不同进程中。

1. 生产者 / 消费者问题

1.1 基本特点

生产者/消费者问题具体表现为：

1. 两个进程对同一个内存资源进行操作，一个是生产者，一个是消费者。
2. 生产者往共享内存资源填充数据，如果区域满，则等待消费者消费数据。
3. 消费者从共享内存资源取数据，如果区域空，则等待生产者填充数据。
4. 生产者的填充数据行为和消费者的消费数据行为不可在同一时间发生。

1.2 解决思路

首先，我分析了其中存在的同步互斥关系： 生产者-消费者之间的同步关系表现为缓冲区空，则消费者需要等待生产者往里填充数据，缓冲区满则生产者需要等待消费者消费。两者共同完成数据的转移或传送；生产者-消费者之间的互斥关系表现为生产者往缓冲区里填充数据的时候，消费者无法进行消费，需要等待生产者完成工作，反之亦然。

然后，我根据存在的互斥同步关系设置了三个信号量：由于存在互斥关系，我设置了一个互斥信号量mutex控制两者不能同时操作缓冲区；由于存在同步关系，我设置了两个信号量empty和full分别表示缓冲区中的资源数和缓冲区中的空位置数。mutex初值为1，empty初值为0，full初值为缓冲区大小。

最后，进行对生产者和消费者的行为设计：

针对生产者，生产者生产资源，先用P(full)判断缓冲区是否有空，再用P(mutex)判断是否有人在用缓冲区，若缓冲区有空且无人用，则生产者将资源放入缓冲区。放完后，先用V(mutex)释放缓冲区的使用权，再用V(empty)将缓冲区中的资源数加1，生产者进程结束。

针对消费者，消费者先用P(empty)判断缓冲区中是否有资源，再用P(mutex)判断缓冲区是否有人用，若缓冲区有资源且无人用，则消费者从缓冲区中取资源。取完后，先用V(mutex)释放缓冲区的使用权，再用V(full)将缓冲区中的空位置数加1，消费者进程结束。

1.3 代码及运行结果

生产者 / 消费者问题的C语言代码实现如下：

/*****************************************************************问题：多个生产者，多个消费者，有限缓冲区*描述：*1.两个进程对同一个内存资源进行操作，一个是生产者，一个是消费者。*2.生产者往共享内存资源填充数据，如果区域满，则等待消费者消费数据。*3.消费者从共享内存资源取数据，如果区域空，则等待生产者填充数据。*4.生产者的填充数据行为和消费者的消费数据行为不可在同一时间发生。
****************************************************************/
#include <stdio.h>
#include <unistd.h>
#include <pthread.h>
#include <semaphore.h>#define N 5  //生产者N个，消费者N个
#define BUFFERSIZE 3  //缓冲区大小sem_t mutex;  //互斥信号量
sem_t empty;  //缓冲区中的资源数
sem_t full;   //缓冲区的空位置数void *producer(void *arg) {int i = *((int *) arg);//生产者生产资源printf("The %dth producer is producing...\n", i);sleep(3);sem_wait(&full);  //判断缓冲区是否有空sem_wait(&mutex); //判断是否有人在用缓冲区//若缓冲区有空且无人用，生产者将资源放入缓冲区printf("The %dth producer is appending...\n", i);sleep(3);sem_post(&mutex); //生产者退出缓冲区sem_post(&empty); //缓冲区的资源数增加  
}void *consumer(void *arg) {int i = *((int *) arg);sem_wait(&empty); //判断缓冲区中是否有资源sem_wait(&mutex); //判断是否有人在用缓冲区//若缓冲区中有资源且无人用，消费者从缓冲区取资源printf("The %dth consumer is taking...\n", i);sleep(3);sem_post(&mutex); //消费者退出缓冲区sem_post(&full);  //缓冲区的空位置数增加//消费者消耗资源printf("The %dth consumer is consuming...\n", i);sleep(3);
}int main() {int i;pthread_t proThread[N];pthread_t conThread[N];int proId[N];int conId[N];sem_init(&mutex, 0, 1);  //初始化互斥信号量为1sem_init(&empty, 0, 0);  //初始化缓冲区中的资源数为0sem_init(&full, 0, BUFFERSIZE);  //初始化缓冲区中的空位置等于缓冲区大小for (i = 0; i < N; i++) {proId[i] = i;conId[i] = i;pthread_create (&proThread[i], NULL, producer, &proId[i]);//创建生产者线程pthread_create (&conThread[i], NULL, consumer, &conId[i]);//创建消费者线程}for ( i = 0; i < N; i++) {pthread_join(proThread[i], NULL);//等待所有的生产者线程执行完毕再结束pthread_join(conThread[i], NULL);//等待所有的消费者线程执行完毕再结束}return 0;
}

运行结果如下图所示：

2. 读者 / 写者问题

2.1 基本特点

读者/写者问题具体表现为：

1. 一个进程在读的时候，其他进程也可以读。
2. 一个进程在读/写的时候，其他进程不能进行写/读。
3. 一个进程在写的时候，其他进程不能写。

2.2 解决思路

首先，分析其中存在的同步互斥关系：读者-写者之间没有明显的同步关系，它们不需要合作完成某件事情；读者-写者之间的互斥关系表现为两者不能同时访问文件。

然后，根据存在的互斥关系设置信号量：由于读者-写者的互斥，我设置了一个互斥信号量wsem来控制读者和写者的互斥访问。但如果只设置了这一个信号量，读者和读者之间的互斥也出现了。因为可能会有多个读者，所以我又设置了一个变量readcount记录读者的数量。这时，readcount又需要实现多个读者对它的互斥访问，为此，我设置了一个互斥信号量x。wsem与x的初值均为1，readcount的初值为0，现在所有的信号量已经设置好了。

最后，进行行为设计：读者 / 写者问题有读者优先与写者优先两种解决思路。

2.2.1 读者优先

读者优先的解决思路如下：

针对读进程，首先用P(x)判断是否有人在更新readcount，若无人在改动readcount，则将readcount加1。如果加1后的readcount等于1，则说明加1前的readcount为0，此时的进程为第一个读进程。第一个读进程出现，就要用P(wsem)来限制写进程的访问。然后，用V(x)释放readcount的更新权，读者开始读。读完后，再用P(x)重新获取readcount的更新权，将读进程的数量readcount减1。如果减1后的readcount等于0，则说明所有的读进程都读完了，可以用V(wsem)释放读/写的访问权了。最后，再用V(x)释放readcount的更新权。读进程结束。

针对写进程，首先用P(wsem)获取写的访问权，不让其他读/写进程访问。然后该写进程开始写，写完再用V(wsem)释放读/写的访问权。写进程结束。

2.2.2 写者优先

写者优先与读者优先的很大不同是，如果同时有读写进程在等待，要保证在等待的写进程比在等待的读进程优先执行。为此，设置了信号量z，保证等待的写进程可以跳过它前面等待的读进程。在读者优先的信号量设置基础上，增加了互斥信号量rsem控制写进程想写时，不允许新的读进程来读。增加了整型变量writecount记录等待的写者数，因writecount是共享变量，因此还要设置新的互斥信号量y以实现进程对writecount的互斥访问。

行为设计如下：

针对读进程，首先用P(z)保证写者优先，然后用P(rsem)判断有没有写进程在临界区，有，则等待；没有，则不让新的写进程进入临界区。接下来用P(x)开始对readcount的互斥访问，更新读进程的数量，第一个读进程用P(wsem)判断是否有写进程在进行写操作，有，则需要等待；没有，则不让写进程进行新写操作，用V(x)结束对readcount的互斥访问，用V(rsem)给写进程进入临界区的权利。然后V(z)，可以开始读了。读完后的行为与读者优先时一样。读进程结束。

针对写进程，首先用P(y)开始对writecount的互斥访问，更新写进程的数量，第一个写进程需要判断是否有读进程在临界区，有的话需要等待，没有的话不让新的读进程进来。然后，用V(y)结束对writecount的互斥访问。接着就是写进程的互斥写操作了，同一时刻只有一个写进程可以写，这些行为也与读者优先时一样。在写完后，用P(y)开始对writecount的互斥访问，更新写进程数量。对最后一个离开临界区的写进程，用V(rsem)给读进程可以进临界区的权利，最后用V(y)结束对writecount的互斥访问。写进程结束。

2.3 代码及运行结果

2.3.1 读者优先

读者 / 写者问题（读者优先）的C语言代码实现如下：

/***************************************************************问题：读者/写者问题，读者优先*描述：*1.一个进程在读的时候，其他进程也可以读。*2.一个进程在读/写的时候，其他进程不能进行写/读。*3.一个进程在写的时候，其他进程不能写。*4.当至少有一个读进程在读时，后来的读进程无须等待，可直接加入。
**************************************************************/
#include <stdio.h>
#include <unistd.h>
#include <pthread.h>
#include <semaphore.h>#define N 10  //读者N个，写者N个int readcount;  //记录读进程的数量
sem_t x;     //x控制readcount的互斥访问
sem_t wsem;  //wsem对写互斥控制void *reader(void *arg) {int i = *((int *) arg);sem_wait(&x);readcount++;if (readcount == 1) { //第一个读进程出现，锁住不让写sem_wait(&wsem);}sem_post(&x);printf("The %dth reader is reading...\n", i);sleep(3);sem_wait(&x);readcount--;if (readcount == 0) { //所有的读进程读完，释放写的访问sem_post(&wsem);}sem_post(&x);
}void *writer(void *arg) {int i = *((int *) arg);sem_wait(&wsem); //锁住不让其他写进程写printf("The %dth writer is writing...\n", i);sleep(3);sem_post(&wsem); //释放写的访问
}int main() {int i;pthread_t rdThread[N];pthread_t wtThread[N];int rdId[N];int wtId[N];readcount = 0;//初始化信号量sem_init(&x, 0, 1);sem_init(&wsem, 0, 1);for (i = 0; i < N; i++) {rdId[i] = i;wtId[i] = i;pthread_create (&rdThread[i], NULL, reader, &rdId[i]);//创建读者线程pthread_create (&wtThread[i], NULL, writer, &wtId[i]);//创建写者线程}for ( i = 0; i < N; i++) {pthread_join(rdThread[i], NULL);//等待所有的读者线程执行完毕再结束pthread_join(wtThread[i], NULL);//等待所有的写者线程执行完毕再结束}return 0;
}

运行结果如下图所示：

2.3.2 写者优先

读者 / 写者问题（写者优先）的C语言代码实现如下：

/***************************************************************问题：读者/写者问题，写者优先*描述：*1.一个进程在读的时候，其他进程也可以读。*2.一个进程在读/写的时候，其他进程不能进行写/读。*3.一个进程在写的时候，其他进程不能写。*4.写进程声明想写时，不允许新的读进程来访问数据
**************************************************************/
#include <stdio.h>
#include <unistd.h>
#include <pthread.h>
#include <semaphore.h>#define N 10  //读者N个，写者N个int readcount;  //记录读进程的数量
int writecount; //记录写进程的数量
sem_t x;     //x控制readcount的互斥访问
sem_t y;     //y控制writecount的互斥访问
sem_t z;     //z保证写跳过读，保证写优先
sem_t wsem;  //wsem对写互斥控制
sem_t rsem;  //rsem对读互斥控制void *reader(void *arg) {int i = *((int *) arg);sem_wait(&z);sem_wait(&rsem);sem_wait(&x);readcount++;if (readcount == 1) { //第一个读进程出现，锁住不让写sem_wait(&wsem);}sem_post(&x);sem_post(&rsem);  //释放读的访问，允许其他读者进入sem_post(&z);printf("The %dth reader is reading...\n", i);sleep(3);sem_wait(&x);readcount--;if (readcount == 0) { //所有的读进程读完，释放写的访问sem_post(&wsem);}sem_post(&x);
}void *writer(void *arg) {int i = *((int *) arg);sem_wait(&y);writecount++;if(writecount == 1) { //第一个写进程，判断是否有读进程正在进行sem_wait(&rsem);}sem_post(&y);sem_wait(&wsem); //锁住不让其他写进程写printf("The %dth writer is writing...\n", i);sleep(3);sem_post(&wsem); //释放写的访问sem_wait(&y);writecount--;if (writecount == 0) { //所有写进程写完，释放读的访问sem_post(&rsem);}sem_post(&y);
}int main() {int i;pthread_t rdThread[N];pthread_t wtThread[N];int rdId[N];int wtId[N];readcount = 0;writecount = 0;//初始化信号量sem_init(&x, 0, 1);sem_init(&y, 0, 1);  sem_init(&z, 0, 1);  sem_init(&wsem, 0, 1);sem_init(&rsem, 0, 1);for (i = 0; i < N; i++) {rdId[i] = i;wtId[i] = i;pthread_create (&rdThread[i], NULL, reader, &rdId[i]);//创建读者线程pthread_create (&wtThread[i], NULL, writer, &wtId[i]);//创建写者线程}for ( i = 0; i < N; i++) {pthread_join(rdThread[i], NULL);//等待所有的读者线程执行完毕再结束pthread_join(wtThread[i], NULL);//等待所有的写者线程执行完毕再结束}return 0;
}

运行结果如下图所示：

3. 哲学家问题

3.1 基本特点

哲学家问题的具体表现为：
有N个哲学家，他们的生活方式是交替地进行思考和进餐，哲学家们共用一张圆桌，分别坐在周围的N张椅子上，在圆桌上有N个碗和N支筷子，平时哲学家进行思考，饥饿时便试图取其左、右最靠近他的筷子，只有在他拿到两支筷子时才能进餐，进餐完毕，放下筷子又继续思考。

约束条件如下：

1. 只有拿到两只筷子时，哲学家才能吃饭。
2. 如果筷子已被别人拿走，则必须等别人吃完之后才能拿到筷子。
3. 任一哲学家在自己未拿到两只筷子吃饭前，不会放下手中拿到的筷子。
4. 用完之后将筷子返回原处。

3.2 解决思路

首先，分析其中存在的同步互斥关系：筷子是临界资源，每根筷子只能一个人取，这是互斥关系；如果筷子被取走，那么需要等待，这是同步关系。

可能出现死锁的错误解法是：设置一个信号量表示一只筷子，有N只筷子，所以设置N个信号量，哲学家每次饥饿时先试图拿左边的筷子，再试图拿右边的筷子，拿不到则等待，拿到了就吃饭，最后逐个放下筷子。这种解法下，如果N个哲学家同时感到饥饿，同时试图拿左边的筷子，都没成功；又同时试图拿右边的筷子，又都没成功，由于第3个约束条件的存在，这时出现了死锁。

因此，此问题的关键是互斥及避免死锁。在错误解法的基础上，一种可行解法是让奇数号与偶数号的哲学家拿筷子的顺序不同，破坏环路等待条件。

第二种可行的解法是只允许N-1位哲学家同时进餐，这样N-1个人都拿起一根筷子时，第N个人不能再拿筷子，就空出了一根筷子。

3.3 代码及运行结果

3.3.1 方法1

编号为奇数的哲学家先拿左手的筷子，编号为偶数的哲学家先拿右手的筷子，C语言代码实现如下：

/************************************************************************问题：哲学家问题*描述：*五个哲学家共用一张圆桌，分别坐在周围的五张椅子上，*在桌子上有五个碗和五根筷子，他们的状态是思考和进餐交替，*平时，一个哲学家思考，饿了就取离他最近的筷子，只有拿到了两只筷子才能进餐。*进餐毕，放下筷子继续思考。*方法1：编号为奇数的哲学家先拿左手的筷子，编号为偶数的哲学家先拿右手的筷子
***********************************************************************/
#include <stdio.h>
#include <unistd.h>
#include <pthread.h>
#include <semaphore.h>#define N 5/*一共N根筷子，每根筷子设置一个信号量,记录筷子的状态*/
sem_t chopsticks[N]; //1代表筷子已经被用过，0代表筷子正等待被使用void *philosopher(void *arg) {int i = *((int *) arg);//为避免死锁，编号为奇数的哲学家先拿左手的筷子，编号为偶数的哲学家先拿右手的筷子if (i % 2) { //奇数编号sem_wait(&chopsticks[i]);  //先拿左手的筷子sleep(1);sem_wait(&chopsticks[(i + 1) % N]);  //再拿右手的筷子//哲学家吃啊吃printf("The %dth philosopher is eating...\n", i);sleep(3); sem_post(&chopsticks[(i + 1) % N]);sleep(1);sem_post(&chopsticks[i]);//哲学家想啊想printf("The %dth philosopher is thinking...\n", i);sleep(3);  }else {sem_wait(&chopsticks[(i + 1) % N]);  //先拿右手的筷子sleep(1);sem_wait(&chopsticks[i]);  //再拿左手的筷子//哲学家吃啊吃printf("The %dth philosopher is eating...\n", i);sleep(3); sem_post(&chopsticks[i]);sleep(1);sem_post(&chopsticks[(i + 1) % N]);//哲学家想啊想printf("The %dth philosopher is thinking...\n", i);sleep(3);  }
}int main() {int i;pthread_t thread[N];int id[N];  //记录哲学家编号for (i = 0; i < N; i++) { //初始化信号量为1sem_init(&chopsticks[i], 0, 1);}for (i = 0; i < N; i++) {id[i] = i;pthread_create (&thread[i], NULL, philosopher, &id[i]);//创建线程}for ( i = 0; i < N; i++) {pthread_join(thread[i], NULL);//等待所有的线程执行完毕再结束}return 0;
}

运行结果如下图所示：

3.3.2 方法2

只允许N-1位哲学家同时进入餐厅，C语言代码实现如下：

/************************************************************************问题：哲学家问题*描述：*五个哲学家共用一张圆桌，分别坐在周围的五张椅子上，*在桌子上有五个碗和五根筷子，他们的状态是思考和进餐交替，*平时，一个哲学家思考，饿了就取离他最近的筷子，只有拿到了两只筷子才能进餐。*进餐毕，放下筷子继续思考。*方法2：只允许4位哲学家同时进入餐厅
***********************************************************************/
#include <stdio.h>
#include <unistd.h>
#include <pthread.h>
#include <semaphore.h>#define N 5/*一共N根筷子，每根筷子设置一个信号量,记录筷子的状态*/
sem_t chopsticks[N]; //1代表筷子已经被用过，0代表筷子正等待被使用
sem_t room;void *philosopher(void *arg) {int i = *((int *) arg);sem_wait(&room);sleep(1);sem_wait(&chopsticks[i]);  //先拿左手的筷子sleep(1);sem_wait(&chopsticks[(i + 1) % N]);  //再拿右手的筷子//哲学家吃啊吃printf("The %dth philosopher is eating...\n", i);sleep(3); sem_post(&chopsticks[(i + 1) % N]);sleep(1);sem_post(&chopsticks[i]);sleep(1);sem_post(&room);//哲学家想啊想printf("The %dth philosopher is thinking...\n", i);sleep(3);  
}int main() {int i;pthread_t thread[N];int id[N];  //记录哲学家编号for (i = 0; i < N; i++) { //初始化筷子信号量为1sem_init(&chopsticks[i], 0, 1);}sem_init(&room, 0, 4);   //初始化room信号量为4for (i = 0; i < N; i++) {id[i] = i;pthread_create (&thread[i], NULL, philosopher, &id[i]);//创建线程}for ( i = 0; i < N; i++) {pthread_join(thread[i], NULL);//等待所有的线程执行完毕再结束}return 0;
}

运行结果如下图所示：