同步通信与死锁课件

1、同步通信与死锁1第三章第三章 同步、通信与死锁同步、通信与死锁同步通信与死锁23.1 进程的同步与互斥n在多道程序的环境中，系统中的多个进程可以并发执行，同时它们又要共享在多道程序的环境中，系统中的多个进程可以并发执行，同时它们又要共享系统中的资源，由此诸进程间会产生错综复杂的相互制约的关系。系统中的资源，由此诸进程间会产生错综复杂的相互制约的关系。一、进程的相互制约关系一、进程的相互制约关系 1.1.间接相互制约关系间接相互制约关系 源于资源共享源于资源共享 若一个进程要求使用某一资源，而该资源正被另一个进程使若一个进程要求使用某一资源，而该资源正被另一个进程使用，并且这一资源不允许两个进程

2、同时访问，那么该进程只有用，并且这一资源不允许两个进程同时访问，那么该进程只有等待，只有这一资源释放后才能使用。等待，只有这一资源释放后才能使用。2.2.直接相互制约关系直接相互制约关系 源于进程间的合作源于进程间的合作 一组进程分工协作，在执行的先后次序有约束，在一些关键一组进程分工协作，在执行的先后次序有约束，在一些关键点上协调工作。若一个进程运行到某点时，在尚未收到另一协点上协调工作。若一个进程运行到某点时，在尚未收到另一协作进程发来的信息前应阻塞自己，等协作进程发来消息后方可作进程发来的信息前应阻塞自己，等协作进程发来消息后方可继续执行。继续执行。进程进程资源资源进程进程进程进程进程进

3、程同步通信与死锁3n进程间这种相互依赖又相互制约，相互合作又相互竞进程间这种相互依赖又相互制约，相互合作又相互竞争的关系，主要表现在进程互斥和进程同步两方面争的关系，主要表现在进程互斥和进程同步两方面二、进程互斥二、进程互斥引例：引例： 宿舍电话的使用宿舍电话的使用 打印机的使用打印机的使用1 1、临界资源、临界资源 一次仅允许一个进程使用的资源称为临界资源。一次仅允许一个进程使用的资源称为临界资源。 引例中的电话和打印机都属于临界资源。还有光引例中的电话和打印机都属于临界资源。还有光盘刻录机、绘图仪、共享变量、共享的数据结构等等盘刻录机、绘图仪、共享变量、共享的数据结构等等也是临界资源。也是

4、临界资源。2 2、临界区：、临界区： 每个进程中访问临界资源的那段程序段称为临界每个进程中访问临界资源的那段程序段称为临界区。（临界段）区。（临界段）同步通信与死锁4例：统计两个进程例：统计两个进程P1和和P2对共享变量对共享变量count的访问计数。的访问计数。P1： . P2: . R1=count; R2=count; R1=R1+1; R2=R2+1; count=R1; count=R2; . .两进程并发执行，可能的执行顺序为：两进程并发执行，可能的执行顺序为： P1: R1=count; R1=R1+1; P2: R2=count; R2=R2+1; count=R2; P1:

5、count=R1; 虽然两个进程各自都执行了对虽然两个进程各自都执行了对count加加1的操作，但结果为何的操作，但结果为何count只增加只增加1？ count是临界资源，是临界资源，P1、P2访问访问count的两个程序段就是临界的两个程序段就是临界区，两个进程必须互斥的进入临界区区，两个进程必须互斥的进入临界区,否则就可能出与时间有关的否则就可能出与时间有关的错误错误. .同步通信与死锁5、进程互斥、进程互斥n当某一进程正在访问某临界区时，就不允许其它进程当某一进程正在访问某临界区时，就不允许其它进程进入，否则就会发生无法估计的错误。进程之间的这进入，否则就会发生无法估计的错误。进程之间

6、的这种相互制约的关系称为进程互斥。种相互制约的关系称为进程互斥。4 4、进入临界区的准则：、进入临界区的准则：每次至多有一个进程进入临界区内执行；每次至多有一个进程进入临界区内执行；若已有进程在临界区中，试图进入此临界区的其他若已有进程在临界区中，试图进入此临界区的其他进程应等待；进程应等待；进入临界区的进程应在有限时间内退出，以便让等进入临界区的进程应在有限时间内退出，以便让等待队列中的一个进程进入。待队列中的一个进程进入。同步通信与死锁6三、进程同步引例：两位同学约好星期天去玩，早上引例：两位同学约好星期天去玩，早上8:00在校门口，在校门口，不见不散。当一个同学先来到校门口，要等另一个同

