搜索
2020/2/211操作系统第9讲第3章进程管理(3)(进程互斥与同步)主讲：闫新庆2012–032020/2/212第3章进程管理内容提纲3.1认识进程前的准备3.2进程的概念与描述3.3进程状态及其转换3.4进程控制3.5进程互斥与同步3.6进程通信3.7死锁问题3.8线程与超级线程●本章小结●习题2020/2/2133.5进程互斥与同步一、研究进程互斥与同步目的分析一组并发进程在执行过程中，因资源竞争，资源共享引起的对其执行速度的影响，并找出消除其负面影响的条件与方法。二、认识进程互斥与同步相关的重要概念与术语1.临界区●引入背景：为保证并发进程执行结果的正确性。●定义：不允许多个并发进程交叉执行的一段程序称为临界区。◆临界区是由属于不同并发进程的程序段共享公用数据或公用数据变量而引起的，临界区不可能用增加硬件的方法来解决。因此，临界区被称为访问公用数据的那段程序。2020/2/2143.5进程互斥与同步二、认识进程互斥与同步相关的重要概念与术语（2）2．间接制约◆该概念的讨论，是面向互斥而言，面向共享资源（如公用数据和变量），是面向一组并发进程（2个以上）而言，面向其因资源竞争而对其速度影响问题。◆定义：指一组并发进程因资源共享（如公用数据及变量）对其执行速度的影响（制约）的过程。3.进程互斥的定义：◆一组并发进程因间接制约互相合作，互相等待的过程，称为进程的互斥。注释1:是多个进程和一个进程之间的关系，即1对多的关系。注释2:目的是禁止两个以上共享同一资源的并发进程同时进入临界区。PA（慢）是因为PB占用了PA的资源而不得不等待，所以进程PA的慢是因为PB的间接制约而引起的2020/2/2153.5进程互斥与同步二、认识进程互斥与同步相关的重要概念与术语(3)4.直接制约（与同步相关的概念）●该概念的讨论是面向同步而言，是面向2个进程而言，是面向2个进程因资源竞争而对其速度影响问题。●定义：2个在异步环境下的并发进程，各自执行的结果互为对方继续执行的条件，因而引起的对其执行速度限制（影响）的过程，称之为直接制约。注释1：是对两个进程而言，即1对1问题。注释2：目的是禁止因直接制约而引发的死锁现象。2020/2/2163.5进程互斥与同步二、认识进程互斥与同步相关的重要概念与术语（4）5．进程同步定义：2个并发进程，因直接制约，互相发送消息，而进行的相互合作、相互等待，使其按照一定的速度执行的过程叫做进程的同步。6．异步环境：在同一段时间内，一组并发进程，各自以不可预知的速度独立地向前推进，称为进程的异步性或异步环境。（起始时间的随机性)2020/2/2173.5进程互斥与同步三、原语及其类型1．原语定义：●在系统态下，执行某些具有特定功能的程序段称之为原语。（调用核心层子程序的指令）●微软1999年第3版(239页)之计算机词典解释:在OS中，调用核心层子程序的指令，它好像是一条扩充了的机器指令。2．原语类别：（semaphor）简称sem●指令级原语——该程序段（或扩充了的指令）在其执行期间不允许中断，是一个不可再分的指令单位。●功能级原语——该程序段在执行期间不允许并发执行。2020/2/2183.5进程互斥与同步四、信号量1.是用于控制进程执行过程的信号式标志型变量。2．定义：在程序设计中，一种用来对共享系统资源进行控制的信号，即一种标志变量，信标向潜在的用户（进程）指明，某个文件或资源正在使用中，以防止除此之外的其它用户来访问它。引入信号量的目的，是为了服务于PV原语。(744页中的英汉双解词典解释)3．说明:与互斥相关的信号量叫公用信号量，与多个进程有关。与同步相关的信号量叫私有信号量，与2个进程有关。2020/2/2193.5进程互斥与同步五、P.V原语1．是1965年荷兰学者Dijkstra(迪科斯塔)根据火车信号原理，提出来用于解决进程互斥和同步存在问题的模型。P（荷文Passeren，英文Pass简称P原语）调度；V（荷文Venhoog，英文incremane简称V原语）增量。Tannibaum提出相对应的Down(sleep)P和Up(wekeup)V。2．P.V原语是基于对信号量的操作，是两个不可中断的指令级原语操作，是用于解决进程的同步与互斥问题。2020/2/21103.5进程互斥与同步3．用PV原语实现两个进程PA与PB的描述①设Sem的初值为1，取值范围为（0，1，-1）②设Sem=1初值临界区为空，PA、PB都未进入◆当一个进程执行P原语减1操作，Sem=0，表示该进程可以进入临界区。另一个进程也要进入临界区，也必需先进行P操作，若Sem=-1说明已有一个进程进入临界区，另一个进程则进入在等待状态。Sem=0，允许PA、PB有一个进入临界区2020/2/21113.5进程互斥与同步4．P(sem)原语操作（减法操作）●进程进入临界区首先必须进行的操作，即减1操作。●设Sem初值为1●Sem=Sem-1，Sem的结果只可能是0，或-1●若≥0，则进程调入进占临界区，访问共享资源。第一次进程进行P操作之后，Sem=０，说明临界区未占用，则该进程可以进占临界区。●第2个进程欲进入，也要先进行P操作，Sem=－1，则说明临界区已占用，则该进程不能进占临界区，而后转入阻塞队列。第3个..．….第n个欲进入的进程操作，也要先进行P操作．．！！2020/2/2112N3.5进程互斥与同步Sem=0入口Sem=Sem-1转进程调度，该进程进入临界区，进占相应资源返回到进程的下一步将该进程阻塞转进程调度执行其它进程Y图3.11Ｐ原语操作流程2020/2/21133.5进程互斥与同步5．V(sem)原语操作（加法操作）●进程退出临界区必须进行的操作，即Sem=Sem+1操作。●若Sem=0，则从阻塞队列中唤醒一进程，返回到原进程中断处继续执行或转入进程调度。●若无后续进程继续进行，系统则令Sem=1有无Sem=Sem+1=－1，－2，－3，－4，－5之可能？？？？2020/2/21143.5进程互斥与同步图3.12Ｖ原语操作流程sem=sem+1是从阻塞队列中唤醒等待队列中的一个进程返回或转进程调度s≤0入口返回否2020/2/21153.5进程互斥与同步七、互斥实现的条件（篮球竞争问题）●如果一个进程在执行期间，访问公用资源，若允许发生中断，则有可能导致前后计算出现不一致，为防止问题出现，需满足如下条件：1.空则让进，只允进1——指临界区空闲，允许一个进程进入。2.内可阻外，外不相扰——临界区只允许一个进程访问公用资源，临界区之外的其它进程互相之间不发生阻挠。3.限时等待——在限定时间内，必须进入临界区，以防止死锁发生。死锁是指各并发进程彼此相互等待对方所拥有的资源，且在得到对方资源之前，不会释放自己所拥有资源之现象。4.让权等待——当进程不能进入临界区时，应即通知CPU，以免陷入盲等。2020/2/21163.5进程互斥与同步八、互斥的负面影响，解决的途径与方法目的在于避免因进程并发可能导致结果不可再现1．软件的方法●公用变量整型法●数组法●变量与数组混合算法软件的方法从理论上行的通，在方法上也有解决的途径，但却难以实现，因为要保证下一个并发进程的连续性，不被别的进程中断，需要对执行的下一步进行判断，从而导致计算机系统的整体性能下降，因而软件的方法是不可取的。2.硬件的方法为全局和每个硬件设置一个布尔变量（即逻辑值的真假）2020/2/21173.5进程互斥与同步九、实现进程互斥的PV原语操作1.解决方案，使用PV原语加信号量的方法2.任一进程要获取某一共享资源，必须通过临界区来判定是否具有获取独占共享资源的资格。3.任一进程在申请某一共享资源时，必须首先进行P操作。4.Sem初值为1。5.P操作步骤:设P为某一组进程P1、P2、P3、P4，申请某一共享资源，依序进行P1操作：2020/2/21183.5进程互斥与同步5.P操作步骤（续）（1）Sem=Sem-1=0（2）P1进占临界区，即进占申请的某一共享资源，在P1未退出占有的资源时，依序进行P2、P3、P4操作，依次对Sem进行减一操作，则Sem＜0，P2、P3、P4被阻塞。●请问1：的値会否出现-1，-2，-3，-4的问题？●请问2：P操作如何设计，才能避免交叉使用同一资源而引起结果不可再现性。●请问3：此时强行置Sem=-1，结果如何？2020/2/21193.5进程互斥与同步九、实现进程互斥的PV原语操作(2)6.V操作步骤（1）任一进程完成P操作，独占某一共享资源，使用完毕后，必须立即退出，退出时必须进行V操作，即Sem+1操作。Sem=Sem+1=0（2）若Sem=0，则进程调度从就绪队列选一进程进占CPU。（3）V操作完成之后,不会出现Sem＜0的情况？？？2020/2/21203.5进程互斥与同步十、实现进程同步的PV原语操作（1）●面向2个进程，即乒乓问题）1．条件（以计算进程PA和输出进程PB为例）(1)PA必须向缓冲区发送一个数据，PB才能从中取出一个数据，取须有之，无则不取。(2)空则可发，满则停止。(3)FIFO算法。（先进先出算法）2020/2/21213.5进程互斥与同步十、实现进程同步的PV原语操作（2）2．用PV原语实现进程同步⑴同步是解决两个进程（PA、PB）因共享同一资源因直接制约产生的死锁问题，所谓同步，是两个进程各自执行的结果互为对方执行条件。⑵同步所讨论的是进程1对1问题，使用的信号量称为私用信号量。虽然通过每一步操作可以解决问题，但会浪费大量的CPU资源，因此而引起系统效率的大幅度降低。????????2020/2/2122223.5进程互斥与同步十、实现进程同步的PV原语操作（3)(3)解决步骤①设置私用信号量Sem，并为其赋初值②用同步原语（发送和接收）+信号量（私用）解决问题(4)例:PA（计算进程）PB（打印进程）●计算进程为Sem(A)=n，n表示有n个缓冲区●打印进程为Sem(B)=0，表示无数据可取●PA向缓冲区发送一个数据，则Sem(A)=Sem(A)-1，Sem(A)=0，缓冲区满。●PA同步原语向PB发送一个消息●Sem(B)进行n次V操作，当Sem=n，说明缓冲区空，向PA发送消息，PA可继续向缓冲区发送数据，直到发送与接收完毕。2020/2/21233.5进程互斥与同步十一、互斥的加锁实现1.实现并发进程的互斥。只需把临界区中的各个过程按不同的时间排列调用就可以实现并发进程的互斥。但事实上这是不可能的。因为这要求该组并发进程中的每个进程事先知道其他并发进程与系统的动作，由用户程序执行开始的随机性可知，这是不可能的。2.一种可能的办法是对临界区加锁以实现互斥。当某个进程进入临界区之后，它将锁上临界区，直到它退出临界区时为止。并发进程在申请进入临界区时，首先测试该临界区是否是上锁的。如果该临界区已被锁住，则该进程要等到该临界区开锁之后才有可能获得临界区。2020/2/21243.5进程互斥与同步十一、互斥的加锁实现3.设临界区的类名为Ｓ。为了保证每一次临界区中只能有一个程序段被执行，又设锁定位key［Ｓ］。key［Ｓ］表示该锁定位属于类名为Ｓ的临界区。加锁后的临界区程序描述如下：lock(key［Ｓ］)〈临界区〉unlock(key［Ｓ］)设key［Ｓ］=1时表示类名为Ｓ的临界区可用，key［Ｓ］=0时表示类名为Ｓ的临界区不可用。则，unlock(key［Ｓ］)只用一条语句即可实现。即：key［Ｓ］←1不过，由于lock(key［Ｓ］)必须满足key［Ｓ］=02020/2/21253.5进程互斥与同步4.一种简便的实现方法是：lock(x)=beginlocalvrepeatv←xuntilv=1x←0end这种实现方法是不能保证并发进程互斥执行所要求的准则(3)的。因为当同时有几个进程调用lock(key［Ｓ］)时，在x←0语句执行之前，可能已有两个以上的多个进程由于key［Ｓ］=1而进入临界区。为解决这个问题有些机器在硬件中设置了“测试与设置指令，保证第一步和第