经典进程的同步问题和管程——操作系统笔记

一、生产者消费者问题

  系统中有一组生产者进程和一组消费者进程，生产者进程每次生产一个产品放入缓冲区，消费者进程每次从缓冲区中取出一个产品并使用。（注：这里的“产品”理解为某种数据）

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

1、PV 操作题目分析步骤

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

2、实现过程

3、能否改变相邻P、V操作的顺序？

  实现过程如下：

  若此时缓冲区内已经放满产品，则 empty=0，full=n。则生产者进程执行 ① 使mutex变为 0，再执行 ②，由于已没有空闲缓冲区，因此生产者被阻塞。由于生产者阻塞，因此切换回消费者进程。消费者进程执行 ③，由于mutex为 0，即生产者还没释放对临界资源的“锁”，因此消费者也被阻塞。

  这就造成了生产者等待消费者释放空闲缓冲区，而消费者又等待生产者释放临界区的情况，生产者和消费者循环等待被对方唤醒，出现“死锁”。同样的，若缓冲区中没有产品，即 full=0，empty=n。按 ③④① 的顺序执行就会发生死锁。因此，实现互斥的 P 操作一定要在实现同步的 P 操作之后。V 操作不会导致进程阻塞，因此两个 V 操作顺序可以交换。

二、多生产者-多消费者

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

1、关系分析

• 互斥关系（mutex=1）： 对缓冲区（盘子）的访问要互斥地进行；
• 同步关系（一前一后）：
  • 父亲将苹果放入盘子后，女儿才能取苹果；
  • 母亲将橘子放入盘子后，儿子才能取橘子；
  • 只有盘子为空时，父亲或母亲才能放入水果。（“盘子为空”这个事件可以由儿子或女儿触发，事件发生后才允许父亲或母亲放水果）

2、实现过程

（1）问题：可不可以不用互斥信号量？

  不使用互斥信号量的实现过程如下：

  即使不设置专门的互斥变量 mutex，也不会出现多个进程同时访问盘子的现象。

  分析：子、女儿进程即使上处理机运行也会被阻塞。如果刚开始是父亲进程先上处理机运行，则：父亲 P(plate) 可以访问盘子 → 母亲 P(plate) 阻塞等待盘子 → 父亲放入苹果 V(apple)，女儿进程被唤醒，其他进程即使运行也都会阻塞，暂时不可能访问临界资源（盘子）→ 女儿 P(apple) 访问盘子 V(plate)，等待盘子的母亲进程被唤醒 → 母亲进程访问盘子（其他进程暂时都无法进入临界区）→……

  原因在于：本题中的缓冲区大小为 1，在任何时刻，apple、orange、plate 三个同步信号量中最多只有一个是 1。因此在任何时刻， 最多只有一个进程的 P 操作不会被阻塞，并顺利地进入临界区...

（2）如果盘子（缓冲区）容量为 2

  父亲 P(plate) 可以访问盘子 → 母亲P(plate) 可以访问盘子 → 父亲在往盘子里放苹果，同时母亲也可以往盘子里放橘子。于是就出现了两个进程同时访问缓冲区的情况，有可能导致两个进程写入缓冲区的数据相互覆盖的情况。因此，如果缓冲区大小大于1，就必须专门设置一个互斥信号量 mutex 来保证互斥访问缓冲区。

总结：

  在生产者-消费者问题中，如果缓冲区大小为 1，那么有可能不需要设置互斥信号量就可以实现互斥访问缓冲区的功能。当然，这不是绝对的，要具体问题具体分析。

3、同步关系的分析方法

  在分析同步问题（一前一后问题）的时候不能从单个进程行为的角度来分析，要把“一前一后”发生的事看做是两种“事件”的前后关系。比如，如果从单个进程行为的角度来考虑的话，我们会有以下结论：

• 如果盘子里装有苹果，那么一定要女儿取走苹果后父亲或母亲才能再放入水果；
• 如果盘子里装有橘子，那么一定要儿子取走橘子后父亲或母亲才能再放入水果。

  这么看是否就意味着要设置四个同步信号量分别实现这四个“一前一后”的关系了？

  正确的分析方法应该从“事件”的角度来考虑，我们可以把上述四对“进程行为的前后关系”抽象为一对“事件的前后关系”。盘子变空事件 → 放入水果事件。“盘子变空事件”既可由儿子引发，也可由女儿引发；“放水果事件”既可能是父亲执行，也可能是母亲执行。这样的话，就可以用一个同步信号量解决问题了。

三、吸烟者问题

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

1、关系分析

• 桌子可以抽象为容量为 1 的缓冲区，要互斥访问。
• 把资源分为三种：
  • 组合一：纸+胶水；
  • 组合二：烟草+胶水；
  • 组合三：烟草+纸。
• 同步关系（从事件角度来分析）：
  • 桌上有组合一 → 第一个抽烟者取走东西；
  • 桌上有组合二 → 第二个抽烟者取走东西；
  • 桌上有组合三 → 第三个抽烟者取走东西；
  • 发出完成信号 → 供应者将下一个组合放到桌上。

