王道操作系统笔记（五）——— 经典同步问题

向右看齐 2023-10-11 20:33 62阅读 0赞

## 前言：PV 操作题目分析步骤 ##

1.  **关系分析：** 找出题目中描述的各个进程，分析它们之间的同步、互斥关系。
2.  **整理思路：** 根据各进程的操作流程确定 P、V 操作的大致顺序。
3.  **设置信号量：** 并根据题目条件确定信号量初值。（互斥信号量初值一般为1，同步信号量的初始值要看对应资源的初始值是多少）

--------------------

#### 文章目录 ####

*  前言：PV 操作题目分析步骤
 *  一、生产者消费者问题
 *   *  1.1 问题分析
     *  1.2 进程描述
     *  1.3 扩展思考
     *   *  1.3.1 能否改变相邻 PV 操作的顺序 ？
         *  1.3.2 能否只设置一个同步信号量？
 *  二、多生产者多消费者问题
 *   *  2.1 问题分析
     *  2.2 进程描述
     *  2.3 扩展思考
     *   *  2.3.1 能否不设置互斥信号量？
         *  2.3.2 为什么要从事件的角度分析？
 *  三、吸烟者问题
 *   *  3.1 问题分析
     *  3.2 进程描述
     *  3.3 扩展思考：能否从进程角度思考？
 *  四、读者-写者问题
 *   *  4.1 问题分析
     *  4.2 进程描述
     *   *  4.2.1 方案1
         *  4.2.2 方案2
 *  五、哲学家进餐问题
 *   *  5.1 问题分析
     *  5.2 进程描述
 *  总结：各种同步问题适用的情况
 *  六、管程
 *   *  6.1 管程的定义
     *  6.2 管程的基本特征
     *  6.3 拓展：用管程解决生产者消费者问题

--------------------

## 一、生产者消费者问题 ##

系统中有一组生产者进程和一组消费者进程，生产者进程每次生产一个产品放入缓冲区，消费者进程每次从缓冲区中取出一个产品并使用。生产者、消费者共享一个 初始为空、大小为 n 的缓冲区。只有 缓冲区没满 时，生产者才能把产品放入缓冲区，否则必须等待。只有 缓冲区不空 时，消费者才能从中取出产品，否则必须等待。缓冲区是临界资源，各进程必须 互斥 地访问。

### 1.1 问题分析 ###

1.  **关系分析**  
    同步关系：缓冲区没满，生产者生产；缓冲区没空，消费者消费。  
    互斥关系：各进程互斥访问缓冲区。
2.  **整理思路**  
    ![在这里插入图片描述][51a89fdf9e594fb384ae212d810f97af.png_pic_left]
3.  **信号量的设置**
    
        semaphore mutex = 1; //互斥信号量，实现对缓冲区的互斥访问
        semaphore empty = n; //同步信号量，表示空闲缓冲区的数量
        semaphore full = 0;  //同步信号量，表示产品的数量，也即非空缓冲区的数量

--------------------

### 1.2 进程描述 ###

![在这里插入图片描述][fa5416e4f6dc4b718ab17bf8c38bd4b4.png_pic_left]

--------------------

### 1.3 扩展思考 ###

#### 1.3.1 能否改变相邻 PV 操作的顺序 ？ ####

若此时缓冲区内已经放满产品，则 empty=0，full=n。则生产者进程执行 ① 使mutex变为0，再执行②，由于已没有空闲缓冲区，因此生产者被阻塞。由于生产者阻塞，因此切换回消费者进程。消费者进程执行 ③，由于 mutex 为 0，即生产者还没释放对临界资源的 “锁”，因此消费者也被阻塞。生产者和消费者循环等待被对方唤醒，出现 死锁。  
![在这里插入图片描述][2c754dcb57824933b85650c2ff8b0bbf.png_pic_left]  
同样的，若缓冲区中没有产品，即 full=0，empty=n。按③④① 的顺序执行就会发生死锁。  
因此 实现互斥的 P 操作一定要在实现同步的 P 操作之后。  
V 操作不会导致进程阻塞，因此 两个 V 操作顺序可以交换。

#### 1.3.2 能否只设置一个同步信号量？ ####

答：不能。原因在于：两个信号量 empty 和 full，其中 empty 用于制约生产者生产，full 用于制约消费者消费。如果只设置一个信号量，如 full，那么生产者会无限的生产，起不到制约作用。

--------------------

## 二、多生产者多消费者问题 ##