7、不见不散。当一个同学先来到校门口，要等另一个同学，到齐后一起去玩。学，到齐后一起去玩。n互斥的概念来自于诸进程对临界资源的竞争，同步互斥的概念来自于诸进程对临界资源的竞争，同步来源于多个进程的合作。在人类社会中竞争与合作来源于多个进程的合作。在人类社会中竞争与合作是永恒的。是永恒的。 n进程同步进程同步：几个进程相互合作，一个进程到达某点：几个进程相互合作，一个进程到达某点后，若另一进程尚未完成某些操作，就必须停下来后，若另一进程尚未完成某些操作，就必须停下来等待，只有等另一进程的这些操作完成了才能继续等待，只有等另一进程的这些操作完成了才能继续执行。执行。同步通信与死锁7例：计算例：计算fu

8、n1(X)fun1(X)* *fun2(y)fun2(y)两进程合作完成任务两进程合作完成任务进程进程1 1：计算：计算fun1(X)fun1(X)。进程进程2 2：计算：计算fun2(X)fun2(X)；与进程；与进程1 1结果相乘。结果相乘。进程进程1 1和进程和进程2 2并发执行。并发执行。同步通信与死锁83.2 3.2 进程互斥的实现进程互斥的实现一、实现进程互斥的软件算法一、实现进程互斥的软件算法n现在很少用软件方法解决互斥，但通过学习现在很少用软件方法解决互斥，但通过学习软件解法能使读者了解到，在早期进程互斥软件解法能使读者了解到，在早期进程互斥问题的解决并不是一件很简单的事。问题

9、的解决并不是一件很简单的事。同步通信与死锁9尝试尝试 (1)(1)bool inside1=false; /P1不在其临界区内不在其临界区内bool inside2=false; /P2不在其临界区内不在其临界区内cobegin process P1( ) process P2( ) while(inside2); while(inside1); inside1=true; inside2=true; 临界区临界区; 临界区临界区; inside1=false; inside2=false; coend P1P1和和P2P2可能同时进入临界区可能同时进入临界区同步通信与死锁10尝试尝试 (2)

10、(2)bool inside1=false; /P1不在其临界区内不在其临界区内bool inside2=false; /P2不在其临界区内不在其临界区内cobeginprocess P1( ) process P2( ) inside1=true; inside2=true; while(inside2); while(inside1);临界区临界区; 临界区临界区; inside1=false; inside2=false; coendP1P1和和P2P2可能永远等待。可能永远等待。同步通信与死锁11process P0( ) inside0=true; turn=1; while(ins

11、ide1&turn=1); 临界区临界区; inside0=false; process P1( ) inside1=true; turn=0; while(inside0&turn=0); 临界区临界区; inside1=false; cobegincoendbool inside2;inside0=false;inside1=false;enum 0,1 turn;Peterson算法同步通信与死锁12n为 每 一 进 程 设 标 志 位为 每 一 进 程 设 标 志 位 i n s i d e i i n s i d e i ， 当， 当insidei=trueinsidei=true时

12、，表示进程时，表示进程pipi要求进入，或正要求进入，或正在临界区中执行。此外再设一个变量在临界区中执行。此外再设一个变量turnturn，用于，用于指示允许进入的进程编号。指示允许进入的进程编号。n进程进程0 0为了进入先置为了进入先置inside0=trueinside0=true，并置，并置turnturn为为1 1，表示应轮到，表示应轮到p1p1进入。接着再判断进入。接着再判断inside1&turn=1inside1&turn=1的条件是否满足的条件是否满足, ,若不满足则若不满足则可进入。或者说当可进入。或者说当inside 1 =falseinside 1 =false或者或者t

13、urn=0turn=0时，进程可以进入。前者表示时，进程可以进入。前者表示p1p1未要求进未要求进入，后者表示仅允许入，后者表示仅允许p0p0进入进入. .同步通信与死锁13软件解法的缺点软件解法的缺点1. 1. 忙等待忙等待2. 2. 实现过于复杂，需要较高的编程技巧实现过于复杂，需要较高的编程技巧同步通信与死锁14二、实现进程互斥的硬件设施二、实现进程互斥的硬件设施用软件解决很难，现代计算机大多提供一用软件解决很难，现代计算机大多提供一些硬件指令。些硬件指令。n利用关中断实现进程互斥利用关中断实现进程互斥 n利用利用Test-and-SetTest-and-Set指令实现互斥指令实现互斥

