|
|
|
对于本知识点的考查，重点在于理解信号量与P、V操作的基本概念，能够正确地理解在互斥、同步方面的控制应用，并能够灵活地运用，相对来说是个难点。
|
|
|
|
在操作系统中，进程之间经常会存在互斥（都需要共享独占性资源时）和同步（完成异步的两个进程的协作）两种关系。为了有效地处理这两种情况，W.Dijkstra在1965年提出信号量和P、V操作。
|
|
|
|
（1）信号量：是一种特殊的变量，表现形式是一个整型S和一个队列。
|
|
|
|
（2）P操作：S=S-1，若S<0，进程暂停执行，进入等待队列。
|
|
|
|
（3）V操作：S=S+1，若S≤0，唤醒等待队列中的一个进程。
|
|
|
|
|
|
互斥控制是为了保护共享资源，不让多个进程同时访问这个共享资源，换句话说，就是阻止多个进程同时进入访问这些资源的代码段，这个代码段称为临界区，而这种一次只允许一个进程访问的资源称为临界资源。为了实现进程互斥地进入自己的临界区，代码可以如下所示：
|
|
|
|
|
|
由于只允许一个进程进入，因此信号量S的初值应该为1。该值表示可以允许多少个进程进入，当S<0时，其绝对值就是等待使用临界资源的进程数，也就是等待队列中的进程数。而当一个进程从临界区出来时，执行V操作（S=S+1），如果等待队列中还有进程（S≤0），则调入一个新的进程进入（唤醒）。
|
|
|
|
|
|
最简单的同步形式是进程A在另一个进程B到达L2以前，不应前进到超过点L1，这样就可以使用如下程序：
|
|
|
|
|
|
因此，要确保进程B执行V操作之前，不让进程A的运行超过L1，就要设置信号量S的初值为0。这样，如果进程A先执行到L1，那么执行P操作（S=S-1）后，则S<0，就停止执行。直到进程B执行到L2时，将执行V操作（S=S+1），唤醒A以继续执行。
|
|
|
|
|
|
生产者－消费者是一个经典的问题，它不仅要解决生产者进程与消费者进程的同步关系，还要处理缓冲区的互斥关系，因此通常需要3个信号量来实现，如下表所示。
|
|
|
|
|
|
|
|
如果对缓冲区的读写无须进行互斥控制的话，那么就可以省去mutex信号量。
|
|
|
|
|
|
信号量与P、V操作的概念比较抽象，在历年的考试中总是难倒许多考生，其实主要还是没有能够正确地理解信号量的含义。
|
|
|
|
（1）信号量与P、V操作是用来解决并发问题的，而在并发问题中最重要的是互斥与同步两个关系，也就是说只要有这两个关系存在，信号量就有用武之地。因此，在解题时，应该先从寻找互斥与同步关系开始。这个过程可以套用简单互斥、简单同步、生产者－消费者问题。
|
|
|
|
（2）通常来说，一个互斥或一个同步关系可以使用一个信号量来解决，但要注意经常会忽略一些隐藏的同步关系。例如：在生产者－消费者问题中，就有两个同步关系，一个是判断是否还有足够的空间给生产者存放产物，另一个是判断是否有足够的内容让消费者使用。
|
|
|
|
（3）信号量的初值通常就是表示资源的可用数。而且通常对于初始为0的信号量，会先做V操作。
|
|
|
|
（4）在资源使用之前，将会使用P操作；在资源用完之后，将会使用V操作。在互斥关系中，P、V操作是在一个进程中成对出现的；而在同步关系中，则P、V操作一定是在两个进程甚至是多个进程中成对出现的。
|
|
|
|
|
|
在考试时，可能会出现一些需要综合应用的问题，需要考生根据基本的概念，结合实际问题进行解答。
|
|
|
|
例如：在某并发系统中，有一个发送进程A、一个接收进程B、一个环形缓冲区BUFFER、信号量S1和S2。发送进程不断地产生消息并写入缓冲区BUFFER，接收进程不断地从缓冲区BUFFER取消息。假设发送进程和接收进程可以并发地执行，那么，当缓冲区的容量为N时，如何使用P、V操作才能保证系统的正常工作。发送进程A和接收进程B的工作流程如下图所示。请在下图中的（1）～（4）处填写正确的操作。
|
|
|
|
|
|
|
|
根据题意，很显然，这是一个“生产者－消费者”问题，根据该问题的特性，通常需要3个信号量来实现：两个用来管理缓冲区同步，信号量empty表示空闲缓冲区数量，初值为缓冲区最大数N，信号量full表示已填充缓冲区数量，初值为0；一个用于管理互斥，由信号量mutex保证只有一个进程在写缓冲区，初值为1。但在本题中，进程A和进程B允许并发地访问缓冲区，因此无须管理互斥，就不需要使用信号量mutex了。因此只需定义两个信号量：S1和S2，初值为N的S1在此承担的是信号量empty的功能，初值为0的S2在此则承担的是信号量full的功能。
|
|
|
|
通过这样的分析，不难得出：（1）处应该是P（S1），将空闲缓冲区数量减1；（2）处应该是V（S2），将已填充的缓冲区数量加1；（3）处则是P（S2），（4）处为V（S1）。
|
|
|
|
在这个例子的基础上，如果系统中有多个发送进程和接收进程，进程间的工作流程如下图所示，其中空（1）～（4）的内容与上图相同。发送进程产生消息并顺序地写入环形缓冲区BUFFER，接收者进程顺序地从BUFFER中取消息，且每条消息只能读取一次。为了保证进程间的正确通信，增加了信息量SA和SB。请说明信息量SA和SB的物理意义，在下图中的（5）和（6）处填入正确的内容，并从下图的（a）～（l）中选择四个位置正确地插入P（SA），V（SA），P（SB），V（SB）。
|
|
|
|
下图所涉及的问题在普通的“生产者－消费者”问题上增加了一些复杂度：“系统中有多个发送进程和接收进程”，根据题意，我们可以得知它要完成的控制是：发送进程顺序写入，接收进程顺序读取，而且每条消息都只能够读取一次。这显然是两个互斥的问题，即多个发送进程在写缓冲区时是互斥关系，多个接收进程读缓冲区也是互斥关系。因此，信号量SA和SB分别实现这两个用来完成两个进程的互斥控制。
|
|
|
|
（1）SA：初值为1，表示允许同时对缓冲区进行写操作的进程数量。
|
|
|
|
（2）SB：初值为1，表示允许同时对缓冲区进行读操作的进程数量。
|
|
|
|
当然，两个对调也是可以的。在发送进程和接收进程中分别有一组信号量SA和SB的P、V操作。因此，接下来的问题就是找出插入点。互斥控制的要点在于判断出临界区的范围，也就是哪部分程序必须互斥进入，否则将出现问题。根据这一点，我们可以进行如下分析。
|
|
|
|
|
|
|
|
（1）发送进程：在进程产生消息之后准备写入缓冲区时，这时就需要进行互斥判断，因此在位置（b）应插入P（SA）；而直到完成“i=（i+1）modN”操作后，才完成缓冲区操作，因此必须在位置（f）插入V（SA）。
|
|
|
|
（2）接收进程：由于接收进程是负责读数据的，如果数据区是空的则应该等待，因此必须先完成P（S2）操作，来决定其是否需要阻塞。如果没有阻塞时，再进入临界区，因此应该在位置（h）处操作P（SB）；而“对读取的消息进行处理”已显然在临界区之外，因此应该在位置（k）插入V（SB）。
|
|
|
