进程的同步与互斥.ppt

第第第第3 3章章章章 进程管理进程管理进程管理进程管理 3.1 进程的引入进程的引入 3.2 进程的结构进程的结构 3.3 进程控制进程控制 3.4 进程的同步与互斥进程的同步与互斥 3.5 进程间通信进程间通信 3.6 进程调度进程调度 3.7 死锁死锁 3.8 线程线程5/17/20231两种制约关系两种制约关系两种制约关系两种制约关系直接相互制约关系（同步）直接相互制约关系（同步）间接相互制约关系（互斥）间接相互制约关系（互斥）产生的原因产生的原因进程合作进程合作资源共享资源共享 5/17/20232进程的同步（进程的同步（进程的同步（进程的同步（1 1）直接相互制约关系（同步）直接相互制约关系（同步）指系统中一些进程需要相互合作，共同完成一指系统中一些进程需要相互合作，共同完成一项任务项任务,这种协作进程之间相互等待对方消息或信这种协作进程之间相互等待对方消息或信号的协调关系称为号的协调关系称为进程同步进程同步.具体说，并发进程在具体说，并发进程在一些关键点上可能需要互相等待与互通消息，进程一些关键点上可能需要互相等待与互通消息，进程间的相互联系是间的相互联系是有意识有意识的安排的。的安排的。产生的原因产生的原因进程合作进程合作5/17/20233进程的同步（进程的同步（进程的同步（进程的同步（2 2）一般同步问题有两类一般同步问题有两类保证一组合作进程按逻辑需要的执行次序执行保证一组合作进程按逻辑需要的执行次序执行 【例例】司机司机 P1 售票员售票员 P2 REPEAT REPEAT 启动启动 关门关门 正常运行正常运行 售票售票 到站停到站停 开门开门 UNTIL FALSE UNTIL FALSE保证共享缓冲区（共享数据）的合作进程的同步保证共享缓冲区（共享数据）的合作进程的同步 【例例】输入输入进程进程PI缓冲区缓冲区缓冲区缓冲区计算计算进程进程PC打印打印进程进程PP5/17/20234进程的互斥进程的互斥进程的互斥进程的互斥是解决进程间竞争关系是解决进程间竞争关系(间接制约关系间接制约关系)的手段。的手段。间接相互制约关系（互斥）间接相互制约关系（互斥）是指若干个进程同时竞争一个是指若干个进程同时竞争一个需要互斥使用需要互斥使用的资源的资源时，任何时刻最多允许一个进程去使用，其时，任何时刻最多允许一个进程去使用，其他要使用该资源的进程必须等待，直到该资源被释他要使用该资源的进程必须等待，直到该资源被释放。进程间要通过某种中介发生联系，是放。进程间要通过某种中介发生联系，是无意识无意识安安排的。排的。产生的原因产生的原因资源共享资源共享互斥是一种特殊的同步互斥是一种特殊的同步逐次使用互斥资源，也是对进程使用资源次序逐次使用互斥资源，也是对进程使用资源次序上的一种协调。上的一种协调。5/17/20235临界资源临界资源临界资源临界资源 系统中某些资源系统中某些资源一次只允许一一次只允许一个进程使用个进程使用，称这样的资源为临界资，称这样的资源为临界资源或互斥资源或共享变量。源或互斥资源或共享变量。硬件临界资源：打印机、磁带机硬件临界资源：打印机、磁带机软件临界资源：只能排它使用的变量、软件临界资源：只能排它使用的变量、表格、队列表格、队列5/17/20236临界资源实例临界资源实例临界资源实例临界资源实例二人合作存款二人合作存款 count=100;count=100;P PA A S1:N=count;S1:N=count;S2:N=N+100;S2:N=N+100;S3:count=N;S3:count=N;P PB B S4:M=count;S4:M=count;S5:M=M+200;S5:M=M+200;S6:count=M;S6:count=M;执行情况：执行情况：（1）P PA A P PB B,P,PB B P PA A count=400 count=400 （2）S1S1 P PB BS2S3 count=200 count=200（3）S4S4 P PA AS5S6 count=300 count=300 因因count是一个互斥性使用的变量，是一个临界资源是一个互斥性使用的变量，是一个临界资源5/17/20237临界区临界区临界区临界区临界区（临界段）临界区（临界段）在进程中访问临界资源的那段代码区。在进程中访问临界资源的那段代码区。例子例子5/17/20238具有临界资源的进程结构具有临界资源的进程结构 /*进入区进入区*/critical section;/*临界区临界区*/*退出区退出区*/remainder section;/*剩余区剩余区*/entry sectionexit section5/17/20239访问临界区应遵循的原则访问临界区应遵循的原则空闲让进空闲让进 当无进程在临界区时，任何有权使用临界区当无进程在临界区时，任何有权使用临界区的进程可进入。的进程可进入。忙则等待忙则等待 不允许两个以上的进程同时进入临界区。不允许两个以上的进程同时进入临界区。有限等待有限等待 任何进入临界区的要求应在有限的时间内得任何进入临界区的要求应在有限的时间内得到满足。到满足。让权等待让权等待 不能进入临界区的进程应放弃占用不能进入临界区的进程应放弃占用CPUCPU。5/17/202310临界区互斥解决方法临界区互斥解决方法硬件硬件缺点：成本高缺点：成本高软件软件用编程解决用编程解决缺点：缺点：(1)(1)忙等待忙等待 (2)(2)实现过于复杂，需要高的编程技巧实现过于复杂，需要高的编程技巧信号量机制信号量机制5/17/202311信号量机制信号量机制信号量机制信号量机制一类资源一类资源抽象成抽象成S（信号量）（信号量）信号量信号量 只能由只能由P P、V V操作对其进行操作的变量。操作对其进行操作的变量。信号量的使用应注意信号量的使用应注意必须置一次且只能置一次初值。必须置一次且只能置一次初值。初值只能为非负整数，实现互斥时初值为初值只能为非负整数，实现互斥时初值为1 1。只能执行只能执行P P、V V操作。操作。5/17/202312P P、V V操作操作操作操作 P(S)：表示申请一个资源表示申请一个资源。V(S)：表示释放一个资源。表示释放一个资源。P、V操作必须成对出现，有一个操作必须成对出现，有一个P操作就一定操作就一定有一个有一个V操作。操作。5/17/202313整型信号量整型信号量整型信号量整型信号量信信号号量量S：整整型型量量，除除初初始始化化外外仅仅能能通通过过P P、V V操作访问操作访问P P和和V V操作原语定义：操作原语定义：var S:integer;S=1;var S:integer;S=1;P(S)：while S 0 do no-op S=S-1；V(S)：S=S+1；一类资源一类资源抽象成抽象成S（信号量）（信号量）整型量整型量5/17/202314利用整型信号量实现进程互斥利用整型信号量实现进程互斥P(S)V(S)P(S)V(S)5/17/202315记录型信号量记录型信号量记录型信号量记录型信号量记录型信号量记录型信号量信信号号量量S S：记记录录型型数数据据结结构构,一一个个分分量量为为整整型型量量value,value,另另一个分量为信号量队列一个分量为信号量队列 L L；信号量的物理含义信号量的物理含义 当当S.value0：表示可用资源个数表示可用资源个数 当当S.value0：表示可用资源正好用完表示可用资源正好用完 当当S.value0：表示等待该类资源的进程数表示等待该类资源的进程数一类资源一类资源抽象成抽象成S（信号量）（信号量）value 0L=nil信号量的值信号量的值(-2)(-2)信号量队列指针信号量队列指针5/17/202316struct semaphore int value;int*L;void P(struct semaphore S);S.value=S.value 1;/*把信号量减去把信号量减去1*/if S.value 0 then block(S.L);/*若信号量小于若信号量小于0，则调用，则调用P(S)的进的进 程被置成等待信号量程被置成等待信号量S的状态的状态*/物物理理意意义义：申申请请一一个个资资源源，如如果果申申请请成成功功，则则返返回回；如如果果申申请请不不成成功功，则挂在该资源的等待队列上。则挂在该资源的等待队列上。void V(struct semaphore S);S.value=S.value+1;/*把信号量加把信号量加1*/if S.value 0:表示有表示有S.value个资源可用个资源可用S.value=0:表示无资源可用表示无资源可用S.value 0:则则|S.value|表示等待队列中的进程表示等待队列中的进程个数个数 信号量的初值应该大于等于信号量的初值应该大于等于05/17/202319P P、V V操作讨论操作讨论操作讨论操作讨论(2)(2)P(S)：表示申请一个资源表示申请一个资源 V(S)：表示释放一个资源。表示释放一个资源。P、V操作必须成对出现，有一个操作必须成对出现，有一个P操作就一定操作就一定有一个有一个V操作操作P、V操作的优点操作的优点 简单，而且表达能力强，可解决任何互斥问题简单，而且表达能力强，可解决任何互斥问题P、V操作的缺点操作的缺点 不够安全，不够安全，P、V操作使用不当会出现死锁，遇操作使用不当会出现死锁，遇到复杂互斥问题时，实现复杂。到复杂互斥问题时，实现复杂。5/17/202320用用用用P P、V V操作实现互斥操作实现互斥操作实现互斥操作实现互斥信号量初值为信号量初值为1对于两个并发进程，互斥信号量的值仅取对于两个并发进程，互斥信号量的值仅取1、0和和-1三个值三个值：若若mutex.value1表示没有进程进入临界区表示没有进程进入临界区若若mutex.value0表表示示有有一一个个进进程程进进入入临临界界区区若若mutex.value-1表示一个进程进入临界表示一个进程进入临界区，另一个进程等待进入。区，另一个进程等待进入。5/17/202321利用利用P、V操作实现两个进程互斥的模板如下操作实现两个进程互斥的模板如下：struct semaphore mutex;mutex.value=1;mutex.L=nil;cobegin Process P1:Begin M P(mutex);临界区临界区1 V(mutex);M End Process P2:Begin M P(mutex);临界区临界区2 V(mutex);M End coend 5/17/202322使用使用使用使用PVPVPVPV操作实现互斥应注意操作实现互斥应注意操作实现互斥应注意操作实现互斥应注意识别临界资源识别临界资源是否被共享是否被共享;是否有排它性使用要求。是否有排它性使用要求。临界区代码应尽量短小，不能有死循环。临界区代码应尽量短小，不能有死循环。P和和V原语应分别紧靠临界区的头尾。原语应分别紧靠临界区的头尾。P、V操作在同一进程中必须成对出现。操作在同一进程中必须成对出现。5/17/202323思考题思考题思考题思考题 用记录型信号量解决二人存款问题，用用记录型信号量解决二人存款问题，用类类C语言编写进程互斥算法语言编写进程互斥算法。5/17/202324用用用用P P、V V操作实现操作实现操作实现操作实现进程的同步进程的同步进程的同步进程的同步只要信号量初值是一个大于等于只要信号量初值是一个大于等于0的整数就能的整数就能达到同步的目的，就可以直接使用达到同步的目的，就可以直接使用P、V操作操作实现同步实现同步互斥是一种特殊的同步互斥是一种特殊的同步P、V操作既可以实现互斥，也可以实现同步操作既可以实现互斥，也可以实现同步5/17/202325利用信号量实现进程同步的实例利用信号量实现进程同步的实例利用信号量实现进程同步的实例利用信号量实现进程同步的实例设有三个并发执行的进程设有三个并发执行的进程P1、P2、P3，其前趋图如下，其前趋图如下，试用信号量实现这三个进程同步。试用信号量实现这三个进程同步。设两个同步信号量设两个同步信号量S1、S2分别表示进程分别表示进程P2、P3能否开始执行能否开始执行struct semaphore S1,S2=0,0;/*初值均为初值均为0*/cobegin P1:V(S1);V(S2);P2:P(S1);P3:P(S2);coend P1P3P25/17/202326使用使用使用使用PVPVPVPV操作实现同步应注意操作实现同步应注意操作实现同步应注意操作实现同步应注意信号量的设置信号量的设置 信号量的初值信号量的初值 PVPV操作要成对出现，并在不同的进操作要成对出现，并在不同的进程中程中5/17/202327信号量及信号量及信号量及信号量及P P、V V操作讨论操作讨论操作讨论操作讨论(3)(3)(1)P、V操作必须成对出现，有一个操作必须成对出现，有一个P操作就一定有一操作就一定有一 个个V操作操作(2)当为互斥操作时，它们同处于同一进程当为互斥操作时，它们同处于同一进程 当为同步操作时，则不在同一进程中出现当为同步操作时，则不在同一进程中出现(3)如果如果P(S1)和和P(S2)两个操作在一起，那么两个操作在一起，那么P操作的操作的 顺序至关重要。顺序至关重要。一个同步一个同步P操作与一个互斥操作与一个互斥P操作在一起时，同步操作在一起时，同步 P操作在互斥操作在互斥P操作前，而两个操作前，而两个V操作无关紧要。操作无关紧要。5/17/202328PVPV操作实现互斥与同步的模板操作实现互斥与同步的模板操作实现互斥与同步的模板操作实现互斥与同步的模板进程互斥进程互斥 S初值为初值为1 P1 P2 P(S)P(S)临界区临界区1 临界区临界区2 V(S)V(S)在在P1与与P2中设置相同的中设置相同的P、V操作操作进程同步进程同步 S1初值为初值为n，S2初值为初值为0 P1 P2 P(S1)P(S2)段段1 段段2 V(S2)V(S1)5/17/202329经典的进程同步问题经典的进程同步问题 生产者生产者/消费者问题消费者问题 读者读者/写者问题写者问题 哲学家进餐问题哲学家进餐问题5/17/202330生产者生产者/消费者问题消费者问题 生生产产者者消消费费者者问问题题是是一一种种同同步步问问题题的的抽抽象象描描述述。计计算算机机系系统统中中的的每每个个进进程程都都可可以以消消费费（使使用用）或或生生产产（释释放放）某某类类资资源源。这这些些资源可以是硬件资源，也可以是软件资源。资源可以是硬件资源，也可以是软件资源。当当某某一一进进程程使使用用某某一一资资源源时时，可可以以看看作作是是消消费费，称称该该进进程程为为消消费费者者。而而当当某某一一进进程程释放某一资源时，它就相当于生产者。释放某一资源时，它就相当于生产者。5/17/202331生产者生产者/消费者问题消费者问题(描述描述)通过一个公用缓冲池可以把一群生产者通过一个公用缓冲池可以把一群生产者p1,p2,pm，和一群消费者，和一群消费者Q1,Q2,Qn联联系起来。如图系起来。如图:只要缓冲区未满，生产者就可以把产品送入只要缓冲区未满，生产者就可以把产品送入缓冲区缓冲区;只要缓冲区未空，消费者就可以从缓冲区中只要缓冲区未空，消费者就可以从缓冲区中取走物品。取走物品。5/17/202332生产者生产者/消费者问题消费者问题(图示图示)5/17/202333生产者生产者/消费者问题消费者问题(分析分析)为解决生产者消费者问题，应该设两个同步信号量，一个说明为解决生产者消费者问题，应该设两个同步信号量，一个说明空缓冲区的数目，用空缓冲区的数目，用empty表示，初值为缓冲池的大小表示，初值为缓冲池的大小N，另，另一个说明已用缓冲区的数目，用一个说明已用缓冲区的数目，用full表示，初值为。表示，初值为。由于在此问题中有由于在此问题中有i个生产者和个生产者和j个消费者，它们在执行生产活个消费者，它们在执行生产活动和消费活动中要对缓冲池进行操作。由于缓冲池是一个临界动和消费活动中要对缓冲池进行操作。由于缓冲池是一个临界资源，必须互斥使用，所以，另外还需要设置一个互斥信号量资源，必须互斥使用，所以，另外还需要设置一个互斥信号量mutex，其初值为。，其初值为。struct semaphone empty=n,full=0,mutex=1;void buffern-1;int in=,out=0;5/17/202334生产者生产者/消费者问题消费者问题(解决解决)Consumerj:while(1)P(full);P(mutex);从从Bufferout取产品取产品;out=(out+1)mod n;V(mutex);V(empty);消费产品消费产品;coend;cobeginprocedurei:while(1)生产产品生产产品;P(empty);P(mutex);往往Buffer in放产品放产品;in=(in+1)mod n;V(mutex);V(full);5/17/202335生产者生产者生产者生产者/消费者问题消费者问题消费者问题消费者问题(思考思考思考思考)在在生产者进程和消费者进程中，两个生产者进程和消费者进程中，两个P操作操作的执行顺序是否能交换？两个的执行顺序是否能交换？两个V操作的执行操作的执行顺序是否能交换？顺序是否能交换？5/17/202336思考题思考题思考题思考题 两个进程合作完成数据计算和打印工作，两个进程合作完成数据计算和打印工作，计算进程未计算完就不可打印，反之也然，计算进程未计算完就不可打印，反之也然，双方共用一个缓冲区，写出此算法双方共用一个缓冲区，写出此算法。5/17/202337读者读者/写者问题写者问题 有两组并发进程有两组并发进程:读者和写者读者和写者,共享一个数据文件共享一个数据文件 要求：要求：允许多个读者同时执行读操作允许多个读者同时执行读操作不允许读者、写者同时操作不允许读者、写者同时操作不允许多个写者同时操作不允许多个写者同时操作5/17/202338读者读者/写者问题写者问题 如果读者来：如果读者来：1）无读者、写者，新读者可以读）无读者、写者，新读者可以读2）有写者等，但有其它读者正在读，则新读者也可以读）有写者等，但有其它读者正在读，则新读者也可以读3）有写者写，新读者等）有写者写，新读者等 如果写者来：如果写者来：1）无读者、写者，新写者可以写）无读者、写者，新写者可以写2）有读者，新写者等待）有读者，新写者等待3）有其它写者，新写者等待）有其它写者，新写者等待5/17/202339读者写者问题的解法读者写者问题的解法为实现读者和写者、写者和写者之间的互斥，设置一个互斥为实现读者和写者、写者和写者之间的互斥，设置一个互斥信号量信号量Wmutex=1由于由于“读读读读”允许，再设置一个整型变量允许，再设置一个整型变量Readcount表示表示正在读的进程数，初值正在读的进程数，初值Readcount=0由于由于Readcount是一个可被多个读者进程访问的临界资源是一个可被多个读者进程访问的临界资源，所以要为它设置一个互斥信号量所以要为它设置一个互斥信号量Rmutex=1读者读者写者算法如下：写者算法如下：读者：读者：P(Rmutex);if readcount=0 then P(Wmutex);Readcount=Readcount+1;V(Rmutex);读读 P(Rmutex);Readcount=Readcount-1;if Readcount=0 then V(Wmutex);V(Rmutex);写者：写者：P(Wmutex);写写 V(Wmutex);5/17/202340哲学家就餐问题哲学家就餐问题哲学家就餐问题哲学家就餐问题有五个哲学家围坐在一圆桌旁，有五个哲学家围坐在一圆桌旁，桌中央有一盘通心粉，每人面前桌中央有一盘通心粉，每人面前有一只空盘子，每两人之间放一有一只空盘子，每两人之间放一只筷子。只筷子。每个哲学家的行为是思考，感到每个哲学家的行为是思考，感到饥饿，取筷子，然后吃通心粉，饥饿，取筷子，然后吃通心粉，放筷子，思考。放筷子，思考。为了吃通心粉，每个哲学家必须为了吃通心粉，每个哲学家必须拿到两只筷子，并且每个人只能拿到两只筷子，并且每个人只能直接从自己的左边或右边去取筷直接从自己的左边或右边去取筷子。子。筷子是临界资源，要用筷子是临界资源，要用5 5个互斥个互斥信号量来表示这信号量来表示这5 5只筷子。只筷子。5/17/202341哲学家就餐问题解哲学家就餐问题解哲学家就餐问题解哲学家就餐问题解设设fork5为为5 个信号量，初值均为个信号量，初值均为1struct semaphore fork 4;forki:=1;Philosopheri：While(1)思考；思考；P(forki);P(fork(i+1)mod 5)；进食；进食；V(forki);V(fork(i+1)mod 5)；以上解法会出现死锁以上解法会出现死锁,为防止死锁发生可采为防止死锁发生可采取的措施：取的措施：最多允许最多允许4 4个哲学家同时坐在桌子周围个哲学家同时坐在桌子周围给所有哲学家编号，奇数号的哲学家必须首给所有哲学家编号，奇数号的哲学家必须首 先拿左边的筷子，偶数号的哲学家则反先拿左边的筷子，偶数号的哲学家则反仅当一个哲学家左右两边的筷子都可用仅当一个哲学家左右两边的筷子都可用 时，才允许他拿筷子（时，才允许他拿筷子（）5/17/202342思考题思考题思考题思考题 桌桌子子上上有有一一只只盘盘子子，每每次次只只能能放放入入一一只只水水果果。爸爸爸爸专专向向盘盘中中放放苹苹果果，妈妈妈妈专专向向盘盘中中放放桔桔子子，一一个个儿儿子子专专等等吃吃盘盘中中的的桔桔子子，一一个个女女儿儿专专等等吃吃盘盘中中的的苹苹果果。请请利利用用P P、V V操操作作写写出出父父亲亲、母母亲亲、儿儿子子、女女儿儿进进程程的的同同步步算算法。法。5/17/202343思考题思考题思考题思考题分析：在本题中，应设置三个信号量分析：在本题中，应设置三个信号量s s、soso、sa sa，信号量信号量s s表示盘子是否为空，其初值为表示盘子是否为空，其初值为1 1；信信号号量量soso表表示示盘盘中中是是否否有有桔桔子子，其其初初值值为为0 0；信号量信号量sasa表示盘中是否有苹果，其初值为表示盘中是否有苹果，其初值为0 0。同步描述如下：同步描述如下：5/17/202344 struct semaphone s=1,so=0,sa=0;cobegin father();father();mother();mother();son();son();daughter();daughter();coendcoend father()father()p(s);p(s);将水果放入盘中；将水果放入盘中；v(sa);v(sa);mother()mother()p(s);p(s);将水果放入盘中；将水果放入盘中；v(so);v(so);son()son()p(so);p(so);从盘中取出桔子；从盘中取出桔子；v(s);v(s);吃桔子；吃桔子；daughter()daughter()p(sa);p(sa);从盘中取出苹果；从盘中取出苹果；v(s);v(s);吃苹果；吃苹果；5/17/202345