14、n利用利用swapswap指令实现进程互斥指令实现进程互斥 同步通信与死锁151.1.利用关中断实现进程互斥利用关中断实现进程互斥 n进程进入临界区时关中断，在进程退出临界进程进入临界区时关中断，在进程退出临界区时开中断。区时开中断。n关中断方法简单有效关中断方法简单有效n关中断方法的缺点关中断方法的缺点同步通信与死锁162.Test-and-Set2.Test-and-Set（TSTS）指令实现互斥）指令实现互斥TSTS指令指令bool TS(bool &x) if(x) x=false; return true; else return false; 同步通信与死锁17TSTS指令实现进程

15、互斥指令实现进程互斥bool s=true;cobeginprocess Pi( ) /i=1,2,.,n while(!TS(s); /上锁上锁 临界区临界区; s=true; /开锁开锁coend 变量变量s s代表了临界资源的状态，可把它看成一把锁。代表了临界资源的状态，可把它看成一把锁。S S初初值设为值设为truetrue，表示没有进程在临界区，资源可用。进入临界，表示没有进程在临界区，资源可用。进入临界区前，首先用区前，首先用TSTS指令测试指令测试s s，若没有进程在临界区，则可进，若没有进程在临界区，则可进入，否则循环测试直至入，否则循环测试直至s s的值为的值为truetru

16、e；当进程退出临界区时，；当进程退出临界区时，把把s s的值置为的值置为truetrue。 同步通信与死锁183.swap3.swap指令实现进程互斥指令实现进程互斥swapswap指令指令又称交换指令，在又称交换指令，在Intel x86Intel x86中称为中称为XCHGXCHG。功能是交换两个字的内容。功能是交换两个字的内容。void S &a,bool &b) bool temp=a;a=b;b=temp; 同步通信与死锁19利用利用swapswap实现进程互斥实现进程互斥n为每一临界资源设置一个全局布尔变量为每一临界资源设置一个全局布尔变量locklock，其初值为，其初值为fal

17、sefalse，表示无进程在临界区内。在每个进程中有局部布尔，表示无进程在临界区内。在每个进程中有局部布尔变量变量keyikeyi。bool lock=false;cobeginProcess Pi( ) /i=1,2,.,n bool keyi=true; do S); while(keyi); /上锁上锁 临界区临界区; S); /开锁开锁coend同步通信与死锁20n实现进程互斥的软件算法太过复杂，效率实现进程互斥的软件算法太过复杂，效率低下；低下；n实现进程互斥的硬件方法虽简单有效，但实现进程互斥的硬件方法虽简单有效，但采用忙式等待，白白浪费采用忙式等待，白白浪费cpucpu时间；将测

18、试时间；将测试能否进入临界区的责任推卸给各进程，会能否进入临界区的责任推卸给各进程，会削弱系统的可靠性，加重用户的编程负担；削弱系统的可靠性，加重用户的编程负担；且这些方案只能解决进程互斥问题，却不且这些方案只能解决进程互斥问题，却不能解决进程同步问题。能解决进程同步问题。同步通信与死锁213.3 3.3 信号量与信号量与PVPV操作操作一、信号量的概念一、信号量的概念 信号量的概念是由荷兰科学家信号量的概念是由荷兰科学家DijkstraDijkstra于于19651965年提出的。年提出的。 n管理和控制铁路和公路交通的重要工具是信号灯，利管理和控制铁路和公路交通的重要工具是信号灯，利用信号

19、灯的颜色控制各种车辆的正常通行。在操作系用信号灯的颜色控制各种车辆的正常通行。在操作系统中引入了信号灯（信号量）的概念，让多个进程通统中引入了信号灯（信号量）的概念，让多个进程通过信号量展开交互。过信号量展开交互。同步通信与死锁221.信号量的定义是一个结构型数据结构，定义如下：是一个结构型数据结构，定义如下： struct semaphore struct semaphore int value; / int value; /信号量的值信号量的值 struct pcb struct pcb * *list; /list; /信号量队列的头指针信号量队列的头指针 信号量说明：信号量说明： se

20、maphore s;semaphore s;n信号量信号量必须置一次且只能置一次初值，初值不能为负数。必须置一次且只能置一次初值，初值不能为负数。n对信号量只能执行对信号量只能执行P P、V V操作操作同步通信与死锁232.P2.P、V V操作操作对信号量仅能执行对信号量仅能执行P、V操作。操作。n对信号量的对信号量的P P操作记为：操作记为：P(S)P(S)，P P操作是一个原操作是一个原子操作。子操作。n对信号量的对信号量的V V操作记为：操作记为：V(S), VV(S), V操作是操作是一个一个原原子操作。子操作。 在实际系统中，一般情况下是由机器硬件提供在实际系统中，一般情况下是由机器

