文章目录

• 一、概述
• 二、信 量的定义
• 三、P 和 V 的定义
• 四、互斥实现的模版
• 五、同步实现的模版
• 六、生产者消费者经典问题
• • 6.1 简单类型问题
  • 6.2 中等类型问题
  • 6.3 复杂类型问题
• 七、典型的双缓冲问题
• 八、四道练习题【由易到难】
• • 8.1 火车售票问题
  • 8.2 阅览室登记问题
  • 8.3 经典的读写问题
  • 8.4 经典的独木桥问题
  • 8.5 经典的独木桥问题 —— 升级版（2022/1/2补充的）
• 九、参考附录：

model

上一篇文章地址链接: 【操作系统⑥】——进程联系与临界区管理【同步与互斥 Dekker算法 TS指令 SWAP指令】.
下一篇文章地址链接: 【操作系统⑧】——信 量与PV操作(下)【哲学家进餐问题 AND型信 量 信 量集机制】.

期末考试总复习——地址链接：《操作系统期末总复习——绝地求生版》.

一、概述

上一篇文章中提到各种管理临界区的，不管是软件方法，还是硬件的方法，都是存在一个隐藏的问题：它们都是一种平等进程间的协商机制，在协商分配资源时，可能会出现公用资源的使用问题。这时我们就需要一个地位高于进程的管理者来解决这类问题。

965年，荷兰著名科学家，Dijkstra提出了一种控制进程同步、互斥的信 量与P/V操作机制。有效地解决了其问题。

里举个来说，在百度百科上找的例子上进行了拓展：
以一个停车场的运作为例。简单起见，假设停车场只有 3 个车位，一开始 3 个车位都是空的。这时如果同时来了 5 辆车，看门人允许其中 3 辆直接进入，然后放下车拦，剩下的车则必须在入口等待。此后来的车也都不得不在入口处等待。这时，有 1 辆车离开停车场，得知后，打开车拦，放入外面的 1 辆进去，如果又离开 2 辆，则又可以放入 2 辆，如此往复。
在这个停车场系统中，车位是公共资源，每辆车好比一个进程，起的就是的作用。

那这和上一章的并发处理机制比起来，有什么不同呢br> 如果说，上一章也存在这么一个 “停车场和车位”(公共资源)，也有这么些 “车”(进程)的话。那么上一章就不存在这个 “”(信 量)。而当前 3 辆车进入时，第 4、5 两辆车就不能进入，他俩就在原地等待，但是他们的车 “没有熄火”，一直 “启动着车的”，因为他俩不知道多久有车能出来，所以他俩人也是醒着的。但是，当有了 “”(信 量) 的时候，他俩就可以 “熄火并安心睡觉” 了。因为当有车出来的时候，“” 会自动来叫醒他俩。另外，“看门人” 具有 “”(放车进去) 和 “”(放车出去)。

绿色字体部分是个人理解，不一定完全正确，旨在帮助理解。

strong>重点掌握两个模板、几个经典例题的PV操作。然后在遇到问题时，能够回忆起这些模板和PV操作时，再结合具体情形，即可快速有效地解决问题。

二、信 量的定义

量的一个数据结构。

量一般由两部分组合，第一个部分是整数类型的计数器（储存了信 量的数值）。第二个部分是一个等待队列，里面装有等待进程的唯一标识符 PCB 。

strong>信 量具有一些特性，若结合刚才停车场的例子来说的话就是：
量是一个非负整数（车位数）。
有 “进或出” 它的进程（车辆）都会将该整数 “减1或加1”。（进入它就是为了获取并使用资源，离开它就是释放资源）
该整数值为 0 时，所有试图 “进入” 它的进程都将会处于等待状态。

三、P 和 V 的定义

量的数值仅能由 P、V 原语 操作改变。原语的执行必须是连续的，可以通过关中断指令来实现。

strong>P 原语的定义如下：

strong>P 原语操作主要动作的说明：
一个进程调用 P 操作时，它要么得到资源然后将信 量减 1 （即“s.count = s.count – 1;”）。
么一直等待下去，即放入阻塞队列。
到信 量 >= 1 时，“看门人” 唤醒 ta，ta（进程） 便再次开始执行。

strong>V 原语的定义如下：

strong>V 原语操作的说明：当一个进程调用 V 操作时，它要么释放资源然后将信 量加1 （即“s.count = s.count + 1;”）。

strong>补充说明一：S 大于 0 那就表示有临界资源可供使用，为什么不唤醒进程strong>该说明源自参考附录[3] 。
答：S 大于 0 的确表示有临界资源可供使用，也就是说这个时候没有进程被阻塞在这个资源上，所以不需要唤醒。

strong>补充说明二：S 小于 0 应该是说没有临界资源可供使用，为什么还要唤醒进程strong>该说明源自参考附录[3] 。
答：V 原语操作的本质在于：一个进程使用完临界资源后，释放临界资源，使 S 加 1，以通知其它的进程。这个时候如果 S<0，表明有进程阻塞在该类资源上，因此要从阻塞队列里唤醒一个进程来 “转手” 该类资源。比如，有两个某类资源，四个进程 A、B、C、D 要用该类资源，最开始初始化 S=2，当 A 进入，S=1。当 B 进入 S=0，表明该类资源刚好用完。 当 C 再进入时 S=-1 ，表明有一个进程被阻塞了。然后D进入，S=-2，也被阻塞。当 A 用完该类资源时，进行 V 操作，S=-1，释放该类资源，因为S<0，表明有进程阻塞在该类资源上，于是唤醒一个。

