华联学院《操作系统原理》课件06进程间的制约关系

1、第6章 进程间的制约关系6.16.26.3本章讲述内容：进程间的制约关系 ；信号量与P、V操作 ；死锁、高级进程通信。 为输出井设置一张 “输出井文件目录表”，它由若干目录项组成。每个目录项记录一个要打印输出的文件名以及该文件在磁盘的存放地址。6.1 进程间的制约关系6.1.1与时间有关的错误与时间有关的错误1. 进程的并发，使一个进程何时占有处理机、占有多长时间、执行速度的快慢、以及外界对进程产生作用等都带有随机性。因此，一个进程对其他进程的影响无法预测。在操作系统里，把这种由于时间因素的影响而产生的错误，称为“与时间有关的错误”。 例：对输入井文件目录的管理2.读in的当前内容 ;根据指点

2、，存入打印文件名 ;in的值加1 ;test . cgroup . probit . txt45674out7in输入井文件目录表“井管理写” 程序. 为管理该目录表，系统安排两个指针：out和in。“缓输出程序”根据out的指点进行打印，out总是指向下一个被打印的文件；井管理写程序根据in的指点存放要求输出的文件目录信息，in总是指向下一个可用的目录项位置。. 再次调度进程A运行，从断点往下做。由于它已做读in的操作，就把文件“games”存入输出井文件目录表中的第7个表目，把原来里面进程B的文件名删去，并且把in更新为9（因为进程B已把in改为8了），然后做其他的操作。 若现在进程A要求

3、打印名为“games”的文件。为此调用“井管理写”程序。在做了准备工作后，读出in中当前的内容为7。恰在此时，系统分配给进程A的时间片到，调度进程B运行。假定现在进程B要求打印文件“mail”，于是也去调用“井管理写”程序。在做了准备工作后，它读取in中的内容。此时，in中的值没改变，得到的仍为7。于是把它的文件“mail”存入输出井文件目录表中的第7个表目，并把in改为8，然后做其他的操作。. 这样一来，进程B要输出的文件信息全无，永远也得不到任何打印输出。另外，输出井文件目录表的表目8被跳过去了，它里面没有记录下任何要输出的文件信息。从而产生了“与时间有关的错误”。 .3.例：通过双缓冲区

4、复制文件. 编写复制n个记录的程序，它把文件F中的记录依次读到输入缓冲区R，再从R拷贝到输出缓冲区T，最后写到文件G中。假定R和T正好存放一个记录。写下面三个子程序作为进程来完成整个工作： (1)GET：从文件F按照顺序读出一个记录，然后送入输入缓冲区R；(2)COPY：把输入缓冲区R里的记录拷贝到输出缓冲区T里；(3)PUT：从输出缓冲区T里读出一个记录，然后依照顺序写入文件G。读in的当前内容 ;根据指点，存入打印文件名 ;in的值加1 ;test . cgroup . probit . txt45674out7in输入井文件目录表“井管理写” 程序 复制时，若COPY已把R里的记录拷贝到

5、了T中，那GET和PUT就可并发执行了。即GET从F里读下一个记录送到R中的操作，与PUT从T中取出内容写入G的操作，谁先谁后都没有关系，不会影响到复制结果的正确性。由于利用并发性，工作效率就会提高。记录1记录2记录nGETCOPYPUT文件F记录1记录2记录n文件G输入缓冲区R输出缓冲区T. 若不顾及这三者间执行顺序的内在制约关系，随意让GET、COPY、PUT并发执行，那么就会产生“与时间有关的错误”。. 不管GET、COPY、PUT的执行关系，有六种可能的执行顺序：1）COPYPUTGET；2）COPYGETPUT；3）PUTCOPYGET；4）PUTGETCOPY；5）GETCOPYP

