在上一篇笔记中，我们介绍到了通过信号量机制解决进程同步和进程互斥问题的原理，不过，在遇到实际问题的时候，信号量机制到底是如何发挥作用的呢？这篇笔记将会从几个经典的问题出发，在解决问题的过程中，我们会体会到信号量机制的运用。
1 生产者 — 消费者问题
生产者 — 消费者问题描述的是一个对产品生产和消费的过程：首先，对于生产者，如果缓冲区没满，它就会生产产品并将其放入缓冲区，如果缓冲区已满，它就会进行等待；对于消费者，如果缓冲区不空，它就会取走产品并释放缓冲区，如果缓冲区已空，它就会进行等待。
对于这个问题，不难看出有两个进程，一个是生产者进程，一个是消费者进程；同时有一个互斥关系，在同一时间内，只能有一个进程访问同一个缓冲区，要么放入产品，要么取走产品；同时有两个同步关系，一个指的是：必定是先生产产品，后取走产品，另一个指的是：必定是先释放缓冲区，后使用缓冲区。
因此，我们在这里需要准备两个进程，一个是表示生产者进程的 producer，一个是表示消费者进程的 consumer；同时，我们需要准备三个信号量。第一个信号量是互斥信号量，实现对缓冲区这个资源的互斥访问，用 mutex = 1 表示；第二个信号量是同步信号量，表示空闲缓冲区的数量，用 empty = n 表示；第三个信号量也是同步信号量，表示非空闲缓冲区的数量，也即产品数量，用 full = 0 表示。
先考虑对互斥关系的实现。这里所谓的临界资源其实就是某一个缓冲区，生产者进程把产品放进去，消费者进程从里面取走产品，这两者不能同时进行，所以这里是互斥的关系。我们可以想象到，对每一个进程而言，他都有属于自己的一对 PV 操作，用以实现对缓冲区资源的访问。另外，生产者在进行 PV 操作之前，必定要先生产产品；而消费者在进行 PV 操作之后，必定要使用产品。这时候，初步的伪代码是这样的：
producer(){ consumer(){
while(1){ while(1){
生产产品 P(mutex)
P(mutex) 从缓冲区中取走产品
把产品放入缓冲区 V(mutex)
V(mutex) 使用产品
} }
} }接着考虑第一个同步关系。关注缓冲区，可以知道一定是先释放缓冲区，后使用缓冲区，所以这里“前操作”是释放缓冲区，“后操作”是使用缓冲区，根据上篇笔记所讲的 “前VP后”，我们需要在“前操作”之后针对 empty 这个信号量进行一次 V 操作，需要在“后操作”之前针对 empty 进行一次 P 操作。所以，这时候代码变成：
producer(){ consumer(){
while(1){ while(1){
生产产品 P(mutex)
P(empty) 从缓冲区中取走产品
P(mutex) V(mutex)
把产品放入缓冲区 V(empty)
V(mutex) 使用产品
} }
} }再考虑第二个同步关系。关注产品本身，可以知道一定是先生产产品，后使用产品，更进一步地说，一定是先生产产品并将其放入缓冲区，后从缓冲区取出产品并使用。这里划分出前后两个操作，所以再次安排一对 PV 操作。这时候，代码变成：
producer(){ consumer(){
while(1){ while(1){
生产产品 P(full)
P(empty) P(mutex)
P(mutex) 从缓冲区中取走产品
把产品放入缓冲区 V(mutex)
V(mutex) V(empty)
V(full) 使用产品
} }
} }这个实际上就是最后的代码了。现在我们试着跑一下流程：初始的时候 empty = n，表示所有缓冲区都是空闲的，同时 full = 0，表示一个产品都没生产出来。假如处理机首先来到 consumer 进程，那么就会通过 P(full) 检查是否有产品，这里当然是没有，所以它只能进行等待；处理机来到 producer，首先通过 P(empty) 检查是否有空闲缓冲区，这里当然有，于是它开始把生产的产品放入缓冲区，随后记录产品的数量，这个过程可以反复进行，直到所有缓冲区都被占用了，此时 producer 就会进入等待状态，等待 consumer 进程取出产品、释放缓冲区；当然还有可能的情况是，producer 尚未占用完所有缓冲区，进程就切换到 consumer 了，那么这时候 consumer 因为检查到有产品，所以也会取出产品、释放缓冲区。
这里要注意可能会引起“死锁”现象的一种写法。如下所示：
producer(){ consumer(){
while(1){ while(1){
生产产品 P(mutex)
P(mutex) P(full)
P(empty) 从缓冲区中取走产品
把产品放入缓冲区 V(mutex)
V(mutex) V(empty)
V(full) 使用产品
} }
} }这个写法的问题在于，还没有先检查缓冲区是否没满或者是否非空，就强行进行互斥的“上锁”。假如还是按照前面的流程，一开始处理机在 consumer 这里，那么 consumer 实际上在没有检查缓冲区是否非空的情况下就直接“上锁”了，这导致它在 P(full) 这一步的时候被卡住，只能等待，而在之后切换到 producer 的时候，正常情况下他应该生产可供对方消费的产品，但是由于对方已经上了锁，所以 producer 在 P(mutex) 这一步也被卡住了，只能进行等待。这也就是说，producer 等待 consumer 释放临界区，而 consumer 等待 producer 使用缓冲区，双方陷入循环等待，造成了“死锁”。
另一种情况，我们也可以设想一开始处理机是在 producer 这里，那么是不是不会导致“死锁”呢？并不是。事实上，按照这种情况正常用完全部缓冲区之后，如果处理机还是在 producer 这里，那么 producer 在检查缓冲区是否已满之前也会将自己提前上锁，在 P(empty) 这一步陷入等待，之后即使进程切换到 consumer 这里，它也会因为对方提前上锁，而导致自己在 P(mutex) 这一步陷入等待。也就是说，这不过是前面那种”死锁“现象的翻版。
总之，关键就在于不管是消费者进程，还是生产者进程，都不能先上锁再检查，否则就有可能发生死锁。
2. 橘子 — 苹果问题
橘子 — 苹果问题其实是生产者 — 消费者问题的一种变形，它有多种类型的生产者、多种类型的消费者，所以也叫多生产者 — 多消费者问题。它描述的是：有一个只能放一种水果的空盘子，父亲可以放苹果在上面，母亲可以放橘子在上面，女儿只吃父亲的苹果，而儿子只吃母亲的橘子。只有盘子空的时候父母亲才放水果上去，只有盘子中的水果符合自己的喜好时，女儿或者儿子才会去拿。
从上面这个过程，我们可以分析一下有哪些变量。首先可以肯定的是，有四个进程，父母亲扮演着生产者，女儿儿子扮演着消费者；同时有一个互斥关系，在同一个时间，只能有一个人去“访问”盘子这个资源，所谓“访问”，无非是四种情况：放苹果、放橘子、拿苹果、拿橘子；同时，有三个同步关系，第一个指的是，必定是先有父亲放苹果，后有女儿拿苹果。第二个指的是，必定是先有母亲放橘子，后有儿子拿橘子。第三个指的是，必定是先有女儿或者儿子拿走水果，后有父亲或者母亲放上水果。
因此，这里我们准备四个进程：Dad，Mom，Son，Daughter；同时，我们需要准备四个信号量。第一个信号量是互斥信号量，实现对盘子这个资源的互斥访问，用 mutex = 1 表示；第二个信号量是同步信号量，表示盘子中苹果的数量，用 apple = 0 表示；第三个信号量也是同步信号量，表示盘子中橘子的数量，用 orange = 0 表示；第四个同样是同步信号量，表示盘子中还可以放多少水果，用 plate=1 表示。
接下来，我们仿照生产者—消费者问题，对伪代码进行推导。由于四个进程都有对互斥资源的访问，也即都有一个 PV 操作，然后，对父亲而言，在 PV 操作之前自己要先拿出苹果，母亲则是拿出橘子；对女儿而言，在 PV 操作之后要吃掉苹果，儿子则是吃掉橘子。这时候，初步的伪代码是这样的：
Dad(){ Mom(){
while(1){ while(1){
拿出苹果 拿出橘子
P(mutex) P(mutex)
把苹果放入盘子 把橘子放入盘子
V(mutex) V(mutex)
} }
} }
Daughter(){ Son(){
while(1){ while(1){
P(mutex) P(mutex)
从盘中取出苹果 从盘中取出橘子
V(mutex) V(mutex)
吃掉苹果 吃掉橘子
} }
} }再来考虑第一类同步关系，关注盘子，可以看到必定是先让盘子空出来，后让人使用盘子，所以这里前后操作就分清楚了，接下来再根据“前VP后”插入代码，此时的伪代码是这样的：
Dad(){ Mom(){
while(1){ while(1){
拿出苹果 拿出橘子
P(plate) P(plate)
P(mutex) P(mutex)
把苹果放入盘子 把橘子放入盘子
V(mutex) V(mutex)
} }
} }
Daughter(){ Son(){
while(1){ while(1){
P(mutex) P(mutex)
从盘中取出苹果 从盘中取出橘子
V(mutex) V(mutex)
V(plate) V(plate)
吃掉苹果 吃掉橘子
} }
} }最后考虑第二类同步关系，这次关注水果，可以看到必定是先拿出水果放到盘子上，后取出盘子上的水果吃掉，根据“前VP后”，最后的伪代码如下：
Dad(){ Mom(){
while(1){ while(1){
拿出苹果 拿出橘子
P(plate) P(plate)
P(mutex) P(mutex)
把苹果放入盘子 把橘子放入盘子
V(mutex) V(mutex)
V(apple) V(orange)
} }
} }
Daughter(){ Son(){
while(1){ while(1){
P(apple) P(orange)
P(mutex) P(mutex)
从盘中取出苹果 从盘中取出橘子
V(mutex) V(mutex)
V(plate) V(plate)
吃掉苹果 吃掉橘子
} }
} }更进一步地，其实我们这里并不需要互斥变量 mutex，试着把它去掉并跑一下流程：
Dad(){ Mom(){
while(1){ while(1){
拿出苹果 拿出橘子
P(plate) P(plate)
把苹果放入盘子 把橘子放入盘子
V(apple) V(orange)
} }
} }
Daughter(){ Son(){
while(1){ while(1){
P(apple) P(orange)
从盘中取出苹果 从盘中取出橘子
V(plate) V(plate)
吃掉苹果 吃掉橘子
} }
} }在一开始，任何进程都可能先来到处理机，如果是儿子或者女儿，则会因为盘子中暂时没有水果而被堵塞，如果是父母亲，则会按照正常流程放水果上去，我们假设是第一种情况。由于儿子和女儿进程相继被阻塞，所以进程来到父亲这，拿出苹果并放在盘子上。假设这中途因为时间片的缘故被切换到母亲进程，母亲进程由于盘子已经被使用，所以也进入阻塞队列。之后又来到父亲进程，由于它唤醒了女儿进程，女儿进程直接来到就绪队列，并在父亲进程执行完毕之后执行，吃掉苹果。一吃掉苹果，盘子就空了，唤醒了母亲进程，母亲进程放上橘子（这期间即使其它进程进来，也会被阻塞），唤醒了儿子进程，儿子进程就可以吃掉橘子了。
整个过程可能存在各种进程切换的情况，但是无论哪种情况，都可以保证做到进程同步和进程互斥，并且这是在不借助互斥信号量的前提下做到的。基于这个原因，我们在这里可以不使用互斥信号量。
3. 吸烟者问题
吸烟者问题其实是生产者 — 消费者问题的另一种变形，它有可以生产多种类型产品的一个生产者，以及多种类型的消费者，所以也叫单生产者 — 多消费者问题。它描述的是：有一个供应者和三个抽烟者，供应者拥有无限的烟草、纸、胶水三种材料，抽烟者1号只有烟草，抽烟者2号只有纸，抽烟者3号只有胶水。每次供应者提供其中两种材料，其中一个抽烟者拿着这两种材料与自己的材料结合进行抽烟，抽完再发送信号给供应者，供应者重新供应材料。整个过程按照三个抽烟者轮流抽烟的顺序循环往复。
从上面这个过程，我们可以分析一下有哪些变量。首先可以肯定的是，有四个进程，也就是一个供应者和三个抽烟者；同时有一个互斥关系，在同一个时间，只能有一个人去“访问”桌子这个资源（假定材料放在桌子上），所谓访问，无非就是放东西和拿东西两个动作；同时，有四个同步关系，第一个指的是，必定是先放材料组合一，后有抽烟者1号拿材料。第二个指的是，必定是先放材料组合二，后有抽烟者2号拿材料。第三个指的是，必定是先放材料组合三，后有抽烟者3号拿材料；第四个指的是，必定是某一个抽烟者先发出信号，后有供应者重新供应材料。
因此，这里我们准备四个进程：Provider，Smoker1，Smoker2，Smoker3；同时，我们准备三个同类信号量，即 offer1 到 offer3，分别表示桌子上某个组合的数量。注意我们这里不准备互斥信号量，因为正如之前的问题提到的，这里即使不引入互斥信号量，也不会影响到我们对于进程互斥和同步的实现。另外，我们再准备一个信号量 finish = 0 表示抽烟是否完成。除了这些，由于题目要求三个抽烟者是轮流抽烟的，所以对于供应者来说，它不能只提供单一材料组合，而要根据索取者的身份选择给定的材料，这里我们还需要再用一个变量 i 记录具体是哪个抽烟者。从 0 到 2，分别表示三个抽烟者。而且在每一次给完材料之后，我们还要改变这个变量的值，好让它指向下一个抽烟者，从而达到“轮流抽烟”的目的。
接下来，我们对伪代码进行推导。由于四个进程都有对互斥资源的访问，也即都有一个 PV 操作，所以初步的伪代码是这样的：
Provider(){ Smoker1(){ Smoker2(){ Smoker3(){
while(1){ while(1){ while(1){ while(1){
P(mutex) P(mutex) P(mutex) P(mutex)
放组合一 拿走组合一 拿走组合二 拿走组合三
放组合二 抽烟，发信号 抽烟，发信号 抽烟，发信号
放组合三 V(mutex) V(mutex) V(mutex)
} } } }
} } } }不过，我们前面说了这里不需要互斥信号量，所以把它去掉。并且这里 Provider 的三个操作肯定是要根据抽烟者身份来决定的，所以我们加个 if 判断，以及对于 i 值的修改：
Provider(){ Smoker1(){
while(1){ while(1){
if(i==0){ 拿走组合一
放组合一 抽烟，发信号
} else if(i==1){ }
放组合二 }
} else if(i==2){
放组合三
}
i = (i+1)%3
}
}
Smoker2(){ Smoker3(){
while(1){ while(1){
拿走组合二 拿走组合三
抽烟，发信号 抽烟，发信号
} }
} } 按照“前VP后”的原则，必定是先把某个组合放在桌子上，后有某个抽烟者把组合拿走，所以我们考虑在放置组合的语句后面加上 V(offer)，在拿组合的语句前面加上 P(offer)；同理，必定是抽烟者先抽完烟发出信号，后有供应者重新放上材料组合，所以我们考虑在抽完烟的语句后面加上 V(finish)，在放置组合的语句前面加上 P(finish)，所以此时伪代码如下：
Provider(){
while(1){
P(finish)
if(i==0){
放组合一
V(offer1)
} else if(i==1){
放组合二
V(offer2)
} else if(i==2){
放组合三
V(offer3)
}
i = (i+1)%3
}
}
Smoker1(){ Smoker2(){ Smoker3(){
while(1){ while(1){ while(1){
P(offer1) P(offer2) P(offer3)
拿走组合一 拿走组合二 拿走组合三
抽烟，发信号 抽烟，发信号 抽烟，发信号
V(finish) V(finish) V(finish)
} } }
} } }不过这样我们会发现，Provider 一上处理机就会被阻塞了，因为马上就遇到了 P(finish)，而此时根本还没有人拿到烟，更不可能抽完烟。事实上，我们想要的效果只是“抽烟者先抽完烟发出信号，供应者后重新供应”，也就是说，在抽烟者发出信号之前，我们要阻止 Provider 到达“重新放置组合”这一步，我们下意识考虑到的是直接在放置组合语句前加上限制条件，但这样会造成阻塞，所以放弃这个方案。那么何不把限制条件放在放置组合语句后面呢？while 本来就是个首尾连接的循环，放置组合语句的尾部其实就是语句的首部，如果我们在尾部给予了限制，而限制条件满足了，那么照样可以实现“阻止进程 Provider 到达放置组合语句”这个效果。如下所示：
Provider(){
while(1){
if(i==0){
放组合一
V(offer1)
} else if(i==1){
放组合二
V(offer2)
} else if(i==2){
放组合三
V(offer3)
}
i = (i+1)%3
P(finish)
}
}
Smoker1(){ Smoker2(){ Smoker3(){
while(1){ while(1){ while(1){
P(offer1) P(offer2) P(offer3)
拿走组合一 拿走组合二 拿走组合三
抽烟，发信号 抽烟，发信号 抽烟，发信号
V(finish) V(finish) V(finish)
} } }
} } }可以看到，这里一定会是抽烟者抽完烟发出信号之后，Provider 才有办法重新放置组合。因为但凡 Provider 想要抢先一步重新放置组合，它都要经过底部 P(finish) 的检查，而这个检查在 Smoker 发出信号之前，不可能轻易通过，因此 Provider 如果想要“强闯”，只会导致自己进入阻塞队列，之后进程切换到 Smoker，Smoker 发出信号，V(finish) 将 Provider 唤醒，Provider 才能重新放置组合，由此就实现了“先发出信号，后重新放置组合”的效果。
4. 读者 — 写者问题
读者 — 写者问题与我们之前遇到的问题类型不同，它描述的是：有读者和写者两组进程，它们共同访问同一个文件。对于读者，它可以与多个读者共同读取文件（因为不会修改到文件）；对于写者，它不能与其他任何进程共同访问文件（如果另一进程是写，则可能覆盖同一内容；如果是读，则可能修改到要读的内容）。也就是说，这里的互斥问题是读写互斥的问题，但与之前不同的是，除了实现读写的互斥，我们还要实现读读的“不互斥”。
首先准备一个信号量 rw = 1 表示当前是否有进程在访问文件（注意一开始是没有这样的进程的，1 表示的不是进程数目，仅仅是使用互斥信号量时习惯上给定的初始值，这个看 wait 的代码就能理解了）。
在不考虑“读读不互斥”的情况下，我们的伪代码是这样的：
Writer(){ Reader(){
while(1){ while(1){
P(rw) P(rw)
写文件 读文件
V(rw) V(rw)
} }
} }这个代码可以实现读写互斥，但显然无法实现“读读不互斥”，因为每个读进程之间也会受到 rw 的影响，使得最后只能有一个读进程访问文件。于是我们考虑从读进程入手，做一些改进。这里读和读不能同时进行的本质原因在于，所有的读进程都会经历“检查并上锁”这个步骤，而一个读进程进入后就会马上检查并上锁，导致另一个也想要进入的读进程被阻塞，所以我们考虑：能不能不要让所有的读进程都经历“检查并上锁”这一步骤？也就是说，某些进程可以跳过 P 操作，直接进入临界区，这样一来，这些进程就不存在在 P 操作这里被阻塞的可能性。
什么样的进程可以跳过 P 操作呢？就是中间的那些读进程。因为一开始肯定要有读进程上锁、最后肯定要有读进程解锁，所以上锁和解锁的任务交付给第一个和最后一个进程，而中间的那些进程来去自如，只需要负责读文件，不需要参与上锁和解锁。为了区分读进程的次序，我们准备一个 count = 0 的变量，它表示的是当前有多少个读进程正在访问文件。然后在读文件的前后，我们分别对 count 进行加一和减一的操作，每次读文件开始之前 count 会加一，所以在此之前如果变量为 0 ，说明当前读进程是第一个读进程；同理，每次读文件之后 count 会减一，所以在此之后如果变量为 0 ，说明当前读进程是最后一个读进程；
此时伪代码如下：
Reader(){
while(1){
if(count==0)
P(rw)
count++
读文件
count--
if(count==0)
V(rw)
}
}但是这样会产生一些问题。比方 1 号读进程首先进入并上锁，然后在 P 操作之后、count 加一变成 1 之前，进程切换到 2 号读进程，那么 2 号读进程就会卡在 P 操作这个地方，陷入阻塞，显然这时候无法实现我们想要的“读读不互斥”；又比方说，1 号读进程在 count 减一变成 0 之后、释放 rw 之前，进程切换到了 2 号读进程，那么 2 号同样又会被卡在 P 操作这里。所以我们还要进行改进。
问题其实就出在，对 count 的检查和赋值不是一个原子操作，这导致的结果是，如果在检查和赋值之间的空隙，进程发生切换，则必然会使得另一进程陷入阻塞。那么能不能让这两个操作一气呵成呢？事实上，可以把 count 当作是一个互斥访问的资源，对 count 的访问是互斥的，也就说明一个时间段内只能有一个读进程去访问它，即使这个过程中切换到了其它进程，那个进程也会被阻塞，从而保证只有一个进程可以访问 count，而这个访问就是检查和赋值，这种情况下，检查和赋值一定是不会被中断的。
准备一个互斥信号量 mutex = 1 表示对 count 的互斥访问，将检查和赋值封装在一个 PV 操作里。伪代码如下：
Reader(){
while(1){
P(mutex)
if(count==0)
P(rw)
count++
V(mutex)
读文件
P(mutex)
count--
if(count==0)
V(rw)
V(mutex)
}
}现在我们再来跑一下过程。假设还是 1 号读进程运行到 P 操作的时候，进程切换到了 2 号读进程，那么由于互斥信号量 mutex 的存在，导致 2 号进程进入了 mutex 对应的阻塞队列 —— 是的，这时候看起来 2 号进程还是被阻塞了，不过我们要关注到的是，阻塞它的信号量是 mutex，不是 rw。这意味着，在进程重新切换回 1 号进程的时候，1 号进程一旦执行了 V(mutex)，就可以将 2 号进程唤醒并送到就绪队列了。也就是说，尽管 2 号进程还是经历了“阻塞”这个过程，但是这个过程只是为了确保 1 号进程检查和上锁两个操作的原子性，一旦操作完成，2 号进程马上就被唤醒了。而之前那种情况不同，之前的情况是，导致 2 号进程被阻塞的是信号量 rw，除非 1 号进程读完后释放，否则 2 号进程会一直处于阻塞状态。这就是说，2 号进程永远不可能与 1 号进程同时读文件，但是改进后是可以的。
但随之而来的又是另一个问题， “读写不公平”。也就是说，这样的代码本质上是对读进程更有利的。
因为对读进程来说，一旦第一个读进程进来了，中间即使穿插再多的读进程，也都是允许的，他们根本不受到 rw 这个“锁”的限制；而对于写进程，它的运气就没这么好了，写进程只要想进来，就必须通过 rw 这个“锁”，而这个“锁” 实际上又掌握在最后一个读进程手里 —— 这就是说，万一读进程源源不断进来，始终轮不到最后一个读进程解锁，那么写进程就只能陷入无尽的等待了。
既然 rw 这把锁无法做到公正对待每一个进程，那我们就考虑在外层加一把“更大、更公正的锁”。也就是说，所有的进程，无论读还是写，无一例外必须通过这把“锁”的检查。为此，我们准备一个新的互斥信号量 w = 1，并将 Writer 和 Reader 的一些关键操作封装在 w 的一对 PV 操作里。此时，伪代码如下：
我们来跑一下流程。假设首先来到 1 号读进程，那么它就会执行 P 操作上锁，这个过程中即使有写进程想进来，也会被送到 w 对应的阻塞队列。在 1 号读进程执行到 V 操作之后，写进程才会被唤醒并送到就绪队列，之后就轮到写进程执行了，而写进程虽然通过第一个 P 操作，但是被卡在了第二个 P 操作（读进程尚未释放 rw），所以他来到了 rw 对应的阻塞队列。
注意！重点来了，如果这时候 2 号读进程也想要访问文件，那么在以前，它是不需要通过任何检查就可以直接来读文件的，并且直到 2 号读进程释放 rw 之后，写进程才能真正来执行写文件的操作。但是现在由于我们加了一把“更大的锁”，导致 2 号进程也必须先通过 w 的检查，而由于写进程抢先在他之前上了锁，所以 2 号读进程被送到了 w 对应的阻塞队列。也就是说，现在的情况是：写进程等着 1 号读进程释放 rw，而 2 号读进程等着写进程释放 w，1 号读进程是让一切正常进行下去的关键。在处理机又来到 1 号读进程并执行 V(rw) 之后，写进程从 rw 的阻塞队列被唤醒，继续往下执行写文件的操作。而在写进程真正执行完之后，w 才能得到释放，由此又唤醒了 w 阻塞队列中的 2 号读进程，2 号读进程来到处理机运行。
如果换一种情况，是按照 写者 — 读者 — 写者的顺序，那么由于读者在第二个写者之前，所以是读者作为阻塞队列队头，第二个写者则次之，在后续执行过程中，根据队列“先进先出”的原则，也会是读者先于第二个写者访问文件。
也就是说，实际上谁先到、谁就在后续过程中先被执行（而不是像之前那种情况，无论写进程先还是后，读进程都可以“无视规则”抢先一步执行）。由此，我们就实现了“读写公平”。
5. 哲学家就餐问题
最后我们再来看哲学家就餐问题。这个问题描述的是：一张圆桌，五个哲学家，五支筷子（每两个哲学家中间会有一支筷子），哲学家要么思考，要么吃饭，吃饭前会拿起左右两边的筷子，吃饭后会放下筷子。如果筷子被其它哲学家拿走，则自己需要等待。我们的目的很简单：保证所有哲学家都有机会吃上饭，不能让一个或者多个哲学家始终无法吃饭。
首先，五个哲学家对应了五个进程，然后在同一个时间段内，对于同一支筷子，只能有一个哲学家去使用它，所以筷子是一种临界资源，我们用互斥信号量 chopstick = 1 表示。鉴于这里有五支筷子，所以我们准备一个互斥信号量数组 chopstick[5] = {1,1,1,1,1}。另外，由于任何一个哲学家都只可能拿离自己最近的左右筷子，所以为了加以区分，我们需要给哲学家和筷子进行编号。对于哲学家，从 0 到 4 进行编号，由于哲学家按照圆桌首尾连接，所以某个哲学家左右两边的筷子编号与自己本身的编号相关。以哲学家 i 为例，它左边的筷子编号是 i。右边则是 (i+1)%5，如下图所示：
对每一个哲学家进程来说，它都只能拿起左右两边的筷子，并且一定是吃饭前拿筷子，吃饭后放下筷子，所以初步的伪代码是这样的（这里忽略思考的过程）：
Pi(){
while(1){
P(chopstick[i])
P(chopstick[(i+1)%5])
eat()
V(chopstick[i])
V(chopstick[(i+1)%5])
}
}如果哲学家 0 号拿起左右筷子后，进程切换到哲学家 1 号，那么哲学家 1 号是会被阻塞的，所以这样写可以保证相邻的哲学家中有一个可以吃饭。但是，如果是拿起左筷子，之后进程切换到 1 号，那么 1 号也会拿起自己的左筷子，以此类推，直到 4 号也拿起自己的左筷子。接着，进程来到 0 号，这时候，0 号会发现自己已经没有右筷子可以拿了（作为 1 号的左筷子），于是 0 号被阻塞；同理，1 号也没有右筷子，所以他也被阻塞…以此类推，由于所有的哲学家都只有左筷子，他们的右筷子都在其他人手里，这导致了所有的哲学家都被阻塞，等待着另一个哲学家释放筷子。但实际上，没有任何哲学家能够吃饭，因此没有人可以释放筷子，这使得这些哲学家都陷入无限的等待中，造成“死锁”的发生。
解决这个问题有三个方法。
（1）实现原子操作
很容易想到的是，这里的一个问题在于，拿起左筷子和拿起右筷子并不是一个原子操作，如果在这之间发生了进程切换，那么就可能会像上面那样导致“死锁”的发生。所以我们设想能否将这两个操作一气呵成完成。按照前面问题的思路，第一种做法就是准备一个互斥信号量 mutex = 1 ，并把拿筷子的操作封装在一个 PV 操作里。代码如下：
Pi(){
while(1){
P(mutex)
P(chopstick[i])
P(chopstick[(i+1)%5])
V(mutex)
eat()
V(chopstick[i])
V(chopstick[(i+1)%5])
}
}这样一来，在 0 号哲学家拿起左筷子之后，即使发生进程切换，来到 1 号进程，1 号进程也会被卡在 mutex 的 P 操作这里。被送往阻塞队列，其它进程也同理。所以最后又来到了 0 号进程，0 号进程顺利拿起了右筷子，之后释放阻塞队列队头的 1 号进程，自己开始吃饭。这种做法保证了有一个哲学家是可以吃饭的，不存在“所有哲学家都无法吃饭”的情况。
另外，这里涉及到了一个进程需要一次性两个资源才能完成任务的问题，这时候也可以考虑使用我们之前提到的 AND 信号量集机制。我们回顾一下，AND 信号量集机制的 P 操作是一个相对苛刻的操作，要求一个进程要么拿到全部资源，要么一个资源也拿不到，所以这里可以做到的是：对于初始的那个 0 号进程，他在拿筷子的时候要么左右筷子都拿到，要么一支筷子都拿不到。由于一开始筷子数量足够，所以它在一开始就可以一次性拿到左右筷子。同理，在释放筷子的时候，也是一次性释放两支筷子。
代码如下：
Pi(){
while(1){
Swait(chopstick[(i+1)%5],chopstick[i]);
eat()
Ssignal(chopstick[(i+1)%5],chopstick[i]);
}
}因此，我们同样可以保证有一个哲学家是可以吃饭的，不存在“所有哲学家都无法吃饭”的情况。
（2）只有四个人可以参与这个过程
我们也可以从另一个角度考虑，之前的情况是五个哲学家，五支筷子，所以很容易出现谁也无法吃饭的情况，但是如果我们规定整个过程最多只有四个哲学家参与，那么即使这四个哲学家每个人都拿走了一支筷子，也还剩下一支筷子可以分配给某个哲学家。换句话说，这样做，我们同样可以让至少一个哲学家吃到饭。
问题在于如何限定“只有最多四个人可以参与这个过程”呢？我们可以准备一个互斥信号量 count，但是这个信号量初值不再是 1 ，而是 4，表示最多允许四个哲学家参与过程。当 count 减少到 -1 的时候，就不能再让哲学家进来了，因此可以保证最多只有四个哲学家。代码如下：
Pi(){
while(1){
P(count)
P(chopstick[i])
P(chopstick[(i+1)%5])
eat()
V(chopstick[i])
V(chopstick[(i+1)%5])
V(count)
}
}我们再来演示前面发生“死锁”的过程。假如一开始还是从 0 号进程开始，在他拿到左筷子之后，进程切换到 1 号进程，由于 count 数量充足，所以它不会阻塞，而是同样拿到了左筷子…以此类推，到了 4 号哲学家的时候，由于 count = -1<0，所以它此时是无法进来的。所以有一支筷子在一开始谁也没拿到，就是 4 号哲学家左边的筷子。而在稍后进程轮到 3 号哲学家的时候，它是可以拿到这支筷子然后去吃饭的。
这只是其中一种情况，但即便是其它情况，也能保证剩下一支暂时没被用到的筷子，而这支筷子也一定会在最后被某个进程拿走。因此得以保证总会存在至少一个进程可以吃到饭。
（3）奇数拿左边，偶数拿右边
还可以考虑对拿筷子的优先顺序进行调整。规定对于奇数哲学家，总是先拿左筷子再拿右筷子；对于偶数哲学家，总是先拿右筷子再拿左筷子。那么 0 号哲学家和 1 号哲学家就会争夺 1 号筷子，而 2 号哲学家和 3 号哲学家就会争夺 3 号筷子。如图所示：
伪代码如下：
Pi(){
while(1)
{
if(i%2 == 0) // 偶数哲学家，先右后左。
{
P(chopstick[(i + 1)%5]) ;
P(chopstick[i]) ;
eat();
V(chopstick[(i + 1)%5]) ;
V(chopstick[i]) ;
}
else //奇数哲学家，先左后右。
{
P(chopstick[i]) ;
P(chopstick[(i + 1)%5]) ;
eat();
V(chopstick[i]) ;
V(chopstick[(i + 1)%5]) ;
}
}
}假如一开始还是从 0 号进程开始，很显然 0 号先拿到 1 号筷子，所以在之后切换进程的时候，1 号进程就会直接被阻塞。接着来到 2 号进程，显然他先拿到 3 号筷子，所以之后轮到 3 号进程的时候，3 号进程直接被阻塞。现在考虑轮到 4 号进程，它优先拿到右边的 0 号筷子，之后进程又切换到其它地方。但是，由于先前 3 号进程已经被阻塞，所以在再次轮到 4 号进程的时候，并没有人和他一起争夺 4 号筷子，换言之，4 号进程可以拿到 4 号筷子，再加上之前优先拿到的 0 号筷子，4 号进程现在就可以吃饭了。
值得提醒的是，这仍然只是其中一种情况，类似的排列组合有很多，但是无论是哪一种，在一对进程的争抢中必然有一个进程首先被送到阻塞队列，“被淘汰出局”，因此这个“被淘汰的”进程很难再去影响其它进程，相当于间接提高了其它进程拿到筷子的可能性。就像我们上面的例子一样，一下子“淘汰了” 1 号和 3 号两个进程，并且这两个进程当时并没有带着筷子进入阻塞队列，所以对于其它进程 2 号、4 号、 0 号来说，再次拿到一支筷子的可能性就大大提高了。所以，我们还是能够达到最初的目的，也就是至少让一个哲学家吃上饭。
操作系统系列学习笔记：