桌子上有一只盘子，每次只能向其中放入一个水果。爸爸专向盘子中放苹果，妈妈专向盘子中放橘子，儿子专等着吃盘子中的橘子，女儿专等着吃盘子中的苹果。只有盘子空时，爸爸或妈妈才可向盘子中放一个水果。仅当盘子中有自己需要的水果时，儿子或女儿可以从盘子中取出水果。用 PV 操作实现上述过程。

### 2.1 问题分析 ###

1.  **关系分析**  
    同步关系：① 父亲将苹果放入盘子，女儿才能取苹果；  
         ② 母亲将句子放入盘子，儿子才能取橘子；  
         ③ 只有盘子为空，父亲或者母亲才能放水果。  
    互斥关系：对缓冲区(盘子)的访问要互斥的进行。
2.  **整理思路**  
    ![在这里插入图片描述][715b4760323a46c1b97dcd79b01788e7.png_pic_left]  
    注：盘子为空这个事件可由儿子或者女儿触发，发生后父亲或母亲才可放水果。  
    分析同步要以 **事件** 的角度分析，不要以 **进程** 的角度分析。
3.  **信号量的设置**
    
        semaphore mutex = 1;  //实现互斥访问盘子（缓冲区）
        semaphore apple = 0;  //盘子中有几个苹果
        semaphore orange = 0; //盘子中有几个橘子
        semaphore plate = 1;  //盘子中还可以放多少个水果

--------------------

### 2.2 进程描述 ###

![在这里插入图片描述][03b5b144181941df8f7455a5350b5658.png_pic_left]  
注：互斥一定要在同步信号量之后，防止出现进程阻塞，进而导致死锁，参考上题。

--------------------

### 2.3 扩展思考 ###

#### 2.3.1 能否不设置互斥信号量？ ####

如果缓冲区大小为1，在任何时刻，apple、orange、plate 三个信号量中最多只有一个是1。因此在任何时刻，最多只有一个进程的P操作不会被阻塞，并顺利地进入临界区。  
  如果缓冲区大小大于1，数据可能存在相互覆盖的情况。如：父亲在向盘子放橘子的同时，母亲也可以往盘子里放橘子，有可能导致两个进程写入缓冲区的数据相互覆盖的情况。  
  因此，当缓冲区大小等于1，有可能不设置互斥变量。当缓冲区大小大于1，必须设置互斥变量。是否不用设置互斥信号量主要观察，同一时刻信号量是否最多一个1，**建议设置互斥信号量**。

![在这里插入图片描述][3b52be6d997145738c875b31abacb69c.png_pic_left]

--------------------

#### 2.3.2 为什么要从事件的角度分析？ ####

如果从 单个进程的角度 来考虑的话，会有以下结论：  
① 如果盘子里装有苹果，那么一定要女儿取走苹果后父亲或母亲才能再放入水果；  
② 如果盘子里装有橘子，那么一定要儿子取走橘子后父亲或母亲才能再放入水果。  
这就意味着要 设置四个同步信号量 分别实现这 四个一前一后的关系，较为复杂。

![在这里插入图片描述][d17b09a31472491e98d081a335f1ef4a.png_pic_left]

若从 事件的角度 来考虑，我们可以把上述四对进程行为的前后关系抽象为 一对事件 的前后关系，即：盘子变空事件 **→** 放入水果事件。

--------------------

## 三、吸烟者问题 ##

假设一个系统有 三个抽烟者进程 和 一个供应者进程。每个抽烟者不停地卷烟并抽掉它，但是要卷起并抽掉一支烟，抽烟者需要有三种材料：烟草、纸和胶水。三个抽烟者中，第一个拥有烟草、第二个拥有纸、第三个拥有胶水。供应者进程无限地提供三种材料，供应者每次将两种材料放桌子上，拥有剩下那种材料的抽烟者卷一根烟并抽掉它，并给供应者进程一个信号告诉完成了，供应者就会放另外两种材料在桌上，这个过程一直重复（让三个抽烟者轮流地抽烟）。

### 3.1 问题分析 ###

1.  **关系分析**  
    同步关系：① 桌上有组合一，第一个抽烟者取走东西  
         ② 桌上有组合二，第二个抽烟者取走东西  
         ③ 桌上有组合三，第三个抽烟者取走东西  
         ④ 抽烟者抽完发出完成信号，供应者将下一个组合放到桌上  
    互斥关系：对缓冲区的访问要互斥的进行。
2.  **整理思路**  
    ![在这里插入图片描述][a2e2be6b31ec48f6b9e4a63a7ce1cb20.png_pic_left]  
    注：由于缓冲区大小为1，任意时刻同步信号量和互斥信号量最多只有一个1，因此互斥信号量可以不设置。