6、UT；6）GETPUTCOPY. 假定现在处于如图所示的状态，文件F的第1个记录已顺利地复制到了文件G，文件F的第2个记录也已由GET读到了输入缓冲区R中。 记录3记录4记录n文件F记录2记录1文件GRT记录1.GETPUT记录1记录1文件GRT记录3记录4记录n文件F记录1记录4记录n文件F记录3记录1文件GRT记录1COPY记录1记录4记录n文件F记录3记录3文件GRT记录1123比如在前图基础上，来看第6种可能“GETPUTCOPY”时导致的错误结果。 . 这时先执行GET，把文件F中的第3个记录读入缓冲区R，致使原来R中的记录2被删去，由记录3代替，如图(a)所示。 (a). 然后，执

7、行PUT，把现在还在输出缓冲区中的记录1写入到文件G中，成为它的第2个记录，如图(b)所示。 .(b)(c) 最后做COPY，把记录3从R拷贝到T中，如图(c)所示。 . 由于没有遵循三个程序在执行顺序上的限制，复制过程中，丢失了第2个记录，第1个记录在文件G里重复复制了两次。导致了“与时间有关的错误”的发生。6.1.2 竞争资源互斥 若在进程A用完变量in（即取出in的值，把文件按其指点存入输出井目录表，把in的值加1）后，进程B才去用in ，那是不会发生“与时间有关的错误”的。同样地，若在进程B用完变量in后，进程A才去用，那么也不会发生“与时间有关的错误”。1.输入井文件目录管理导致“与

8、时间有关的错误”的分析. 例子里进程A和B没有任何直接的关系，各做各的事情。不过，当它们要输出时，都要访问变量in。也就是说，in是它们的共享变量。 . 现在是在A取出变量in的值、还没按其指点往目录表中存放文件信息、没对in实行加1操作的情况下，B就去用了变量in，从而导致了“与时间有关的错误”。 . 很明显，A和B谁先做或谁先用in都没关系，重要的是它们不能同时用in。“不能同时”的含义是：在一个进程已开始用in、且还没有用完时，不允许另一个进程也用in，即它们对in的使用必须“互斥”。 在操作系统中，凡牵扯到数据、队列、缓冲区、表格和变量等任何形式的共享资源时，都容易出现这种“与时间有关

9、的错误”。为避免错误的发生，关键是要找到一种途径，来阻止多于一个进程同时使用它们。 . 称可以共享的资源（文件、队列、变量等）为共享变量或临界资源。为保证与一个共享变量交往的多个进程各自运行的正确性，当其中一个进程正在对该变量进行操作时，绝不允许其他进程同时对它进行操作。进程间的这种制约关系被称为“互斥”。2.互斥与临界区.读in的当前内容 ;根据指点，存入打印文件名 ;in的值加1 ;test . cgroup . probit . txt45674out7in输入井文件目录表“井管理写” 程序 一个进程在临界区内逗留有限时间后，就应该退出，以便给其他进程创造进入临界区的机会。 如果有若干个

10、进程要求进入自己的临界区，那么它们不应互相排斥，致使谁也进不了临界区。 . 在进程程序中，涉及到共享变量的那一部分程序，才真正需要保证互斥地执行。在操作系统中，把进程程序中“真正需要保证互斥执行”的那一段程序，称为该进程的“临界区（或临界段）”。 3.设计互斥进程的注意事项.每次只允许一个进程进入临界区。 具有互斥关系的进程，它的一部分程序可能用于内部的计算，用于内部的数据处理等。只有涉及共享变量的那一部分程序，才真正需要保证互斥地执行。 . 有互斥关系的进程，并不关心对方的存在性。即使对方不存在，自己也能够正确的运行，不会受到它存在与否的影响。 . 有互斥关系的那些进程程序中的临界区，虽然都

11、是针对同一个共享变量的程序段，但在其上的操作可以相同也可以不相同。 . 进程的临界区是相对于某个共享变量而言的，不同共享变量的临界区之间，不存在互斥关系。 设计进程临界区时必须遵循的准则 4.6.1.3 协同工作同步1.用双缓冲区复制文件导致“与时间有关的错误”的分析. 在GET没把记录从F读到R前，COPY不能把R中的内容拷贝到T中去；在COPY没把R中的内容拷贝到T之前，GET不得把下一个记录从F读到R中。即只有GET先于COPY工作，COPY的工作才正确；只有COPY取走了R中的内容，GET做下一步工作才正确。COPY与PUT之间也有这种关系，这是进程之间由于协同工作而产生的一种直接关系

