第6章 进程间的制约关系

第6章进程间的制约关系6.16.26.3本章讲述内容：进程间的制约关系；信号量与P、V操作；死锁、高级进程通信。为输出井设置一张“输出井文件目录表”，它由若干目录项组成。每个目录项记录一个要打印输出的文件名以及该文件在磁盘的存放地址。6.1进程间的制约关系•6.1.1与时间有关的错误与时间有关的错误1.进程的并发，使一个进程何时占有处理机、占有多长时间、执行速度的快慢、以及外界对进程产生作用等都带有随机性。因此，一个进程对其他进程的影响无法预测。在操作系统里，把这种由于时间因素的影响而产生的错误，称为“与时间有关的错误”。例：对输入井文件目录的管理2.读in的当前内容;根据指点，存入打印文件名;in的值加1;test.cgroup.probit.txt45674out7in输入井文件目录表“井管理写”程序.为管理该目录表，系统安排两个指针：out和in。“缓输出程序”根据out的指点进行打印，out总是指向下一个被打印的文件；井管理写程序根据in的指点存放要求输出的文件目录信息，in总是指向下一个可用的目录项位置。..再次调度进程A运行，从断点往下做。由于它已做读in的操作，就把文件“games”存入输出井文件目录表中的第7个表目，把原来里面进程B的文件名删去，并且把in更新为9（因为进程B已把in改为8了），然后做其他的操作。若现在进程A要求打印名为“games”的文件。为此调用“井管理写”程序。在做了准备工作后，读出in中当前的内容为7。恰在此时，系统分配给进程A的时间片到，调度进程B运行。假定现在进程B要求打印文件“mail”，于是也去调用“井管理写”程序。在做了准备工作后，它读取in中的内容。此时，in中的值没改变，得到的仍为7。于是把它的文件“mail”存入输出井文件目录表中的第7个表目，并把in改为8，然后做其他的操作。.这样一来，进程B要输出的文件信息全无，永远也得不到任何打印输出。另外，输出井文件目录表的表目8被跳过去了，它里面没有记录下任何要输出的文件信息。从而产生了“与时间有关的错误”。.3.例：通过双缓冲区复制文件.编写复制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里的记录拷贝到了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）COPY→PUT→GET；2）COPY→GET→PUT；3）PUT→COPY→GET；4）PUT→GET→COPY；5）GET→COPY→PUT；6）GET→PUT→COPY.假定现在处于如图所示的状态，文件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种可能“GET→PUT→COPY”时导致的错误结果。..这时先执行GET，把文件F中的第3个记录读入缓冲区R，致使原来R中的记录2被删去，由记录3代替，如图(a)所示。(a).然后，执行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.输入井文件目录管理导致“与时间有关的错误”的分析.例子里进程A和B没有任何直接的关系，各做各的事情。不过，当它们要输出时，都要访问变量in。也就是说，in是它们的共享变量。.现在是在A取出变量in的值、还没按其指点往目录表中存放文件信息、没对in实行加1操作的情况下，B就去用了变量in，从而导致了“与时间有关的错误”。..很明显，A和B谁先做或谁先用in都没关系，重要的是它们不能同时用in。“不能同时”的含义是：在一个进程已开始用in、且还没有用完时，不允许另一个进程也用in，即它们对in的使用必须“互斥”。在操作系统中，凡牵扯到数据、队列、缓冲区、表格和变量等任何形式的共享资源时，都容易出现这种“与时间有关的错误”。为避免错误的发生，关键是要找到一种途径，来阻止多于一个进程同时使用它们。.称可以共享的资源（文件、队列、变量等）为共享变量或临界资源。为保证与一个共享变量交往的多个进程各自运行的正确性，当其中一个进程正在对该变量进行操作时，绝不允许其他进程同时对它进行操作。进程间的这种制约关系被称为“互斥”。2.互斥与临界区.读in的当前内容;根据指点，存入打印文件名;in的值加1;test.cgroup.probit.txt45674out7in输入井文件目录表“井管理写”程序一个进程在临界区内逗留有限时间后，就应该退出，以便给其他进程创造进入临界区的机会。如果有若干个进程要求进入自己的临界区，那么它们不应互相排斥，致使谁也进不了临界区。.在进程程序中，涉及到共享变量的那一部分程序，才真正需要保证互斥地执行。在操作系统中，把进程程序中“真正需要保证互斥执行”的那一段程序，称为该进程的“临界区（或临界段）”。3.设计互斥进程的注意事项..每次只允许一个进程进入临界区。具有互斥关系的进程，它的一部分程序可能用于内部的计算，用于内部的数据处理等。只有涉及共享变量的那一部分程序，才真正需要保证互斥地执行。.有互斥关系的进程，并不关心对方的存在性。即使对方不存在，自己也能够正确的运行，不会受到它存在与否的影响。.有互斥关系的那些进程程序中的临界区，虽然都是针对同一个共享变量的程序段，但在其上的操作可以相同也可以不相同。.进程的临界区是相对于某个共享变量而言的，不同共享变量的临界区之间，不存在互斥关系。设计进程临界区时必须遵循的准则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之间也有这种关系，这是进程之间由于协同工作而产生的一种直接关系。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发消息。..正是由于例中的GET、COPY、PUT之间没有保持这种关系，因此产生了所谓的“与时间有关的错误”。记录1记录2记录nGETCOPYPUT文件F记录1记录2记录n文件G输入缓冲区R输出缓冲区T一个进程需要等待另一个进程完成的操作或发送的信息，称为“同步条件”。一个进程运行到某点时，除非合作进程已经完成了某种操作或发来了信息，否则就必须暂时等待那些操作的完成或信息的到来。进程间的这种关系被称为“同步”。.4.同步、同步点、同步条件.暂停等待以取得同步的那一点，称为“同步点”。.3.设计有直接制约关系进程时应注意的问题.具有这种关系的进程，需要在某些点上协调相互的动作，谁先到达谁后到达是有顺序要求的。比如，GET应先在R中为COPY准备好记录，并向COPY发送“可拷贝”的消息。这样，当COPY运行时就有数据可用了。如果COPY先于GET到达等待GET发来“可拷贝”消息的地方，那么由于GET还没有为它准备好数据，它就只能等待。..这些进程都应了解对方的工作，对方如果不存在，或任何一方单独运行，就会出现差错。比如，GET应知道COPY只有得到自己给它的数据后，才能往下运行。COPY应该知道GET只有在得到它发出的“拷贝结束”消息后，才能继续做。只有这样配合，才能保证它们处于正常的工作状态。一方或双方的运行会直接地依赖于对方所产生的信息或发出的消息。比如，GET和COPY之间是双方都依赖于对方发来的消息，接收不到对方的消息，自己就一直保持等待。•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，则调用进程由运行态变为阻塞态，到与该信号量有关的队列Vq上排队等待，直到其他进程在S上执行V操作将其释放为止。当一个进程调用V（S）时，应该顺序做下面两个不可分割的动作：(1)Vs=Vs+1，即把当前信号量S的取值加1；(2)若Vs0，则调用进程继续运行；若Vs=0，则先从与该信号量有关的队列Vq上摘下一个等待进程，让它从阻塞态变为就绪态，到就绪队列排队，然后调用进程继续运行。如果一个进程在做P操作后被阻塞，那么就要到关于该信号量的队列上去排队等待。其含义就是将这个进程的PCB到此队列上去排队，并把该进程由运行状态变迁为阻塞状态。从P（S）的定义可以看出，调用它的进程有两个出路。如果对信号量当前值减1后，信号量值大于等于0，则该进程继续运行下去；否则它就被阻塞，直到有别的进程通过做V（S）来唤醒它。但是从V（S）的定义可以看出，调用它的进程的状态不会改变。无论对信号量当前值加1后的结果如何，调用它的进程最终都是继续运行下去。4.关于信号量及其P、V操作的几点说明...设置的信号量初值，一定是一个非负的整数。比如，它可以是0、可以是1、也可以是8等，但不能是−1、−3等。不过，由于P操作总是在信号量的当前值上进行减1操作，而V操作总是在信号量的当前值上进行加1操作，因此运行过程中，信号量的取值就不再受“非负”所限了。定义在信号量上的P操作和V操作，