3.  **信号量的设置**
    
        semaphore offer1 = 0; //桌上组合一的数量
        semaphore offer2 = 0; //桌上组合二的数量
        semaphore offer3 = 0; //桌上组合三的数量
        semaphore finish = 0; //抽烟是否完成
        int i = 0; //用于实现“三个抽烟者轮流抽烟”

--------------------

### 3.2 进程描述 ###

![在这里插入图片描述][029d0f3880d441a5b46ae6b0db27b3ad.png_pic_left]

--------------------

### 3.3 扩展思考：能否从进程角度思考？ ###

答：不可以。  
  同多生产者多消费者问题，假设从进程角度思考，那么第一个抽烟者抽完后，供应者再将第一个组合放到桌上；第二个抽烟者抽完后，供应者再将第二个组合放到桌上；第三个抽烟者抽完后，供应者再将第三个组合放到桌上。这样相比于从事件考虑的一个一前一后的关系，多出了多个关系，并且较为复杂。因此要从事件的角度思考 PV 关系。

--------------------

## 四、读者-写者问题 ##

有读者和写者两组并发进程，共享一个文件，当两个或两个以上的读进程同时访问共享数据时不会产生副作用，但若某个写进程和其他进程（读进程或写进程）同时访问共享数据时则可能导致数据不一致的错误。因此要求：① 允许多个读者可以同时对文件执行读操作；② 只允许一个写者往文件中写信息;③ 任一写者在完成写操作之前不允许其他读者或写者工作；④ 写者执行写操作前，应让已有的读者和写者全部退出。

### 4.1 问题分析 ###

读者-写者问题中只有互斥关系，互斥关系如下：  
   ① 写进程与写进程、写进程与读进程存在互斥关系。  
   ② 读进程与读进程之间不存在互斥关系。  
![在这里插入图片描述][ec6a024d98d74f21a86025ca9a930ba1.png_pic_left]

--------------------

### 4.2 进程描述 ###

#### 4.2.1 方案1 ####

方案设置 rw 和 mutex 两个信号量。rw 信号量 用于实现 读进程与写进程、写进程与写进程 对共享文件的互斥访问。mutex 信号量 用于保证对 count 变量的互斥访问。

![在这里插入图片描述][a62d7354ba5944ffb4ca05e7662404f1.png_pic_left]

若没有设置 mutex 信号量，两个读进程并发执行到 if 条件且都满足，都会执行 P(rw)，会造成其中一个读进程阻塞的情况。设置 mutex 信号量，使得 count 信号量的检查和赋值操作一气呵成，保证了对 count 信号量访问的互斥性。

**方案 1 存在的问题：** 只要有读进程还在读，写进程就要一直阻塞等待，可能 “饿死”。因此，这种算法中，读进程是优先的。

--------------------

#### 4.2.2 方案2 ####

方案 2 是对方案 1 问题的修正，添加了 w 信号量，保证了 读写公平 。如：假设对共享文件的访问顺序是：读者1**→**读者2**→** 写者1 **→** 读者3 ，读者 2 执行完后，写者 3 将会进行写文件，读者 3 进程将会被阻塞。待写者1写完文件后，读者 3 进行读写者 1 访问后的文件。  
![在这里插入图片描述][2b29530b97b94604b6d6bcafa84d217c.png_pic_left]  
  算法 核心思想 在于设置了一个 计数器 count 用来记录当前正在访问共享文件的读进程数。我们可以用 count 的值来判断当前进入的进程是否是第一个/最后一个读进程，从而做出不同的处理。另外，还需考虑 count 变量的互斥性。  
  算法实现：连续进入的多个读者可以同时读文件；写者和其他进程不能同时访问文件；写者不会饥饿，但也并不是真正的“写优先”，而是相对公平的先来先服务原则。算法又称读写公平法。

--------------------

## 五、哲学家进餐问题 ##

一张圆桌上坐着5名哲学家，每两个哲学家之间的桌上摆一根筷子，桌子的中间是一碗米饭。哲学家们倾注毕生的精力用于思考和进餐，哲学家在思考时，并不影响他人。只有当哲学家饥饿时，才试图拿起左、右两根筷子（一根一根地拿起）。如果筷子已在他人手上，则需等待。饥饿的哲学家只有同时拿起两根筷子才可以开始进餐，当进餐完毕后，放下筷子继续思考。

### 5.1 问题分析 ###

1.  **关系分析**  
    系统中有5个哲学家进程，5位哲学家与左右邻居对其中间筷子的访问是互斥关系。