12、。 2.保证GET和COPY间协调一致的作法从文件F取出一个记录送至输入缓冲区R向COPY发送“可以拷贝” 的消息等待COPY发来的“拷贝结束”的消息等待GET发来“可以拷贝” 的消息将输入缓冲区R里的记录拷贝到输出缓冲区T里向GET发送“拷贝结束”的消息GETCOPY1.1.2.2.3.3. GET读记录到R后，给COPY发消息，告诉它R中已有记录，然后暂停，等待COPY发来 “拷贝结束”的消息。只有接到这个消息，GET才能往下做。. COPY一直等待。只有接到GET发来 “可以拷贝”的消息才能工作，将R里的记录拷到T里，然后向GET发“拷贝结束”的消息，随之又等待GET发消息。 . 正是由

13、于例中的GET、COPY、PUT之间没有保持这种关系，因此产生了所谓的“与时间有关的错误”。记录1记录2记录nGETCOPYPUT文件F记录1记录2记录n文件G输入缓冲区R输出缓冲区T一个进程需要等待另一个进程完成的操作或发送的信息，称为“同步条件”。 一个进程运行到某点时，除非合作进程已经完成了某种操作或发来了信息，否则就必须暂时等待那些操作的完成或信息的到来。进程间的这种关系被称为“同步”。 .4.同步、同步点、同步条件.暂停等待以取得同步的那一点，称为“同步点”。.3.设计有直接制约关系进程时应注意的问题. 具有这种关系的进程，需要在某些点上协调相互的动作，谁先到达谁后到达是有顺序要求的

14、。比如，GET应先在R中为COPY准备好记录，并向COPY发送“可拷贝”的消息。这样，当COPY运行时就有数据可用了。如果COPY先于GET到达等待GET发来“可拷贝” 消息的地方，那么由于GET还没有为它准备好数据，它就只能等待。 . 这些进程都应了解对方的工作，对方如果不存在，或任何一方单独运行，就会出现差错。比如，GET应知道COPY只有得到自己给它的数据后，才能往下运行。COPY应该知道GET只有在得到它发出的“拷贝结束”消息后，才能继续做。只有这样配合，才能保证它们处于正常的工作状态。 一方或双方的运行会直接地依赖于对方所产生的信息或发出的消息。比如，GET和COPY之间是双方都依赖

15、于对方发来的消息，接收不到对方的消息，自己就一直保持等待。 6.2.1 信号量与P、V操作的定义1.信号量的定义 所谓“信号量”，是一个具有非负初值的整型变量，并有一个队列与它关联。因此，定义一个信号量S时，要给出它的初值Vs，给出与它相关的队列指针Vq。在一个信号量S上，只能做规定的两种操作：P操作，记为P(S)；和V操作，记为V(S)。 2.信号量S上的P操作定义 6.2 信号量与P、V操作3.信号量S上的V操作定义 当一个进程调用P（S）时，应该顺序做下面两个不可分割的动作： (1) Vs=Vs-1，即把当前信号量S的取值减1； (2) 若Vs=0，则调用进程继续运行；若Vs0，则调用进

16、程继续运行；若Vs=0，则表示可给该进程分一个资源；若Vs0，表示现在已没有资源可分配，进程只能阻塞，到队列Vq上去等待，这时Vs的绝对值恰是提出资源请求、但没有分配到资源的进程个数。某进程在S上做一次V操作后，若Vs0，表示原资源等待队列上没有进程等待，只是收回了一个资源。 2.简单的“生产者-消费者”问题生产者：生产一个产品P(M)(申请一个缓冲区)按in指点将物品存入缓冲区in=(in+1) mod 10(调整存入指针in)V(N)(向消费者发消息，缓冲区里已有物品)消费者：消费物品P(N)(等待生产者发来消息)按out指点从缓冲区取出物品out=(out+1) mod 10(调整取出指

17、针out)V(N)(向生产者发消息，已有空缓冲区)Vm=10Vn=0(M,N初值) 若有一个生产者和一个消费者，他们共享10个缓冲区。生产者不断地生产物品，并依次放入缓冲区中。消费者依次从缓冲区里取出物品进行消费。只有在缓冲区有空位时，生产者生产出来的物品才能往里存放；只有在缓冲区有物品时，消费者才能从里面取出物品消费。试用 P、V 操作来协调生产者和消费者间的工作。 设置4个信号量：m为空闲缓冲区的数目；n为已放物品缓冲区的数目；S1控制互斥进入in临界区；S2控制互斥进入out临界区。6.2.5 互斥/同步样例分析1.“生产者-消费者”问题 若有 i 个生产者和j 个消费者，共享 k个缓冲