21、硬件提供P P、V V操作的指令，当然是原子操作，若机器不提供操作的指令，当然是原子操作，若机器不提供P P、V V操操作的指令，则操作系统提供作的指令，则操作系统提供P P、V V操作原语。操作原语。同步通信与死锁24P(s)：s.value-；若若s.value0，则执行，则执行P(s)的进程继续执行；的进程继续执行；若若s.value0 ，则执行，则执行V(s)的进程继续执行；的进程继续执行；若若s.value0，则执行，则执行V(s)的进程从等待信号量的进程从等待信号量s的阻的阻塞队列中唤醒头一个进程，然后自己继续执行。塞队列中唤醒头一个进程，然后自己继续执行。 操作系统正是利用信号量

22、的状态对进程和资源进行管理。从物操作系统正是利用信号量的状态对进程和资源进行管理。从物理意义上理解，理意义上理解，P P操作相当于申请资源；操作相当于申请资源；V V操作相当于释放资源。操作相当于释放资源。同步通信与死锁25二、用信号量实现进程互斥1. 两个进程间的互斥两个进程间的互斥 semaphore S； S =1； cobegin Process P1( ) Process P2( ) P（S） P（S） V（S） V（S） coend临界区临界区临界区临界区同步通信与死锁26对于两个并发进程，互斥信号量的值仅取对于两个并发进程，互斥信号量的值仅取1、0和和-1三个值三个值 若若S1表

23、示没有进程进入临界区表示没有进程进入临界区若若S0表示有一个进程进入临界区表示有一个进程进入临界区若若S-1表示一个进程进入临界区，另一个进程等待进入。表示一个进程进入临界区，另一个进程等待进入。 同步通信与死锁27例：有一个售票厅只能容纳例：有一个售票厅只能容纳300300人，当少于人，当少于300300人时，人时，可以进入购票；否则在外等待。若将每一个购票者看可以进入购票；否则在外等待。若将每一个购票者看作一个进程，请用作一个进程，请用P P、V V操作编程实现。操作编程实现。semaphore Ssemaphore S；S=300S=300；Process Pi()Process Pi(

24、)（i=1i=1，2 2，3 3，） P(S)P(S)； 进入购票厅；进入购票厅； 购票；购票； 离开购票厅；离开购票厅； V(S)V(S)； 同步通信与死锁28思考：思考：对于对于n n个并发进程，如何实现互斥；个并发进程，如何实现互斥；信号量的取值范围是什么，有什么含义。信号量的取值范围是什么，有什么含义。设置互斥信号量设置互斥信号量 S=m（m为某种临界资源可用数量）为某种临界资源可用数量）cobegin process P1 process P2 process pn P（S） P（S） P（S） V（S） V（S） V（S） coend临界区临界区临界区临界区临界区临界区互斥信号量联

25、系一组并发进程，各进程对此信号量互斥信号量联系一组并发进程，各进程对此信号量执行执行P P、V V操作，因此又称为公用信号量。操作，因此又称为公用信号量。同步通信与死锁29n信号量取值范围：信号量取值范围：mm-nmm-nn信号量的含义：信号量的含义： S0S0表示有表示有S S个资源可用个资源可用 S=0S=0表示无资源可用表示无资源可用 S0S0则则| S | S |表示表示S S等待队列中的进程个数等待队列中的进程个数同步通信与死锁30三、用信号量实现进程的同步三、用信号量实现进程的同步1.1.进程同步模型进程同步模型 进程进程P1P1到达到达L1L1这一点时，若进程这一点时，若进程P2

26、P2还未执行到还未执行到L2L2点，进程点，进程P1P1就必须停下来等待，等到进程就必须停下来等待，等到进程P2P2到达到达L2L2这一点时，这一点时，P1P1才能继才能继续运行。也就是进程续运行。也就是进程P1P1在在L1L1这一点要与进程这一点要与进程P2P2同步。同步。（P1P1等待等待P2P2）semaphore s；S=0Cobegin process P1（）（） process P2（）（） L1:P(s) L2:V(s) coend总结：总结：P1P1在在L1L1点等待点等待P2P2进程进程执行到执行到L2L2点才能继续点才能继续执行。执行。设置信号量设置信号量s=0s=0P1

27、P1进程进程L1L1点：点：P(S)P(S)P2P2进程进程L2L2点：点：V(S)V(S)同步通信与死锁31在操作系统中，同步有各种各样，归纳起来有两类：在操作系统中，同步有各种各样，归纳起来有两类：n保证一组合作进程按确定的次序执行保证一组合作进程按确定的次序执行n保证共享缓冲区的合作进程的同步。保证共享缓冲区的合作进程的同步。2.2.合作进程的执行次序合作进程的执行次序 若干个进程为了完成一个共同任务而并发执行，若干个进程为了完成一个共同任务而并发执行，在这些进程中，有些进程之间有次序的要求，有些在这些进程中，有些进程之间有次序的要求，有些进程之间没有次序的要求。进程之间没有次序的要求。