2.  **整理思路**  
    哲学家进餐问题中 只有互斥关系，但与之前遇到的问题不同点在于，每个哲学家进程需要同时持有两个临界资源才能开始吃饭。如何避免临界资源分配不当造成的死锁现象，是哲学家问题的关键。
3.  **信号量的设置**  
    定义互斥信号量数组 `chopstick[5]={1,1,1,1,1}` 用于实现对 5 个筷子的互斥访问。并对哲学家按0~4编号，哲学家 i 左边的筷子编号为 i，右边的筷子编号为 (i+1)%5。此外，还需要设置互斥信号量 `mutex`，用以保证哲学家进程左右两支筷子都可用。  
    ![在这里插入图片描述][6c94f1c773ad4e12934447c004e912c8.png_pic_left]

--------------------

### 5.2 进程描述 ###

![在这里插入图片描述][0f12c4e77b7b47388efa55b690a67e02.png_pic_left]  
算法保证，一个哲学家再拿到筷子拿到一半时被阻塞，也不会有别的哲学家尝试拿筷子，即至少有一个哲学家进程不阻塞。

> **其他方案：**  
> ① 对哲学家进程施加一些限制条件，如最多允许四个哲学家同时进餐。这样可以保证至少有一个哲学家是可以拿到左右两只筷子的。  
> ② 要求奇数号哲学家先拿左边的筷子，然后再拿右边的筷子，而偶数号哲学家刚好相反。用这种方法可以保证如果相邻的两个奇偶号哲学家都想吃饭，那么只会有其中一个可以拿起第一只筷子，另一个会直接阻塞。这就避免了占有一支后再等待另一只的情况。

--------------------

## 总结：各种同步问题适用的情况 ##

1.  生产者消费者问题：两类进程。
2.  吸烟者问题：两类进程，其中一类个数有限。
3.  哲学家问题：一个进程需要翅多个临界资源。
4.  读写者问题：其中一类进程可以共享，用 count 变量。

--------------------

## 六、管程 ##

管程的引入让程序员写程序时不需要再关注复杂的PV操作，从而避免了传统信号量机制存在的很多问题。

### 6.1 管程的定义 ###

管程是一种特殊的软件模块，由以下部分组成：

> ① 局部于管程的 共享数据结构 说明。  
> ② 对该数据结构进行操作的 一组过程 。  
> ③ 对局部于管程的共享数据设置初始值的语句。  
> ④ 管程有一个名字。

注：过程其实就是函数，如下面这个 People 类，People 是管程的名字，username 和 str 是局部于管程的共享数据结构，login 方法是该数据结构进行操作的过程。

public class People{
        
    	private String username = "admin"; // 用户名
    	private String str= "123456"; // 密码
    	
    	public void login(){
        
    		if("admin".equals(username) && "123456".equals(str)){
        
    			System.out.println("登录成功！");	
    		}
    	}
    }

--------------------

### 6.2 管程的基本特征 ###

1.  局部于管程的数据只能被局部于管程的过程所访问；
2.  一个进程只有通过调用管程内的过程才能进入管程访问共享数据；
3.  每次仅允许一个进程在管程内执行某个内部过程。

--------------------

### 6.3 拓展：用管程解决生产者消费者问题 ###

引入管程的目的无非就是要更方便地实现进程互斥和同步。

