操作系统第4章

1、第四章 进 程 通 信 1第四章第四章 进程通信进程通信 4.1 4.1 进程的同步与互斥进程的同步与互斥 4.2 4.2 进程间互斥控制方法进程间互斥控制方法 4.3 4.3 信号灯和信号灯和WaitWait、SignalSignal操作操作 4.4 4.4 信号灯的应用信号灯的应用 4.5 4.5 进程间的数据通信进程间的数据通信 4.6 4.6 软中断和信号机构软中断和信号机构 4.7 4.7 死锁死锁4.8 Linux4.8 Linux进程间通信进程间通信第四章 进 程 通 信 24.1 4.1 进程的同步与互斥进程的同步与互斥4.1 同步与互斥的概念同步与互斥的概念 两种形式的制约关

2、系两种形式的制约关系 间接制约：间接制约：进行竞争独占分配到的部分或进行竞争独占分配到的部分或全部共享资源，全部共享资源，“互斥互斥”.进程间要通过某种进程间要通过某种中介发生联系，是无意识安排的，可发生在中介发生联系，是无意识安排的，可发生在相交进程之间，也可发生在无关进程之间。相交进程之间，也可发生在无关进程之间。直接制约：直接制约：进行协作等待来自其他进程的进行协作等待来自其他进程的信息，信息，“同步同步”。进程间的相互联系是有意。进程间的相互联系是有意识的安排的，直接作用只发生在相交进程间识的安排的，直接作用只发生在相交进程间第四章 进 程 通 信 34.1.2 临界段问题临界段问题u

3、如前所述，互斥是由于进程竞争使用资源引起的。如前所述，互斥是由于进程竞争使用资源引起的。u有些硬件资源（如内存、显示器和硬盘）和软件有些硬件资源（如内存、显示器和硬盘）和软件资源（如共享程序段）允许多个进程并发地访问。资源（如共享程序段）允许多个进程并发地访问。u但另一些硬件设备（如打印机、磁带机、光盘刻但另一些硬件设备（如打印机、磁带机、光盘刻写机、绘图仪等）在一段时间内只允许一个进程写机、绘图仪等）在一段时间内只允许一个进程独占，只有当该进程使用完毕，释放该类设备后，独占，只有当该进程使用完毕，释放该类设备后，另一个进程才能使用，多个进程的交叉使用将使另一个进程才能使用，多个进程的交叉使用

4、将使输出结果变得毫无意义。输出结果变得毫无意义。第四章 进 程 通 信 44.1.2 临界段问题临界段问题u这种在一段时间内只能允许一个进程访问的资源这种在一段时间内只能允许一个进程访问的资源称为称为临界资源临界资源。u除了物理设备外，由若干进程共享访问的变量、除了物理设备外，由若干进程共享访问的变量、数据、数据结构等数据、数据结构等“无形无形”的软件资源，也可以的软件资源，也可以是临界资源。是临界资源。u进程执行的进程执行的访问临界资源的程序段访问临界资源的程序段称为称为临界段临界段或或互斥段互斥段。第四章 进 程 通 信 5u例如，考虑一个统计两个进程例如，考虑一个统计两个进程 P1和和P

5、2对共享变对共享变量量count访问计数的程序段，它们的有关代码表访问计数的程序段，它们的有关代码表示如下：示如下：uP1： R1=count P2： R2=count R1=R1+1 R2=R2+1 count=R1 count=R2u由于在系统中随时可能发生中断，中断处理任由于在系统中随时可能发生中断，中断处理任务完成后，系统可以重新进行进程调度，因此，务完成后，系统可以重新进行进程调度，因此，如下所示是这两个进程可能的相对执行次序：如下所示是这两个进程可能的相对执行次序：第四章 进 程 通 信 6P1： R1=count R1=R1+1P2： R2=count R2=R2+1 count

6、=R2P1： count=R1u虽然虽然P1和和P2进程各自都执行了对进程各自都执行了对count加加1的操的操作段，但结果作段，但结果count只增加只增加1，这不符合对，这不符合对 count 的访问计数结果。因此，变量的访问计数结果。因此，变量 count 就是临界资就是临界资源，源，P1、P2 访问访问 count 的两个程序段就是临界的两个程序段就是临界段，诸进程必须互斥地进入临界段。段，诸进程必须互斥地进入临界段。第四章 进 程 通 信 7不加控制的并发执行所带来的影响不加控制的并发执行所带来的影响u例：为了了解某单行道的交通流量，在路口安放一个监视器，例：为了了解某单行道的交通流

7、量，在路口安放一个监视器，功能是有车通过该路段时，就向计算机发送一个信号。程序功能是有车通过该路段时，就向计算机发送一个信号。程序A功能：接收到监视器信号时，就在计数单元功能：接收到监视器信号时，就在计数单元COUNT上加上加1；程序程序B功能：每个半个小时，打印功能：每个半个小时，打印COUNT的值，然后清零。的值，然后清零。程序程序A：While(1)A1:收到监视器信号；收到监视器信号；A2:COUNT=COUNT+1;程序程序B：While(1)B1:延迟半小时；延迟半小时；B2:打印打印COUNT的值的值;B3:COUNT=0;A1A2B1B2A1A2B3第四章 进 程 通 信 8互

