《同步通信与死锁PPT课件》由会员分享，可在线阅读，更多相关《同步通信与死锁PPT课件（67页珍藏版）》请在金锄头文库上搜索。
1、第三章第三章 同步、通信与死锁同步、通信与死锁13.1 进程的同步与互斥n在多道程序的环境中，系统中的多个进程可以并发执行，同时它们又要共享在多道程序的环境中，系统中的多个进程可以并发执行，同时它们又要共享系统中的资源，由此诸进程间会产生错综复杂的相互制约的关系。系统中的资源，由此诸进程间会产生错综复杂的相互制约的关系。一、进程的相互制约关系一、进程的相互制约关系 1.1.间接相互制约关系间接相互制约关系 源于资源共享源于资源共享 若一个进程要求使用某一资源，而该资源正被另一个进程使若一个进程要求使用某一资源，而该资源正被另一个进程使用，并且这一资源不允许两个进程同时访问，那么该进程只有用，并
2、且这一资源不允许两个进程同时访问，那么该进程只有等待，只有这一资源释放后才能使用。等待，只有这一资源释放后才能使用。2.2.直接相互制约关系直接相互制约关系 源于进程间的合作源于进程间的合作 一组进程分工协作，在执行的先后次序有约束，在一些关键一组进程分工协作，在执行的先后次序有约束，在一些关键点上协调工作。若一个进程运行到某点时，在尚未收到另一协点上协调工作。若一个进程运行到某点时，在尚未收到另一协作进程发来的信息前应阻塞自己，等协作进程发来消息后方可作进程发来的信息前应阻塞自己，等协作进程发来消息后方可继续执行。继续执行。进程进程资源资源进程进程进程进程进程进程2n进程间这种相互依赖又相互
3、制约，相互合作又相互竞进程间这种相互依赖又相互制约，相互合作又相互竞争的关系，主要表现在进程互斥和进程同步两方面争的关系，主要表现在进程互斥和进程同步两方面二、进程互斥二、进程互斥引例：引例： 宿舍电话的使用宿舍电话的使用 打印机的使用打印机的使用1 1、临界资源、临界资源 一次仅允许一个进程使用的资源称为临界资源。一次仅允许一个进程使用的资源称为临界资源。 引例中的电话和打印机都属于临界资源。还有光盘引例中的电话和打印机都属于临界资源。还有光盘刻录机、绘图仪、共享变量、共享的数据结构等等也刻录机、绘图仪、共享变量、共享的数据结构等等也是临界资源。是临界资源。2 2、临界区：、临界区： 每个进
4、程中访问临界资源的那段程序段称为临界每个进程中访问临界资源的那段程序段称为临界区。（临界段）区。（临界段）3例：统计两个进程例：统计两个进程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:count=R1;虽然两个进程各自都执行了对虽然两个进程各自都执行了对count加加1的操作，但结果
5、为何的操作，但结果为何count只增加只增加1？count是临界资源，是临界资源，P1、P2访问访问count的两个程序段就是临界的两个程序段就是临界区，两个进程必须互斥的进入临界区区，两个进程必须互斥的进入临界区,否则就可能出与时间有关的否则就可能出与时间有关的错误错误. .4、进程互斥、进程互斥n当某一进程正在访问某临界区时，就不允许其它进程当某一进程正在访问某临界区时，就不允许其它进程进入，否则就会发生无法估计的错误。进程之间的这进入，否则就会发生无法估计的错误。进程之间的这种相互制约的关系称为进程互斥。种相互制约的关系称为进程互斥。4 4、进入临界区的准则：、进入临界区的准则：每次至多
6、有一个进程进入临界区内执行；每次至多有一个进程进入临界区内执行；若若已已有有进进程程在在临临界界区区中中，试试图图进进入入此此临临界界区区的的其其他他进程应等待；进程应等待；进进入入临临界界区区的的进进程程应应在在有有限限时时间间内内退退出出，以以便便让让等等待队列中的一个进程进入。待队列中的一个进程进入。5三、进程同步引引例例：两两位位同同学学约约好好星星期期天天去去玩玩，早早上上8:00在在校校门门口口，不不见见不不散散。当当一一个个同同学学先先来来到到校校门门口口，要要等等另另一一个个同同学，到齐后一起去玩。学，到齐后一起去玩。n互互斥斥的的概概念念来来自自于于诸诸进进程程对对临临界界资
7、资源源的的竞竞争争，同同步步来来源源于于多多个个进进程程的的合合作作。在在人人类类社社会会中中竞竞争争与与合合作作是永恒的。是永恒的。n进进程程同同步步：几几个个进进程程相相互互合合作作，一一个个进进程程到到达达某某点点后后，若若另另一一进进程程尚尚未未完完成成某某些些操操作作，就就必必须须停停下下来来等等待待，只只有有等等另另一一进进程程的的这这些些操操作作完完成成了了才才能能继继续续执行。执行。6例：计算例：计算fun1(X)*fun2(y)fun1(X)*fun2(y)两进程合作完成任务两进程合作完成任务进程进程1 1：计算：计算fun1(X)fun1(X)。进程进程2 2：计算：计算f
8、un2(X)fun2(X)；与进程；与进程1 1结果相乘。结果相乘。进程进程1 1和进程和进程2 2并发执行。并发执行。73.2 3.2 进程互斥的实现进程互斥的实现一、实现进程互斥的软件算法一、实现进程互斥的软件算法n现现在在很很少少用用软软件件方方法法解解决决互互斥斥，但但通通过过学学习习软软件件解解法法能能使使读读者者了了解解到到，在在早早期期进进程程互互斥斥问题的解决并不是一件很简单的事。问题的解决并不是一件很简单的事。8尝试尝试 (1) (1)bool inside1=false; /P1不在其临界区内不在其临界区内bool inside2=false; /P2不在其临界区内不在其临
9、界区内cobegin process P1( ) process P2( ) while(inside2); while(inside1); inside1=true; inside2=true; 临界区临界区; 临界区临界区; inside1=false; inside2=false; coend P1P1和和P2P2可能同时进入临界区可能同时进入临界区9尝试尝试 (2) (2)bool inside1=false; /P1不在其临界区内不在其临界区内bool inside2=false; /P2不在其临界区内不在其临界区内cobeginprocess P1( ) process P2( )
10、 inside1=true; inside2=true; while(inside2); while(inside1);临界区临界区; 临界区临界区; inside1=false; inside2=false; coendP1P1和和P2P2可能永远等待。可能永远等待。10processP0()inside0=true;turn=1;while(inside1&turn=1);临界区临界区;inside0=false;processP1()inside1=true;turn=0;while(inside0&turn=0);临界区临界区;inside1=false;cobegincoendboo
11、linside2;inside0=false;inside1=false;enum0,1turn;Peterson算法11n为为 每每 一一 进进 程程 设设 标标 志志 位位 insideiinsidei， 当当insidei=trueinsidei=true时时，表表示示进进程程pipi要要求求进进入入，或或正正在在临临界界区区中中执执行行。此此外外再再设设一一个个变变量量turnturn，用用于于指示允许进入的进程编号。指示允许进入的进程编号。n进程进程0 0为了进入先置为了进入先置inside0=trueinside0=true，并置，并置turnturn为为1 1，表示应轮到，表示应
12、轮到p1p1进入。接着再判断进入。接着再判断inside1&turn=1inside1&turn=1的条件是否满足的条件是否满足, ,若不满足则若不满足则可进入。或者说当可进入。或者说当inside 1 =falseinside 1 =false或者或者turn=0turn=0时，进程可以进入。前者表示时，进程可以进入。前者表示p1p1未要求进未要求进入，后者表示仅允许入，后者表示仅允许p0p0进入进入. .12软件解法的缺点软件解法的缺点1. 1. 忙等待忙等待2. 2. 实现过于复杂，需要较高的编程技巧实现过于复杂，需要较高的编程技巧13二、实现进程互斥的硬件设施二、实现进程互斥的硬件设施
13、用软件解决很难，现代计算机大多提供一用软件解决很难，现代计算机大多提供一些硬件指令。些硬件指令。n利用关中断实现进程互斥利用关中断实现进程互斥 n利用利用Test-and-SetTest-and-Set指令实现互斥指令实现互斥 n利用利用swapswap指令实现进程互斥指令实现进程互斥141.1.利用关中断实现进程互斥利用关中断实现进程互斥 n进程进入临界区时关中断，在进程退出临界进程进入临界区时关中断，在进程退出临界区时开中断。区时开中断。n关中断方法简单有效关中断方法简单有效n关中断方法的缺点关中断方法的缺点15（TSTS）指令实现互斥）指令实现互斥TSTS指令指令bool TS(bool
14、 &x) if(x) x=false; return true; else return false; 16TSTS指令实现进程互斥指令实现进程互斥bool s=true;cobeginprocess Pi( ) /i=1,2,.,n while(!TS(s); /上锁上锁 临界区临界区; s=true; /开锁开锁coend 变变量量s s代代表表了了临临界界资资源源的的状状态态，可可把把它它看看成成一一把把锁锁。S S初初值值设设为为truetrue，表表示示没没有有进进程程在在临临界界区区，资资源源可可用用。进进入入临临界界区区前前，首首先先用用TSTS指指令令测测试试s s，若若没没有
15、有进进程程在在临临界界区区，则则可可进进入入，否否则则循循环环测测试试直直至至s s的的值值为为truetrue；当当进进程程退退出出临临界界区区时时，把把s s的值置为的值置为truetrue。 17指令实现进程互斥指令实现进程互斥swapswap指令指令又称交换指令，在又称交换指令，在Intel x86Intel x86中称为中称为XCHGXCHG。功能是交换两个字的内容。功能是交换两个字的内容。voidSWAP(bool&a,bool&b)booltemp=a;a=b;b=temp;18利用利用swapswap实现进程互斥实现进程互斥n为为每每一一临临界界资资源源设设置置一一个个全全局局
16、布布尔尔变变量量locklock，其其初初值值为为falsefalse，表表示示无无进进程程在在临临界界区区内内。在在每每个个进进程程中中有有局局部部布布尔尔变量变量keyikeyi。bool lock=false;cobeginProcess Pi( ) /i=1,2,.,n bool keyi=true; do SWAP(keyi,lock); while(keyi); /上锁上锁 临界区临界区; SWAP(keyi,lock); /开锁开锁coend19n实现进程互斥的软件算法太过复杂，效率实现进程互斥的软件算法太过复杂，效率低下；低下；n实现进程互斥的硬件方法虽简单有效，但实现进程互斥
17、的硬件方法虽简单有效，但采用忙式等待，白白浪费采用忙式等待，白白浪费cpucpu时间；将测试时间；将测试能否进入临界区的责任推卸给各进程，会能否进入临界区的责任推卸给各进程，会削弱系统的可靠性，加重用户的编程负担；削弱系统的可靠性，加重用户的编程负担；且这些方案只能解决进程互斥问题，却不且这些方案只能解决进程互斥问题，却不能解决进程同步问题。能解决进程同步问题。203.3 3.3 信号量与信号量与PVPV操作操作一、信号量的概念一、信号量的概念 信信号号量量的的概概念念是是由由荷荷兰兰科科学学家家DijkstraDijkstra于于19651965年提出的。年提出的。 n管理和控制铁路和公路交
18、通的重要工具是信号灯，利管理和控制铁路和公路交通的重要工具是信号灯，利用信号灯的颜色控制各种车辆的正常通行。在操作系用信号灯的颜色控制各种车辆的正常通行。在操作系统中引入了信号灯（信号量）的概念，让多个进程通统中引入了信号灯（信号量）的概念，让多个进程通过信号量展开交互。过信号量展开交互。211.信号量的定义是一个结构型数据结构，定义如下：是一个结构型数据结构，定义如下： struct semaphore struct semaphore int value; / int value; /信号量的值信号量的值 struct pcb *list; / struct pcb *list; /信号量
19、队列的头指针信号量队列的头指针 信号量说明：信号量说明： semaphore s; semaphore s;n信信号号量量必必须须置置一一次次且且只只能能置置一一次次初初值值，初初值值不不能能为为负负数。数。n对信号量只能执行对信号量只能执行P P、V V操作操作22、V V操作操作对信号量仅能执行对信号量仅能执行P、V操作。操作。n对对信信号号量量的的P P操操作作记记为为：P(S)P(S)，P P操操作作是是一一个个原原子操作。子操作。n对对信信号号量量的的V V操操作作记记为为：V(S), V(S), V V操操作作是是一一个个原原子操作。子操作。在在实实际际系系统统中中，一一般般情情况
20、况下下是是由由机机器器硬硬件件提提供供P P、V V操操作作的的指指令令，当当然然是是原原子子操操作作，若若机机器器不不提提供供P P、V V操操作的指令，则操作系统提供作的指令，则操作系统提供P P、V V操作原语。操作原语。23P(s)：-；若若0，则执行，则执行P(s)的进程继续执行；的进程继续执行；若若0，则执行，则执行V(s)的进程继续执行；的进程继续执行；若若0，则执行，则执行V(s)的进程从等待信号量的进程从等待信号量s的阻塞队列的阻塞队列中唤醒头一个进程，然后自己继续执行。中唤醒头一个进程，然后自己继续执行。 操作系统正是利用信号量的状态对进程和资源进行管理。从物操作系统正是利
21、用信号量的状态对进程和资源进行管理。从物理意义上理解，理意义上理解，P P操作相当于申请资源；操作相当于申请资源；V V操作相当于释放资源。操作相当于释放资源。24二、用信号量实现进程互斥1.两个进程间的互斥两个进程间的互斥 semaphore S； S =1； cobegin Process P1( ) Process P2( ) P（S） P（S） V（S） V（S） coend临界区临界区临界区临界区25对于两个并发进程，互斥信号量的值仅取对于两个并发进程，互斥信号量的值仅取1、0和和-1三个值三个值若若S1表示没有进程进入临界区表示没有进程进入临界区若若S0表示有一个进程进入临界区表示
22、有一个进程进入临界区若若S-1表示一个进程进入临界区，另一个进程等待进入。表示一个进程进入临界区，另一个进程等待进入。26例：有一个售票厅只能容纳例：有一个售票厅只能容纳300300人，当少于人，当少于300300人时，人时，可以进入购票；否则在外等待。若将每一个购票者看可以进入购票；否则在外等待。若将每一个购票者看作一个进程，请用作一个进程，请用P P、V V操作编程实现。操作编程实现。semaphore Ssemaphore S；S=300S=300；Process Pi()Process Pi()（i=1i=1，2 2，3 3，） P(S)P(S)； 进入购票厅；进入购票厅； 购票；购票
23、； 离开购票厅；离开购票厅； V(S)V(S)； 27思考：思考：对于对于n n个并发进程，如何实现互斥；个并发进程，如何实现互斥；信号量的取值范围是什么，有什么含义。信号量的取值范围是什么，有什么含义。设置互斥信号量设置互斥信号量S=m（m为某种临界资源可用数量）为某种临界资源可用数量）cobeginprocessP1processP2processpnP（S）P（S）P（S）V（S）V（S）V（S）coend临界区临界区临界区临界区临界区临界区互斥信号量联系一组并发进程，各进程对此信号量互斥信号量联系一组并发进程，各进程对此信号量执行执行P P、V V操作，因此又称为公用信号量。操作，因此
24、又称为公用信号量。28n信号量取值范围：信号量取值范围：mm-nmm-nn信号量的含义：信号量的含义： S0 S0表示有表示有S S个资源可用个资源可用 S=0 S=0表示无资源可用表示无资源可用 S0 S0则则| S | S |表示表示S S等待队列中的进程个数等待队列中的进程个数29三、用信号量实现进程的同步三、用信号量实现进程的同步1.1.进程同步模型进程同步模型 进程进程P1P1到达到达L1L1这一点时，若进程这一点时，若进程P2P2还未执行到还未执行到L2L2点，进程点，进程P1P1就必须停下来等待，等到进程就必须停下来等待，等到进程P2P2到达到达L2L2这一点时，这一点时，P1P
25、1才能继续运才能继续运行。也就是进程行。也就是进程P1P1在在L1L1这一点要与进程这一点要与进程P2P2同步。同步。（P1P1等待等待P2P2）semaphores；S=0CobeginprocessP1（）（）processP2（）（）L1:P(s)L2:V(s)coend总结：总结：P1P1在在L1L1点等待点等待P2P2进程执进程执行到行到L2L2点才能继续执行。点才能继续执行。设置信号量设置信号量s=0s=0P1P1进程进程L1L1点：点：P(S)P(S)P2P2进程进程L2L2点：点：V(S)V(S)30在操作系统中，同步有各种各样，归纳起来有两类：在操作系统中，同步有各种各样，归
26、纳起来有两类：n保证一组合作进程按确定的次序执行保证一组合作进程按确定的次序执行n保证共享缓冲区的合作进程的同步。保证共享缓冲区的合作进程的同步。2.2.合作进程的执行次序合作进程的执行次序若干个进程为了完成一个共同任务而并发执行，若干个进程为了完成一个共同任务而并发执行，在这些进程中，有些进程之间有次序的要求，有些在这些进程中，有些进程之间有次序的要求，有些进程之间没有次序的要求。进程之间没有次序的要求。为了描述方便，可以用为了描述方便，可以用一个图来一个图来描述诸进程合描述诸进程合作完成某一任务的次序。作完成某一任务的次序。进程流图进程流图3132进程流图是实际例子抽象出来的。进程流图是实
27、际例子抽象出来的。例：例：(a+b)*(c+d)+c*f(a+b)*(c+d)+c*fP2P1P3P4P5SFP1P2P3P4P533例：试用信号量实现这三个并发进程按确例：试用信号量实现这三个并发进程按确定的次序执行。定的次序执行。a、分析进程的同步关系、分析进程的同步关系进进程程P1、P2可可并并发发执执行行，P3的的执执行行必必须等待须等待P1、P2都完成后才能开始执行。都完成后才能开始执行。b、设置信号量，说明含义、初值、设置信号量，说明含义、初值。s13=0表示进程表示进程P1尚未执行完成；尚未执行完成；s23=0表示进程表示进程P2尚未执行完成；尚未执行完成；c、写出程序描述、写出
28、程序描述3435例：试用信号量实现这三个进程的同步。例：试用信号量实现这三个进程的同步。SemaphoreSB，SC；SB=0；SC=0；cobeginPa（）（）Pb（）（）Pc（）（）P(SB);P(SC)；V(SB);V(SC);coend363.3.共享缓冲区的合作进程的同步共享缓冲区的合作进程的同步设设有有一一个个缓缓冲冲区区buffer，大大小小为为一一个个字字节节，某某计计算算进进程程和和打打印印进进程程共共用用，CP进进程程不不断断产产生生字字符符，送送buffer，IOP进进程程从从buffer中取出字符打印。中取出字符打印。如如不不加加控控制制，会会有有多多种种打打印印结结
29、果果，这这取取决决于于这这两两个个进进程程运运行行的的相相对对速速度度。在在这这众众多多的的打打印印结结果果中中，只只有有CP、IOP进进程程的的运运行行刚刚好好匹匹配配的的一一种种是是对对的的，其其它它均均为为错错误误，并并且且不不能重现。能重现。37要要保保证证打打印印结结果果的的正正确确，CP、IOP必必须须遵遵循循以以下下同步规则：同步规则：(1)当当CP把把结结果果送送入入buffer后后，IOP才才能能从从buffer中中取取，否则否则IOP必须等待；必须等待；(2)当当IOP从从buffer中中取取走走数数据据后后，CP才才能能将将新新产产生生数数据送据送buffer，否则也必须
30、等待。，否则也必须等待。n解决这个问题的步骤：解决这个问题的步骤：(1)分析问题，弄清楚同步关系，如上分析；分析问题，弄清楚同步关系，如上分析；(2)设置信号量，说明含义、初值；设置信号量，说明含义、初值；(3)写出程序描述。写出程序描述。3839四、互斥和同步对信号量操作方法的差异四、互斥和同步对信号量操作方法的差异 互斥和同步都是通过对信号量的互斥和同步都是通过对信号量的P P、V V操作来实现的，但操作来实现的，但这两种控制机制对信号量的操作策略是不同的。这两种控制机制对信号量的操作策略是不同的。n互斥的实现：互斥的实现： 是不同进程对同一信号量进行是不同进程对同一信号量进行P P、V
31、V操作。进入临界操作。进入临界区之前执行区之前执行P P操作，退出临界区后执行操作，退出临界区后执行V V操作。操作。n同步的实现：同步的实现： Pa Pa进程要同步等待进程要同步等待PbPb需设置一信号量，需设置一信号量，PaPa进程中实进程中实行行P P操作，操作，PbPb进程实行进程实行V V操作。操作。 若进程若进程PbPb也要同步等待也要同步等待PaPa，则要设置另一个信号量。，则要设置另一个信号量。n操作必须成对出现，有一个操作必须成对出现，有一个P P操作就一定有一个操作就一定有一个V V操作操作 当为互斥操作时，它们同处于同一进程当为互斥操作时，它们同处于同一进程 当为同步操作
32、时，则不在同一进程中出现当为同步操作时，则不在同一进程中出现40五、经典的进程同步、互斥问题五、经典的进程同步、互斥问题1.1.生产者生产者消费者问题消费者问题问题描述：问题描述：n有有m m个生产者个生产者和和n n个消费者个消费者，它们共享，它们共享可存放可存放k k件产品件产品的缓冲区的缓冲区。n只要缓冲区未满，生产者就可以把产品送入缓冲区只要缓冲区未满，生产者就可以把产品送入缓冲区; ;n只要缓冲区未空，消费者就可以从缓冲区中取走物只要缓冲区未空，消费者就可以从缓冲区中取走物品。品。消费者消费者0 1 2 k-1生产者生产者消费者消费者生产者生产者生产者生产者41n著著名名的的生生产产
33、者者-消消费费者者问问题题是是计计算算机机操操作作系系统统中中并并发发进进程程内内在在关关系系的的一一种种抽抽象象，是是典典型型的进程同步问题。的进程同步问题。n在在操操作作系系统统中中，生生产产者者进进程程可可以以是是计计算算进进程程、发发送送进进程程；而而消消费费者者进进程程可可以以是是打打印印进进程程、接收进程等等。接收进程等等。n解解决决好好生生产产者者-消消费费者者问问题题就就解解决决好好了了一一类类并发进程的同步问题。并发进程的同步问题。42问题分析问题分析n对对于于生生产产者者进进程程：生生产产一一个个产产品品，当当要要送送入入缓缓冲冲区区时时，要要检检查查是是否否有有空空缓缓冲
34、冲区区，若若有有，则则可可将将产产品品送送入缓冲区，并通知消费者进程；否则，等待；入缓冲区，并通知消费者进程；否则，等待；n对对于于消消费费者者进进程程：当当它它去去取取产产品品时时，要要看看缓缓冲冲区区中中是是否否有有产产品品可可取取，若若有有则则取取走走一一个个产产品品，并并通通知知生生产者进程，否则，等待。产者进程，否则，等待。n这种相互等待，并互通信息就是典型的进程同步。这种相互等待，并互通信息就是典型的进程同步。n因此应该设因此应该设两个同步信号量：两个同步信号量： emptyempty：表示可用的空缓冲区的数目，初值为：表示可用的空缓冲区的数目，初值为k k fullfull：表示
35、可以使用产品的数目，初值为。：表示可以使用产品的数目，初值为。n缓冲区是一个临界资源，必须互斥使用，所以另外缓冲区是一个临界资源，必须互斥使用，所以另外还需要设置一个还需要设置一个互斥信号量互斥信号量mutexmutex，其初值为。，其初值为。43问题的解问题的解itemBk;semaphoreempty;empty=k;/可以使用的空缓冲区数可以使用的空缓冲区数semaphorefull;full=0;/缓冲区内可以使用的产品数缓冲区内可以使用的产品数semaphoremutex;mutex=1;/互斥信号量互斥信号量intin=0;/放入缓冲区指针放入缓冲区指针intout=0;/取出缓冲
36、区指针取出缓冲区指针cobeginprocessproducer_i()processconsumer_j()while(true)while(true)produce();P(full);P(empty);P(mutex);P(mutex);take()fromBout;appendtoBin;out=(out+1)%k;in=(in+1)%k;V(mutex);V(mutex);V(empty);V(full);consume();coend44讨论：讨论：n若将生产者进程中两个若将生产者进程中两个P P操作交换次序，那么操作交换次序，那么当缓冲区存满当缓冲区存满k k件产品（件产品（em
37、pty=0empty=0，mutex=1mutex=1，full=kfull=k）时，生产者又生产一件产品，将在）时，生产者又生产一件产品，将在P(empty)P(empty)上等待，此时上等待，此时mutex=0mutex=0。消费者进程。消费者进程将在将在P(mutex)P(mutex)上等待。这就导致两进程都处上等待。这就导致两进程都处于无休止的等待状态，造成了死锁。于无休止的等待状态，造成了死锁。n若将消费者进程中两若将消费者进程中两P P操作交换次序，则当缓操作交换次序，则当缓冲区为空时，也会出项上述类似问题。冲区为空时，也会出项上述类似问题。45总结：总结：n操作必须操作必须成对成
38、对出现，有一个出现，有一个P P操作就一定有一个操作就一定有一个V V操作。操作。 当为当为互斥互斥操作时，它们同操作时，它们同处于同一进程处于同一进程。 当为当为同步同步操作时，则操作时，则不在同一进程中不在同一进程中出现。出现。n如果如果两个两个P P操作操作在一起，那么在一起，那么P P操作的顺序至关重要操作的顺序至关重要。 一个同步一个同步P P操作与一个互斥操作与一个互斥P P操作在一起时，操作在一起时，同步同步P P操作在互斥操作在互斥P P操作前。操作前。n而而两个两个V V操作操作在一起时在一起时顺序无关紧要顺序无关紧要。462. 2. 读者读者/ /写者问题写者问题问题描述问
39、题描述有两组并发进程有两组并发进程: : 读者和写者读者和写者, ,共享一个文件共享一个文件F F要求：要求： n允许多个读者同时执行读操作允许多个读者同时执行读操作n只允许一个写者执行写操作只允许一个写者执行写操作n任任一一写写者者在在完完成成写写操操作作之之前前不不允允许许其其它它读读者者或或写写者者工作工作n写写者者执执行行写写操操作作前前，应应让让已已有有的的写写者者和和读读者者全全部部退退出出47问题分析问题分析n读者和写者互斥读者和写者互斥，写者和写者互斥写者和写者互斥访问文件访问文件n设设信号量信号量writeblock，用于实现读写互斥、，用于实现读写互斥、写写互斥地访问文件。
40、写写互斥地访问文件。n另设一个全局变量另设一个全局变量readcount，记录正在读，记录正在读的读者数目。的读者数目。n设置设置信号量信号量mutex，用于使读者互斥地访问，用于使读者互斥地访问共享变量共享变量readcount。48int readcount=0; /读进程计数semaphore writeblock,mutex;writeblock=1; mutex=1;cobeginprocess reader_i( ) process writer_j( ) P(mutex); P(writeblock); readcount+; 写文件; if(readcount=1) V(wri
41、teblock); P(writeblock); V(mutex); 读文件; P(mutex); readcount-; if(readcount=0) V(writeblock); V(mutex); Coend493.3.哲学家就餐问题哲学家就餐问题问题描述问题描述 有有五五个个哲哲学学家家围围坐坐在在一一圆圆桌桌旁旁，桌桌中中央央有有一一盘盘通通心心面面，每每人人面面前前有有一一只只空空盘盘于于，每每两两人人之之间间放放一一把把叉叉子子。每每个个哲哲学学家家思思考考、饥饥饿饿、然然后后吃吃通通心心面面。为为了了吃吃面面，每每个个哲哲学学家家必必须须获获得得两两把把叉叉子子，且且每每人人
42、只只能能直直接接从从自自己己左左边边或或右右边边去去取叉子。取叉子。 50问题分析问题分析n每把叉子都必须互斥使用，因此为每把叉子设每把叉子都必须互斥使用，因此为每把叉子设置互斥信号量置互斥信号量forki(i=0,1,2,3,4),初值均为初值均为1；n当哲学家吃面前必须执行两个当哲学家吃面前必须执行两个P操作，获得自操作，获得自己左边和右边的两把叉子；吃完后必须执行两己左边和右边的两把叉子；吃完后必须执行两次次V操作，放下两把叉子。操作，放下两把叉子。51semaphore fork5;for (int i=0;i5;i+) forki=1;cobegin process philosop
43、her_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); coend52n上上述述解解法法可可能能出出现现永永远远等等待待，有有若若干干种种办办法法可避免死锁：可避免死锁：（1 1）至多允许四个哲学家同时吃；）至多允许四个哲学家同时吃；（2 2）奇奇数数号号先先取取左左手手边边的的叉叉子子，偶偶数数号号先先 取右手边的叉子；取右手边的叉子；（3 3）每每个个哲哲学学家家取取到到手手边边的的两两把把叉叉子子才才吃吃，否则一把叉子也不取。否则一把叉
44、子也不取。533.4 3.4 进程通信进程通信n进程通信进程通信(Interprocess (Interprocess Communication,IPC)Communication,IPC)是指进程之间的信息交是指进程之间的信息交换。换。n信号量及操作实现的是进程之间的低级通讯，信号量及操作实现的是进程之间的低级通讯，所以为低级通讯原语。它只能传递简单的信所以为低级通讯原语。它只能传递简单的信号，不能传递交换大量信息。号，不能传递交换大量信息。n本节介绍本节介绍高级进程通信，是指进程间高效的高级进程通信，是指进程间高效的传送大量数据的通信方式。传送大量数据的通信方式。54进程间通信的方式进程
45、间通信的方式 n信号信号(signal)(signal)通信机制通信机制n管道管道(pipeline)(pipeline)通信机制通信机制 n消息传递消息传递(message passing)(message passing)通信机制通信机制 n信号量信号量(semaphore)(semaphore)通信机制通信机制n共享主存共享主存(shared memory)(shared memory)通信机制通信机制n前两种是前两种是UNIXUNIX最早的版本就提供的进程通信机制。最早的版本就提供的进程通信机制。信号通信机制只能发送单个信号而不能传递数据；信号通信机制只能发送单个信号而不能传递数据；管
46、道通信虽能传送数据，却只能在进程家族内使管道通信虽能传送数据，却只能在进程家族内使用，应用范围有限。用，应用范围有限。55进程通信方式发展进程通信方式发展nUNIXUNIX发发展展历历史史中中，AT&TAT&T的的BellBell与与加加大大伯伯克利的克利的BSDBSD是两大主力。是两大主力。nBellBell致致力力于于改改进进传传统统的的进进程程IPCIPC，形形成成了了SYSTEM SYSTEM IPCIPC机机制制（上上述述后后三三种种通通信信机机制）。制）。nBSDBSD在在改改进进IPCIPC的的同同时时，把把网网络络通通信信规规程程(TCP/IP)(TCP/IP)实实现现到到UN
47、IXUNIX内内核核中中，考考虑虑把把同同一一计计算算机机上上的的进进程程通通信信纳纳入入更更广广的的网网络络范范围围的的进进程程间间通通信信，这这种种努努力力结结果果出出现现了了socketsocket网络通信机制。网络通信机制。 56一、管道通信机制一、管道通信机制n管道通信是管道通信是UNIXUNIX的传统进程通信方式，也是的传统进程通信方式，也是UNIXUNIX发展最有意义的贡献之一。发展最有意义的贡献之一。n所谓管道，是指用于连接一个读进程和一个写进所谓管道，是指用于连接一个读进程和一个写进程的特殊文件，称程的特殊文件，称pipepipe文件。文件。n发发送送进进程程以以字字符符流流
48、形形式式把把大大量量数数据据送送入入管管道道，接接收进程从管道中接收数据，所以叫管道通信。收进程从管道中接收数据，所以叫管道通信。发送进程发送进程接收进程接收进程字符流方式写入读出字符流方式写入读出先进先出顺序先进先出顺序57n管管道道的的实实质质是是一一个个共共享享文文件件，基基本本上上可可借借助助于于文文件件系系统统的的机机制制实实现现，包包括括（管管道道）文文件件的的创创建建、打打开开、关闭和读写。关闭和读写。n但写进程和读进程间的相互协调单靠文件系统机制但写进程和读进程间的相互协调单靠文件系统机制解决不了，读写进程相互同步，必须做到以下几点：解决不了，读写进程相互同步，必须做到以下几点
49、：（1 1）互斥，即一个进程正在使用某个管道写入或读出）互斥，即一个进程正在使用某个管道写入或读出数据时，另一个进程就必须等待；数据时，另一个进程就必须等待；（2 2）发送者和接收者双方必须能够知道对方是否存在）发送者和接收者双方必须能够知道对方是否存在，如果对方已经不存在，就没有必要再发送信息。，如果对方已经不存在，就没有必要再发送信息。（3 3）同步，指当写进程把一定量的数据发送后，便睡）同步，指当写进程把一定量的数据发送后，便睡眠等待，直到读进程把管道中数据取走后，在把它眠等待，直到读进程把管道中数据取走后，在把它唤醒。反之当读进程读空管道时，也被阻塞，直到唤醒。反之当读进程读空管道时，
50、也被阻塞，直到写进程将数据写入管道后，才将它唤醒。写进程将数据写入管道后，才将它唤醒。58二、共享主存通信机制二、共享主存通信机制n在主存中开辟一个公用存储区，要通信的进程把自在主存中开辟一个公用存储区，要通信的进程把自己的虚地址空间映射到共享主存区。发送进程将信己的虚地址空间映射到共享主存区。发送进程将信息写入共享主存区的某个位置上，接收进程可从此息写入共享主存区的某个位置上，接收进程可从此位置读取信息。位置读取信息。 虚存段进程1的虚存空间 虚存段进程2的虚存空间 物理主存共享主存59三、消息传递通信机制三、消息传递通信机制n进程间的数据交换以消息为单位，程序员进程间的数据交换以消息为单位
51、，程序员利用系统的通信原语实现通信。操作系统利用系统的通信原语实现通信。操作系统隐藏了通信的实现细节，简化了通信程序隐藏了通信的实现细节，简化了通信程序编制的复杂性。因而得到广泛应用。编制的复杂性。因而得到广泛应用。60消息传递通信机制消息传递通信机制可分为：可分为：n直直接接通通信信：发发送送进进程程直直接接把把消消息息发发送送给给接接收收者者，并并将将它它挂挂在在接接收收进进程程的的消消息息缓缓冲冲队队列列上上。接收进程从消息缓冲队列中取得消息。接收进程从消息缓冲队列中取得消息。n间接通信：间接通信：发送进程将消息发送到某种中间发送进程将消息发送到某种中间实体中（信箱），接收进程从中取得消
52、息。实体中（信箱），接收进程从中取得消息。也称信箱通信也称信箱通信，在网络中称为电子邮件系统。，在网络中称为电子邮件系统。61思考思考两种方式的主要区别？两种方式的主要区别？前者需要两进程都存在，后者不需要。前者需要两进程都存在，后者不需要。621.1.直接通信的实现直接通信的实现n发送或接收消息的进程必须指出消息发给谁或从谁发送或接收消息的进程必须指出消息发给谁或从谁那里接收消息。至少需要提供两条原语：那里接收消息。至少需要提供两条原语：原语原语sendsend（P P，消息）：把一个消息发送给进程，消息）：把一个消息发送给进程P P原语原语receivereceive（Q Q，消息）：从进
53、程，消息）：从进程Q Q接收一个消息接收一个消息n直接通信的实现直接通信的实现在操作系统空间设置一组缓冲区在操作系统空间设置一组缓冲区。n当发送进程需要发送消息时，执行当发送进程需要发送消息时，执行sendsend系统调用，系统调用，产生访管中断，进入操作系统。产生访管中断，进入操作系统。n操作系统为发送进程分配一个空缓冲区，并将所发操作系统为发送进程分配一个空缓冲区，并将所发送的消息从发送进程送的消息从发送进程copycopy到缓冲区中，然后将该载到缓冲区中，然后将该载有消息的缓冲区连接到接收进程的消息链链尾，如有消息的缓冲区连接到接收进程的消息链链尾，如此就完成了发送过程。此就完成了发送过
54、程。n发送进程返回到用户态继续执行。发送进程返回到用户态继续执行。63n在以后某个时刻，当接收进程执行到在以后某个时刻，当接收进程执行到receivereceive接收原语时，也产生访管中断进入接收原语时，也产生访管中断进入操作系统。操作系统。n由操作系统将载有消息的缓冲区从消息链由操作系统将载有消息的缓冲区从消息链中取出，并把消息内容中取出，并把消息内容copycopy到接收进程空到接收进程空间，之后收回缓冲区，如此就完成了消息间，之后收回缓冲区，如此就完成了消息的接收。的接收。n接收进程返回到用户态继续进行。接收进程返回到用户态继续进行。642.2.间接通信的实现间接通信的实现Send实现
55、实现nsend（MailBox，M）：把信件）：把信件M送到指定的信箱送到指定的信箱MailBox中中步骤：步骤：查找指定信箱查找指定信箱MailBox；若信箱未满，则把信件若信箱未满，则把信件M送入信箱且唤醒送入信箱且唤醒“等信件等信件”者；者；若信箱已满置发送信件进程为若信箱已满置发送信件进程为“等信箱等信箱”状态；状态；65Receive实现实现nreceive（MailBox，X）：从指定信箱）：从指定信箱MailBox中取中取出一封信，存放到指定的地址出一封信，存放到指定的地址X中中步骤：步骤：查找指定信箱查找指定信箱MailBox；若信箱有信，则取出一封信存于若信箱有信，则取出一封信存于X中且唤醒中且唤醒“等信箱等信箱”者；者；若信箱无信件则置接收信件进程若信箱无信件则置接收信件进程“等信件等信件”状态；状态；66信箱的设置信箱的设置n私有信箱私有信箱设置在用户空间设置在用户空间设置在系统空间设置在系统空间n公用信箱公用信箱67
