操作系统入门（三）万字长文细说进程间关系：互斥、同步和通信
上一节我们介绍了进程的概念、构成、组织方式、状态转换和进程控制，以及线程概念、线程与进程的关系和线程模型。本节我们将关注进程间的关系：互斥、同步和通信，以及操作系统使用什么方式实现进程间的互斥、同步和通信；
实际上，互斥、同步和通信不仅是一个操作系统控制进程的知识点，也和我们的日常开发息息相关，尤其是做并发编程的开发时我们无时无刻不在研究加锁解锁、信号量、共享内存、消息队列等互斥同步和通信的手段（且并不限于进程，在线程和协程中，这些也是我们不得不面对的问题）。大家可以通过这篇文章进一步加深对并发的理解。
01 进程间互斥、同步和通信概述
- 临界资源和临界区
同一时刻仅允许一个进程使用的共享资源就是临界资源，进程中访问临界资源的那段程序就是临界区。例如，在生产者消费者模型中，一个进程往一个消息队列里面存取内容，这个队列就是临界资源，为了往队列写入任务或从队列取出任务时保护数据安全而为消息队列加锁，
从加锁到释放锁的这段代码就是临界区 。
- 进程间关系
互斥：多个并发进程需要共享临界资源时，宏观或微观上一段时间内进程只能交替使用这个资源，而不能共享这个资源，我们称多个进程互斥访问资源。
同步：多个并发进程合作完成一个任务的过程中，不同进程的子任务是相互依赖的，让无序的进程按指定顺序完成各自的任务从而完成整体任务就是同步。同步的需求，是因为多个并发进程需要协作按一定工作次序完成某一任务。
通信：进程通信即进程之间交换信息。
其实说的直白点，互斥是指让并发进程同一时刻只能有一个进程进入到临界区使用临界资源，其他进程必须等待直到正在使用资源的进程释放资源；同步是指让并发进程按照指定顺序执行任务，我们要知道按顺序执行一个任务在串行下是很容易实现的，但并发下，进程的执行是无序的，如何让无序的进程按用户规定的顺序执行某任务就是同步要做的事情。
简单来说， 互斥是进程间竞争，同步是进程间协作
。通信与互斥和同步不是并列关系，而是一个有交集的关系，因为互斥和同步或多或少的都会涉及到进程间的通信。同步是协作关系，互斥是竞争关系，通信是信息交换。
02 进程间通信
进程通信即进程之间交换信息。为了保证数据安全，进程不能直接访问另一个进程的内存地址，因此OS提供了一些安全通信的方式。
- 进程通信的方式
1、共享内存
共享内存是在内存分配一块空间作为多个通信进程的共享存储区， 需要通信的多个进程把共享存储区附加到自己的地址空间
就可以对共享存储区读写（其实是将共享存储区扩展到进程自己的逻辑空间，共享存储区的页加入到本进程的页表中，如果进程A和B共享内存区X，可能X在A和B的逻辑地址不同，页号也不同，但是对应的块号肯定是相同的）。
共享内存有 “基于数据结构的共享” 和 “基于存储区的共享” 两种。
基于数据结构的共享 是指
操作系统分配一个指定长度和数据结构的共享空间用于多进程通信。例如共享空间只能放一个长度为10的数组，该方式速度慢、限制多，是一种低级通信方式。
基于存储区的共享 是指 操作系统分配一个共享存储区，其数据的形式、存放位置都有用户进程控制，而非操作系统，是一种高级通信方式。
多个进程对共享空间的访问是互斥的，通过操作系统提供的互斥工具实现互斥，因此进程间共享需要系统介入，相比同一进程的线程间通信代价高。
2、管道通信
管道是用于连接读写进程的一个共享文件（又称pipe文件），其本质是OS在内存中开辟的一个大小固定的缓冲区（通常为一个内存页大小，约为4K）。读写进程可以通过该共享文件传递数据。
管道特征如下：
a. 管道采用半双工通信，某一时间段内只能实现单向传输（进程1->进程2 和
进程2->进程1都可以发生，但不能同时发生）。如果要实现双向同时通信，则需要设置两个管道。
b.
各进程要互斥的访问管道，这意味着：单生产者和单消费者使用管道时，写进程写的时候，读进程不能读，必须写完之后，写进程释放管道，读进程才能从管道读；多生产者和单消费者使用管道时，写进程A写的时候，写进程B不能往管道写入，因此管道内不会出现A和B数据交错的情况，这个管道是进程安全的。
c.
数据以字符流的形式写入管道。管道写满时，写进程执行write()系统调用会阻塞进程，直到管道有空间写入；管道读空时，读进程执行read()系统调用会阻塞进程，直到管道有数据到来；
这其实是管道的同步功能。
d. 如果没写满，则不允许读；如果没读空，就不允许写。（必须写满/读空管道，写/读的进程才会释放管道）
e.
数据一旦被读出，就会被管道抛弃，即数据只能被消费一次，读进程最多只能有1个。如果有多个读进程，可能会发生读错数据的情况（一个进程A读到数据，进程B读不到，或者进程B以为自己读到了和A一样的数据，但其实读到了别的数据）。
f. 管道会确认通信双方是否存在，如果有一方不存在，则不会开始通信。
综上，其实管道同时提供了互斥和同步的功能，来实现安全通信。
3、消息传递
即 进程间的数据以格式化的消息为单位，通过OS提供的 “发送消息send/接收消息receive” 两个原语进行数据交换。
消息头包括：发送进程ID，接收进程ID，消息类型，消息长度等格式化的信息。
消息传递有直接通信方式和间接通信方式这2种。直接通信方式是将消息直接挂在接收进程的消息缓冲队列上。
间接通信方式是先将消息发送到中间实体（又称信箱）中，接收方再从信箱中获取发给自己的消息，因此也称为“信箱通信方式”。
03 进程互斥
互斥是指多个并发进程共享临界资源时，操作系统或用户程序组织多个并发进程交替的访问资源，不能同时访问。
对临界资源的互斥访问，在逻辑上分为4个过程：进入区、临界区、退出区和剩余区。
临界区是进程访问临界资源的代码段。进入区和退出区是负责实现互斥的代码段。进入区负责检测资源是否空闲以及对资源上锁，退出区负责对资源解锁。
进程互斥需要遵循 空闲让进、忙则等待、有限等待和让权等待 的原则。
1、空闲让进：临界区空闲（临界资源空闲）时，允许一个请求进入临界区的进程立刻进入临界区。
2、忙则等待：如果已经有进程进入临界区，其他试图进入临界区的进程会被阻塞，等待临界区被释放。
3、有限等待：保证处于等待临界区的进程在有限时间内进入临界区，不会一直等待（不会饥饿）。
4、让权等待：等待临界区的进程必须立刻释放CPU，防止进程忙等。
进程互斥有软件和硬件两种实现方法。
PS：下面介绍的软件实现和硬件实现的互斥方法多多少少有些缺陷，之所以介绍这些有缺陷的方法，是为了逐步推衍出最终没有缺陷的方法。如果大家觉得过于啰嗦，可以直接跳到下方的
“04 进程互斥和同步的完美解决方案——信号量机制”。
- 进程互斥的软件实现方法
了解进程互斥的软件实现方法时，我们需要关注每个方法的思想原理、在进入区、退出区都做了什么、以及他们的优缺点。
单标志法
进程访问完临界资源后会把使用临界资源的权限主动转让给另一个进程 。即每个进程进入临界区的权限只能被另一个进程赋予，而进程自己无法主动获取。
如下所示
进入区做的事情：判断允许进入临界区的进程是不是自己（自己是否有资源的占有权），不是则忙等。
退出区做的事情：将进入临界区的权限让给其他进程。
turn 的初值为 0，表示刚开始只允许 0 号进程进入临界区。
若 P1 先上处理机运行，由于turn == 0，所以P1会一直卡在 ⑤。直到 P1 的时间片用完，发生调度，切换 P0 上处理机运行。
代码 ① 不会卡住 P0，P0 可以正常访问临界区，在 P0 访问临界区期间如果切换回 P1，P1依然会卡在 ⑤。
只有 P0 在退出区将 turn 改为 1 后，P1才能进入临界区。
单标志法的问题在于：如果一开始允许进入临界区的进程是P0（即turn=0），但进程P0此时不需要访问临界资源而是在做别的事情，因此不会执行代码1~4。那么P1会一直被卡在代码5的循环，无法使用到资源。
因此 单标志法违背了 “空闲让进” 原则，让资源无故闲置也不分配给需要该资源的其他进程。
双标志先检查法
设置一个布尔型数组 flag[]，数组元素表示各进程想要进入临界区的意愿，每个进程在使用资源之前先检查是否有别的进程想进入临界区。如果没有则将自身对应的标志
flag[i]置为true，并开始访问临界区；有则先让其他进程使用。
由于进程P0和P1是并发执行，因此1~4和5~8 的执行顺序是无序的，因此我们需要考虑1~4和5~8 以任意顺序执行是否会引发问题。
结果若按照 ①⑤②⑥③⑦….的顺序执行，P0 和 P1 将会同时访问临界区。
因此 双标志先检查法 违反了 “忙则等待” 原则。出现这个问题的根本原因是进入区代码的“检查” 和 “上锁”
两个动作不是一气呵成的，“检查”后，“上锁”前可能发 生进程切换。
双标志后检查法
和双标志先检查法的思想基本一致，不同的地方在于，后检查法是 先“上锁” 后 “检查”。
若按照 ①⑤②⑥….的顺序执行，P0 和 P1 将都无法进入临界区。
因此，双标志后检查法虽然解决了“忙则等待”的问题，但是又违背了 “空闲让进” 和 “有限等待” 原则。
两个进程都争着想进入临界区，但是谁也不让谁，最后谁都无法进入临界区。
Peterson 算法
结合双标志后检查法和单标志法，本进程使用资源前，判断对方是否想使用资源，而且资源的使用权利是否已经让出给对方，如果不是则自己使用资源，是则让对方使用资源。
Peterson算法已经遵循了空闲让进、忙则等待和有限等待原则，但未遵循让权等待的原则，会出现忙等（前3种软件方法也未遵循让权等待原则）。
- 进程互斥的硬件实现方法
中断屏蔽
**** 利用
“开/关中断指令”实现互斥。关中断和开中断之间的代码就是临界区，由于关中断后CPU会屏蔽中断，而进程切换依赖于中断，因此可以保证关中断和开中断之间的临界区在执行时不会切换到其他进程，其他进程就不会访问到这个临界区，避免了资源竞争。
优点：简单、高效
缺点：关中断只能让执行关中断指令的CPU屏蔽中断，如果计算机有多个CPU，进程A1和A2在CPU1运行，进程B1和B在CPU2上运行，中断屏蔽机制只能保证
A1 和 A2之间是互斥的，B1和B2之间是互斥的，但A1和B1可能同时访问到临界区。
因此 中断屏蔽作为互斥方法不适合运行在多处理机的进程；
此外，开/关中断指令只能运行在内核态（因为用户进程使用这种高权限指令不安全），所以 中断屏蔽实现互斥只能用于内核进程，不能用于用户进程 。
TestAndSet指令
TestAndSet指令是一个执行过程中不可中断的，用硬件方式实现互斥的指令集。简称为 TS指令或者TSL指令。
其逻辑是：检测一个lock变量判断其他进程是否已经进入临界区，无论是与否都将lock置为true（如果之前lock是false表示没有其他进程使用临界资源，因此本进程就可以使用，于是将lock置为true；如果之前lock是true表示有其他进程使用临界资源，置为true没有影响），并返回置为true之前的lock变量是true还是false。
下面是用软件代码实现的TS指令逻辑（实际上不存在这样的软件代码，该逻辑是用硬件实现的）
上锁过程由TestAndSet完成，检查资源是否被占用由用户进程判断。
之前的 双标志检查法 之所以无法完美实现互斥，就是因为 “上锁” 和 “检查” 过程不是原子操作，而TS指令则弥补了这个缺点。
优点：实现简单，无需像软件实现方法那样严格检查是否会有逻辑漏洞；适用于多处理机环境
缺点：不满足“让权等待”原则，暂时无法进入临界区的进程会占用CPU循环执行TSL指令，从而导致“忙等”。
Swap指令
Swap指令也是一个执行过程中不可中断的指令集，其作用是交换两个变量的值，可以用于实现互斥，也可以用在其他地方。在实现互斥上，其逻辑和TestAndSet指令一样，优缺点也和TS指令一样。
old = true 表示一开始本进程假设临界区已经被占用。
如果临界区已经被占用，则循环内就不停更新当前临界区的占用状态，再检测一次。
04 进程互斥和同步的完美解决方案——信号量机制
上面说的4种软件互斥方法和3种硬件互斥方法的共同缺点是不满足 让权等待 原则。而信号量机制可以解决这个问题。
信号量S是一个用来表示系统中某种资源的可用数量的变量。
信号量机制是操作系统提供的一对用来操作信号量的 wait(S) 和 signal(S) 原语，通过 wait/signal
原语可以很方便的实现进程互斥和同步。
对信号量的操作只有3种：初始化，wait操作 和 signal操作。从前面的内容我们知道，原语是不可中断的，原语是通过“关中断/开中断”指令实现的，因此
wait 和 signal 之间的代码也是被关中断/开中断包裹着，是不可中断的，执行时不会发生进程切换的。
wait 和 signal 原语简称为P、V操作。
信号量可以分为 整型信号量（即信号量是一个整型） 和 记录型信号量（即信号量是一个对象，一个结构体）。因此，信号量机制也分为两种。
- 整型信号量
用一个整数型的变量作为信号量，用来表示系统中某种资源的可用数量。
下面是整型信号量机制的逻辑实现：
从逻辑上看，整型信号量机制类似于 双标志先检查 的互斥机制，即先检查后上锁（S–
可以理解为上锁这一过程），只不过在这里，检查和上锁是原子操作，不可分割和中断。
该机制的问题依旧是不满足 “让权等待”，进程等待资源释放过程中会占用CPU。
- 记录型信号量
记录型信号量除了记录资源的可用数量，还包含了一个等待队列（阻塞队列）。
wait 操作申请资源时，如果可用资源数量不够，会使用 block原语 使进程进入阻塞态，主动让出CPU，并将该进程PCB挂到信号量S的等待队列中。
signal 操作给资源释放锁时，若还有别的进程 在等待这种资源，则使用 wakeup 原语 唤醒等待队列中的 一个进程，该进程从阻塞态变
为就绪态，让该进程进入临界区。（如果调用signal时没有其他进程阻塞，则不做唤醒操作）。
下面是整型信号量机制的逻辑实现，类似于：
使用记录型信号量的信号量机制实现互斥，满足了 ”让权等待“ 的要求，真正意义上完美实现了互斥。
信号量小结：无论是哪种类型的信号量，对信号量的两种操作分别表示：
wait：申请一单位的资源并对这一单位资源上锁；
signal：释放一单位的资源；
信号量实现进程互斥 的基本逻辑如下 ：
/* 信号量机制实现互斥 */semaphore mutex = 1; // 初始化信号量为资源数量
P1(){ ... P(mutex); 临界区... V(mutex); ...}
P2(){ ... P(mutex); 临界区... V(mutex); ...}
注意：对不同的临界资源需要设置 不同的互斥信号量。P、V操作必须成对出现。缺少 P(mutex) 就不能保证临界资源的互 斥访问。缺少 V(mutex)
会导致资源永不被释放，等待进程永不被唤醒。
信号量实现进程同步 的基本逻辑如下：
1. 分析什么地方需要实现“同步关系”，即必须保证不同进程的“一前一后”执行的两个操作；
2. 设置同步信号量 S, 初始为 0；
3. 在进程1的“前操作”之后执行 V(S)，在进程2的“后操作”之前执行 P(S)，这样就可以保证如果CPU先执行后操作时进程2会被阻塞；
我们可以将进程同步中的信号量S看做“某种虚拟的资源”，刚开始是没有这种资源的。进程2的后操作需要使用这种资源， 而又只能由进程1的前操作产生这种资源。
举个例子，假如存在两个进程P1和P2，P1要执行代码1~3，P2要执行代码4~6。要求执行顺序为 1~2 -> 4~6 -> 3。
/* 信号量机制实现同步 */semaphore S = 0; // 初始化信号量为资源数量
P1(){ 代码1; 代码2; V(S) 代码3;}
P2(){ P(S) 代码4; 代码5; 代码6;}
再看一个简单的用信号量实现同步的问题。
假设，进程 P1 中有句代码 S1，P2 中有句代码 S2 ，P3中有句代码S3 …… P6 中有句代码
S6。这些代码要求按如下图所示的顺序来执行，该如何实现呢？
实现逻辑如下：
最后小结：无论是用信号量实现互斥还是同步，关键都在于“阻塞”。
互斥是P和V操作在同一进程中；同步则是P和V操作分别发生在两个不同进程中。
05 进程互斥与同步经典模型
接下来我们探讨几个进程互斥与同步的经典模型，以及如何通过信号量来实现这些模型。这些经典模型包括：生产者消费者模型、读者写者问题、吸烟者问题 和
哲学家进食问题。
- 生产者消费者模型
系统中有一组生产者进程和一组消费者进程，生产者进程每次生产一个产品放入缓冲区，消费者进程每次从缓冲区中取出一个产品并使用。
生产者、消费者共享一个初始为空、大小为n的缓冲区。
只有缓冲区没满时，生产者才能把产品放入缓冲区，否则必须等待。（同步关系）
只有缓冲区不空时，消费者才能从中取出产品，否则必须等待。（同步关系）
缓冲区是临界资源，各进程必须互斥地访问。（互斥关系）
请用代码实现上述模型。
题目中存在2个同步关系和1个互斥关系，因此需要3个信号量实现，实现的伪代码如下：
semaphore mutex = 1; //互斥信号量，实现对缓冲区的互斥访问semaphore empty = n; //同步信号量，表示空闲缓冲单位的数量semaphore full = 0; //同步信号量，表示产品的数量，也即非空缓冲单位的数量
producer(){ while(1){ 生产1个产品; P(empty); // 消耗一个空闲缓冲单位 P(mutex); // 访问缓冲区 把产品放入缓冲区; V(mutex); V(full); // 增加一个产品 }
consumer(){ while(1){ P(full); // 消耗一个缓存区中的产品 P(mutex); // 访问缓冲区 从缓冲区取出产品; V(mutex); V(empty); // 增加一个可用缓冲区单位 使用产品; }}
问题1：producer()中能否改变 P(empty) 和 P(mutex)的顺序？
答：不可以，会发生死锁。
若此时缓冲区内已经放满产品，则 empty=0，full=n。
则生产者进程执行① 使mutex变为0，再执行②，由于已没有空闲缓冲区，因此生产者被阻塞。
由于生产者阻塞，因此切换回消费者进程。消费者进程执行③，由于mutex为0，即生产者还没 释放对临界资源的“锁”，因此消费者也被阻塞。
这就造成了生产者等待消费者消费以腾出空闲单元，而消费者又等待生产者释放临界区，生 产者和消费者循环等待被对方唤醒，出现“死锁”。
因此， 实现互斥的P（wait）操作一定要在实现同步的P（wait）操作之后 。
问题2：producer()中能否改变V(full) 和 V(mutex)的顺序？
答：V操作不会导致进程阻塞，因此两个V操作顺序可以交换。
问题3：能否把 “使用产品;” 放到PV操作之间？
答：可以是可以，但是会使临界区代码增多，临界区是只允许串行的代码区，因此会导致并发度降低，建议尽可能将无需互斥访问的代码放到临界区之外。
- 多生产者-多消费者模型
桌子上有一只盘子，每次只能向其中放入一个水果。爸爸专向盘子中放苹果，妈妈专向盘子中放
橘子，儿子专等着吃盘子中的橘子，女儿专等着吃盘子中的苹果。只有盘子空时，爸爸或妈妈才
可向盘子中放一个水果。仅当盘子中有自己需要的水果时，儿子或女儿可以从盘子中取出水果。
如何用伪代码操作实现上述过程？我们分析一下：
1、首先4个人，代表4个进程；
2、父母只能在盘子有空间的时候放水果，否则阻塞。需要同步信号量plate表示盘子是否为空来同步父母的放水果操作，对应的V(plate)操作放在子女进程中取完水果后执行，唤醒父母。
3、子女需要两个同步信号量apple和orange表示是否有苹果和橘子来同步子女的拿水果操作。对应的V操作在父母放完水果后执行，唤醒子女。
4、互斥访问盘子资源需要一对PV操作。
实现代码如下：
orange = 0; // 盘子中的橘子数 apple = 0; // 盘子中的苹果数empty = 1; // 盘子是否为空mutex = 1;
father(){ while(1){ 生产苹果; P(empty); // 如果盘子不为空则阻塞，为空则将empty置为非空 P(mutex); 苹果放入盘子; V(mutex); V(apple); // 通知女儿有苹果了 }}
mother(){ while(1){ 生产橘子; P(empty); P(mutex); 橘子放入盘子; V(mutex); V(orange); }}
son(){ while(1){ P(orange) // 检查盘子中是否有橘子，并减少盘子中的一个橘子。没有则阻塞 P(mutex); 从盘子拿走橘子; V(mutex); V(empty); }}
daughter(){ while(1){ P(apple) P(mutex); 从盘子拿走苹果; V(mutex); V(empty); // 通知爸爸盘子空了，可以继续放苹果 }}
问题：可不可以不用互斥信号量mutex？
答：在本例中可以，因为缓冲区大小为1，在任何时刻，apple、orange和empty这三个同步信号量最多只有一个是1，因此任意时刻最多只有一个进程的P操作不会被阻塞，其他进程都会被阻塞，也就相当于是串行操作了。
如果缓冲区大小为2，则必须要用互斥信号量，否则父母可能同时访问临界资源导致数据混乱。
- 读者-写者问题
情景如下：
有读者和写者两组并发进程，共享一个文件，当两个或两个以上的读进程同时访问共享数据时不会产生副作用，但若某个写进程和其他进程（读进程或写进程）同时访问共享数据时则可能导致
数据不一致的错误。
因此要求：①读读可并发；②写写互斥；③读写互斥；④写读互斥。
读者-写者问题和生产者-消费者问题的区别在于，生产者-消费者问题中任何对容器的读或写操作要求互斥，不能并发进行；而读者-写者问题中的读读是可以并发的。
分析：本题目是一个纯互斥的问题，不涉及同步（因为没有必须先读后写，或者先写后读的要求）。
其实 后面3个要求比较容易解决，直接用一个互斥量锁住读操作和写操作的临界区即可，如何解决读读并发是难点。
实际上读者-写者问题可以使用一个互斥信号量和一个计数器实现。
可以用一个计数器count记录当前执行读操作的读进程有多少个，只有第一个读进程才需要读前加锁，count > 0
时，说明有其他读进程在读，本读进程就不上锁了。
这就相当于， 所有读进程可以共同持有一把锁，而写进程不能共享一把锁，只能独占的使用这把锁。
代码实现：
rw_lock = 1; // 互斥量，保证读写数据是串行的count = 0; // 当前执行读操作的读进程有多少个count_lock = 1; // 互斥量，保证count变量的访问是串行的
reader(){ while(1){ P(count_lock) if(count==0){ P(rw_lock) // 没有读进程上锁，则本读进程上锁 } count++ V(count_lock) 读数据; P(count_lock) count-- if(count==0){ V(rw_lock) // 如果本进程是最后一个持有锁的读进程，则解锁 } V(count_lock) }}
writer(){ while(1){ P(rw_lock); // 申请锁，上锁 写数据; V(rw_lock); // 释放锁，解锁 }}
需要注意：count的检查和修改是原子性的。否则，读进程1执行完 if(count==0)后对文件上锁，没来得及执行
count++就切换到了读进程2，那么读进程2也会上锁，于是读读互斥。
解决写饥饿问题
按照上述代码的逻辑，如果有足够多的读进程，他们执行while循环不停地进行读操作，那么 rw_lock
会一直被读进程们持有，导致写进程一直等待，无法写入数据，也就是写饥饿问题。
比如，有3个进程并发执行，开始执行的顺序是读进程1->写进程1->读进程2。之所以写进程1会饥饿是因为写进程1被P(rw_lock)阻塞住了，读进程1在执行count
–之前，读进程2就执行了count++，导致读进程1无法释放 rw_lock。
如何解决写进程饥饿问题呢？如果能按进程先来后到的顺序公平的获得rw_lock就可以破解饥饿，例如写进程1比读进程2先来，写进程1就优先获得rw_lock的权利，因此写进程1可以先预订读进程1正在持有的rw_lock，即用一个互斥量w锁住rw_lock，只有进程拿到rw_lock锁之后才能释放w。可以将
P(w)理解为进程在申请获取rw_lock锁的权利。
如下所示：
rw_lock = 1; // 互斥量，保证读写数据是串行的count = 0; // 当前执行读操作的读进程有多少个count_lock = 1; // 互斥量，保证count变量的访问是串行的w = 1; // 互斥量，用来锁住rw_lock
reader(){ while(1){ P(w); // 申请持有rw_lock锁的权利 P(count_lock) if(count==0){ P(rw_lock) // 没有读进程上锁，则本读进程上锁 } count++ V(w); // 拿到rw_lock锁之后才释放w，必须放在count++之后，因为对于读进程而言，count++才算让读进程拿到了rw_lock锁 V(count_lock) 读数据; P(count_lock) count-- if(count==0){ V(rw_lock) // 如果本进程是最后一个持有锁的读进程，则解锁 } V(count_lock) }}
writer(){ while(1){ P(w); // 申请持有rw_lock锁的权利 P(rw_lock); // 申请锁，上锁 V(w); // 拿到rw_lock锁之后才释放w 写数据; V(rw_lock); // 释放锁，解锁 }}
下图为官方答案
- 吸烟者问题
假设一个系统有三个抽烟者进程和一个供应者进程。每个抽烟者不停地卷烟并抽掉它，但是要卷
起并抽掉一支烟，抽烟者需要有三种材料：烟草、纸和胶水。三个抽烟者中，第一个拥有烟草、
第二个拥有纸、第三个拥有胶水。供应者进程无限地ᨀ供三种材料，供应者每次将两种材料放桌
子上，拥有剩下那种材料的抽烟者卷一根烟并抽掉它，并给供应者进程一个信号告诉完成了，供
应者就会放另外两种材料再桌上，这个过程一直重复（让三个抽烟者轮流地抽烟）。
实现代码如下：
s1 = 0; // 纸s2 = 0; // 烟草s3 = 0; // 胶水finished = 1; // 当前被服务的抽烟者是否已经抽完烟
producer(){ start = 0 while(1){ choice = start % 3 if(choice == 0){ // 提供纸巾和烟草 V(s1); V(s2); } if(choice == 1){ V(s1); V(s3); } if(choice == 3){ V(s2); V(s3); } P(finished); // 提供完材料之后，供应者阻塞，直到其他抽烟者通知唤醒本进程 }}consumer1(){ // 自带烟草 while(1){ P(s1); // 请求纸 P(s3); // 请求胶水 从桌子上拿走纸、胶水; 抽烟; V(finished); // 唤醒供应者 }}consumer2(){ // 自带纸 while(1){ P(s2); // 请求烟草 P(s3); // 请求胶水 从桌子上拿走烟草、胶水; 抽烟; V(finished); // 唤醒供应者 }}
consumer3(){ // 自带胶水 while(1){ P(s2); // 请求烟草 P(s1); // 请求纸 从桌子上拿走烟草、纸; 抽烟; V(finished); // 唤醒供应者 }}
其实，桌子可以看成是一个大小为1的缓冲区，因为缓冲区大小为1，所以可以不用互斥量finished，只需要同步信号量。上面的解法就没有使用互斥信号量。
- 哲学家进食问题
一张圆桌上坐着5名哲学家，每两个哲学家之间摆一根筷子（是一根而不是一双哦），桌子的中间是一锅海底捞。
哲学家们倾注毕生的精力用于思考和进餐，哲学家在思考时，并不影响他人。只有当哲学家饥饿时，
才试图拿起左、右两根筷子（先拿左边的筷子，后拿右边的筷子）。如果筷子已在他人手上，则需等待。饥饿的哲学家只有同时拿起两根筷子才可以开始进餐，当进餐完毕后，放下筷子继续思考。
哲学家进食问题是单纯的互斥问题，但可能发生死锁，如何死锁是该问题的关键。
第一版本的答案：
chopstick = {1,1,1,1,1}; // chopstick[i]表示i号筷子是否可用human(i){ // 表示 i 号哲学家进食和思考，i号哲学家会使用i号和i+1号筷子 while(1){ P(chopstick[i]); // 拿起i号筷子 P(chopstick[(i+1)%5]); // 拿起i+1号筷子 进食; // 临界区，不过临界资源不是火锅，而是筷子，这里锁住的其实是两根筷子 V(chopstick[i]); // 释放i号筷子 V(chopstick[(i+1)%5]); // 释放i+1号筷子 思考; }}
某一个人在进食时，它相邻的两个人不能进食，但它对面的两个人可以并发进食。
这个解法问题是如果1~5号哲学家分别先后拿起他左边的筷子，就会发生死锁。
为了避免死锁，可以使用以下几种思路：
1. 让哲学家一拿就拿两根筷子，也就是说，一个哲学家拿左边筷子和右边筷子的时候不允许其他哲学家拿筷子。
chopstick = {1,1,1,1,1}; // chopstick[i]表示i号筷子是否可用mutex = 1; // 互斥量，使某个人拿2只筷子的过程中，其他哲学家不能拿筷子human(i){ // 表示 i 号哲学家进食和思考，i号哲学家会使用i号和i+1号筷子 while(1){ P(mutex); P(chopstick[i]); // 拿起i号筷子 P(chopstick[(i+1)%5]); // 拿起i+1号筷子 V(mutex); 进食; // 临界区，不过临界资源不是火锅，而是筷子，这里锁住的其实是两根筷子 V(chopstick[i]); // 释放i号筷子 V(chopstick[(i+1)%5]); // 释放i+1号筷子 思考; }}
该方式的一个小缺点在于任何一个人拿筷子的时候，其他人不能拿筷子，因此哲学家拿筷子是串行的，但拿筷子的时间非常短，因此也不会造成多少性能损失。
2.让最多4个人能用筷子，第5个人如果要用筷子就被阻塞。
chopstick = {1,1,1,1,1}; // chopstick[i]表示i号筷子是否可用max = 4; // 最多4个人拿筷子human(i){ // 表示 i 号哲学家进食和思考，i号哲学家会使用i号和i+1号筷子 while(1){ P(max); P(chopstick[i]); // 拿起i号筷子 P(chopstick[(i+1)%5]); // 拿起i+1号筷子 进食; // 临界区，不过临界资源不是火锅，而是筷子，这里锁住的其实是两根筷子 V(chopstick[i]); // 释放i号筷子 V(chopstick[(i+1)%5]); // 释放i+1号筷子 V(max); 思考; }}
该解法虽然预防了死锁，但是在4个相邻哲学家同时拿起左边筷子时会造成这4个哲学家进食是串行的，但4个人同时拿筷子发生几率比较小，可以接受。
3. 让奇数号哲学家先拿左边的筷子，偶数号哲学家先拿右边的筷子，该方法是3种方法中效率最高的。
chopstick = {1,1,1,1,1}; // chopstick[i]表示i号筷子是否可用
human(i){ // 表示 i 号哲学家进食和思考，i号哲学家会使用i号和i+1号筷子 while(1){ if(i & 1 == 1){ P(chopstick[i]); // 拿起i号筷子 P(chopstick[(i+1)%5]); // 拿起i+1号筷子 }else{ P(chopstick[(i+1)%5]); // 拿起i号筷子 P(chopstick[i]); // 拿起i+1号筷子 } 进食; // 临界区，不过临界资源不是火锅，而是筷子，这里锁住的其实是两根筷子 V(chopstick[i]); // 释放i号筷子 V(chopstick[(i+1)%5]); // 释放i+1号筷子 思考; }}