经典进程同步问题
（1）生产者——消费者问题
单生产者——消费者问题
1.问题描述
系统中有一组生产者进程和一组消费者进程，生产者进程每次生产一个产品放入缓冲区；消费者进程每次从有界缓冲区中取出一个产品并使用。生产者和消费者共享一个初始为空、大小为n的缓冲区。
- 只有缓冲区没满时，生产者才能把产品放入缓冲区，否则必须等待。
- 只有缓冲区不空时，消费者才能从缓冲区中取出产品，否则必须等待。
- 缓冲区是临界资源，各进程必须互斥的访问
2.问题分析
由于缓冲区是临界资源必须互斥使用，因此需要设置一个互斥信号量mutex，缓冲区有两种状态：进程正在访问和没有进程正在访问，因此可以给mutex赋初值为1。
缓冲区中的大小是生产者和消费者都可以进行操作的，当缓冲区满时，生产者要等待消费者取走产品，按一定次序访问这属于同步关系；当缓冲区空时，消费者要等待生产者生产产品，按一定次序访问这属于同步关系，因此需要设置两个同步信号量，full和empty
Semaphore mutex = 1; //互斥信号量实现对缓冲区的互斥访问 Semaphore empty = n; //同步信号量，表示空闲缓冲区的数量，初值为有界缓冲区大小n Semaphore full = 0; //同步信号量，表示产品数量，也是非空缓冲区数量，初值为0
3.伪代码逻辑实现
Producer(){ while (1) { 生产一个产品; P(empty); //消耗一个空闲缓冲区 P(mutex); 把产品放入缓冲区; V(mutex); V(full); //增加一个产品 } } Consumer(){ while (1) { 生产一个产品; P(full); //消耗一个产品 P(mutex); 把产品放入缓冲区; V(mutex); V(empty); //增加一个空闲缓冲区 } }
由伪代码逻辑可以发现，实现两进程的同步关系，是在其中一个进程中执行P，另一个进程中执行V，（增加一个产品V(full) ,消耗一个产品P(full) )
不能交换两个P操作的先后顺序
多生产者——消费者问题
1.问题描述
桌子上有一个盘子，每次只能向其中放入一个水果。爸爸只向盘子中放苹果，妈妈只向盘子中放橘子，儿子专等着吃盘子中的橘子，女儿专等着吃盘子中的苹果。只有盘子为空时，爸爸妈妈才能往盘子里放一个水果。仅当盘子中有自己需要的水果时，儿子或女儿可以从盘子中取出水果。
2.问题分析
盘子相当于一个初始为空，大小为1的缓冲区。爸爸妈妈分别可以看作生产者进程1、生产者进程2，儿子可以看作消费者进程1，女儿可以看作消费者进程2
互斥关系：(mutex = 1) 对缓冲区（盘子）的访问要互斥地进行
同步关系（一前一后）：
1.父亲将苹果放入盘子后，女儿才能取苹果
2.母亲将橘子放入盘子后，儿子才能取橘子
只有盘子为空时，父亲或母亲才能放入水果
3.伪代码逻辑实现
semaphore mutex = 1; //实现互斥访问盘子(缓冲区) semaphore apple = 0; //盘子中有几个苹果 semaphore orange = 0; //盘子中有几个橘子 semaphore plate = 1; //盘子中还可以放多少个水果 dad(){ while(1){ 准备一个苹果; P(plate); P(mutex); 把苹果放入盘子; V(mutex); V(apple); } } mom(){ while(1){ 准备一个橘子; P(plate); P(mutex); 把橘子放入盘子; V(mutex); V(orange); } } daughter(){ while(1){ P(apple); P(mutex); 从盘子中取出苹果; V(mutex); V(plate); 吃苹果 } } son(){ while(1){ P(orange); P(mutex); 从盘子中取出橘子; V(mutex); V(plate); 吃掉橘子 } }
（2）读者——写者问题
1.问题描述
有两组并发进程: 读者和写者,共享一组数据区。
读者/写者问题是指保证一个写者进程必须与其他进程互斥访问共享对象的同步问题
- 允许多个读者同时执行读操作
- 不允许读者、写者同时操作
- 不允许多个写者同时操作
2.问题分析
两类进程：写进程、读进程
互斥关系：写进程——写进程、写进程——读进程。读进程与读进程不存在互斥关系。
写进程和任何进程都要互斥，设置一个互斥信号量rw，在写者访问共享文件前后分别执行P、V操作，读者进程和写者进程也要互斥，因此读者访问共享文件前后也要对rw进行P、V操作，但是如果所有读者进程在访问共享文件之前都进行P(rw)操作，那么会导致各个读进程之间也无法同时访问文件。该如何解决这个问题？
P（rw）和V（rw）其实就是对共享文件的加锁和解锁，既然各个读进程可以同时访问文件，而读进程和写进程需要互斥访问文件，那么就让第一个读进程对文件进行加锁，最后一个读进程对文件解锁，如何知道是还有几个读进程呢？就需要设置一个整形变量count来记录当前有几个读进程在在访问文件。
解决上述问题后，我们再来看这一种情况，当两个读进程并发来访问文件时，有可能第一个进程还没来的及进行count++，第二个进程就就已经过了判断count是否为0的操作了，这个时候第二个进程也被阻塞在P(rw)，再次出现了上述问题，该如何解决？ 其实仔细分析可知道会出现这种情况在于对count的判断和赋值没办法保证一致性，即不是原语操作，为了解决这个问题我们要引入一个互斥信号量mutex来保证对count的判断和赋值是一个互斥的操作。
3.伪代码逻辑
semaphore rw = 1; //用于实现对文件的互斥访问，表示当前是否有进程在访问共享文件 int count = 0; // 记录当前有几个读进程在访问文件 semaphore mutex = 1; //用于保证对count变量的互斥访问 writer(){ while(1){ P(rw); //写之前"加锁" 写文件 V(rw); //写之后"解锁" } } reader(){ while(1){ P(mutex); //各进程互斥访问count if(count==0) P(rw); //第一个读进程负责加锁 count++; //读进程+1 V(mutex); 读文件 P(mutex); //各进程互斥访问count count--; // 访问文件的读进程数-1 if(count == 0) V(rw); //最后一个读进程负责解锁 V(mutex); } }
在这个算法中，读进程是优先的，如果有一个读进程正在访问文件，这个时候来了一堆读进程和一个写进程，那么读进程一直在访问文件，写进程可能一直等待，发生”饿死“，如何解决这个问题？
semaphore rw = 1; //用于实现对文件的互斥访问，表示当前是否有进程在访问共享文件 int count = 0; // 记录当前有几个读进程在访问文件 semaphore mutex = 1; //用于保证对count变量的互斥访问 semaphore w = 1 // 实现写者优先 writer(){ while(1){ P(w) P(rw); //写之前"加锁" 写文件 V(rw); //写之后"解锁" V(w); } } reader(){ while(1){ p(w) P(mutex); //各进程互斥访问count if(count==0) P(rw); //第一个读进程负责加锁 count++; //读进程+1 V(mutex); V(w); 读文件 P(mutex); //各进程互斥访问count count--; // 访问文件的读进程数-1 if(count == 0) V(rw); //最后一个读进程负责解锁 V(mutex); } }
加入互斥信号量w就可以解决写者饿死的问题了，当一个读者在读文件时此时w已经被解锁了，这个时候一个写者进程尝试访问文件，先对w进行加锁，然后阻塞在rw，此时读者进程再来就会被阻塞在w，等待写进程执行。
（3）哲学家进餐问题
1.问题描述
一张圆桌上坐着5名哲学家，每两个哲学家之间的桌上摆一根筷子，桌子的中间是一碗米饭。哲学
家们倾注毕生的精力用于思考和进餐，哲学家在思考时，并不影响他人。只有当哲学家饥饿时，
才试图拿起左、右两根筷子(一根一根地拿起)。如果筷子已在他人手上，则需等待。饥饿的哲
学家只有同时拿起两根筷子才可以开始进餐，当进餐完毕后，放下筷子继续思考。
2.问题分析
1.关系分析。系统中有5个哲学家进程，5位哲学家与左右邻居对其中间筷子的访问是互斥关系。
2.整理思路。这个问题中只有互斥关系，但与之前遇到的问题不同的是，每个哲学家进程需要同时持有两个临界资源才能开始吃饭。如何避免临界资源分配不当造成的死锁现象，是哲学家问题的精髓。
3.信号量设置。定义互斥信号量数组chopstick[5]={1,1,1,1,1}用于实现对5个筷子的互斥访问。并对哲学家按0~4编号，哲学家i左边的筷子编号为i，右边的筷子编号为(i+1)%5。
semaphore chopstick[5] = {1,1,1,1,1}; Philosopher i： while (1) { 思考; P(chopstick[i]); P(chopstick[(i+1) % 5]); 进食; V(chopstick[i]); V(chopstick[(i+1) % 5]); }
这种解法会导致死锁，每个哲学家都拿一只筷子然后等待其他人放下筷子
为防止死锁发生还可采取的措施：
- 最多允许4个哲学家同时去拿左边的筷子；
- 仅当一个哲学家左右两边的筷子都可用时，才允许他拿筷子；
- 给所有哲学家编号，奇数号的哲学家必须首先拿左边的筷子，偶数号的哲学家则反之
3.伪代码逻辑
1.最多允许4个哲学家同时去拿左边的筷子
semaphore chopstick[5] = {1,1,1,1,1}; semaphore count = 4; //最多允许四位哲学家同时进餐 Philosopher i： while (1) { 思考; p(count); P(chopstick[i]); //取左 P(chopstick[(i+1) % 5]); //取右 进餐; V(chopstick[i]); //放左 V(chopstick[(i+1) % 5]); // 放右 V(count); }
2.仅当一个哲学家左右两边的筷子都可用时，才允许他拿筷子；
// 记录型信号量法 semaphore chopstick[5] = {1,1,1,1,1}; semaphore mutex = 1; //互斥的取筷子 Philosopher i： while (1) { 思考; p(mutex); P(chopstick[i]); //取左 P(chopstick[(i+1) % 5]); // 取右 V(mutex); 进餐; V(fchopstick[i]); //放左 V(chopstick[(i+1) % 5]); // 放右 }
//AND信号量法 semaphore chopstick[5] = {1,1,1,1,1}; Philosopher i： while (1) { 思考; Swait(chopstick[(i+1)%5]，chopstick[i]); 进餐; Signal(chopstick[(i+1) % 5],chopstick[i]); }
3.给所有哲学家编号，奇数号的哲学家必须首先拿左边的筷子，偶数号的哲学家则反之
// 记录型信号量法 semaphore chopstick[5] = {1,1,1,1,1}; Philosopher i： while (1) { 思考; if(i % 2 == 1) { P(chopstick[i]); //取左 P(chopstick[(i+1) % 5]); // 取右 }else{ P(chopstick[(i+1) % 5]); // 取右 P(chopstick[i]); //取左 } 进餐; V(chopstick[i]); //放左 V(chopstick[(i+1) % 5]); // 放右 }
参考《计算机操作系统》（汤小丹 第四版）
参考《王道考研操作系统》