28、 为了描述方便，可以用为了描述方便，可以用一个图来一个图来描述诸进程合描述诸进程合作完成某一任务的次序。作完成某一任务的次序。进程流图进程流图同步通信与死锁32同步通信与死锁33进程流图是实际例子抽象出来的。进程流图是实际例子抽象出来的。例：例：(a+b)(a+b)* *(c+d)+c(c+d)+c* *f fP2P1P3P4P5SFP1P2P3P4P5同步通信与死锁34例：试用信号量实现这三个并发进程按确例：试用信号量实现这三个并发进程按确定的次序执行。定的次序执行。a、分析进程的同步关系、分析进程的同步关系 进程进程P1、P2可并发执行，可并发执行，P3的执行必的执行必须等待须等待P1、P

29、2都完成后才能开始执行。都完成后才能开始执行。b、设置信号量，说明含义、初值、设置信号量，说明含义、初值。 s13 = 0 表示进程表示进程P1尚未执行完成；尚未执行完成； s23 = 0 表示进程表示进程P2尚未执行完成；尚未执行完成；c、写出程序描述、写出程序描述同步通信与死锁35同步通信与死锁36例：试用信号量实现这三个进程的同步。例：试用信号量实现这三个进程的同步。 Semaphore SB，SC；SB=0； SC=0；cobegin Pa（）（） Pb（）（） Pc（）（） P(SB); P(SC)； V(SB); V(SC); coend同步通信与死锁373.3.共享缓冲区的合作进

30、程的同步共享缓冲区的合作进程的同步 设有一个缓冲区设有一个缓冲区buffer，大小为，大小为一个字节，一个字节，某计算进程和打印某计算进程和打印进程共用，进程共用，CP进程不断产生进程不断产生字符，送字符，送buffer，IOP进程从进程从buffer中取出字符打印。中取出字符打印。 如不加控制，如不加控制，会有多种打印结果会有多种打印结果，这取决于这两个进程运行的相对速这取决于这两个进程运行的相对速度。在这众多的打印结果中，度。在这众多的打印结果中，只有只有CP、IOP进程的运行刚好匹配的一进程的运行刚好匹配的一种是对的，种是对的，其它均为错误，并且不其它均为错误，并且不能重现。能重现。同步

31、通信与死锁38 要保证打印结果的正确，要保证打印结果的正确，CP、IOP必须遵循以下必须遵循以下同步规则：同步规则：(1)当当CP把结果送入把结果送入buffer后，后，IOP才能从才能从buffer中取，中取，否则否则IOP必须等待；必须等待；(2)当当IOP从从buffer中取走数据后，中取走数据后，CP才能将新产生数才能将新产生数据送据送buffer，否则也必须等待。，否则也必须等待。n解决这个问题的步骤：解决这个问题的步骤：(1)分析问题，弄清楚同步关系，如上分析；分析问题，弄清楚同步关系，如上分析；(2)设置信号量，说明含义、初值；设置信号量，说明含义、初值；(3)写出程序描述。写出

32、程序描述。同步通信与死锁39同步通信与死锁40四、互斥和同步对信号量操作方法的差异四、互斥和同步对信号量操作方法的差异 互斥和同步都是通过对信号量的互斥和同步都是通过对信号量的P P、V V操作来实现的，但操作来实现的，但这两种控制机制对信号量的操作策略是不同的。这两种控制机制对信号量的操作策略是不同的。n互斥的实现：互斥的实现： 是不同进程对同一信号量进行是不同进程对同一信号量进行P P、V V操作。进入临界操作。进入临界区之前执行区之前执行P P操作，退出临界区后执行操作，退出临界区后执行V V操作。操作。n同步的实现：同步的实现： PaPa进程要同步等待进程要同步等待PbPb需设置一信号

33、量，需设置一信号量，PaPa进程中实进程中实行行P P操作，操作，PbPb进程实行进程实行V V操作。操作。 若进程若进程PbPb也要同步等待也要同步等待PaPa，则要设置另一个信号量。，则要设置另一个信号量。nP.VP.V操作必须成对出现，有一个操作必须成对出现，有一个P P操作就一定有一个操作就一定有一个V V操作操作 当为互斥操作时，它们同处于同一进程当为互斥操作时，它们同处于同一进程 当为同步操作时，则不在同一进程中出现当为同步操作时，则不在同一进程中出现同步通信与死锁41五、经典的进程同步、互斥问题五、经典的进程同步、互斥问题1.1.生产者生产者消费者问题消费者问题问题描述：问题描述