8、斥的概念互斥的概念u互斥互斥：与一个共享变量（或临界资源）交往的：与一个共享变量（或临界资源）交往的多个进程，为了保证它们各自运行结果的正确多个进程，为了保证它们各自运行结果的正确性，当其中的一个进程正在对该变量（或临界性，当其中的一个进程正在对该变量（或临界资源）进行操作时，就不允许其他进程同时对资源）进行操作时，就不允许其他进程同时对它进行操作。它进行操作。进程间的这种制约关系被称为进程间的这种制约关系被称为“互斥互斥”。第四章 进 程 通 信 9对具有互斥关系的进程，要注意以下四点对具有互斥关系的进程，要注意以下四点（1）做为互斥关系的进程，它的一部分可能用于内做为互斥关系的进程，它的一

9、部分可能用于内部的计算，用于内部的数据处理等。只有涉及到部的计算，用于内部的数据处理等。只有涉及到共享变量的那一部分程序，才真正需要保证互斥共享变量的那一部分程序，才真正需要保证互斥的执行。通常，把进程程序中的执行。通常，把进程程序中“真正需要保证互真正需要保证互斥执行斥执行”的那一段程序，称为该进程的的那一段程序，称为该进程的“临界区临界区（或临界段）（或临界段）”。进入区进入区(entry section)：在进入临界区之前，检查：在进入临界区之前，检查可否进入临界区的一段代码。如果可以进入临界可否进入临界区的一段代码。如果可以进入临界区，通常设置相应区，通常设置相应“正在访问临界区正在访

10、问临界区”标志。标志。退出区退出区(exit section)：用于将：用于将正在访问临界区正在访问临界区标标志清除。志清除。第四章 进 程 通 信 10临界区临界区(critical section) 可把一个访问临界资源的循环进程描述如下：可把一个访问临界资源的循环进程描述如下：repeat critical section; remainder section;until false; entry sectionexit section第四章 进 程 通 信 11（2）具有互斥关系的进程，并不关心对方的存在具有互斥关系的进程，并不关心对方的存在性。即使对方不存在，自己也能正确运行，不会性

11、。即使对方不存在，自己也能正确运行，不会受到它存在与否的影响。受到它存在与否的影响。（3）具有互斥关系进程的临界区，虽然都是针对具有互斥关系进程的临界区，虽然都是针对同一个共享变量的程序段，但在其上的操作可以同一个共享变量的程序段，但在其上的操作可以相同也可以不同。相同也可以不同。（4）进程的临界区是相对于某个共享变量而言的，进程的临界区是相对于某个共享变量而言的，不同共享变量的临界区之间，不存在互斥关系。不同共享变量的临界区之间，不存在互斥关系。下面，只要谈到临界区，一定是指相对于同一个下面，只要谈到临界区，一定是指相对于同一个共享变量的。共享变量的。第四章 进 程 通 信 122.临界段的

12、调度原则临界段的调度原则u能支持各进程互斥地执行临界段的调度机制必须满能支持各进程互斥地执行临界段的调度机制必须满足下列要求。足下列要求。u 在所有共享相同资源或对象的临界段中，每次只在所有共享相同资源或对象的临界段中，每次只能允许一个进程进入。能允许一个进程进入。u 一个进程在非临界段中的暂停运行不能影响其他一个进程在非临界段中的暂停运行不能影响其他进程。进程。u 一个进程如需要进入临界段，不能发生无限延迟一个进程如需要进入临界段，不能发生无限延迟的情况，即既不会死锁，也不会饥饿。的情况，即既不会死锁，也不会饥饿。第四章 进 程 通 信 132.临界段的调度原则临界段的调度原则u 当无进程在

13、临界段时，必须让任何希望进入该程当无进程在临界段时，必须让任何希望进入该程序段的进程无延迟地进入。序段的进程无延迟地进入。u 一个进程只能在临界段内停留有限的时间。一个进程只能在临界段内停留有限的时间。u 对于相关进程的运行速度和处理机的数量不做假对于相关进程的运行速度和处理机的数量不做假设设第四章 进 程 通 信 14CobeginCobegin get; get; copy; copy; put; put;CoendCoendgetcopyputfRTg协同工作同步（直接作用）协同工作同步（直接作用）源记录源记录目标记录目标记录第四章 进 程 通 信 15协同工作同步（直接作用）协同工作同

14、步（直接作用）u只有只有GET先于先于COPY工作，工作，COPY的工作才有的工作才有意义；只有意义；只有COPY取走了取走了R中的内容，中的内容，GET进进入下一步工作才有意义。入下一步工作才有意义。COPY与与PUT之间也之间也有这种类似的关系，这时进程之间由于协同工有这种类似的关系，这时进程之间由于协同工作而产生的一种直接关系。作而产生的一种直接关系。第四章 进 程 通 信 16GETGET和和COPYCOPY协调一致的工作协调一致的工作从文件从文件F取出一个记取出一个记录送到输入缓冲区录送到输入缓冲区R向向COPY发送发送“可以可以拷贝拷贝”的消息的消息等待等待COPY发来的发来的“拷

15、贝结束拷贝结束”的消的消息息等待等待GET发来发来“可可以拷贝以拷贝”的消息的消息将输入缓冲区将输入缓冲区R里的记录里的记录拷贝到输出缓冲区拷贝到输出缓冲区T里里向向GET发送发送“拷贝拷贝结束结束”的信息的信息第四章 进 程 通 信 17同步的概念同步的概念进程的同步：进程的同步：synchronismu指系统中一些进程需要相互合作，共同完成一指系统中一些进程需要相互合作，共同完成一项任务。项任务。u具体说，一个进程运行到某一点时要求另一个具体说，一个进程运行到某一点时要求另一个进程为它提供消息，在未获得消息之前，该进进程为它提供消息，在未获得消息之前，该进程处于等待状态，获得消息后被唤醒进