1.  需要在管程中定义 共享数据 和用于访问这些 数据的入口(函数) 和，只有通过这些特定的入口，才能访问共享数据。
2.  管程中有很多 入口，但每次只能开放其中一个入口，并且只能让一个进程或者线程进入。  
    (如：生产者消费者问题中，各进程需要互斥的访问共享缓冲区，管程的这种特性即可保证一个进程在访问缓冲区。 注意：这种互斥特性是由编译器负责实现的，程序员不用关心）
3.  可在管程中设置 条件变量及等待/唤醒操作 以解决同步问题。可以让一个进程或线程在条件变量上等待（此时，该进程应先释放管程的使用权，也就是让出“入口”）；可以通过唤醒操作将等待在条件变量上的进程或线程唤醒。

模拟管程决生产者消费者问题：

![在这里插入图片描述][7169b03eb4f34d3aa0b4092f3d16b250.png_pic_left]

注：

1.  由编译器负责实现各进程互斥地进入管程中的过程。如：有三个生产者进程同时调用 insert() 函数，编译器会阻塞后两个进程。  
    ![在这里插入图片描述][887040abfc1948f294b7af8854c36db3.png_pic_left]
2.  管程中设置条件变量和等待/唤醒操作，以解决同步问题。如：现有两个消费者进程，前后互斥的调用 remove() 方法，当前系统 count 为 0，因此都会执行wait(empty)，即被阻塞到 empty 队列。直到有生产者进程调用 insert() 方法，执行 insert\_item() 函数，添加产品数量，并执行 signal(empty) 方法，唤醒等待队列 empty 中的进程。  
    ![在这里插入图片描述][7c3f1628ef594750870a0aefb9f12357.png_pic_left]
3.  对条件变量 wait() 操作类似于信号量的 P 操作，对条件变量 signal() 操作类似于信号量的 V 操作，但 wait() 与 signal()操作不用修改信号量。信号量机制除了排队功能以外，还需要修改信号量。

`管程只能实现进程的互斥。(x) 解析：还有同步 (来源：2016年408第32题)`  
`若 x 是管程内的条件变量，则当进程执行 x.wait() 时所做的工作是（D） A. 实现对变量 x 的互斥访问 B. 唤醒一个在 x 上阻塞的进程 C. 根据 x 的值判断该进程是否进入阻塞态 D. 阻塞该进程，并将之插入 x 的阻塞队列中 解析：条件变量是管程内部说明和使用的一种特殊变量，其作用类似于信号量机制中的信号量(但不用修改信号量)，都用于实现进程同步。但在同一时刻，管程中只能有一个进程在执行。 (来源：2018年408第28题)`

[51a89fdf9e594fb384ae212d810f97af.png_pic_left]: https://img-blog.csdnimg.cn/51a89fdf9e594fb384ae212d810f97af.png#pic_left
[fa5416e4f6dc4b718ab17bf8c38bd4b4.png_pic_left]: https://img-blog.csdnimg.cn/fa5416e4f6dc4b718ab17bf8c38bd4b4.png#pic_left
[2c754dcb57824933b85650c2ff8b0bbf.png_pic_left]: https://img-blog.csdnimg.cn/2c754dcb57824933b85650c2ff8b0bbf.png#pic_left
[715b4760323a46c1b97dcd79b01788e7.png_pic_left]: https://img-blog.csdnimg.cn/715b4760323a46c1b97dcd79b01788e7.png#pic_left
[03b5b144181941df8f7455a5350b5658.png_pic_left]: https://img-blog.csdnimg.cn/03b5b144181941df8f7455a5350b5658.png#pic_left
[3b52be6d997145738c875b31abacb69c.png_pic_left]: https://img-blog.csdnimg.cn/3b52be6d997145738c875b31abacb69c.png#pic_left
[d17b09a31472491e98d081a335f1ef4a.png_pic_left]: https://img-blog.csdnimg.cn/d17b09a31472491e98d081a335f1ef4a.png#pic_left
[a2e2be6b31ec48f6b9e4a63a7ce1cb20.png_pic_left]: https://img-blog.csdnimg.cn/a2e2be6b31ec48f6b9e4a63a7ce1cb20.png#pic_left
[029d0f3880d441a5b46ae6b0db27b3ad.png_pic_left]: https://img-blog.csdnimg.cn/029d0f3880d441a5b46ae6b0db27b3ad.png#pic_left
[ec6a024d98d74f21a86025ca9a930ba1.png_pic_left]: https://img-blog.csdnimg.cn/ec6a024d98d74f21a86025ca9a930ba1.png#pic_left
[a62d7354ba5944ffb4ca05e7662404f1.png_pic_left]: https://img-blog.csdnimg.cn/a62d7354ba5944ffb4ca05e7662404f1.png#pic_left
[2b29530b97b94604b6d6bcafa84d217c.png_pic_left]: https://img-blog.csdnimg.cn/2b29530b97b94604b6d6bcafa84d217c.png#pic_left
[6c94f1c773ad4e12934447c004e912c8.png_pic_left]: https://img-blog.csdnimg.cn/6c94f1c773ad4e12934447c004e912c8.png#pic_left
[0f12c4e77b7b47388efa55b690a67e02.png_pic_left]: https://img-blog.csdnimg.cn/0f12c4e77b7b47388efa55b690a67e02.png#pic_left
[7169b03eb4f34d3aa0b4092f3d16b250.png_pic_left]: https://img-blog.csdnimg.cn/7169b03eb4f34d3aa0b4092f3d16b250.png#pic_left
[887040abfc1948f294b7af8854c36db3.png_pic_left]: https://img-blog.csdnimg.cn/887040abfc1948f294b7af8854c36db3.png#pic_left
[7c3f1628ef594750870a0aefb9f12357.png_pic_left]: https://img-blog.csdnimg.cn/7c3f1628ef594750870a0aefb9f12357.png#pic_left