34、：n有有m m个生产者个生产者和和n n个消费者个消费者，它们共享，它们共享可存放可存放k k件产件产品的缓冲区品的缓冲区。n只要缓冲区未满，生产者就可以把产品送入缓冲区只要缓冲区未满，生产者就可以把产品送入缓冲区; ;n只要缓冲区未空，消费者就可以从缓冲区中取走物只要缓冲区未空，消费者就可以从缓冲区中取走物品。品。消费者消费者0 1 2 k-1生产者生产者消费者消费者生产者生产者生产者生产者同步通信与死锁42n著名的生产者著名的生产者-消费者问题是计算机操作系消费者问题是计算机操作系统中并发进程内在关系的一种抽象，是典型统中并发进程内在关系的一种抽象，是典型的进程同步问题。的进程同步问题。n

35、在操作系统中，生产者进程可以是计算进程、在操作系统中，生产者进程可以是计算进程、发送进程；而消费者进程可以是打印进程、发送进程；而消费者进程可以是打印进程、接收进程等等。接收进程等等。n解决好生产者解决好生产者-消费者问题就解决好了一类消费者问题就解决好了一类并发进程的同步问题。并发进程的同步问题。同步通信与死锁43问题分析问题分析n对于生产者进程对于生产者进程：生产一个产品，当要送入缓冲区：生产一个产品，当要送入缓冲区时，要检查是否有空缓冲区，若有，则可将产品送时，要检查是否有空缓冲区，若有，则可将产品送入缓冲区，并通知消费者进程；否则，等待；入缓冲区，并通知消费者进程；否则，等待；n对于消

36、费者进程对于消费者进程：当它去取产品时，要看缓冲区中：当它去取产品时，要看缓冲区中是否有产品可取，若有则取走一个产品，并通知生是否有产品可取，若有则取走一个产品，并通知生产者进程，否则，等待。产者进程，否则，等待。n这种相互等待，并互通信息就是典型的进程同步。这种相互等待，并互通信息就是典型的进程同步。n因此应该设因此应该设两个同步信号量：两个同步信号量： emptyempty：表示可用的空缓冲区的数目，初值为：表示可用的空缓冲区的数目，初值为k k fullfull：表示可以使用产品的数目，初值为。：表示可以使用产品的数目，初值为。n缓冲区是一个临界资源，必须互斥使用，所以另外缓冲区是一个临

37、界资源，必须互斥使用，所以另外还需要设置一个还需要设置一个互斥信号量互斥信号量mutexmutex，其初值为。，其初值为。同步通信与死锁44问题的解问题的解item Bk;semaphore empty;empty=k; /可以使用的空缓冲区数可以使用的空缓冲区数semaphore full; full=0; /缓冲区内可以使用的产品数缓冲区内可以使用的产品数semaphore mutex;mutex=1; /互斥信号量互斥信号量int in=0; /放入缓冲区指针放入缓冲区指针int out=0; /取出缓冲区指针取出缓冲区指针 cobeginprocess producer_i ( ) p

38、rocess consumer_j ( ) while(true) while(true) produce( ); P(full); P(empty); P(mutex); P(mutex); take( ) from Bout; append to Bin; out=(out+1)%k; in=(in+1)%k; V(mutex); V(mutex); V(empty); V(full); consume( ); coend同步通信与死锁45讨论：讨论：n若将生产者进程中两个若将生产者进程中两个P P操作交换次序，那么操作交换次序，那么当缓冲区存满当缓冲区存满k k件产品（件产品（empty

39、=0empty=0，mutex=1mutex=1，full=kfull=k）时，生产者又生产一件产品，将在）时，生产者又生产一件产品，将在P(empty)P(empty)上等待，此时上等待，此时mutex=0mutex=0。消费者进程。消费者进程将在将在P(mutex)P(mutex)上等待。这就导致两进程都处上等待。这就导致两进程都处于无休止的等待状态，造成了死锁。于无休止的等待状态，造成了死锁。n若将消费者进程中两若将消费者进程中两P P操作交换次序，则当缓操作交换次序，则当缓冲区为空时，也会出项上述类似问题。冲区为空时，也会出项上述类似问题。同步通信与死锁46总结：总结：nP.VP.V操