16、入就绪程处于等待状态，获得消息后被唤醒进入就绪态态第四章 进 程 通 信 18特点特点（1）具有这种关系的进程，需要在某些点上协具有这种关系的进程，需要在某些点上协调相互的动作，谁先到谁后到达是有先后顺序调相互的动作，谁先到谁后到达是有先后顺序要求的。要求的。（2）这些进程都应该了解对方的工作，对方不这些进程都应该了解对方的工作，对方不存在，或任何一方单独运行，就会出现差错。存在，或任何一方单独运行，就会出现差错。（3）一方或双方的运行会直接地依赖于对方所一方或双方的运行会直接地依赖于对方所产生地信息或发出地消息。产生地信息或发出地消息。第四章 进 程 通 信 19同步与同步点、同步条件同步与

17、同步点、同步条件u一个进程运行到了某一点时，除非合作进程已一个进程运行到了某一点时，除非合作进程已经完成了某种操作或发来了信息，否则就必须经完成了某种操作或发来了信息，否则就必须暂时等待那些操作的完成或信息的到来。进程暂时等待那些操作的完成或信息的到来。进程间的这种关系被称为间的这种关系被称为“同步同步”；u暂停等待以取得同步的那一点，称为暂停等待以取得同步的那一点，称为“同步同步点点”；u需要等待一个进程完成的操作或发送的消息，需要等待一个进程完成的操作或发送的消息，称为称为“同步条件同步条件”。第四章 进 程 通 信 204.2 4.2 进程间互斥控制方法进程间互斥控制方法4.2.1 锁的

18、表示和操作锁的表示和操作u锁可以用于控制临界段的互斥执行。锁可以用于控制临界段的互斥执行。u锁有两个状态：一个是打开状态；另一个是关锁有两个状态：一个是打开状态；另一个是关闭状态。故锁可以用布尔变量表示。闭状态。故锁可以用布尔变量表示。u在在C语言中，锁变量可以定义为语言中，锁变量可以定义为char 或或int类型类型变量。设变量。设x为锁变量，则定义：为锁变量，则定义：x0 锁的打开状态锁的打开状态1 锁的关闭状态锁的关闭状态第四章 进 程 通 信 21u用对锁变量用对锁变量x 的访问，可以控制临界段的执行。的访问，可以控制临界段的执行。u设设x 的初值为的初值为 0，即锁处于打开状态。，即

19、锁处于打开状态。u当一个进程希望进入临界段时，首先要测试一下锁当一个进程希望进入临界段时，首先要测试一下锁的状态。如锁是打开的，表示无进程处于临界段，的状态。如锁是打开的，表示无进程处于临界段，那么它可以关闭该锁，并进入临界段；那么它可以关闭该锁，并进入临界段；u当该进程处于临界段时，其他试图进入临界段的进当该进程处于临界段时，其他试图进入临界段的进程由于在测试锁的状态时发现它处于关闭状态，就程由于在测试锁的状态时发现它处于关闭状态，就只能在临界段外等待。只能在临界段外等待。u当原先进入临界段的进程执行完有关临界资源的操当原先进入临界段的进程执行完有关临界资源的操作，退出了临界段，并将锁打开后

20、，才允许那些在作，退出了临界段，并将锁打开后，才允许那些在临界段外等待的进程中的一个进入。临界段外等待的进程中的一个进入。第四章 进 程 通 信 22第四章 进 程 通 信 234.2.2 锁的安全控制锁的安全控制u锁的关闭操作锁的关闭操作LOCK包含测试和关闭两个操作包含测试和关闭两个操作步骤，这两个操作步骤涉及临界资源步骤，这两个操作步骤涉及临界资源x，故这，故这段程序也是段程序也是临界段临界段。u假定锁是打开的，当一个进程假定锁是打开的，当一个进程 P1 在在测试锁测试锁的的状态后，还没来得及关闭它的一瞬间，发生了状态后，还没来得及关闭它的一瞬间，发生了中断，中断返回时，系统可能调度另一

21、个进程中断，中断返回时，系统可能调度另一个进程P2执行。执行。第四章 进 程 通 信 244.2.2 锁的安全控制锁的安全控制uP2执行时也对该锁的状态进行测试，发觉它处执行时也对该锁的状态进行测试，发觉它处于打开状态，于是于打开状态，于是关闭该锁关闭该锁，并进入临界段。，并进入临界段。u在在 P1 被重新调度时，继续执行原先测试锁的被重新调度时，继续执行原先测试锁的状态的后续操作，状态的后续操作，关闭该锁，进入临界段关闭该锁，进入临界段。u假如此时假如此时P2还未退出临界段，那么两个进程就还未退出临界段，那么两个进程就同时处于一个临界段之中，这就破坏了临界段同时处于一个临界段之中，这就破坏了

22、临界段的执行原则，也就是说对临界段的互斥控制的执行原则，也就是说对临界段的互斥控制失失败败了。了。第四章 进 程 通 信 251. 测试并设置指令测试并设置指令test&setu有些计算机提供专门的锁操作指令有些计算机提供专门的锁操作指令test&set;u该指令首先测试锁变量的值，如为该指令首先测试锁变量的值，如为1，则重复，则重复执行本指令；执行本指令；u如为如为0，则立即将锁变量的值置为，则立即将锁变量的值置为1。u由于由于test&set是一条完整的指令，而在一条指是一条完整的指令，而在一条指令的执行中间是不会被中断的，故保证了锁的令的执行中间是不会被中断的，故

