《操作系统》 8并发性：互斥和同步课件

8.5.2信箱通信第8章并发性：互斥和同步8.1互斥和同步8.1.1互斥和临界区8.1.2同步8.2实现互斥的方法讨论8.2.1实现互斥的硬件方法8.2.2实现互斥的软件方法8.3信号量与P、V操作8.3.1信号量与P、V操作定义8.3.2用P、V操作实现互斥8.3.3用P、V操作实现同步8.3.4用P、V操作实现资源分配8.3.5管程8.4互斥、同步的样例分析8.4.1读者-写者问题8.4.2哲学家就餐问题8.4.3理发师理发问题8.5高级进程通信8.5.1消息缓冲通信本章目录某用户编写进程p1用于存款，进程p2用于取款。它们都访问变量balance表示的余额：p1用于增加balance，p2用于减少balance。p1和p2的几条汇编指令代码框架如下（其中x1、x2分别是p1和p2的临时变量）：p1的代码框架：p2的代码框架：…………loadR1,balanceloadR1,balanceloadR2,x1loadR2,x2addR1,R2subR1,R2storeR1,balancestoreR1,balance…………8.1互斥和同步8.1.1互斥和临界区进程间的间接制约关系1.系统中有这样的一类资源，哪个进程先用它、哪个进程后用它没有什么关系，但不能同时使用。即在一个进程使用时，另一个进程不能使用，否则会导致错误。这种由于使用具有“排他性”资源、而对进程的执行产生影响，使它们间产生了的关系，就是进程间所谓的“间接制约”关系。.例8-1：p2读balance的值（应该和p1读出的值一样）到R1，读x2的值到R2，然后计算（在寄存器R1里的）balance和（在寄存器R2里的）x2的差，并将这个差值（在寄存器R1里）回存到变量balance；p1中断时，运行现场寄存器（R1、R2）里的值被保存到PCB1中；P1的执行：…loadR1,balanceloadR2,x1addR1,R2storeR1,balance…时钟中断P2的执行：…loadR1,balanceloadR2,x2subR1,R2storeR1,balance…时钟中断.代码单独执行时，都会正确地工作。关键是如果两个进程在系统中并发地运行，就可能会发生灾难性的错误。比如如果两个进程的执行有如图所示的顺序。.这时，p1在执行到指令：“loadR2,x1”后，被时钟中断。随后调度到p2执行。在这个特定的运行情景下，会发生下面的动作序列：(1)(2)(3)又由于时钟中断，使p1最终得到执行，依据PCB1恢复寄存器R1和R2后，计算（在寄存器R1里的）balance与（在寄存器R2里的）x1的和，但因为balance还是p2执行前被保存在寄存器R1里的旧值，因此计算时并没有考虑到p2已经把它改变了；(4)最后的结局是balance里面的值没有正确反映出用户存、取款的情况。.进程间因资源共享（这里的资源体现为是一个公共变量）而产生间接制约关系时，它们随意的并发执行顺序不可能保证运行结果的正确。互斥：如果有一个进程在临界区内执行，欲进入临界区的其他进程只能在临界区外等待进入。2.互斥和临界区例8-1中的进程p1和p2之所以会出问题，不在于它们个体的行为，它们的个体行为都是没有问题的（p1和p2的程序编写是正确的），问题在于“共享”，在于大家都要竞争使用这种共享的资源。.计算机中，凡涉及共享变量、共享内存区、共享队列（如就绪队列）、共享文件及共享任何资源的情况时，都有可能引发类似的问题。既要允许进程共享资源，又要阻止错误的发生，唯一的办法是保证进程“互斥”地使用资源，即确保当一个进程在使用一个共享资源时，其他进程不能同时去使用。..进程程序中，涉及访问共享资源的程序段，称为“临界区（CS）”，只能排他使用的资源称为“临界资源”。为了保证在临界资源上操作的正确性，需遵循下面的3个要求：.(1)(2)有空让进：如果没有进程在临界区、且有进程希望进入临界区，那么应该立即允许其中的一个进程进入临界区。(3)有限等待：进入临界区的进程，应在有限时间内完成并立即离开临界区，以便能够让其他的进程有机会进入临界区。请求进入临界区的代码段，称为“进入区”，任务是判定是否有进程在临界区里。如果有，则等待进入；否则才能允许进入临界区。.如图所示，给出了临界区互斥时进程的行为。进程A在时刻T1进入临界区。稍后，在时刻T2进程B试图进入临界区。但是由于进程A已经在临界区内，因此进程B被阻挡不得进入，直到时刻T3进程A离开临界区，进程B才被允许进入临界区，并在时刻T4离开临界区。进程A：进程B：A进入临界区A离开临界区B试图进入临界区B进入临界区B离开临界区T1T2T3T4时间B被阻塞.因此，如果进程程序中有临界区，那么其设计应该包括如下的三个部分：(1)(2)(3)请求退出临界区代码段，称为“退出区”，任务是判定是否有进程在等待进入临界区。如果有，就要唤醒它们，给予进入的机会。其他代码段。返回目录GET：负责从文件F中按照顺序读出记录，送到输入缓冲区R；8.1.2同步1.为保证任务的顺利进行，有时必须协调进程相互间使用资源的顺序：在一些进程没有使用该资源前，另一些进程不能使用该资源。即必须保证一些进程先使用资源，另一些进程才能使用该资源，否则进程的执行就要出现问题。这种由于进程间使用资源次序而产生的制约，就是进程间的所谓“直接制约”关系。进程间的直接制约关系.例8-2：编写复制n个记录的程序，它把文件F中的记录依次先读到输入缓冲区R，再从R拷贝到输出缓冲区T，最后写到文件G中。假定R和T的大小正好存放一个记录，如图所示。记录1记录2记录nGETCOPYPUT文件F记录1记录2记录n文件G输入缓冲区R输出缓冲区T解：可编写三个进程GET、COPY、PUT互相配合完成这一工作：(1)(2)COPY：负责把输入缓冲区R中的记录拷贝到输出缓冲区T中；(3)PUT：负责从输出缓冲区T中读出一个记录，然后依照顺序写入文件G。记录3记录4记录n文件F记录2记录1文件GRT记录1GETPUT记录1记录1文件GRT记录3记录4记录n文件F记录1记录4记录n文件F记录3记录1文件GRT记录1COPY记录1记录4记录n文件F记录3记录3文件GRT记录1123(2)(3)(1)(4)若不管GET、COPY、PUT的执行关系，那么可有六种执行可能：1）COPY→PUT→GET；2）COPY→GET→PUT；3）PUT→COPY→GET4）PUT→GET→COPY；5）GET→COPY→PUT；6）GET→PUT→COPY..对第六种情况的分析2.同步.所谓“同步”，是指某进程执行到一点时，若有关进程已完成某种操作，那么该进程就可运行下去；否则必须暂停下来，等待有关进程操作的完成，然后才继续运行。暂停下来等待的那点，称为“同步点”；等待完成的操作，称为“同步条件”。这时称该进程要与有关进程在同步点取得同步。如图所示，给出了进程间同步时的行为。进程A执行到点X处时，要与进程B取得同步；进程B执行到点Y处时，为进程A准备好了同步条件。为此，在进程A执行到点X时，若进程B还没有越过点Y，那么进程A就须在X处阻塞，等待进程B为准备好条件；若进程A执行到点X前，进程B已越过点Y，那么进程A就可不受阻挡地一直执行下去。.进程A：进程B：X同步点同步条件Y.日常生活中，有很多同步的例子。比如工业生产的流水线上，上一道工序是为下一道工序做准备，在上一道工序的半成品没有到达之前，下一道工序的工人只能处于等待状态而无所事事。又比如，接力赛跑中，只有在接力区里下一棒运动员接过上一棒运动员递过来的接力棒，才能奋力奔跑，否则就是犯规。返回目录一些计算机中有专门指令，功能是将内存单元的内容读到寄存器中，然后往该单元里写入一个非零值，且读和写操作是不可分割（即在一个指令周期内完成）。这种指令称为“测试并上锁（TSL）”。格式是：TSLR,x8.2.1实现互斥的硬件方法1.中断禁止所谓“中断禁止”，是指进程以禁止中断的方法，构成临界区的进入区；以开中断的方法，构成临界区的退出区。8.2实现互斥的方法讨论..进程程序关中断开中断临界区进入区临界区退出区临界区由于禁止中断后，时钟中断和其他中断都遭封杀，就不会发生CPU进行进程切换的事情。所以，通过中断禁止的办法，完全不必担心别的进程会进入临界区。这时程序的结构如图所示。.禁止中断对于操作系统来说是实现互斥的一项很有用的技术。在系统内核中，利用它来保证访问共享资源的安全是方便的。2.专用机器指令TSL指令工作流程x→R(将单元x内容读入寄存器R)1→x(将数值1写入单元x)结束开始不可分割..enter_section:TSLR,x/*将x的值读入R后设置为1*/CMPR,#1/*R中的值为1?*/JNEenter_section/*R中的值为1,转enter_section*/exit_section:MOVEx,#0/*把x设置为0*/临界区代码进入区退出区程序中可利用TSL指令形成临界区的进入区，确保进程临界区间的执行是互斥的。如图所示是汇编语言程序中指令TSL的具体安排。图中通过指令TSL把变量x里当前值读入寄存器R，同时把变量x设置为1。这样，寄存器R里保存的是变量x的原值，x的新值为1。.程序中的指令：CMPR,#1JNEenter_section用于测试到变量x的原先值为1时，表明已有进程在其临界区里，别的进程就不能进入；只有在测试到变量x的原先值为0时，请求加入临界区的进程才能够进入它的临界区。也就是说，变量x起到一把“锁”的作用。..由指令MOVEx,#0完成退出临界区的功能，即把变量x设置为0。只有把“锁”x打开了，别的进程才可有机会进入自己的临界区。.利用指令TSL确实能够保证临界区的互斥，其缺点是当已有进程在临界区里时，欲进入临界区的进程就必须不断地去循环执行TSL指令和测试寄存器R的值，从而形成所谓的“忙等待”。返回目录如图是用类C语言描述的Peterson给出的解决互斥的软件方法：进入临界区的enter_section()和退出临界区的exit_section()。8.2.2实现互斥的软件方法..#defineFALSE0#defineTRUE1#defineN2/*进程个数*/intturn;/*现在轮到谁*/intinterested[N];/*初始化为0(FALSE)*/voidenter_section(intp)/*进程0或1想进入临界区*/{intother;/*另一个进程号*/other=1-p;/*另一个进程*/interested[p]=TRUE;/*表明有兴趣*/turn=p;/*设置轮到我标志*/while(turn==p&&interested[other]==TRUE);/*空语句*/}criticalsection/*临界区*/voidexit_section(p)/*进程0或1退出临界区*/{interested[p]=FALSE;}在算法里，用两个共享的量控制进程进入临界区：由变量turn的取值是0还是1，表示现在轮到哪个进程进入临界区；由数组元素interested[]，它以进程号（0或1）为下标，表示该进程是否有兴趣进入临界区。.Peterson算法是正确的，但遗憾的是它也存在忙等待的缺点。返回目录由于通过信号量可在进程间发送和接收信号，由于在进程暂时没有接收到所需信号前必须阻塞等待，因此对于信号量要给出“发送”和“接收”信号这样的两个操作，要安排一个与信号量有关的进程阻塞队列。8.3.1信号量与P、V操作定义.8.3信号量与P、V操作“信号量”是一种新的变量类型。它可在两个或多个进程间传递简单信号，使一个进程可被迫在某个位置阻塞，直到接收到一个特定的信号，达到合作的目的。.为保证执行正确无误，系统把定义在信号量上的两个操作P和V都作为原语的形式来实现。即操作中涉及的所有指令被视为一个整体，要么不执行，要么全都执行，不可加以分割。原语操作也被称为“原子操作”或“不可分割的操作”。.structsemaphore{int