strong>补充说明三：S 的绝对值表示等待的进程数，同时又表示临界资源，这到底是怎么回事br> 答：当信 量 S 小于 0 时，其绝对值表示系统中因请求该类资源而被阻塞的进程数目。S 大于 0 时表示可用的临界资源数。注意在不同情况下所表达的含义不一样。当 S 等于 0时，表示刚好用完。

四、互斥实现的模版

strong>利用信 量和 PV 操作实现进程互斥的一般模型是：

strong>代码说明：P1 进程进入临界区之后 s 的值就变为 0 ，P2 执行 P(s) 之后进入阻塞队列从而实现了对临界区的互斥访问。

strong>使用 PV 操作实现进程互斥时应该注意的是：
个程序中用户实现互斥的 P、V 操作必须成对出现，先做 P 操作，进临界区，后做 V 操作，再出临界区。若有多个分支，要认真检查其成对性。
、V 操作应分别紧靠临界区的头尾部，临界区的代码应尽可能短，不能有死循环。
斥信 量 s 的初值一般为 1。

五、同步实现的模版

strong>利用信 量和 PV 操作实现进程同步的一般模型是：

strong>代码说明：s 的初值为 0，就意味着只能先做 V 操作，也就是先执行 P2，然后才能执行P1 里的 P 操作。所以这实现了 P1 和 P2 先后次序的同步关系。

strong>使用 PV 操作实现进程同步时应该注意的是：
分析清楚进程之间的制约关系，确定信 量种类(上述模板中只有一种，也就是 s )。
保持进程间有正确的同步关系情况下，还要设定好哪个进程先执行，哪些进程后执行，彼此间通过什么资源(信 量)进行协调。
量的初值与相应资源的数量有关，也与 P、V 操作在程序代码中出现的位置有关。
strong>同一信 量的 P、V 操作要成对出现，但它们分别在不同的进程代码中。

六、生产者消费者经典问题

了更好地理解问题的实质，接下来将把生产者消费者问题由简至难分为三种类型，分别做分析。

6.1 简单类型问题

strong>简单类型：一个生产者，一个消费者，共用一个缓冲区。

strong>分析一：两个进程一个生产，一个消费。每一次操作中，生产者生产的产品只能放一个进入 “公用的缓冲区”。同样地，在每一次操作中，消费者也只能从 “公用的缓冲区” 里取出一个产品。

strong>分析二：“程序” 开始执行后。首先，两进程互斥地进入缓冲区，然后是需要同步，先生产再消费。但也需要考虑存在的另一种同步，即当缓冲区满的时候，是先消费再生产。

6.2 中等类型问题

strong>中等类型：一个生产者，一个消费者，共用 n 个环形缓冲区。

strong>分析一下和第一种问题的区别：区别就是需要设缓冲区的编 为 1～n ，定义两个指针 in 和 out ，分别是 生产者进程和消费者进程 使用来指向下一个可用缓冲区的 “指针” 。而且同步和互斥的关系和第一种问题是一样的。

6.3 复杂类型问题

strong>复杂类型：a 个生产者，b 个消费者，共用 n 个环形缓冲区

strong>互斥关系分析：
先设定 P i P_i Pi/span> 为生产者， C j C_j Cj/span> 为消费者， i = 1 , 2 , . . . , a i = 1,2,…,a i=1,2,...,a， j = 1 , 2 , . . . , b j = 1,2,…,b j=1,2,...,b 。
span> i i i 不同的 P i P_i Pi/span> 之间是互斥的。
span> j j j 不同的 C j C_j Cj/span> 之间是互斥的。
i i i和 j j j 相同的情况下， P i P_i Pi/span>和 C j C_j Cj/span> 之间是互斥的。

strong>同步关系分析：
冲区为空时，先生产再消费。
冲区为满时，先消费再生产。

strong>解决问题步骤1 —— 定义 4 个信 量：
mpty —— 表示缓冲区是否为空，初值为 n【第一类同步信 量】
ull —— 表示缓冲区中是否为满，初值为 0【第二类同步信 量】
utex1 —— 生产者之间的互斥信 量，初值为 1
utex2 —— 消费者之间的互斥信 量，初值为 1

strong>解决问题步骤2 —— 设定操作过程
了同步生产者和消费者的行为，需要记录缓冲区中物品的数量。数量可以使用信 量来进行统计，这里需要使用两个信 量：empty 记录空缓冲区的数量、full 记录满缓冲区的数量。需要注意同步信 量初值不一定为 0，只要根据同步关系保证先后执行次序就可以了。
mpty 信 量是在生产者进程中使用，当 empty 不为 0 时，生产者才可以放入物品；
ull 信 量是在消费者进程中使用，当 full 信 量不为 0 时，消费者才可以取走物品。
同一资源使用的一组进程可以设置一个互斥信 量。互斥信 量初值一般为 1，也就是同一时刻只能一个生产者（或一个消费者）对缓冲区做相应处理。
中等问题类似，也要设定缓冲区的编 为 1～n，并定义两个指针 in 和 out ，分别是 生产者进程和消费者进程 使用来指向下一个可用的缓冲区。

strong>同步和互斥的示意图及代码：