23、保证了锁的测试和关闭操作的连续性。测试和关闭操作的连续性。第四章 进 程 通 信 262.交换指令交换指令exchangeu有的计算机提供交换指令，即先将测试单元置为有的计算机提供交换指令，即先将测试单元置为 1，然后在一条指令中将测试单元和锁变量单元的值然后在一条指令中将测试单元和锁变量单元的值进行交换；进行交换；u接下来就对存有锁变量值的测试单元进行测试，接下来就对存有锁变量值的测试单元进行测试，如如值为值为0，证明锁的原先状态是打开的，由于在，证明锁的原先状态是打开的，由于在exchange指令中已将预置为指令中已将预置为1的值更改了锁变量，的值更改了锁变量，使锁处于关闭状态，故进程就可

24、以直接进入临界使锁处于关闭状态，故进程就可以直接进入临界段；段；u如测试如测试值为值为 1，说明锁的原先状态是关闭的，进程，说明锁的原先状态是关闭的，进程就不能进入临界区，只能继续测试，等待锁状态就不能进入临界区，只能继续测试，等待锁状态的改变。注意，在这种情况下，交换指令并没有的改变。注意，在这种情况下，交换指令并没有改变锁的状态。改变锁的状态。第四章 进 程 通 信 273.开关中断法开关中断法u用硬件锁，即用开、关中断的方用硬件锁，即用开、关中断的方法可实现锁操作。法可实现锁操作。u由于进程都是在关闭中断后才进由于进程都是在关闭中断后才进入临界段的，因此，当一个进程入临界段的，因此，当一

25、个进程处于临界段时，只要它不会有自处于临界段时，只要它不会有自行挂起的操作，就会连续地执行行挂起的操作，就会连续地执行下去，直至退出临界段，并在执下去，直至退出临界段，并在执行了开放中断的指令后，才有可行了开放中断的指令后，才有可能发生重新调度的情况，允许其能发生重新调度的情况，允许其他进程进入临界段。他进程进入临界段。第四章 进 程 通 信 28缺点：缺点：u 这种方法只能用于单这种方法只能用于单CPU系统。系统。u 如果临界段操作比较复杂，执行时间较长，那如果临界段操作比较复杂，执行时间较长，那么长时间地关闭中断会降低系统对外部中断响应么长时间地关闭中断会降低系统对外部中断响应的速度，影响

26、系统处理紧迫事件的能力。的速度，影响系统处理紧迫事件的能力。u 一个运行系统可以有很多的临界段，应当允许一个运行系统可以有很多的临界段，应当允许多个进程进入不同的临界段并发地运行。采用开、多个进程进入不同的临界段并发地运行。采用开、关中断的硬件锁方法禁止了其他无关的进程进入关中断的硬件锁方法禁止了其他无关的进程进入不同的临界段，这种做法显然伤害了很多的不同的临界段，这种做法显然伤害了很多的“无无辜者辜者”第四章 进 程 通 信 294.用硬件锁锁软件锁，用软件锁锁临界段用硬件锁锁软件锁，用软件锁锁临界段u由于软件锁的由于软件锁的LOCK操作包含测试操作包含测试和关闭两个操作步骤，它本身也是和关

27、闭两个操作步骤，它本身也是一种临界段，故可以用硬件锁一种临界段，故可以用硬件锁开、关中断保证软件锁操作的完整开、关中断保证软件锁操作的完整性。性。u由于软件锁是一种程序长度最短的由于软件锁是一种程序长度最短的临界段，故用开、关中断的方法保临界段，故用开、关中断的方法保证锁操作的完整性几乎不会影响到证锁操作的完整性几乎不会影响到系统响应其他的中断请求。系统响应其他的中断请求。u用软件锁保证临界段执行的独占性，用软件锁保证临界段执行的独占性，也不会影响到其他无关进程进入不也不会影响到其他无关进程进入不同的临界段，故在单同的临界段，故在单CPU的系统中，的系统中，这是一种安全而高效的锁。这是一种安全

28、而高效的锁。第四章 进 程 通 信 304.3 4.3 信号灯和信号灯和WaitWait、SignalSignal操作操作u但前面对锁操作的定义也有如下严重的缺点。但前面对锁操作的定义也有如下严重的缺点。u 对于不能立即进入临界段的进程，需循环对于不能立即进入临界段的进程，需循环“忙等忙等”，不断地测试锁的状态（故称为不断地测试锁的状态（故称为“自旋锁自旋锁”），以等待它），以等待它打开，这就浪费了大量的处理机时间。打开，这就浪费了大量的处理机时间。u 可能发生饥饿现象可能发生饥饿现象。当一个进程离开临界段时，总是。当一个进程离开临界段时，总是有多个进程在等待进入临界段，如操作系统对等待进入有

29、多个进程在等待进入临界段，如操作系统对等待进入同一临界段的进程的选择是任意的，那么某些进程可能同一临界段的进程的选择是任意的，那么某些进程可能长时间的排斥在临界段外。长时间的排斥在临界段外。u 可能发生可能发生死锁死锁的情况。的情况。第四章 进 程 通 信 31同步机制应遵循的规则同步机制应遵循的规则 (1) 空闲让进空闲让进。当无进程处于自己的临界区时，表明临界资。当无进程处于自己的临界区时，表明临界资源处于空闲状态，应允许一个请求进入临界区的进程立源处于空闲状态，应允许一个请求进入临界区的进程立即进入自己的临界区。即进入自己的临界区。(2) 忙则等待忙则等待。 当已有进程进入临界区时，表明