18、区。生产者不断生产物品，并依次放入缓冲区中。消费者依次从缓冲区里取出物品进行消费。只有在缓冲区里有空位时，生产者生产出来的物品才能往里面放；只有在缓冲区里有物品时，消费者才能从里面取出物品进行消费。试用P、V操作协调生产者和消费者之间的工作。生产者：生产一个产品P(M)(申请一个缓冲区)按in指点将物品存入缓冲区in=(in+1) mod k(调整存入指针in)V(N)(向消费者发消息，缓冲区里已有物品)消费者：消费物品P(N)(等待生产者发来消息)按out指点从缓冲区取出物品out=(out+1) mod k(调整取出指针out)V(N)(向生产者发消息，已有空缓冲区)Vm=k,Vn=0Vs

19、1=1,Vs2=1(信号量初值)P(S1)(要求进入in 临界区)V(S1)(退出in 临界区)P(S2)(要求进入out 临界区)V(S2)(退出out 临界区). 设置两个信号量：MUTEX控制读者互斥进入reader临界区，WRT控制读者及写者互斥进入读/写临界区，初值都是1。reader=reader-1(读者计数器减1)2.“读者-写者”问题读者：reader=1?(是第1个读者?)P(MUTEX)(进入reader临界区)读者读取所需信息reader=reader+1(读者计数器加1)V(MUTEX)(退出reader临界区)P(WRT)(进入读/写临界区)P(MUTEX)(进入r

20、eader临界区)reader=0?(是最后一个读者?)V(MUTEX)(退出reader临界区)V(WRT)(退出读/写临界区)NNYYP(WRT)(进入读/写临界区)写者对数据进行修改V(WRT)(退出读/写临界区)写者： 若一批数据被多个并发进程共享，其中一些进程只要求读数据，称为“读者”；另一些会对数据进行修改，称为 “写者”。多个读者同时工作时，访问不会有问题。但是如果读者和写者或写者和写者同时工作时，就有可能导致错误访问结果。假定在有读者访问时，到来写者要求访问，那么写者只能等待，但到来的后续读者仍可以进行访问，这表示读者比写者有更高的访问权。试用P、V操作来协调读者和写者之间的工

21、作。 . 设一个初值为0的变量reader，它不是信号量，而是用来随时记录当前有多少个读者在同时使用数据。正因为允许多个读者同时使用数据，reader成为各读者共享的变量，所以要设置信号量MUTEX来控制读者互斥地使用它。. 互斥条件：每个资源每次只能分配给一个进程使用。 循环等待条件：系统中存在两个以上的进程，它们组成一个环路，该环路中的每个进程都在等待其相邻进程占用的资源。 部分分配（占用并等待）条件：进程由于申请不到所需要的资源而等待时，仍然占据着已经分配到的资源。 6.3 死锁、高级进程通信6.3.1 死锁与产生死锁的必要条件资源分配图1. 用方框代表资源，圆圈代表进程。画一条由资源到