40、作必须操作必须成对成对出现，有一个出现，有一个P P操作就一定有一个操作就一定有一个V V操作。操作。 当为当为互斥互斥操作时，它们同操作时，它们同处于同一进程处于同一进程。 当为当为同步同步操作时，则操作时，则不在同一进程中不在同一进程中出现。出现。n如果如果两个两个P P操作操作在一起，那么在一起，那么P P操作的顺序至关重要操作的顺序至关重要。 一个同步一个同步P P操作与一个互斥操作与一个互斥P P操作在一起时，操作在一起时，同步同步P P操作在互斥操作在互斥P P操作前。操作前。n而而两个两个V V操作操作在一起时在一起时顺序无关紧要顺序无关紧要。同步通信与死锁472. 2. 读者读

41、者/ /写者问题写者问题问题描述问题描述有两组并发进程有两组并发进程: : 读者和写者读者和写者, ,共享一个文件共享一个文件F F要求：要求： n允许多个读者同时执行读操作允许多个读者同时执行读操作n只允许一个写者执行写操作只允许一个写者执行写操作n任一写者在完成写操作之前不允许其它读者或写者任一写者在完成写操作之前不允许其它读者或写者工作工作n写者执行写操作前，应让已有的写者和读者全部退写者执行写操作前，应让已有的写者和读者全部退出出同步通信与死锁48问题分析问题分析n读者和写者互斥读者和写者互斥，写者和写者互斥写者和写者互斥访问文件访问文件n设设信号量信号量writeblock，用于实现

42、读写互斥、，用于实现读写互斥、写写互斥地访问文件。写写互斥地访问文件。n另设一个全局变量另设一个全局变量readcount，记录正在读，记录正在读的读者数目。的读者数目。n设置设置信号量信号量mutex，用于使读者互斥地访问，用于使读者互斥地访问共享变量共享变量readcount 。同步通信与死锁49int readcount=0; /读进程计数semaphore writeblock,mutex;writeblock=1; mutex=1;cobeginprocess reader_i( ) process writer_j( ) P(mutex); P(writeblock); readc

43、ount+; 写文件; if(readcount=1) V(writeblock); P(writeblock); V(mutex); 读文件; P(mutex); readcount-; if(readcount=0) V(writeblock); V(mutex); Coend同步通信与死锁503.3.哲学家就餐问题哲学家就餐问题问题描述问题描述 有五个哲学家围坐有五个哲学家围坐在一圆桌旁，桌中央有在一圆桌旁，桌中央有一盘通心面，每人面前一盘通心面，每人面前有一只空盘于，每两人有一只空盘于，每两人之间放一把叉子。之间放一把叉子。每个每个哲学家思考、饥饿、然哲学家思考、饥饿、然后吃通心面后吃

44、通心面。为了吃面，。为了吃面，每个哲学家必须获得两每个哲学家必须获得两把叉子，且每人只能直把叉子，且每人只能直接从自己左边或右边去接从自己左边或右边去取叉子。取叉子。 同步通信与死锁51问题分析问题分析n每把叉子都必须互斥使用，因此为每把叉子设每把叉子都必须互斥使用，因此为每把叉子设置互斥信号量置互斥信号量forki(i=0,1,2,3,4),初值均为初值均为1；n当哲学家吃面前必须执行两个当哲学家吃面前必须执行两个P操作，获得自操作，获得自己左边和右边的两把叉子；吃完后必须执行两己左边和右边的两把叉子；吃完后必须执行两次次V操作，放下两把叉子。操作，放下两把叉子。同步通信与死锁52semap

45、hore fork5;for (int i=0;i5;i+) forki=1;cobegin process philosopher_i( ) /i= 0,1,2,3,4 while(true) think( ); P(forki); P(fork(i+1)%5); eat( ); V(forki); V(fork(i+1)%5); coend同步通信与死锁53n上述解法可能出现永远等待，有若干种办法上述解法可能出现永远等待，有若干种办法可避免死锁：可避免死锁：（1 1）至多允许四个哲学家同时吃；）至多允许四个哲学家同时吃；（2 2）奇数号先取左手边的叉子，偶数号先）奇数号先取左手边的叉子，偶

46、数号先 取右手边的叉子；取右手边的叉子；（3 3）每个哲学家取到手边的两把叉子才吃，）每个哲学家取到手边的两把叉子才吃，否则一把叉子也不取。否则一把叉子也不取。同步通信与死锁543.4 3.4 进程通信进程通信n进程通信进程通信(Interprocess Communication,IPC)(Interprocess Communication,IPC)是指进程之间的信息交换。是指进程之间的信息交换。n信号量及信号量及P.VP.V操作实现的是进程之间的低级通操作实现的是进程之间的低级通讯，所以讯，所以P.VP.V为低级通讯原语。它只能传递简为低级通讯原语。它只能传递简单的信号，不能传递交换大量