30、临界资源当已有进程进入临界区时，表明临界资源正在被访问，因而其它试图进入临界区的进程必须等待，正在被访问，因而其它试图进入临界区的进程必须等待，以保证对临界资源的互斥访问。以保证对临界资源的互斥访问。(3) 有限等待有限等待。 对要求访问临界资源的进程，应保证在有对要求访问临界资源的进程，应保证在有限时间内能进入自己的临界区，以免陷入限时间内能进入自己的临界区，以免陷入“死等死等”状态。状态。(4) 让权等待让权等待。当进程不能进入自己的临界区时，应立即释。当进程不能进入自己的临界区时，应立即释放处理机，以免进程陷入放处理机，以免进程陷入“忙等忙等”。 第四章 进 程 通 信 32u将信号灯定

31、义成具有整型值，并能对其施加以下将信号灯定义成具有整型值，并能对其施加以下3种操种操作的变量，除了这作的变量，除了这3种操作之外的任何操作都不能测试种操作之外的任何操作都不能测试和处理信号灯的值。和处理信号灯的值。u 初始化操作初始化操作，信号灯能初始化为非负的值。，信号灯能初始化为非负的值。u Wait操作操作，能减小信号灯的值，如结果值为负，执行，能减小信号灯的值，如结果值为负，执行Wait操作的进程就被封锁。操作的进程就被封锁。u Signal 操作操作，能增加信号灯的值，如果结果值非正，能增加信号灯的值，如果结果值非正，那么原先因执行那么原先因执行 Wait 操作而阻塞的进程被解除阻塞

32、操作而阻塞的进程被解除阻塞信号灯信号灯第四章 进 程 通 信 33它所包含的上述两个数据项可描述为：它所包含的上述两个数据项可描述为： typedef struct semaphore int value; Queue queue; Semaphore;Semaphore s;第四章 进 程 通 信 34（1）信号量）信号量S上的上的Wait操作定义操作定义。 当一个进程调用当一个进程调用Wait （S）时，应该顺序时，应该顺序做下面不可分割的两个动作。做下面不可分割的两个动作。us.values.value1，即把当前信号量，即把当前信号量S的取值的取值减减1。u若若s.value =0，则

33、调度进程继续运行；，则调度进程继续运行；u若若s.value 0，则调用由运行状态变为阻塞状态，则调用由运行状态变为阻塞状态，到与该信号量有关的队列到与该信号量有关的队列s.queue上排队等候，上排队等候，直到其它进程在直到其它进程在S上执行上执行Signal操作将其释放为操作将其释放为止。止。第四章 进 程 通 信 35void Wait(s)semaphore s ；if ( -s.value 0，则调度进程继续运行；，则调度进程继续运行；u若若s.value 0，则先从与该信号量有关的队列，则先从与该信号量有关的队列s.queue上摘下一个等待进程，让它从阻塞状态上摘下一个等待进程，让

34、它从阻塞状态变为就绪状态，到就绪队列里排队，然后调用变为就绪状态，到就绪队列里排队，然后调用进程继续运行。进程继续运行。第四章 进 程 通 信 37void Signal(s)Semaphores；if ( +s.value = 0 ) 从等待队列从等待队列queue中移出一进程；中移出一进程；将该进程置入就绪队列中；将该进程置入就绪队列中；第四章 进 程 通 信 38说明说明1)设置的信号量初值，一定是一个非负数。设置的信号量初值，一定是一个非负数。2)定义在信号量上的定义在信号量上的Wait操作和操作和Signal操作，都由两操作，都由两个不可分割的动作组成，也就是说，只有进入了个不可分割

35、的动作组成，也就是说，只有进入了Wait （S）或）或Signal （S），这两个动作就必须顺），这两个动作就必须顺序地做完，中间不能被打断。序地做完，中间不能被打断。3)从从Wait （S）的定义可以看出，调用它地进程有）的定义可以看出，调用它地进程有两个出路。但时从两个出路。但时从Signal （S）的定义可以看出，）的定义可以看出，调用它的进程的状态不会改变。调用它的进程的状态不会改变。4)注意，如果一个进程在做注意，如果一个进程在做Wait操作后被阻塞，到操作后被阻塞，到有关信号量的队列上去排队等候，其含义是将进有关信号量的队列上去排队等候，其含义是将进程的程的PCB到此队列上排队。到

36、此队列上排队。第四章 进 程 通 信 394.4 4.4 信号灯的应用信号灯的应用u为临界资源设置一个为临界资源设置一个互斥信号量互斥信号量S，其，其初值为初值为1；在每个进程中将在每个进程中将临界区临界区代码置于代码置于Wait(S)和和Signal(S)原语之间原语之间u必须必须成对使用成对使用Wait和和Signal原语：遗漏原语：遗漏Wait原语则原语则不能保证互斥访问，遗漏不能保证互斥访问，遗漏Signal原语则不能在使用原语则不能在使用临界资源之后将其释放（给其他等待的进程）；临界资源之后将其释放（给其他等待的进程）；Wait、Signal原语原语不能次序错误、重复或遗漏不能次序错

37、误、重复或遗漏4.4.1 利用信号灯实现互斥利用信号灯实现互斥第四章 进 程 通 信 40利用信号量实现互斥利用信号量实现互斥signal(s);critical section 临界区临界区remainder sectionwait(s);第四章 进 程 通 信 41第四章 进 程 通 信 42分析分析在这种安排下，哪个进程先对信号量在这种安排下，哪个进程先对信号量s做做wait操作，操作，就会使就会使s的值由的值由1变为变为0，且它就获得了进入临界区，且它就获得了进入临界区的权利。的权利。当有一个进程在临界区内时，当有一个进程在临界区内时，s的值肯定是的值肯定是0。因此，。因此，此时另一个