22、进程的有向边，表示把该资源分配给这个进程；画一条由进程到资源的有向边，表示该进程要申请这个资源。这样的图就是所谓的 “ 资源分配图 ”。 ARBSDCTU死锁的定义2. 所谓“死锁”，即指系统中若存在一组进程，它们中的每一个都占用了某种资源而又都在等待其中另一个所占用的资源，这种等待永远不会结束。这就是死锁，或说这一组进程处于死锁状态。 产生死锁的四个必要条件3.非剥夺条件：已经分配给进程的资源，别的进程不能强行夺取。 6.3.2 死锁的预防1.死锁预防的含义 所谓“死锁的预防”，是指破坏产生死锁四个必要条件中的一条或几条，以使系统不会产生死锁。在死锁预防里，主要是破坏其他几个必要条件，而不去

23、破坏“互斥条件”。 2.破坏“部分分配（占用并等待）条件” 采用的办法是系统对进程实行一次性分配方案，即一个进程总是合盘提出总的资源需求，系统要么分配给它所需要的全部资源，要么一个也不给它。 3.破坏“非剥夺条件” 采用的办法是允许别的进程从占用进程手中强抢所占用的资源。 4.破坏“循环等待条件” 采用的办法是将系统中的所有资源进行统一编号，进程按编号的顺序，由小到大提出对资源使用的申请。假定把不同编号的资源i和j分配给了进程A和B。那么如果ij，A就不允许再申请资源j；如果ij，B就不允许再申请资源 i 。这样就形成不了资源申请的循环等待环路 。AiABijBj1.输入机2.打印机3.绘图仪

24、4.磁带机5.CD-ROM.1.死锁避免的含义 指允许系统存在产生死锁的条件，但在接到一个进程的资源请求时，总是根据当时资源的使用情况，按照一定的算法去模拟分配，探测分配的结果。只有在探测结果表明绝对不会出现死锁时，才真正接受进程的这次资源请求。 2.安全状态和不安全状态. 若能在有限时间内，保证所有进程得到自己需要的全部资源，那么称系统此时处于“安全状态”；否则称系统处于“不安全状态”。很明显，在系统处于安全状态时，绝对不会发生死锁；在系统处于不安全状态时，系统有可能发生死锁。 3.银行家算法对进程的要求.必须预先说明自己对资源的最大需求量； 只能一次一个地申请所需要的资源； . 若已获得了

25、资源的最大需求量，那么应在有限时间内使用完毕，并归还系统。 4.实施银行家算法时系统的承诺. 若进程对资源的最大需求量没超过该资源的总量，应保证接纳这个进程，不得拒绝它； 在接到一个进程对资源的请求时，有权根据当前资源的使用情况暂时加以拒绝（即阻塞该进程）。但应保证在有限的时间内让它得到所需要的资源。 6.3.2 死锁的避免 如果所有进程的“能执行完”均为1，表示接受这次请求是安全的；否则暂时不能接受进程的这次资源请求。 如果找到了，就假设它获得了最大资源数，并运行结束。于是把它的“能执行完”标志置为1。这样就能假定收回它使用的所有资源，使系统剩余资源数增加。 在这一假设下，检查每个进程对资源

26、的还需要数。看能否找到一个进程，其还需数目小于系统剩余资源数。如果找不到，那么系统就有可能死锁，因为任何进程都无法运行结束。 在安全状态下，系统接到进程的资源请求后，先假定接受这一请求，把需要的资源分配给这个进程。 5.单种资源银行家算法的基本思想单种资源银行家算法：将所有进程的“能执行完”标志清0假定接受该请求,把资源分配给进程将系统当前所有剩余资源与”能执行完”标志为0的进程还需资源数比较,找出一个能满足其所有需求的进程找到了吗？将该进程的”能执行完”标志置为1,系统收回它所要求的全部资源数YN检查所有进程的“能执行完”标志还有” 能执行完 ”标志为0的进程吗？这一请求不安全,暂时不予接受

27、YN这一请求是安全的,可以分配. 在“能执行完”标志为0的进程中重复以上两步，直到找不到资源还需数小于系统剩余资源数的进程时为止。 如果存在这种进程，那么假定它已获得需要的所有资源，并完成工作，把它的“能执行完”标志设置成1。收回它占用的资源，更新向量A。 检查还需资源表中是否有一个进程的行向量小于或等于向量A。如果没有，那么系统就可能会死锁，因为现在任何进程都无法完成了。 6.多种资源银行家算法的执行步骤 系统设两张表：“分配资源表”，记录已分配给各进程的资源数；“还需资源表” ，记录各进程还需要的资源数。设3个向量：E记录各种资源的总数，P记录各种资源已分配数，A记录各种资源的剩余数。 进

