《分布式操作系统》PPT课件.ppt

第二章.进程管理及并发控制和同步,第1节进程的定义和特征第2节进程的状态和进程控制块第3节进程控制第4节进程的同步与互斥第5节并发执行的描述方式第6节基于共享变量的同步操作原理第7节基于消息传递的同步操作原语第8节进程调度,进程的定义和特征,1.进程的定义2.进程的特征3.进程的结构,进程的定义,进程（process）或任务（task）这一术语是在六十年代初期，首先在麻省理工学院（MIT）的MULTICS系统和IBM公司的CTSS/360系统中引入的，其后有许多人对进程下过各式各样的定义，下面列举几种比较能反映进程实质的定义：,进程的定义,进程是程序的一次执行，亦即进程是在指定的内存区域中的一组指令序列的执行过程。进程（或任务task）是可以和别的计算并发（concurrent）执行的计算。进程可以定义为一个数据结构和能在其上进行操作的一个程序。进程是程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位进程（process）是一个具有独立功能的程序关于相关的数据集在处理机上的执行过程。,进程的特征,进程具有顺序性动态性并发性独立性和异步性等特征。进程的最基本的特征是并发性。,顺序性,一个进程的顺序性是指每个进程在顺序处理机上的执行是严格按次序进行的，即只有当其中的一个操作结束后，才能开始其后续操作.,动态性,进程的动态性是指它是程序的一次执行过程，表现为它是由“创建（create）”而产生，由调度程序“调度”而运行，因“等待事件”而阻塞，最后，由“撤消（destroy）”而消亡。可见，进程是有一定生命期的，是动态地产生，运行和消亡的。,并发性,进程的并发性是指多个进程可以同时在一个系统中并发地执行。,独立性,进程的独立性是指它可以作为系统进行资源分配和调度的独立单位,异步性,进程的异步性是指系统中的活动的进程总是按照各自独立的、不可预测的速度运行。,进程的结构,为了描述进程的运动变化过程并使之能独立地运行，应该为每个进程配置一个进程控制块（processcontrolblock简记为PCB）。,进程的结构,三部分所组成：一个程序段相应的数据段一个进程控制块在UNIX系统中，把这三部分统称为进程映像（image）。而将进程定义为“进程映像的执行。,进程的状态,就绪状态（Ready）运行状态（Running）阻塞状态（Blocked）,进程的状态,进程的状态(UNIX),进程控制块,进程标识符（Identification）进程的当前状态（Status）处理机状态保护区进程的起始地址资源清单进程优先数队列指针(pointer)或链接字(link)进程族的联系计账信息,为了对于进程进行控制，操作系统内必须设置一个机构，它具有上述进程控制及进程通讯和资源管理等功能。这样的机构称为操作系统的内核（Kernel）,原语,所谓原语（Primitive）是机器指令的延伸，它由若干条指令组成，用以完成特定功能的一段程序。为了保证原语操作的正确性，原语在执行期间是原子的，亦即原语在执行期间是不可分割的。,原语,创建原语（CreatePrimitive）悬挂原语（SuspendPrimitive）激活原语（ActivatePrimitive）阻塞原语（BlockPrimitive）唤醒原语（WakeupPrimitive）撤消原语（DestroyPrimitive）,对进程之间共享资源的控制必须满足下列要求：,安全性（safety）活动性（liveness）公正性（fairness）,安全性（safety）,在任意一个给定时刻只允许至多一个进程使用一个共享资源，不允许两个及两个以上进程同时使用同样的共享资源。否则，进程对共享资源操作的结果往往是破坏性的。,活动性（liveness）,活动性表现为两个方面，一方面任意一个进程在使用共享资源时，必须在有限时间内释放，不能无限期地占用而导致其它进程永远无法使用；另一方面当某个进程欲使用共享资源时，则应在有限时间内达到目的，而不应该互相阻止导致彼此永远都不能使用。,公正性（fairness）,对进程使用共享资源的次序不作不公正的规定。当某个进程欲使用共享资源时，只要其它进程不在使用该共享资源，就应该允许该进程使用。并且任意一个要求使用共享资源的进程不能无限期地等待，总应该在某个公正的时间界限内获得该资源。,第4节进程的同步与互斥,进程之间常常相互作用，并存在某种彼此依赖或互相制约的关系这些关系按其性质可分为同步（synchronization）和互斥（mutualexclusion）关系。,进程的同步,一进程运行到某点时，要求另一伙伴进程它提供信息，在未得到这一信息时，该进程等待，直至收到这一信息后，才能继续执行。它们彼此都清楚对方的存在及作用，而且每一进程还可能直接依赖于本组进程中其它成员所产生（或所提供）的数据。这是进程间的一种直接交互关系，表现了进程间协同工作的特性，因此称为进程间的同步关系。,临界资源,并发进程可以共享系统中的各种资源，但系统中的有些资源具有一次仅允许一个进程所使用的属性。我们称这类资源为临界资源（criticalresources）。,进程的互斥,若一进程在使用临界资源时，则其它欲占用者必须等待，仅当使用者释放后，等待的进程才可使用它。这就导致了若干进程因竞争临界资源而不得互斥地执行的情况。进程间的这种现象就称为进程的互斥。,临界区,在操作系统中把访问临界资源的那段程序称为临界段或临界区（criticalsection）。临界段问题实质上是一个互斥问题。,临界段应遵循下面的原则：,当有多个进程都希望进入它们的临界段时，它们不应相互封锁，而应在有限时间内让其中之一进入临界段。每次至多只有一个进程进入临界段中。当某一进程已进入临界段，其它试图进入该临界段的进程必须等待。位于临界段中的进程只能在其中逗留有限的时间一旦它离开临界段，则应允许某个等待进入临界段的进程进入其中。,同步机制,进程的同步是通过同步机制实现的。同步机制主要有两个作用：第一，它能够推迟一个进程的执行直至给定的条件成立。第二，它可用来保证一个语句序列是一个不可分割的操作。,1.忙等待busywaiting）,为了唤醒一个条件，进程给一个共享变量置值，为了等待那个条件，进程反复地测试那个共享变量直至获得所需要的值。由于等待条件的进程必须反复地测试那个共享变量，因此称采用这种方式阻塞进程执行的技术为忙等待。,计算机硬件配置指令,测试与设置(TestandSet简记为TS)functionTest-and-Set(vartarget:boolean):boolean;Test-and-Set:=target;target:=TRUE;end;,利用测试与设置的同步,lock(mutex)：while(TS(mutex);unlock(mutex)：mutex:=FALSE;,计算机硬件配置指令,对换（Swap）指令该对换指令对换内存两个单元的内容。procedureSwap(vara,b:boolean);vartemp:boolean;begintemp:=a;a:=b;b:=tempend;,利用对换指令的同步,lock(mutex):key:=TRUE;repeatSwap(mutex,key)untilkey=FALSE;unlock(mutex):mutex:=FALSE;,Dekker的软件解（1968）,intturn;booleanflag2;process(i)inti;while(TRUE)compute;flagi:=TRUE;while(flag(i+1)mod2)if(turn=i)continue;flagi:=FALSE;,Dekker的软件解,while(turni);gototry;critical_section;turn:=(turn+1)mod2;flagi:=FALSE;turn:=0;flag0:=FALSE;flag1:=FALSE;Process(0)ANDprocess(1);,Peterson的软件解198l,#includeprototypes.h#defineFALSE0#defineTRUE1#defineN2/*numberofprocess*/intturn;/*whoseturnisit*/intinterestedN;/*allvaluesinitially0(FALSE)*/,voldenter-region(intprocess)/*process:whoisentering(0or1)*/intother;/*/other=1-process;interestedprocess=TRUE;turn=process;while(turn=process/*nullstatement*/,voidleave-region(intprocess)/*process:whoisleaving(0or1)*/interestedprocess=FALSE;/*indicatedeparturefromcriticalregion*/,intturn;booleanflag2;process(i)inti;while(TRUE)compute;flagi:=TRUE;while(flagi+1mod2)(turn=i+1mod2);critical_section;turn:=(turn+1)mod2;flagi:=FALSE;,turn:=0;flag0:=FALSE;flag1:=FALSE;Process(0)ANDprocess(1);,2.信号量及其P、V操作,信号量（semaphore）Dijkstra，1963是一个整型变量，与其相关的两个操作是P、V操作。它是最早提出的同步操作原话，P、V操作的名称源于荷兰字Prolagen（试图降低）和Verhogen（升起)。,信号量及其P、V操作,定义2.1一个信号量s是一个非负整型变量，它仅仅可以由下列的两个不可分的（即原子的）访问例程之一来测试和修改：,P(s)和V(s)操作,P(s):whiles0do;s:=s-1;V(s):s:=s+1主要缺点是忙等待,P(s)操作,typesemaphore=recordvalue:integer;L:listofprocess;end;信号量的value初值表示系统中某类资源的数目。因此，这类信号量又称资源信号量。,P(s)操作,P(semaphoreS)S.valueS.valuel;IfS.value0then阻塞该进程，并把它置入S.L等待队列中；操作系统重新调度;else该进程继续执行;,V(s)操作,V(semaphoreS)S.value=S.valuel;IfS.value0then从S.L等待队列中取出一进程;将其状态改为“就绪”，并且放入就绪队列;else该进程继续执行;,互斥问题,为了解决互斥问题，每个临界段前后分别放一个P、V操作，它们都操作在同一信号量上，所有互斥的临界段利用相同的信号量，且该信号量的初值为1。,programmutex-example;varmutex:semaphoreinitial(1);,processP1;1oopP(mutex);临界段;V(mutex);非临界段;endend;end.,processP2;1oopP(mutex);临界段;V(mutex);非临界段;endend;,programsynch-example;vars1,s2:semaphoreinitial(0,0);,processP1;1oopsend(message);V(s1);P(s2);end;end;end.,processP2;1oopP(s1);receive(message);V(s2);end;end;,有界缓冲区（生产者和消费者）问题,假设一个系统包含两个进程，其中之一产生信息，称之为生产者进程（producerprocess），另一个使用生产者进程所产生的信息，称之为消费者进程（consumerprocess）。两个进程可以交换所需信息，使生产者进程从一个空缓冲池（bufferpool）中得到一个空缓冲区，将信息填写其中，然后再把它放到满缓冲池之中。,有界缓冲区（生产者和消费者）问题,消费者进程从满缓冲池内取出满缓冲区，从满缓冲区复制出信息，然后再把它放到空缓冲池之中，以便再循环利用。我们不喜欢给生产者和消费者进程以无限个缓冲区；而只分配N个缓冲区给它们以交换信息。下列程序表示了生产者和消费者进程的程序。,有界缓冲区（生产者和消费者）问题,Semaphores=1;Semaphorefull=0;Semaphoreempty=N;buf_typebufferN;,producer()ANDconsumer();,produrcer()buf_type*next,*here;while(TRUE)produce_item(next);P(empty);P(s);here:=obtain(empty);V(s);copy_buffer(next,here);P(s);release(here,full);V(s);V(full);,consumer()buf_type*next,*here;while(TRUE)P(full);P(s);here:=obtain(full);V(s);copy_buffer(here,next);P(s);release(here,empty);V(s);V(empty);consume_item(next);,读者和作者(Readers-Writers)问题,Courtois，Heymans和Parnas在1971年提出了另一个有趣的同步问题，即读者和作者问题。假设一个资源被两类不同类型的进程集合之间共享，一类进程称为读者，而另一类进程称为作者。一个读者进程可以和任何其它读者进程共享该资源，但是不和任何一个作者进程共享。每当一个作者进程需要访问这个资源时，要求互斥访问。这种情景非常类似于一个文件被一组进程所共享。,读者和作者(Readers-Writers)问题,为了管理共享资源，可以实施若干不同的策略。通常有弱读者进程优先、强读者进程优先和作者进程优先三种策略。例如，每当任何一个读者进程访问该共享资源时，则任何一个作者进程请求访问该共享资源必须等待，直到无活动的读者进程为止。该共享资源变为可用。这种弱读者进程优先的策略其实现算法请见。,弱读者进程优先策略,resource_type*resource;intread_count=0;读者计数器semaphores=1;semaphorewrite_block=1;第一个读者和所有作者执行P(write_block)最后一个读者离开时执行V(write_block),read()while(TRUE)other_computing;P(s);read_count:=read_count+1;if(read_count=1)P(write_block);V(s);access(resource);P(s);read_count:=read_count-1;if(read_count=0)V(write_block);V(s);,writer()while(TRUE)other_computing;P(write_block);access(resource);V(write_block);/*Therecouldbemanyreadersandmanywriters*/reader()ANDwriter()；,作者进程优先策略,resource_type*resource;intread_count=0write_count=0;semaphores1=1,s2=1;semaphoreread_block=1;semaphorewrite_pending=1;semaphorewrite_block=1;第一个作者阻塞在read_block上随后读者阻塞在write_pending上,read()while(TRUE)other_computing;P(write_pending);P(read_block);P(s1);read_count:=read_count+1;if(read_count=1)P(write_block);V(s1);V(read_block);V(write_pending);,access(resource);P(s1);read_count:=read_count-1;if(read_count=0)V(write_block);V(s1);,writer()while(TRUE)other_computing;P(s2);write_count:=write_count+1;if(write_count=1)P(read_block);V(s2);P(write_block);access(resource);V(write_block);,P(s2);write_count:=write_count-1;if(write_count=0)V(read_block);V(s2);/*Therecouldbemanyreadersandmanywriters*/reader()ANDwriter()；,AND同步机制,在许多并行程序中，进程们必须在某个条件集合上而不是仅在单个条件上同步。下面的哲学家用餐问题就是一个很好的例子。,哲学家用餐问题,Dijkstra引入了五个哲学家问题。假定五个哲学家围住在餐桌旁每人前面放了一个盘子，在相邻的两个盘子之间放了一只筷子，当哲学家在思考时，他不使用盘子和筷子，但是当哲学家决定吃时，他必须拿到他面前盘子的左右两只筷子才能吃。我们规定在一个给定的时刻，哲学家只能拿一只筷子。哲学家们就这样交替地思考和吃。是一个典型的信号量解。不幸地，这个解是不安全的，因为当所有的同时决定吃时，出现死锁。,semaphorefork5;philosopher(i)inti;while(TRUE)Thinking();P(forki);P(fork(i+1)mod5);eat();V(fork(i+1)mod5);V(forki);,同时P（simultaneousP）操作,假定一个P操作能够保证得到在一个集合中的所有信号量或者没有任一个，我们称这个P操作为同时P（simultaneousP）操作。同时P操作具有形式为：Psimultaneous(S1,S2,Sn)同时V操作具有形式为：Vsimultaneous(S1,S2,Sn),Psimultaneous(S1,S2,Sn),if(S11)(S21)(Sn1)thenfori:=1tondoSi:=Si-1;endforelse把进程放在首先找到Si1相联的等待队列中，并置该进程的程序计数器为此操作的开始。endif,Vsimultaneous(S1,S2,Sn),fori:=1tondoSi:=Si+1;把与Si相联的等待队列中所有的进程移到就绪队列。endfor,当n=2时Psimultaneous的一种实现,/*Sharedvariables*/intS1,R1;semaphoremutex;semaphoreblock;/*Initializesemaphores*/mutex:=1;block:=0;,P(S,R)P(mutex);S1:=S1-1;R1:=R1-1;if(S10)(R10)V(mutex);P(block);elseV(mutex);,V(S,R)P(mutex);S1:=S1+1;R1:=R1+1;if(S10)(R10)V(block);V(mutex);,Psimultaneous(S1,t1,d1,S2,t2,d2,Sn,tn,dn),if(S1t1)(S2t2)(Sntn)thenfori:=1tondoSi:=Si-di;endforelse把进程放在首先找到Siti相联的等待队列中，并置该进程的程序计数器为此操作的开始。endif,Vsimultaneous(S1,d1,S2,d2,Sn,dn),fori:=1tondoSi:=Si+di;把与Si相联的等待队列中所有的进程移到就绪队列。endfor,条件临界域,虽然信号量基本上可用于解决差不多任何类型的同步问题，但P、V操作是非结构化的原语，因此在使用它们时极易出错，执行临界段之前必须先执行一个P操作。在退出临界段时再执行一个V操作（在相同的信号量上）。忽略一个P或V操作或者意外地让P操作在一个信号量上而让V操作在另一个信号量上就会乱套，在这种情况下，互斥执行的特性不再会得到保证。,条件临界域,此外，在运用信号量时，程序员可能会忘记将所有涉及到共享变量的语句包括在临界段中，显然，这也可能破坏临界段所需要的互斥执行。使用信号量的另一困难是条件同步互斥都是使用相同形式的原语对偶来编码的，从而难以弄清一对给定的P、V操作的目的。因为互斥和条件同步是不同的概念，它们应该有不同的表示形式。,条件临界域,条件临界域（conditionalcriticalregion）Hoare，1972；BrinchHansen，1972通过提供结构化的表示法来描述同步而弥补了上述不足。共享变量明显地归纳为一组，并且予以命名，称为资源resource），每个共享变量至多只处于一个resource中且只能在命名该resource的条件临界域（简记为CCR）语句中存取。,条件临界域,一个包含变量v1，v2，vn的resourceR说明为resourceR:v1，v2，vn;R中的变量只能由命名R的CCR语句存取。这种语句形如：regionRwhenBdoS;其中，B是一个布尔表达式，S是一组语句，局部于正在执行的进程的局部变量也可以出现在CCR语句中。互斥是通过保证执行不同的CCR语句来实现的。,条件临界域,即每个命名相同resource的语句是不重迭的。条件同步是通过CCR语句中明显地给出的布尔条件加以保证。CCR语句阻塞执行它的进程直至B为true，然后执行s。计算B和执行S是不可由另外命名相同resource的一些CCR语句所中断的。因此，当开始执行S时，B保证为true。这种机制通常假定是公正的，一个处于等待条件B的进程最终会由于B为true而得以继续执行。,条件临界域,programOPSYS;typebuffer(T)=recordslots:array(0.N-1)ofT;head,tail:0.N-1initial(0,0);size:0.Ninitial(0);end;varinpbuff:buffer(cardimage);outbuff:buffer(lineimage);resourceib:inpbuff,ob,outbuff;,条件临界域,processreader;varcard:cardimage;loopreadcardfromcardreader;regionibwheninpbuff.size0docard:=inpbuff.slotsinpbuff.head;inpbuff.size:=inpbuff.size-1;inpbuff.head:=(inpbuff.head+1)modNend;processcardandgenerateline;,条件临界域,regionobwhenoutbuff.size0doline=outbuff.slotsoutbuff.head;outbuff.size:=outbuff.size-1;outbuff.head:=(outbuff.head+1)modNendendend;end.,条件临界域,虽然CCR有许多优点，但实现起来代价过大，因为CCR语句中的条件可以包含对局部变量的访问，而且每个进程都必须计算它自己的条件。在一个含有多道程序的处理机上，这种计算的结果导致若干内容的切换（频繁地保存和恢复进程状态），其中的许多工作可能是无效的，因为活跃的进程仍然可能发现相应的条件为false。若每个进程都在它自己的处理机上运行且内存是共享的，则CCR语句很容易利用忙等待技术实现。,条件临界域,Edison语言BrinchHansen，1981包含有CCR语句，该语言是专为多处理机系统设计的。CCR语句的一些变种也在DPBrinchHansen，1978和ArgueLiskov，Scheifler，1982中使用了。,管程（monitor）,管程（monitor）Dijkstra，1968；BrinchHansen，1973；Hoare，1974是指一组公共数据同与其有关的操作的集合。只有引用管程中的操作才能访问管程中的数据。一个进程引用管程中操作时，只有在管程中的各操作均不处于活跃状态时才被响应，当管程中一个操作已执行完毕或在执行中处于等待状态时，它就不是活跃状态。管程将公共数据同与其有关的操作集中在一起，使得并发程序容易理解，也易于保证程序的正确性。因此，管程是一种结构化的同步机制。,管程（monitor）,定义（Hoare的定义）管程是一个抽象数据类型，在任何给定的时刻仅仅一个进程能够执行管程内的过程。,管程（monitor）,局部于管程的变量仅能被该管程中的过程所访问。一个管程与外部世界的通信是通过其所含过程的参数进行的。管程本身是一个静态的被动的对象。一个进程执行管程的唯一方式是通过调用管程中的过程来体现的。执行给定管程中的过程保证是互斥进行的，这确保了局部于该管程的变量（即该管程首部说明的量）是决不能并发存取的。,条件变量（conditionvariable）,“条件变量”（conditionvariable）用于推迟管程中正在执行的进程，它只能在管程中说明。定义在条件变量上的两个操作是signal和wait。如果cond是一条件变量，那么执行cond.wait将引起引用者阻塞在cond上，并撤消它的互斥控制。,条件变量（conditionvariable）,执行cond.signal的工作过程如下：若没有进程阻塞在cond上，则该引用者继续执行，否则，该引用者暂时被挂起，并且重新激活阻塞在cond上的一个进程；仅当该管程中不存在其它正在执行的进程时，才允许由于signal操作而挂起的进程继续执行。,有界缓冲区管程,typebuffer(T)monitor;varslots:array0.N-1ofT;head,tail:0.N-1;size:0.N;notfull,notempty:condition;,有界缓冲区管程,proceduredeposit(p:T);beginifsize=Nthennotfull.wait;slotstail:=p;size:=size+1;tail:=(tail+1)modN;notempty.signalend;,有界缓冲区管程,procedurefetch(varit:T);beginifsize=0thennotempty.wait;it:=slotshead;size:=size-1;head:=(head+1)modN;notfull.signal;end;beginsize:=0;head:=0;tail:=0;end.,用管程技术编写的简单批处理操作系统,programOPSYS;typebuffer(T)=monitor;varinpbuff:buffer(cardimage);outbuff,buff:buffer(lineimage);processreader;varcard:cardimage;1oopreadcardfromcardreader;callinpbuff.deposit(card);endend;,用管程技术编写的简单批处理操作系统,processexecuter;varcard:cardimage;line:lineimage;1oopcallinpbuff.fetch(card);processcardandgenerateline;calloutbuff.deposit(line);endend;,用管程技术编写的简单批处理操作系统,processprinter;varline:lineimage;1oopcalloutbuff.fetch(line);printlineonlineprinter;endend;end.,优先wait语句,有时程序设计者希望控制唤醒被推迟进程的次序，为此，可使用“优先wait”语句：cond.wait(p)它与cond.wait的语义基本相同，主要差别在于阻塞在条件变量cond上的进程此时是按P的递增次序予以唤醒。,管程（monitor）,并发PASCAL是支持管程的第一个程序设计语言，该语言己被用于编写若干操作系统，例如Solo，（一个单用户操作系统），Jobstream（处理PASCAL程序的一个批处理操作系统）以及一个实时处理控制系统。ModulaWirih，1977也含有类似管程的模块。,定序器和事件计数器SequencersandEventcounts,定义一个事件计数器（eventcount）是一个整型变量，初始值为0，它取值于一个严格单调增加的非负整数集合。一个事件计数器仅仅能够实施下列操作：advance(E)：过程advance(E)用于宣告一个和E有关的事件的出现，它引起事件计数器E增加1；并且唤醒处在事件计数器E等待队列中的一个或多个进程。即E:=E+1；并且唤醒处在事件计数器E等待队列中的达到E当前值的一个或多个进程。,事件计数器,read(E)：一个进程利用read(E)来决定事件计数器E的值，它返回事件计数器E的当前值。即，return(E);await(E,v)：一个进程调用await(E,v)，将引起该进程在Ev时被阻塞。即，ifEvthen将调用的进程放在于E相关的等待队列中，变成阻塞状态，调用进程调度程序；endif;,定序器,定义一个定序器（sequencer）是一个整型变量，初始值为0，它取值于一个严格单调增加的非负整数集合。仅仅ticket(T)能够应用到定序器T上，它导致定序器T增加并且返回定序器T增加前的值。对ticket的调用是原子的，即定序器T被用来在某个半序事件集合上放一个全序。,定序器,一个定序器相应于刚抵达的顾客所拿到的服务号码，一个定序器的值是下一个将要取的号码，可以将定序器看成一个自动售票机。ticket操作对应于一个新来的顾客取一个唯一的服务号码。一个事件计数器可以看成是一个服务号码栈，它的当前值是服务号码栈顶值。一个await操作对应于一个顾客开始等待服务。一个advance操作对应于一个初始化服务，事件计数器被增加并且允许服务下一个顾客（进程）。,定序器,一个进程执行临界区的操作序列为await(E,ticket(S);临界区；advance(E);,利用定序器和事件计数器实现P和V,Structsemaphoreintinitial_value;/*Initialvalueofthesemaphore*/eventcounte;sequencert;s;,利用定序器和事件计数器实现P和V,P(s)V(s)semaphores;semaphores;inti;advance(s.e);i:=ticket(s.t);await(s.e,i+1-s.initial_value);eventcountin,out;sequencerPticket,Cticket;buffer:array0.Nofmessage;producer()consumer()intt,i:=1;intu,i:=1;message:m;messagem;while(true)while(true)m:=produce();t:=ticket(Pticket);u:=ticket(Cticket);/*一次一个生产者*/*一次一个消费者*/await(in,t);awit(out,u);awit(out,t-N+1);await(in,u+1);/*等待一个空缓冲区别*/*等待一个消息*/buffertmodN:=m;m:=bufferumodN;advance(in);advance(out);/*信号一个满缓冲区及*/*信号一个满缓冲区*/*允许其它生产者*/*允许其它消费者*/consume(m);图-利用定序器和事件计数器实现生产者和消费者问题eventcountE;sequencerT;Pboth(R,S)semaphoreR,S;intq,r,s;q:=ticket(T);await(E,q);r:=ticket(R.t);s:=ticket(S.t);advance(E);await(R.e,r+1-R.initial_value);await(R.e,r+1-R.initial_value);图-利用定序器和事件计数器实现SimultaneousP,利用定序器和事件计数器实现P和V,P(s)V(s)semaphores;semaphores;inti;advance(s.e);i:=ticket(s.t);await(s.e,i+1-s.initial_value);eventcountin,out;sequencerPticket,Cticket;buffer:array0.Nofmessage;producer()consumer()intt,i:=1;intu,i:=1;message:m;messagem;while(true)while(true)m:=produce();t:=ticket(Pticket);u:=ticket(Cticket);/*一次一个生产者*/*一次一个消费者*/await(in,t);awit(out,u);awit(out,t-N+1);await(in,u+1);/*等待一个空缓冲区别*/*等待一个消息*/buffertmodN:=m;m:=bufferumodN;advance(in);advance(out);/*信号一个满缓冲区及*/*信号一个满缓冲区*/*允许其它生产者*/*允许其它消费者*/consume(m);图-利用定序器和事件计数器实现生产者和消费者问题eventcountE;sequencerT;Pboth(R,S)semaphoreR,S;intq,r,s;q:=ticket(T);await(E,q);r:=ticket(R.t);s:=ticket(S.t);advance(E);await(R.e,r+1-R.initial_value);await(R.e,r+1-R.initial_value);图-利用定序器和事件计数器实现SimultaneousP,利用定序器和事件计数器实现P和V,P(s)V(s)semaphores;semaphores;inti;advance(s.e);i:=ticket(s.t);await(s.e,i+1-s.initial_value);eventcountin,out;sequencerPticket,Cticket;buffer:array0.Nofmessage;producer()consumer()intt,i:=1;intu,i:=1;message:m;messagem;while(true)while(true)m:=produce();t:=ticket(Pticket);u:=ticket(Cticket);/*一次一个生产者*/*一次一个消费者*/await(in,t);awit(out,u);awit(out,t-N+1);await(in,u+1);/*等待一个空缓冲区别*/*等待一个消息*/buffertmodN:=m;m:=bufferumodN;advance(in);advance(out);/*信号一个满缓冲区及*/*信号一个满缓冲区*/*允许其它生产者*/*允许其它消费者*/consume(m);图-利用定序器和事件计数器实现生产者和消费者问题eventcountE;sequencerT;Pboth(R,S)semaphoreR,S;intq,r,s;q:=ticket(T);await(E,q);r:=ticket(R.t);s:=ticket(S.t);advance(E);await(R.e,r+1-R.initial_value);await(R.e,r+1-R.initial_value);图-利用定序器和事件计数器实现SimultaneousP,利用定序器和事件计数器实现P和V,P(s)V(s)semaphores;semaphores;inti;advance(s.e);i:=ticket(s.t);await(s.e,i+1-s.initial_value);eventcountin,out;sequencerPticket,Cticket;buffer:array0.Nofmessage;producer()consumer()intt,i:=1;intu,i:=1;message:m;messagem;while(true)while(true)m:=produce();t:=ticket(Pticket);u:=ticket(Cticket);/*一次一个生产者*/*一次一个消费者*/await(in,t);awit(out,u);awit(out,t-N+1);await(in,u+1);/*等待一个空缓冲区别*/*等待一个消息*/buffertmodN:=m;m:=bufferumodN;advance(in);advance(out);/*信号一个满缓冲区及*/*信号一个满缓冲区*/*允许其它生产者*/*允许其它消费者*/consume(m);图-利用定序器和事件计数器实现生产者和消费者问题eventcountE;sequencerT;Pboth(R,S)semaphoreR,S;intq,r,s;q:=ticket(T);await(E,q);r:=ticket(R.t);s:=ticket(S.t);advance(E);await(R.e,r+1-R.initial_value);await(R.e,r+1-R.initial_value);图-利用定序器和事件计数器实现SimultaneousP,利用定序器和事件计数器实现P和V,P(s)semaphores;inti;i:=ticket(s.t);await(s.e,i+1-s.initial_value);,V(s)semaphores;advance(s.e);,利用定序器和事件计数器实现生产者和消费者问题,eventcountin,out;sequencerPticket,Cticket;buffer:array0.Nofmessage;producer()consumer()intt,i:=1;intu,i:=1;message:m;messagem;while(true)while(true)m:=produce();t:=ticket(Pticket);u:=ticket(Cticket);/*一次一个生产者*/*一次一个消费者*/await(in,t);awit(out,u);awit(out,t-N+1);await(in,u+1);/*等待一个空缓冲区别*/*等待一个消息*/buffertmodN:=m;m:=bufferumodN;advance(in);advance(out);/*信号一个满缓冲区及*/*信号一个满缓冲区*/*允许其它生产者*/*允许其它消费者*/consume(m);eventcountE;sequencerT;Pboth(R,S)semaphoreR,S;intq,r,s;q:=ticket(T);await(E,q);r:=ticket(R.t);s:=ticket(S.t);advance(E);await(R.e,r+1-R.initial_value);await(R.e,r+1-R.initial_value);图-利用定序器和事件计数器实现SimultaneousP,producer()intt,i:=1;message:m;while(true)m:=produce();u:=ticket(Cticket);/*一次一个生产者*/await(in,t);awit(out,t-N+1);/*等待一个空缓冲区*/buffertmodN:=m;advance(in);/*信号一个满缓冲区及*/*允许其它生产者*/,consumer()intu,i:=1;message:m;while(true)t:=ticket(Pticket);/*一次一个消费者*/awit(out,u);await(in,u+1);/*等待一个消息*/m:=bufferumodN;advance(out);/*信号一个满缓冲区*/*允许其它消费者*/consume(m);,利用定序器和事件计数器实现同时P,eventcountE;sequencerT;Pboth(R,S)semaphoreR,S;intq,r,s;q:=ticket(T);await(E,q);r:=ticket(R.t);s:=ticket(S.t);advance(E);await(R.e,r+1-R.initial_value);await(R.e,r+1-R.initial_value);,路径表达式,路径表达式(pathexpression）是由Campbell和Habermann1974首先提出的，后人又对其进行了完善和扩充。路径表达式的语法公式为pathpath-listend其中path-list由操作名和路径操作符组成，路径操作符包括：，表示并发；表示顺序；n：(path-list)表示path-list的（至多）n次并发激活；path-list表示path-list的无穷次并发激活。,路径表达式,例如，路径表达式pathdeposit,fetchend既没有限制deposit和fetch执行的次序，也没有规定它们的激活次数，它等价于下面的路径表达式：pathdeposit,fetchend或pathdeposit,fetchend但路径表达式pathde