38、进程想通过做此时另一个进程想通过做wait操作进入自己的临界操作进入自己的临界区时，就会因为使区时，就会因为使s的值由的值由0变为变为1而受阻。而受阻。只有等到在临界区内的那个进程退出临界区、对只有等到在临界区内的那个进程退出临界区、对s做做signal操作时，使操作时，使s的值由的值由1变为变为0，才会解除阻，才会解除阻挡，以此来保证进程间的互斥。挡，以此来保证进程间的互斥。第四章 进 程 通 信 43u如有两个并发进程涉及一个临界段，则信号灯如有两个并发进程涉及一个临界段，则信号灯的所有可能取值及意义为：的所有可能取值及意义为：us=1 无进程进入临界段无进程进入临界段us=0 有一进程进

39、入临界段有一进程进入临界段us=-1 有一进程进入临界段，另一进程被阻塞有一进程进入临界段，另一进程被阻塞u如有如有n个并发进程涉及一个临界段，则上式最个并发进程涉及一个临界段，则上式最后一行后一行s的取值为的取值为i，-(n-1)= i=-1，表示当前，表示当前有有|i|个进程被阻塞个进程被阻塞第四章 进 程 通 信 44互斥举例：互斥举例：“观察者报告者观察者报告者”的例子的例子程序程序A：While(1)A1:收到监视器信号；收到监视器信号；A2:COUNT=COUNT+1;程序程序B：While(1)B1:延迟半小时；延迟半小时；B2:打印打印COUNT的值的值;B3:COUNT=0;

40、第四章 进 程 通 信 45互斥举例：互斥举例：“观察者报告者观察者报告者”的例子的例子程序程序A：While(1)A1:收到监视器信号；收到监视器信号；wait(mutex);A2:COUNT=COUNT+1;signal(mutex);程序程序B：While(1)B1:延迟半小时延迟半小时;wait(mutex) ;B2:打印打印COUNT的值的值;B3:COUNT=0;signal(mutex);第四章 进 程 通 信 464.4.2 阻塞阻塞/唤醒协议唤醒协议 u进程是并发异步地运行的，但为了成功地协同工作，进程是并发异步地运行的，但为了成功地协同工作，有关进程必须在某些确定点上同步它

41、们的活动。信有关进程必须在某些确定点上同步它们的活动。信号灯不仅能作为进程间互斥的工具，也能作为进程号灯不仅能作为进程间互斥的工具，也能作为进程间同步的工具。间同步的工具。u阻塞阻塞唤醒协议可以用对某一信号灯的唤醒协议可以用对某一信号灯的Wait、Signal操作来控制两个进程的执行顺序。操作来控制两个进程的执行顺序。u当进程需要等待相关的协同进程完成某个协作任务当进程需要等待相关的协同进程完成某个协作任务时，就可以对时，就可以对初值为初值为 0 的信号灯的信号灯 s 执行执行Wait 操作，操作，以使自己在此点上阻塞。以使自己在此点上阻塞。u当协同进程完成了协作任务时，应执行当协同进程完成了

42、协作任务时，应执行 Signal 操作，操作，以使等待进程可以继续运行下去。以使等待进程可以继续运行下去。第四章 进 程 通 信 47u进程进程A、B协调完成任务协调完成任务第四章 进 程 通 信 48u为达到同步，设置一个为达到同步，设置一个初值为初值为0的信号量的信号量S，在进程，在进程A的的X点处（即同步点），安排一个关于信号量点处（即同步点），安排一个关于信号量S的的Wait操作，在进程操作，在进程B的的Y点处安排关于信号量的点处安排关于信号量的Signal操作。这样，就能够确保进程操作。这样，就能够确保进程A在在X点处与进点处与进程程B取得同步了。取得同步了。第四章 进 程 通 信

43、49第四章 进 程 通 信 50u从图中可以看出，当进程从图中可以看出，当进程a执行到执行到L1点时，如点时，如进程进程b还未执行到还未执行到L2点，也即点，也即func2函数的计算函数的计算还未完成，进程还未完成，进程a就要同步等待进程就要同步等待进程b，而进程，而进程b则不必同步等待进程则不必同步等待进程a。u这种同步是非对称的，或可以称为这种同步是非对称的，或可以称为“半同步半同步”。第四章 进 程 通 信 514.4.3 两个进程间的同步两个进程间的同步1一个全同步的例子一个全同步的例子u设有两个进程设有两个进程 Pa和和 Pb；u进程进程 Pa每次执行一个计算，并每次执行一个计算，并

44、将结果存入一将结果存入一个缓冲区个缓冲区；u进程进程 Pb则则从缓冲区中取出结果从缓冲区中取出结果，并将结果打，并将结果打印出来。印出来。u需要设置两个信号灯需要设置两个信号灯S1和和S2。第四章 进 程 通 信 52computingput (result)get (result)printingPa进程进程Pb进程进程第四章 进 程 通 信 53 S1表示缓冲区中是否已存入进程表示缓冲区中是否已存入进程 Pa的计算结的计算结果，也即通知进程果，也即通知进程 Pb是否可取出缓冲区中的信息是否可取出缓冲区中的信息并送往打印机。并送往打印机。S1值为：值为：u0：Pa没存入新的计算结果没存入新的

45、计算结果u1：Pa已存入新的计算结果已存入新的计算结果 S2：表示缓冲区中的结果是否已被进程：表示缓冲区中的结果是否已被进程 Pb取取去，也即通知进程去，也即通知进程 Pa是否可将新的计算结果再存是否可将新的计算结果再存入缓冲区。入缓冲区。S2的值为：的值为：u0：Pb没取去缓冲区中的数据，缓冲区满没取去缓冲区中的数据，缓冲区满u1：Pb已取去缓冲区中的数据，缓冲区空已取去缓冲区中的数据，缓冲区空第四章 进 程 通 信 54u信号灯的初值可设置为：信号灯的初值可设置为：uS1为为 0：缓冲区还未存入数据：缓冲区还未存入数据uS2为为 1：缓冲空闲（相当于：缓冲空闲（相当于 Pb已取走数据）已取

