资源描述
单击此处编辑母版标题样式,*,*,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第6章并发进程,6.1 进程的并发性,进程的顺序性,目前使用的计算机根本上是冯诺依曼Von Neumann式的结构，其根本特点是处理器按指令地址的指示顺序执行指令，这样的处理器称为顺序处理器。,进程的顺序性是指进程在顺序处理器上的执行是严格按序的，即按照程序规定的操作顺序，只有在前一个操作结束后才能开始后继操作。,当一个进程独占处理器顺序执行时，它具有两个特性：,1封闭性进程执行的结果只取决于进程本身，不受外界影响。也就是说，进程执行的结果与其执行的速度无关。,2可再现性进程重复执行时，必定获得同样的结果。也即，只要初始条件相同，那么无论在什么时间执行都产生相同的结果。,6.1 进程的并发性,进程的并发性,在多道程序设计的系统中会同时存在着许多进程。每一个进程都具有顺序性。在单处理器的情况下，这些进程要竞争处理器，它们必须轮流占用处理器。但是，进程什么时间能占用处理器，能占用多长时间，这不仅取决于进程自身，还取决于进程调度策略。例如，有两个进程A和B，它们各自顺序执行的操作序列如下：,进程A：a1,a2,a3,am；进程B：b1,b2,b3,bn,在多道程序设计系统中，处理器会交替执行它们的操作。处理器可能按序列a1,b1,a2,b2,a3,b3,执行这些操作，也可能按序列a1,a2,b1,b2,b3,a3,执行这些操作，还可能按其他序列来执行。也就是说，在一个进程的工作没有全部完成之前，另一个进程就可以开始工作，我们说这些进程是可同时执行的，或称它们具有并发性，并且把可同时执行的进程称为并发进程。,并发进程相互之间可能是无关的，也可能是有交互的。例如，为两个不同的源程序进行编译的两个进程，它们可以是并发的，但它们之间却是无关的。因为这两个进程分别为不同的源程序进行编译，也就是分别在不同的数据集合上运行，因此一个进程的执行不会影响另一个进程的执行，一个进程的执行与另一个进程的进展情况无关，它们是各自独立的。又如，第2章图2.2计算问题中的输入进程、处理进程、输出进程是三个并发进程，其中每一个进程的执行都依赖另一个进程的进展情况。只有当输入进程把一批数据读入后，处理进程才能对它加工，输出进程要等数据加工好后才能把它输出，也只有当处理进程把输入进程读入的一批数据取走后，输入进程才能读下一批数据。可见，它们是一组有交互的并发进程。有交互的并发进程一定共享某些资源。例如上例中的输入数据是输入进程与处理进程的共享资源，输出数据是处理进程与输出进程的共享资源，存放数据的工作区也是这些并发进程的共享资源。,进程并发执行时，执行结果与其执行的相对速度有关。在上例中，如果输入进程尚未把一批数据全部读入，处理进程就对其进行加工的话，那么其结果就会出错。因而，进程的并发执行会破坏“封闭性和“可再现性。,6.2与时间有关的错误,一个进程运行时，经常会由于自身或外界的原因而被中断，且断点是不固定的,。一个进程被中断后，哪个进程可以运行呢？被中断的进程什么时候能再去占用处理器呢？这是与进程调度策略有关的。所以，,进程执行的相对速度不能由进程自己来控制,，,于是，就可能导致并发进程在共享资源时出现错误,。例如，某游艺场设置了一个自动计数系统，用一个计数器count指示在场的人数。当有一个人进入时，由进程PIN实现计数加1；当退出一个人时，由进程POUT实现计数减1。这两个进程的程序如下：,process PIN,R1:interger;,begin,R1:=count;,R1:=R1+1;,count:=R1;,end;,process POUT,R2:integer;,begin,R2:=count;,R2:=R2-1,count:=R2;,end;,6.2与时间有关的错误,如果这两个程序各自顺序执行，其执行结果毫无疑问是正确的。但是，由于入场和退场是随机的，因此，进程PIN和POUT的执行是并发的。我们把,并发执行的进程,用cobegin和coend括起来，于是，并发执行的程序可表示如下：,begin,count:integer;,count:=0,cobegin,process PIN,R1:ingeger;,begin,R1:=count;,R1:=R1+1;,count:=R1;,end;,process POUT,R2:integer;,begin,R2:=count;,R2:=R2-1;,count:=R2;,end;,coend;,end;,6.2与时间有关的错误,假定某个时候的计数值count=n.。这时有一个人要进入，正好有一个人要退出，于是进程PIN和POUT都要执行。如果进程PIN和POUT的执行都没有被打断过，那么各自完成了count+1和count-1的工作，使计数值保持为n。这是正确的的。如果两个进程执行中由于某种原因，进程PIN被打断，且进程调度使他们的执行呈下面的次序见表6-1：,按这样的次序执行后，count的最终值不能保持为n，而变成n+1。如果进程被打断的情况如下见表6-2。,于是，两个进程执行完后，count的终值为n-1。由此可见，进程的执行次序对结果是有影响的。关键是它们涉及到共享变量count。这两个进程交替访问了count，访问count的时间不同，就可能使count的值不同。所以，造成计数值不正确的因素是与进程被打断的时间和能占用处理器的时间有关。由这种原因造成的错误称为与时间有关的错误。,下面再看一个例子。,设一个飞机航班售票系统有n个售票处，每个售票处通过终端访问系统的公共数据区。假定公共数据区中的一些单元AKK=1，2，m分别存放某月某日某次航班的余票数。设P1，P2，Pn表示各售票处的处理进程，R1，R2，Rn表示各进程执行时所用的工作单元。当各售票处有旅客买票时，进程如下工作：,process Pi(i=1,2,n),begin,按旅客订票要求找到AK；,Ri:=AK;,if Ri=1 then,begin,Ri:=Ri-1;,AK:=Ri;,输出一张票,end,else输出“票已售完,end;,由于各售票处旅客订票的时间以及要订的机票日期和航班是随意的，因此可能有假设干个旅客在几乎相同的时间里到不同的售票处要求购置同一天同一航班的机票，于是假设干个进程都要访问同一个AK，进程并发执行时可能会出现如下情况见表6-3：,进程Pi和Pj分别在时刻t1和t2取到相同的值AK，当AK1时，都认为有票可售给旅客。于是各自执行余票数减1的操作，然后把当前的余票数存回AK。显然，这两个进程共售出同一天同一航班的机票2张。AK的值应该减去2，但是实际上AK的值只被减去了1，产生了错误。特别是，假设当这两个进程执行前AK=1，它们并发执行后，那么将发生“把唯一的一张机票卖给了两个旅客的错误。这个错误也是由于进程交替访问了共享变量AK而造成的与时间有关的错误。,6.3临界区与PV操作,临界区,我们把并发进程中与共享变量有关的程序段称为临界区。在6.2节的第一个例子中，PIN和POUT这两个并发进程的临界区分别如下：,PIN的临界区是：,R1:=count;,R1:=R1+1;,count:=R1;,POUT的临界区是：,R2:=count;,R2:=R2-1;,count:=R2;,在6.2节的第二个例子中有n个并发进程P1，P2，Pn。进程Pii=1，2，n的临界区是：,Ri:=AK;,if Ri=1 then,begin,Ri:=Ri-1;,AK:=Ri;,如果能保证一个进程在临界区执行时，不让另一个进程进入相关的临界区执行，即各进程对共享变量的访问是互斥的，那么就不会造成与时间有关的错误。,6.3临界区与PV操作,相关临界区是指并发进程中涉及到相同变量的那些临界区。例如上面的第一个例子中，进程PIN和POUT都要访问变量count，所以它们的临界区是相关的。同样，第二个例子中，进程P1，P2，Pn都要访问变量AK，所以它们的临界区也是相关的。当然，PIN和POUT是不会去访问任何一个Pi中的变量，反之，各个Pi也不会去访问PIN和POUT中的变量，因而PIN和POUT的临界区与任何一个Pi的临界区是无关的。对同一共享变量的假设干临界区必须互斥执行，而对不同变量的临界区的执行是不必互斥的。所以，当PIN和POUT在临界区执行时，不应阻碍P1，P2，Pn中任何一个进程进入它们的临界区执行。,对假设干个并发进程共享某一变量的相关临界区的管理有三个要求：,1一次最多一个进程能够进入临界区。当有进程在临界区执行时，其他想进入临界区执行的进程必须等待：,2不能让一个进程无限制地在临界区执行，即任何一个进入临界区的进程必须在有限的时间内退出临界区；,3不能强迫一个进程无限制地等待进入它的临界区，即有进程退出临界区时应让一个等待进入临界区的进程进入它的临界区执行。,怎样按照这三个要求实现对临界区的管理呢？,6.3.2 PV操作,为了实现对临界区的管理要求，必须做到：当无进程在临界区时，假设有进程要进入临界区，那么允许一个进程立即进入它的临界区；当有一个进程在临界区执行时，其他试图进入临界区的进程必须等待；当有一个进程离开临界区时，其有等待进入临界区的进程，那么允许其中一个进程进入它的临界区。,Dijkstra创造的PV操作能够实现对临界区的管理要法度。PV操作是由两个操作P操作和V操作组成。它们是两个不可中断的过程，它们在屏蔽中断的情况下连续执行。通常把这种不可中断的过程称为原语。因此，P操作和V操作也可称为P操作原语和V操作原语，简称PV操作。PV操作是对信号量进行操作，它们的定义如下：,P操作PS：将信号量S减去1，假设结果小于0，那么把调用PS的进程置成等待信号量S的状态。,V操作VS：将信号量加1，假设结果不大于0，那么释放一个等待信号量S的进程。,6.3.2 PV操作,这两个操作可表示成如下两个过程。,Procedure P(Var S:Semaphore);,begin,S:=S-1;,if S0 then W(S),end;P,Procedure V(Var S:Semaphore);,begin,S:=S+1;,if S=1 then,begin,Ri:=Ri-1;,AK:=Ri;,V(S);,输出一张票,end,else 输出“票已售完,end;,coend;,end;,进程执行时调用PS判定是否能进入临界区。由于S的初值为1，故每次只能有一个进程进入临界区，其他想进入临界区执行的进程必须等待，这符合临界区管理的第一个要求。但在改写的程序中，忽略了当条件Ri1不成立时执行else局部的V操作，以致使进程在临界区中判别条件Ri1不成立时无法退出临界区，当然也就不能释放等待进入临界区的进程，造成进程无限地等待进入临界区，这就违反了对临界区管理的第二、第三两个要求。正确的做法应该是：,begin,S:semaphore;,S:=1;,cobegin,process Pi(i=1,2,n),begin,按旅客订票要求找到AK；,PS；,Ri=AK;,if Ri=1 then,begin,Ri:=Ri-1;,AK:=Ri;,V(S);,输出一张票,end,else begin,V(S);,输出“票已售完,end,end;,coend;,end;,进程的同步,进程的同步是指在并发进程之间存在一种制约关系，一个进程的执行依赖另一个进程的消息，当一个进程没有得到另一个进程的消息时应等待，直到消息到达才被唤醒。,先看一个例子。设有两个进程A和B，它们共享一个缓冲器。进程A不断地读入记录，并送入缓冲器中。进程B不断地从缓冲器中取出记录并加工。如图6-1所示。,假定缓冲器的容量为每次只能存放一个记录。于是，正确的工作过程应该是：,进程A把一个记录送入缓冲器后，应等到进程B发来信息已将缓冲器中的记录取走，才能把下一个记录存放缓冲器。进程B把已存入缓冲器的记录取走后，也应该等到进程A发来消息缓冲器中已存入一个待加工的记录
展开阅读全文