2、实现过程

  若一个生产者要生产多种产品（或者说会引发多种前驱事件），那么各个 V 操作应该放在各自对应的“事件”发生之后的位置。吸烟者问题可以为我们解决“可以生产多个产品的单生产者”问题提供一个思路。值得吸取的精华是：“轮流让各个吸烟者吸烟”必然需要“轮流的在桌上放上组合一、二、三”，而使用一个变量 i 就可以实现这个“轮流”过程。

四、读者-写者问题

  有读者和写者两组并发进程，共享一个文件，当两个或两个以上的读进程同时访问共享数据时不会产生副作用，但若某个写进程和其他进程（读进程或写进程）同时访问共享数据时，则可能导致数据不一致的错误。因此要求：

• 读者：允许多个读者可以同时对文件执行读操作；
  • 与消费者进程不同，读者进程在读数据后并不会将数据清空，并不会改变数据。因此多个读者可同时访问共享数据。
• 写者：只允许一个写者往文件中写信息，任一写者在完成写操作之前不允许其他读者或写者工作，写者执行写操作前，应让已有的读者和写者全部退出；
  • 两个写进程同时共享数据，可能导致数据错误覆盖的问题；
  • 读进程与写进程同时共享数据，可能导致读出的数据不一致的问题。

1、PV 分析

• 两类进程：写进程、读进程；
• 互斥关系：写进程 → 写进程、写进程 → 读进程。读进程之间不存在互斥问题。

2、如何实现

（1）读进程优先

  以下的实现方法虽然能实现题目要求，但是如果读进程不断的话，写进程可能“饿死”（即：读优先）。

（2）读写公平法（写优先）

  再设置一个互斥资源来实现写优先。

  读者-写者问题为我们解决复杂的互斥问题提供了一个参考思路。其核心思想在于设置了一个计数器 count 用来记录当前正在访问共享文件的读进程数。我们可以用 count 的值来判断当前进入的进程是否是第一个/最后一个读进程，从而做出不同的处理。另外，对 count 变量的检查和赋值不能一气呵成导致了一些错误，如果需要实现“一气呵成”，自然应该想到用互斥信号量。最后，还要认真体会第一种“写进程饥饿”的问题。

五、哲学家

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

1、关系分析

  系统中有 5 个哲学家进程，5位哲学家与左右邻居对其中间筷子的访问是互斥关系。这个问题中只有互斥关系，但与之前遇到的问题不同的是，每个哲学家进程需要同时持有两个临界资源才能开始吃饭。如何避免临界资源分配不当造成的死锁现象，是哲学家问题的精髓。

2、如何实现

  信号量设置。定义互斥信号量数组 chopstick[5]={1,1,1,1,1} 用于实现对 5 个筷子的互斥访问。并对哲学家按 0~4 编号，哲学家 i 左边 的筷子编号为 i，右边的筷子编号为 (i+1)%5。

（1）发生死锁

  每个哲学家吃饭前依次拿起左、右两支筷子。如果5个哲学家并发地拿起了自己左手边的筷子…每位哲学家循环等待右边的人放下筷子（阻塞），发生“死锁”。

（2）防止发生死锁

  哲学家进餐问题的关键在于解决进程死锁。这些进程之间只存在互斥关系，但是与之前接触到的互斥关系不同的是，每个进程都需要同时持有两个临界资源，因此就有“死锁”问题的隐患。

方法一：

  可以对哲学家进程施加一些限制条件，比如最多允许四个哲学家同时进餐。这样可以保证至少有一个哲学家是可以拿到左右两只筷子的。

方法二：

  要求奇数号哲学家先拿左边的筷子，然后再拿右边的筷子，而偶数号哲学家刚好相反。用这种方法可以保证，如果相邻的两个奇偶号哲学家都想吃饭，那么只会有其中一个可以拿起第一只筷子，另一个会直接阻塞。这就避免了占有一支后再等待另一只的情况。

方法三：

  仅当一个哲学家左右两支筷子都可用时才允许他抓起筷子。各哲学家拿筷子这件事必须互斥的执行。这就保证了即使一个哲学家在拿筷子拿到一半时被阻塞，也不会有别的哲学家会继续尝试拿筷子。这样的话，当前正在吃饭的哲学家放下筷子后，被阻塞的哲学家就可以获得等待的筷子了。具体实现如下：

六、管程

1、为什么要引入管程ؑ

  信号量机制存在的问题：编写程序困难、易出错。1973年，Brinch Hansen首次在程序设计语言（Pascal）中引入了“管程”成分——一种高级同步机制。让程序员写程序时不需要再关注复杂的 PV 操作，让写代码更轻松。

2、管程的定义和基本特征

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

• 局部于管程的共享数据结构说明；
• 对该数据结构进行操作的一组过程（函数，方法）;
• 对局部于管程的共享数据设置初始值的语句；
• 管程有一个名字。

  管程的基本特征：

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

3、用管程解决生产者消费者问题

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

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

  程序员可以用某种特殊的语法定义一个管程，之后其他程序员就可以使用这个管程提供的特定“入口”很方便地使用实现进程同步/互斥了。例如：

4、Java 中类似于管程的机制

  Java 中，如果用关键字 synchronized 来描述一个函数，那么这个函数同一时间段内只能被一个线程调用。

5、总结