46、走数据）computingput (result)Pa进程进程Wait(s2)Signal(s1)Wait(s1)Signal(s2)Pb进程进程get (result)Printing1(-1)23(0)45(0)67(-1)89(0)1011(-1)12第四章 进 程 通 信 552. 互斥和同步对信号灯操作方法的差异互斥和同步对信号灯操作方法的差异u互斥和同步都是通过对信号灯的互斥和同步都是通过对信号灯的Wait、Signal操作来实现的，但这两种控制机制对信号灯的操作来实现的，但这两种控制机制对信号灯的操作策略是不同的。操作策略是不同的。u互斥的实现是不同的进程对同一信号灯进行互斥的实

47、现是不同的进程对同一信号灯进行Wait、Signal操作，一个进程在成功地对信号操作，一个进程在成功地对信号灯执行了灯执行了Wait操作后进入临界段，并在退出临操作后进入临界段，并在退出临界段后，由该进程本身对这信号灯执行界段后，由该进程本身对这信号灯执行Signal操作，表示没有进程处于临界段，可让其他进操作，表示没有进程处于临界段，可让其他进程进入。程进入。第四章 进 程 通 信 562. 互斥和同步对信号灯操作方法的差异互斥和同步对信号灯操作方法的差异u同步的实现由一个进程同步的实现由一个进程Pa对一个信号灯进行对一个信号灯进行Wait操作后，只能由另一个进程操作后，只能由另一个进程Pb

48、对同一个信对同一个信号灯进行号灯进行Signal操作，使操作，使Pa能继续前进，在这能继续前进，在这种情况下，进程种情况下，进程Pa要同步等待要同步等待Pb。如进程。如进程Pb也要同步等待也要同步等待Pa，则要设置另一个信号灯。，则要设置另一个信号灯。第四章 进 程 通 信 57经典进程的同步问题经典进程的同步问题 4.4.4 生产者生产者消费者问题消费者问题 由于生产者由于生产者消费者问题是相互合作的进程消费者问题是相互合作的进程关系的一种抽象，例如，关系的一种抽象，例如， 在输入时，输入进程在输入时，输入进程是生产者，计算进程是消费者；而在输出时，则是生产者，计算进程是消费者；而在输出时，

49、则计算进程是生产者，而打印进程是消费者，计算进程是生产者，而打印进程是消费者， 因因此，此，该问题有很大的代表性及实用价值。该问题有很大的代表性及实用价值。 第四章 进 程 通 信 58u在多个进程的互斥问题中已提到，信号灯的取值在多个进程的互斥问题中已提到，信号灯的取值为为1，0，-1-(n-1)，其负值可表示等待进入临界，其负值可表示等待进入临界段的阻塞进程数目。那么段的阻塞进程数目。那么1和和0又可表示什么意思又可表示什么意思呢？为什么信号灯的值在数轴上可朝负方向延伸，呢？为什么信号灯的值在数轴上可朝负方向延伸，而不能向正方向延伸呢而不能向正方向延伸呢?u信号灯的非负值表示可供分配的资源

50、数目或可存信号灯的非负值表示可供分配的资源数目或可存放数据的缓冲区数目等。放数据的缓冲区数目等。第四章 进 程 通 信 59u由于在前面的进程互斥和同步问题中只有一个临由于在前面的进程互斥和同步问题中只有一个临界资源或一个缓冲区，故信号灯的值最大为界资源或一个缓冲区，故信号灯的值最大为 1。u在计算进程和打印进程问题中，如系统可提供在计算进程和打印进程问题中，如系统可提供 n 个缓冲区，且不限于两个进程之间的同步，就可个缓冲区，且不限于两个进程之间的同步，就可将前述的问题一般化，形成了典型的生产者与消将前述的问题一般化，形成了典型的生产者与消费者问题。费者问题。第四章 进 程 通 信 60u生

51、产者和消费者问题是通过有限的缓冲区（仓库）生产者和消费者问题是通过有限的缓冲区（仓库）将一群生产者将一群生产者P1，P2，Pk和一群消费者和一群消费者C1，C2，Cm联系起来。联系起来。B4B3B2B1B0第四章 进 程 通 信 61利用信号量解决生产者利用信号量解决生产者消费者问题消费者问题u假定在生产者和消费者之间的公用缓冲池中，具有假定在生产者和消费者之间的公用缓冲池中，具有n个缓冲区个缓冲区;u这时可利用互斥信号量这时可利用互斥信号量mutex实现诸进程对缓冲池实现诸进程对缓冲池的互斥使用；的互斥使用；ubuffers 的初值为的初值为 n，表示空闲的缓冲区数目。，表示空闲的缓冲区数目

52、。uproducts 的初值为的初值为 0，表示已存入缓冲区中的产品，表示已存入缓冲区中的产品数目。数目。u又假定这些生产者和消费者相互等效，只要缓冲池又假定这些生产者和消费者相互等效，只要缓冲池未满，生产者便可将消息送入缓冲池；只要缓冲池未未满，生产者便可将消息送入缓冲池；只要缓冲池未空，消费者便可从缓冲池中取走一个消息。空，消费者便可从缓冲池中取走一个消息。第四章 进 程 通 信 62u由于在生产者和消费者问题中的两个信号灯由于在生产者和消费者问题中的两个信号灯buffers和和products的值都可以大于的值都可以大于1;u因此就可能发生有多个生产者进程和消费者进因此就可能发生有多个生