28、程磁带机绘图仪打印机CD-ROMA3011B0100C1110D1101E0000进程磁带机绘图仪打印机CD-ROMA1100B0112C3100D0010E2110已分配资源表还需资源表E 6 3 4 2 (资源总数)P 5 3 2 2 (已分配数)A 1 0 2 0 (剩余数).假定接受一个进程提出的资源请求，修改向量P和A。 .重复以上两步，直至再也找不到行向量小于或等于向量A的进程。 检查所有进程的 “能执行完” 标志。若这个标志都是1，则表示都能顺利地完成。因此，接受资源分配后导致的新状态是安全的；如果仍存在“能执行完”标志为0的进程，则说明这一请求所导致的状态是不安全的，应暂时拒绝

29、该请求。 . 系统中有AG共7个进程，6个同类资源rw，当前的资源所属关系如下：6.3.4 死锁的检测并恢复1.利用资源分配图检测死锁rAsCDFwuGtBEv.A得到资源r，需要资源s；.B不占有资源，需要资源t；.C不占有资源，需要资源s；D得到资源u和s，需要资源t；.E得到资源t，需要资源v；F得到资源w，需要资源s；G得到资源v，需要资源u。2.利用表格检测死锁环路资源占用的进程进程等待的资源rAsCtBuBvAAt进程等待的资源AtBCsv 通过建立“资源分配表”和“进程等待表”，随时检测资源的分配是否构成环路。假定现有3个进程AC，有5个同类型资源rv。 资源分配表进程等待表进程

30、等待表3.死锁的恢复 一是删除环中的若干进程，释放占用的资源，使其他进程能继续运行；二是临时把某个资源从占用者手中剥夺，给另一个进程使用；三是周期地记录各进执行情况。一旦检测到死锁，就按记录的文件进行回退，让损失减到最小。 6.3.5 高级进程通信1.进程间的低级与高级通信.进程间的低级通信 信号量上的P、V操作是进程间的一种通信方式，它告诉对方缓冲区里是否可存数据，是否可取数据，是否可读文件，是否可写文件，等等。但通信双方不交换信息，只是事先的一种约定。因此，用P、V操作实现的通信，是进程间的“低级通信”。 进程间的高级通信 为使进程间能交换数据，系统提供通信命令给用户在程序中使用。用户只要

31、准备好参数，调用这些命令就能在进程间传递数据，这就是进程间的“高级通信”。 2.直接通信.进程间直接通信的基本思想 发送者在自己的消息发送区里形成消息，然后申请一个消息缓冲区，把数据从消息发送区移入消息缓冲区中。通过发送命令，把这个消息缓冲区直接发送到接收者的消息队列里。接收者从自己的消息队列上摘下消息缓冲区，把里面的数据读到自己的消息接收区里，然后释放缓冲区。 提供发送消息和接收消息的系统调用命令，比如发送命令为Send，接收命令为Receive。 系统中开辟消息缓冲区，构成是： name发送消息的进程名或标识； size发送消息的长度； text发送消息的正文内容； nPtr下一个消息缓冲

32、区的指针。.进程间直接通信示意Send (消息发送区地址)接收进程名：B消息长度：size消息正文：text进程A的消息发送区Receive (消息接收区地址)发送进程名：A消息长度：size消息正文：text进程B的消息接收区进程A的程序进程B的程序进程B的PCBMUTEX (1)SM (0)hPtr发送进程名：A消息长度：size消息正文：textnPtr：发送进程名：A消息长度：size消息正文：textnPtr：-1消息缓冲区消息缓冲区(1)(2)(3) 在进程的PCB中，增设管理消息队列的有关内容，它们是： hPtr消息队列的队首指针（每个进程的消息队列由其他进程发来的消息缓冲区组成，hPtr总是指向第1个消息缓冲区）； MUTEX