47、信息。单的信号，不能传递交换大量信息。n本节介绍本节介绍高级进程通信，是指进程间高效的高级进程通信，是指进程间高效的传送大量数据的通信方式。传送大量数据的通信方式。同步通信与死锁55进程间通信的方式进程间通信的方式 n信号信号(signal)(signal)通信机制通信机制n管道管道(pipeline)(pipeline)通信机制通信机制 n消息传递消息传递(message passing)(message passing)通信机制通信机制 n信号量信号量(semaphore)(semaphore)通信机制通信机制n共享主存共享主存(shared memory)(shared memory)通

48、信机制通信机制n前两种是前两种是UNIXUNIX最早的版本就提供的进程通信机制。最早的版本就提供的进程通信机制。信号通信机制只能发送单个信号而不能传递数据；信号通信机制只能发送单个信号而不能传递数据；管道通信虽能传送数据，却只能在进程家族内使管道通信虽能传送数据，却只能在进程家族内使用，应用范围有限。用，应用范围有限。同步通信与死锁56进程通信方式发展进程通信方式发展nUNIXUNIX发展历史中，发展历史中，AT&TAT&T的的BellBell与加大伯与加大伯克利的克利的BSDBSD是两大主力。是两大主力。nBellBell致力于改进传统的进程致力于改进传统的进程IPCIPC，形成了，形成了S

49、YSTEM IPCSYSTEM IPC机制（上述后三种通信机机制（上述后三种通信机制）。制）。nBSDBSD在改进在改进IPCIPC的同时，把网络通信规程的同时，把网络通信规程(TCP/IP)(TCP/IP)实现到实现到UNIXUNIX内核中，考虑把同内核中，考虑把同一计算机上的进程通信纳入更广的网络一计算机上的进程通信纳入更广的网络范围的进程间通信，这种努力结果出现范围的进程间通信，这种努力结果出现了了socketsocket网络通信机制。网络通信机制。 同步通信与死锁57一、管道通信机制一、管道通信机制n管道通信是管道通信是UNIXUNIX的传统进程通信方式，也是的传统进程通信方式，也是U

50、NIXUNIX发展最有意义的贡献之一。发展最有意义的贡献之一。n所谓管道，是指用于连接一个读进程和一个写进所谓管道，是指用于连接一个读进程和一个写进程的特殊文件，称程的特殊文件，称pipepipe文件。文件。n发送进程以字符流形式把大量数据送入管道，接发送进程以字符流形式把大量数据送入管道，接收进程从管道中接收数据，所以叫管道通信。收进程从管道中接收数据，所以叫管道通信。发送进程发送进程接收进程接收进程字符流方式写入读出字符流方式写入读出先进先出顺序先进先出顺序同步通信与死锁58n管道的实质是一个共享文件，基本上可借助于文件管道的实质是一个共享文件，基本上可借助于文件系统的机制实现，包括（管道

51、）文件的创建、打开、系统的机制实现，包括（管道）文件的创建、打开、关闭和读写。关闭和读写。n但写进程和读进程间的相互协调单靠文件系统机制但写进程和读进程间的相互协调单靠文件系统机制解决不了，读写进程相互同步，必须做到以下几点：解决不了，读写进程相互同步，必须做到以下几点：（1 1）互斥，即一个进程正在使用某个管道写入或读出）互斥，即一个进程正在使用某个管道写入或读出数据时，另一个进程就必须等待；数据时，另一个进程就必须等待；（2 2）发送者和接收者双方必须能够知道对方是否存）发送者和接收者双方必须能够知道对方是否存在，如果对方已经不存在，就没有必要再发送信息。在，如果对方已经不存在，就没有必要

52、再发送信息。（3 3）同步，指当写进程把一定量的数据发送后，便）同步，指当写进程把一定量的数据发送后，便睡眠等待，直到读进程把管道中数据取走后，在把睡眠等待，直到读进程把管道中数据取走后，在把它唤醒。反之当读进程读空管道时，也被阻塞，直它唤醒。反之当读进程读空管道时，也被阻塞，直到写进程将数据写入管道后，才将它唤醒。到写进程将数据写入管道后，才将它唤醒。同步通信与死锁59二、共享主存通信机制二、共享主存通信机制n在主存中开辟一个公用存储区，要通信的进程把自在主存中开辟一个公用存储区，要通信的进程把自己的虚地址空间映射到共享主存区。发送进程将信己的虚地址空间映射到共享主存区。发送进程将信息写入共享主存区的某个位置上，接收进程可从此息写入共享主存区的某个位置上，接收进程可从此位置读取信息。位置读取信息。 虚存段进程1的虚存空间 虚存段进程2的虚存空间 物理主存共享主存同步通信