53、产者进程和消费者进程同时通过程同时通过 Wait(buffers)和和 Wait(products)操操作，进入缓冲区存或取产品的情况。作，进入缓冲区存或取产品的情况。u由于存放产品的缓冲区是一种数据结构，本身由于存放产品的缓冲区是一种数据结构，本身也是临界资源，故对该部分的操作是一个临界也是临界资源，故对该部分的操作是一个临界段，各个进程也要互斥地执行段，各个进程也要互斥地执行第四章 进 程 通 信 63问题的分析问题的分析u这里有一个互斥，两个等待，需要用信号量上的这里有一个互斥，两个等待，需要用信号量上的wait、signal操作来协调：操作来协调：u（1）对缓冲池的使用应该是互斥的，利

54、用互斥信对缓冲池的使用应该是互斥的，利用互斥信号量号量mutex实现。实现。u（2）一个等待与可用缓冲区个数有关，由于开始一个等待与可用缓冲区个数有关，由于开始时所有缓冲区都空闲可用，所以设置一个初值为时所有缓冲区都空闲可用，所以设置一个初值为n的信号量，取名的信号量，取名buffers 。u（3）一个等待与缓冲区里是否有物品有关，开始一个等待与缓冲区里是否有物品有关，开始时，一个物品也没有，因此设置一个初值为时，一个物品也没有，因此设置一个初值为0的信的信号量，为号量，为products 。第四章 进 程 通 信 64生产产品生产产品Wait(buffers)Wait(mutex)b (in

55、):=product; in:=(in+1) mod n;Signal(mutex)Signal(products)Wait(products)Wait(mutex)goods:= b (out);out:=(out+1) mod n;Signal(mutex)Signal(buffers)消费产品消费产品第四章 进 程 通 信 65producers: while ( ) produce next product; Wait (buffers); Wait (mutex); put product into buffers; Signal (mutex);Signal (products);

56、 customers:while ( ) Wait (products);Wait (mutex);get product from buffers;Signal (mutex);Signal (buffers)consume product;第四章 进 程 通 信 66在生产者在生产者消费者问题中应注意：消费者问题中应注意：l首先，在每个程序中用于实现互斥的首先，在每个程序中用于实现互斥的wait(mutex)和和signal(mutex)必须成对地出现；必须成对地出现； l其次，对资源信号量其次，对资源信号量buffers和和products的的wait和和signal操作，同样需要成对地

57、出现，但它们分别处于操作，同样需要成对地出现，但它们分别处于不同的程序中。例如，不同的程序中。例如，wait(buffers)在生产者进程中，在生产者进程中，而而signal(buffers)则在消费者进程中，则在消费者进程中，生产者生产者进程若进程若因执行因执行wait(buffers)而阻塞，而阻塞， 则以后将由则以后将由消费者消费者进程进程将它唤醒；将它唤醒；l最后，在每个程序中的多个最后，在每个程序中的多个wait操作顺序不能颠倒。操作顺序不能颠倒。应先执行对资源信号量的应先执行对资源信号量的wait操作，然后再执行对互操作，然后再执行对互斥信号量的斥信号量的wait操作，否则可能引起

58、进程死锁。操作，否则可能引起进程死锁。第四章 进 程 通 信 674.4.5 读者读者-写者问题写者问题 问题描述：问题描述： 多个读者同时工作时，不会有问题。但是如果多个读者同时工作时，不会有问题。但是如果读者和写者或写者和写者同时工作时，就有可能导读者和写者或写者和写者同时工作时，就有可能导致错误的访问结果。假定读者访问时，又来写者要致错误的访问结果。假定读者访问时，又来写者要求访问，那么写者只有等待，而到来的后继读者则求访问，那么写者只有等待，而到来的后继读者则可以进行访问（这就隐含读者比写者有更高的访问可以进行访问（这就隐含读者比写者有更高的访问权限）。权限）。第四章 进 程 通 信

59、68问题的分析问题的分析u对共享资源的读写操作，任一时刻对共享资源的读写操作，任一时刻“写者写者”最最多只允许一个，而多只允许一个，而“读者读者”则允许多个则允许多个 “读写读写” 互斥，互斥， “写写写写” 互斥，互斥， “读读读读” 允许允许第四章 进 程 通 信 69问题的分析问题的分析u一批数据被多个读者、写者共享使用；一批数据被多个读者、写者共享使用；u允许多个读者同时访问；允许多个读者同时访问；u如果有一个写者在访问数据时，就不允许其他如果有一个写者在访问数据时，就不允许其他读者和写者使用。读者和写者使用。u所以：所以： 应保证应保证“读写读写” 互斥，互斥， “写写写写” 互斥。

60、互斥。u也就是说，在读者程序中，使用数据的程序段也就是说，在读者程序中，使用数据的程序段应该构成临界区；在写者程序中，使用数据的应该构成临界区；在写者程序中，使用数据的程序段应该构成临界区。信号量程序段应该构成临界区。信号量Wrt被用来在被用来在读者和写者程序中构成这种临界区。读者和写者程序中构成这种临界区。第四章 进 程 通 信 70wait（Wrt）writingsignal（ Wrt ）写者写者：wait （ Wrt ）readingsignal （ Wrt ）读者读者: 第四章 进 程 通 信 71问题的分析问题的分析u对于写者，只需在访问数据对象前，对信号量对于写者，只需在访问数据对象前，对信号量做做wa