第2章分布式操作系统课件.ppt

1、进程（进程（process）或任务（）或任务（task）这）这一术语是在六十年代初期，首先在一术语是在六十年代初期，首先在麻省理工学院（麻省理工学院（MIT）的）的MULTICS系统和系统和IBM公司的公司的CTSS/360系统中系统中引入的，其后有许多人对进程下过引入的，其后有许多人对进程下过各式各样的定义，下面列举几种比各式各样的定义，下面列举几种比较能反映进程实质的定义：较能反映进程实质的定义：有界缓冲区（生产者和消费者）问有界缓冲区（生产者和消费者）问题题假设一个系统包含两个进程，其中之一假设一个系统包含两个进程，其中之一产生信息，称之为生产者进程（产生信息，称之为生产者进程（prod

2、ucerprocess），另一个使用生产者进程所产），另一个使用生产者进程所产生的信息，称之为消费者进程（生的信息，称之为消费者进程（consumer process）。两个进程可以交换所需信息，）。两个进程可以交换所需信息，使生产者进程从一个空缓冲池（使生产者进程从一个空缓冲池（buffer pool）中得到一个空缓冲区，将信息填写）中得到一个空缓冲区，将信息填写其中，然后再把它放到满缓冲池之中。其中，然后再把它放到满缓冲池之中。有界缓冲区（生产者和消费者）问有界缓冲区（生产者和消费者）问题题消费者进程从满缓冲池内取出满缓冲区，消费者进程从满缓冲池内取出满缓冲区，从满缓冲区复制出信息，然后再

3、把它放到从满缓冲区复制出信息，然后再把它放到空缓冲池之中，以便再循环利用。我们不空缓冲池之中，以便再循环利用。我们不喜欢给生产者和消费者进程以无限个缓冲喜欢给生产者和消费者进程以无限个缓冲区；而只分配区；而只分配N个缓冲区给它们以交换信个缓冲区给它们以交换信息。下列程序表示了生产者和消费者进程息。下列程序表示了生产者和消费者进程的程序。的程序。有界缓冲区（生产者和消费者）问有界缓冲区（生产者和消费者）问题题Semaphores=1;Semaphorefull=0;Semaphoreempty=N;buf_type bufferN;producer()AND consumer();produrc

4、er()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

5、_item(next);读者和作者读者和作者(Readers-Writers)问题问题Courtois，Heymans和和Parnas在在1971年提出年提出了另一个有趣的同步问题，即读者和作者了另一个有趣的同步问题，即读者和作者问题。假设一个资源被两类不同类型的进问题。假设一个资源被两类不同类型的进程集合之间共享，一类进程称为读者，而程集合之间共享，一类进程称为读者，而另一类进程称为作者。一个读者进程可以另一类进程称为作者。一个读者进程可以和任何其它读者进程共享该资源，但是不和任何其它读者进程共享该资源，但是不和任何一个作者进程共享。每当一个作者和任何一个作者进程共享。每当一个作者进程需要访

6、问这个资源时，要求互斥访问。进程需要访问这个资源时，要求互斥访问。这种情景非常类似于一个文件被一组进程这种情景非常类似于一个文件被一组进程所共享。所共享。读者和作者读者和作者(Readers-Writers)问题问题为了管理共享资源，可以实施若干不为了管理共享资源，可以实施若干不同的策略。通常有弱读者进程优先、同的策略。通常有弱读者进程优先、强读者进程优先和作者进程优先三种强读者进程优先和作者进程优先三种策略。例如，每当任何一个读者进程策略。例如，每当任何一个读者进程访问该共享资源时，则任何一个作者访问该共享资源时，则任何一个作者进程请求访问该共享资源必须等待，进程请求访问该共享资源必须等待，

7、直到无活动的读者进程为止。该共享直到无活动的读者进程为止。该共享资源变为可用。这种弱读者进程优先资源变为可用。这种弱读者进程优先的策略其实现算法请见。的策略其实现算法请见。弱读者进程优先策略弱读者进程优先策略resource_type*resource;int read_count=0;读者计数器读者计数器semaphore s=1;semaphore write_block=1;第一个读者和所有作者执行第一个读者和所有作者执行P(write_block)最后一个读者离开时执行最后一个读者离开时执行V(write_block)read()while(TRUE)other_computing;P

8、(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);/*There could be many readers and many writers*/reader()AND writer()；作

9、者进程优先策略作者进程优先策略resource_type *resource;int read_count=0write_count=0;semaphore s1=1,s2=1;semaphore read_block=1;semaphore write_pending=1;semaphore write_block=1;第一个作者阻塞在第一个作者阻塞在read_block上上随后读者随后读者 阻塞在阻塞在write_pending上上read()while(TRUE)other_computing;P(write_pending);P(read_block);P(s1);read_count

10、:=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(resou

11、rce);V(write_block);P(s2);write_count:=write_count-1;if(write_count=0)V(read_block);V(s2);/*There could be many readers and many writers*/reader()AND writer()；AND同步机制同步机制在许多并行程序中，进程们必须在某个条在许多并行程序中，进程们必须在某个条件集合上而不是仅在单个条件上同步。件集合上而不是仅在单个条件上同步。下面的哲学家用餐问题就是一个很好下面的哲学家用餐问题就是一个很好的例子。的例子。哲学家用餐问题哲学家用餐问题Dijkst

12、ra引入了五个哲学家问题。假定五引入了五个哲学家问题。假定五个哲学家围住在餐桌旁每人前面放了一个个哲学家围住在餐桌旁每人前面放了一个盘子，在相邻的两个盘子之间放了一只筷盘子，在相邻的两个盘子之间放了一只筷子，当哲学家在思考时，他不使用盘子和子，当哲学家在思考时，他不使用盘子和筷子，但是当哲学家决定吃时，他必须拿筷子，但是当哲学家决定吃时，他必须拿到他面前盘子的左右两只筷子才能吃。我到他面前盘子的左右两只筷子才能吃。我们规定在一个给定的时刻，哲学家只能拿们规定在一个给定的时刻，哲学家只能拿一只筷子。哲学家们就这样交替地思考和一只筷子。哲学家们就这样交替地思考和吃。是一个典型的信号量解。不幸地，这

13、吃。是一个典型的信号量解。不幸地，这个解是不安全的，因为当所有的同时决定个解是不安全的，因为当所有的同时决定吃时，出现死锁。吃时，出现死锁。semaphorefork5;philosopher(i)int i;while(TRUE)Thinking();P(forki);P(fork(i+1)mod 5);eat();V(fork(i+1)mod 5);V(forki);同时同时P（simultaneous P）操作）操作假定一个假定一个P操作能够保证得到在一个集操作能够保证得到在一个集合中的所有信号量或者没有任一个，合中的所有信号量或者没有任一个，我们称这个我们称这个P操作为操作为同时同时P

14、（simultaneous P）操作。）操作。同时同时P操作具有形式为：操作具有形式为：Psimultaneous(S1,S2,Sn)同时同时V操作具有形式为：操作具有形式为：Vsimultaneous(S1,S2,Sn)Psimultaneous(S1,S2,Sn)Vsimultaneous(S1,S2,Sn)当当n=2时时Psimultaneous的一种实现的一种实现/*Shared variables*/int S1,R1;semaphore mutex;semaphore block;/*Initialize semaphores*/mutex:=1;block:=0;P(S,R)P(

15、mutex);S1:=S1-1;R1:=R1-1;if(S1 0)(R1 0)V(mutex);P(block);else V(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)t1t2tntiVsimultaneous(S1,d1,S2,d2,Sn,dn)条件临界域条件临界域虽然信号量基本上可用于解决差不多虽然信号量基本上可用于解决差不多任何类型的同步问题，但任何类型的同步问题，但P、V操作是操作是非结构化的原语，因此在使

16、用它们时非结构化的原语，因此在使用它们时极易出错，执行临界段之前必须先执极易出错，执行临界段之前必须先执行一个行一个P操作。在退出临界段时再执操作。在退出临界段时再执行一个行一个V操作（在相同的信号量上）。操作（在相同的信号量上）。忽略一个忽略一个P或或V操作或者意外地让操作或者意外地让P操操作在一个信号量上而让作在一个信号量上而让V操作在另一操作在另一个信号量上就会乱套，在这种情况下，个信号量上就会乱套，在这种情况下，互斥执行的特性不再会得到保证。互斥执行的特性不再会得到保证。条件临界域条件临界域此外，在运用信号量时，程序员可能会此外，在运用信号量时，程序员可能会忘记将所有涉及到共享变量的语

17、句包括忘记将所有涉及到共享变量的语句包括在临界段中，显然，这也可能破坏临界在临界段中，显然，这也可能破坏临界段所需要的互斥执行。使用信号量的另段所需要的互斥执行。使用信号量的另一困难是条件同步互斥都是使用相同形一困难是条件同步互斥都是使用相同形式的原语对偶来编码的，从而难以弄清式的原语对偶来编码的，从而难以弄清一对给定的一对给定的P、V操作的目的。因为互斥操作的目的。因为互斥和条件同步是不同的概念，它们应该有和条件同步是不同的概念，它们应该有不同的表示形式。不同的表示形式。条件临界域条件临界域条件临界域（条件临界域（conditional critical region）Hoare，1972；

18、Brinch Hansen，1972通过提供结构化的表示法来描述同步而通过提供结构化的表示法来描述同步而弥补了上述不足。共享变量明显地归纳弥补了上述不足。共享变量明显地归纳为一组，并且予以命名，称为资源为一组，并且予以命名，称为资源resource），每个共享变量至多只处于），每个共享变量至多只处于一个一个resource中且只能在命名该中且只能在命名该resource的条件临界域（简记为的条件临界域（简记为CCR）语句中存）语句中存取。取。条件临界域条件临界域一个包含变量一个包含变量v1，v2，vn的的resource R说明为说明为resource R:v1，v2，vn;R中的变量只能由命

19、名中的变量只能由命名R的的CCR语句存语句存取。这种语句形如：取。这种语句形如：region R when B do S;其中，其中，B是一个布尔表达式，是一个布尔表达式，S是一组语是一组语句，局部于正在执行的进程的局部变量句，局部于正在执行的进程的局部变量也可以出现在也可以出现在CCR语句中。互斥是通过语句中。互斥是通过保证执行不同的保证执行不同的CCR语句来实现的。语句来实现的。条件临界域条件临界域即每个命名相同即每个命名相同resource的语句是不重的语句是不重迭的。条件同步是通过迭的。条件同步是通过CCR语句中明显语句中明显地给出的布尔条件加以保证。地给出的布尔条件加以保证。CCR语

20、句语句阻塞执行它的进程直至阻塞执行它的进程直至B为为true，然后，然后执行执行s。计算。计算B和执行和执行S是不可由另外命是不可由另外命名相同名相同resource的一些的一些CCR语句所中断语句所中断的。因此，当开始执行的。因此，当开始执行S时，时，B保证为保证为true。这种机制通常假定是公正的，一。这种机制通常假定是公正的，一个处于等待条件个处于等待条件B的进程最终会由于的进程最终会由于B为为true而得以继续执行。而得以继续执行。条件临界域条件临界域program OPSYS;type buffer(T)=record slots:array(0.N-1)of T;head,tail

21、:0.N-1 initial(0,0);size:0.N initial(0);end;var inpbuff:buffer(cardimage);outbuff:buffer(lineimage);resource ib:inpbuff,ob,outbuff;条件临界域条件临界域 process reader;var card:cardimage;loop read card from cardreader;region ib when inpbuff.size 0 do card:=inpbuff.slotsinpbuff.head;inpbuff.size:=inpbuff.size-1

22、;inpbuff.head:=(inpbuff.head+1)mod N end;process card and generate line;条件临界域条件临界域 region ob when outbuff.size 0 do line=outbuff.slotsoutbuff.head;outbuff.size:=outbuff.size-1;outbuff.head:=(outbuff.head+1)mod N end end end;end.条件临界域条件临界域虽然虽然CCR有许多优点，但实现起来代价有许多优点，但实现起来代价过大，因为过大，因为CCR语句中的条件可以包含语句中的条件

23、可以包含对局部变量的访问，而且每个进程都必对局部变量的访问，而且每个进程都必须计算它自己的条件。在一个含有多道须计算它自己的条件。在一个含有多道程序的处理机上，这种计算的结果导致程序的处理机上，这种计算的结果导致若干内容的切换（频繁地保存和恢复进若干内容的切换（频繁地保存和恢复进程状态），其中的许多工作可能是无效程状态），其中的许多工作可能是无效的，因为活跃的进程仍然可能发现相应的，因为活跃的进程仍然可能发现相应的条件为的条件为false。若每个进程都在它自己。若每个进程都在它自己的处理机上运行且内存是共享的，则的处理机上运行且内存是共享的，则CCR语句很容易利用忙等待技术实现。语句很容易利用

24、忙等待技术实现。条件临界域条件临界域Edison语言语言Brinch Hansen，1981包含有包含有CCR语句，该语言是专为多处语句，该语言是专为多处理机系统设计的。理机系统设计的。CCR语句的一些变语句的一些变种也在种也在DPBrinch Hansen，1978和和ArgueLiskov，Scheifler，1982中使中使用了。用了。管程（管程（monitor）管程（管程（monitor）Dijkstra，1968；BrinchHansen，1973；Hoare，1974是指一组公是指一组公共数据同与其有关的操作的集合。只有引共数据同与其有关的操作的集合。只有引用管程中的操作才能访问管

25、程中的数据。用管程中的操作才能访问管程中的数据。一个进程引用管程中操作时，只有在管程一个进程引用管程中操作时，只有在管程中的各操作均不处于活跃状态时才被响应，中的各操作均不处于活跃状态时才被响应，当管程中一个操作已执行完毕或在执行中当管程中一个操作已执行完毕或在执行中处于等待状态时，它就不是活跃状态。管处于等待状态时，它就不是活跃状态。管程将公共数据同与其有关的操作集中在一程将公共数据同与其有关的操作集中在一起，使得并发程序容易理解，也易于保证起，使得并发程序容易理解，也易于保证程序的正确性。因此，管程是一种结构化程序的正确性。因此，管程是一种结构化的同步机制。的同步机制。管程（管程（moni

26、tor）定义（定义（Hoare的定义）管程是一个的定义）管程是一个抽象数据类型，在任何给定的时刻抽象数据类型，在任何给定的时刻仅仅一个进程能够执行管程内的过仅仅一个进程能够执行管程内的过程。程。管程（管程（monitor）局部于管程的变量仅能被该管程中局部于管程的变量仅能被该管程中的过程所访问。一个管程与外部世的过程所访问。一个管程与外部世界的通信是通过其所含过程的参数界的通信是通过其所含过程的参数进行的。管程本身是一个静态的被进行的。管程本身是一个静态的被动的对象。一个进程执行管程的唯动的对象。一个进程执行管程的唯一方式是通过调用管程中的过程来一方式是通过调用管程中的过程来体现的。执行给定管

27、程中的过程保体现的。执行给定管程中的过程保证是互斥进行的，这确保了局部于证是互斥进行的，这确保了局部于该管程的变量（即该管程首部说明该管程的变量（即该管程首部说明的量）是决不能并发存取的。的量）是决不能并发存取的。条件变量（条件变量（condition variable）“条件变量条件变量”（condition variable）用）用于推迟管程中正在执行的进程，它只于推迟管程中正在执行的进程，它只能在管程中说明。定义在条件变量上能在管程中说明。定义在条件变量上的两个操作是的两个操作是signal和和wait。如果。如果cond是一条件变量，那么执行是一条件变量，那么执行cond.wait将引

28、起引用者阻塞在将引起引用者阻塞在cond上，并撤消上，并撤消它的互斥控制。它的互斥控制。条件变量（条件变量（condition variable）执行执行cond.signal的工作过程如下：若没有进程阻塞在的工作过程如下：若没有进程阻塞在cond上，则该引用者继续执行，否则，上，则该引用者继续执行，否则，该引用者暂时被挂起，并且重新激活该引用者暂时被挂起，并且重新激活阻塞在阻塞在cond上的一个进程；仅当该管上的一个进程；仅当该管程中不存在其它正在执行的进程时，程中不存在其它正在执行的进程时，才允许由于才允许由于signal操作而挂起的进程继操作而挂起的进程继续执行。续执行。有界缓冲区管程有

29、界缓冲区管程type buffer(T)monitor;var slots:array0.N-1 of T;head,tail:0.N-1;size:0.N;notfull,notempty:condition;有界缓冲区管程有界缓冲区管程procedure deposit(p:T);begin if size=N then notfull.wait;slotstail:=p;size:=size+1;tail:=(tail+1)mod N;notempty.signal end;有界缓冲区管程有界缓冲区管程procedure fetch(var it:T);begin if size=0 t

30、hen notempty.wait;it:=slotshead;size:=size-1;head:=(head+1)mod N;notfull.signal;end;begin size:=0;head:=0;tail:=0;end.用管程技术编写的简单批处理操作系统用管程技术编写的简单批处理操作系统program OPSYS;type buffer(T)=monitor;var inpbuff:buffer(cardimage);outbuff,buff:buffer(lineimage);process reader;var card:cardimage;1oop read card f

31、rom cardreader;call inpbuff.deposit(card);end end;用管程技术编写的简单批处理操作系统用管程技术编写的简单批处理操作系统process executer;var card:cardimage;line:lineimage;1oop call inpbuff.fetch(card);process card and generate line;call outbuff.deposit(line);end end;用管程技术编写的简单批处理操作系统用管程技术编写的简单批处理操作系统 process printer;var line:lineimage

32、;1oop call outbuff.fetch(line);print line on lineprinter;end end;end.优先优先wait 语句语句有时程序设计者希望控制唤醒被推有时程序设计者希望控制唤醒被推迟进程的次序，为此，可使用迟进程的次序，为此，可使用“优先优先wait”语句：语句：cond.wait(p)它与它与cond.wait的语义基本相同，主的语义基本相同，主要差别在于阻塞在条件变量要差别在于阻塞在条件变量cond上上的进程此时是按的进程此时是按P的递增次序予以的递增次序予以唤醒。唤醒。管程（管程（monitor）并发并发PASCAL是支持管程的第一个是支持管程

33、的第一个程序设计语言，该语言己被用于编程序设计语言，该语言己被用于编写若干操作系统，例如写若干操作系统，例如Solo，（一，（一个单用户操作系统），个单用户操作系统），Job stream（处理（处理PASCAL程序的一个批处理程序的一个批处理操作系统）以及一个实时处理控制操作系统）以及一个实时处理控制系统。系统。ModulaWirih，1977也含也含有类似管程的模块。有类似管程的模块。定序器和事件计数器定序器和事件计数器Sequencers and Eventcounts定义定义一个事件计数器（一个事件计数器（eventcount）是）是一个整型变量，初始值为一个整型变量，初始值为0，它取

34、值于，它取值于一个严格单调增加的非负整数集合。一一个严格单调增加的非负整数集合。一个事件计数器仅仅能够实施下列操作：个事件计数器仅仅能够实施下列操作：advance(E)：过程：过程advance(E)用于宣告用于宣告一个和一个和E有关的事件的出现，它引起事有关的事件的出现，它引起事件计数器件计数器E增加增加1；并且唤醒处在事件；并且唤醒处在事件计数器计数器E等待队列中的一个或多个进程。等待队列中的一个或多个进程。即即E:=E+1；并且唤醒处在事件计数器；并且唤醒处在事件计数器E等待队列中的达到等待队列中的达到E当前值的一个或多当前值的一个或多个进程。个进程。事件计数器事件计数器read(E)

35、：一个进程利用：一个进程利用read(E)来决定来决定事件计数器事件计数器E的值，它返回事件计数器的值，它返回事件计数器E的当前值。即，的当前值。即，return(E);await(E,v)：一个进程调用：一个进程调用await(E,v)，将引起该进程在将引起该进程在E v时被阻塞。即，时被阻塞。即，if E v then 将调用的进程放在于将调用的进程放在于E相关的等待队相关的等待队 列中，变成阻塞状态，列中，变成阻塞状态，调用进程调度程序；调用进程调度程序；endif;定序器定序器定义定义一个定序器（一个定序器（sequencer）是一个整）是一个整型变量，初始值为型变量，初始值为0，它取

36、值于一个严格，它取值于一个严格单调增加的非负整数集合。仅仅单调增加的非负整数集合。仅仅ticket(T)能够应用到定序器能够应用到定序器T上，它导致定序器上，它导致定序器T增加并且返回定序器增加并且返回定序器T增加前的值。对增加前的值。对ticket的调用是原子的，即定序器的调用是原子的，即定序器T被用被用来在某个半序事件集合上放一个全序。来在某个半序事件集合上放一个全序。定序器定序器一个定序器相应于刚抵达的顾客所拿到一个定序器相应于刚抵达的顾客所拿到的服务号码，一个定序器的值是下一个的服务号码，一个定序器的值是下一个将要取的号码，可以将定序器看成一个将要取的号码，可以将定序器看成一个自动售票

37、机。自动售票机。ticket操作对应于一个新操作对应于一个新来的顾客取一个唯一的服务号码。一个来的顾客取一个唯一的服务号码。一个事件计数器可以看成是一个服务号码栈，事件计数器可以看成是一个服务号码栈，它的当前值是服务号码栈顶值。一个它的当前值是服务号码栈顶值。一个await操作对应于一个顾客开始等待服操作对应于一个顾客开始等待服务。一个务。一个advance操作对应于一个初始操作对应于一个初始化服务，事件计数器被增加并且允许服化服务，事件计数器被增加并且允许服务下一个顾客（进程）。务下一个顾客（进程）。定序器定序器一个进程执行临界区的操作序列为一个进程执行临界区的操作序列为await(E,ti

38、cket(S);临界区；临界区；advance(E);利用定序器和事件计数器实现利用定序器和事件计数器实现P和和VStruct semaphore intinitial_value;/*Initial value of the semaphore*/eventcount e;sequencer t;s;利用定序器和事件计数器实现利用定序器和事件计数器实现P和和VP(s)V(s)semaphore s;semaphore s;i n t i;advance(s.e);i:=ticket(s.t);await(s.e,i+1-s.initial_value);eventcount in,out;s

39、equencer Pticket,Cticket;buffer:array0.N of message;p r o d u c e r()consumer()int t,i:=1;intu,i:=1;message:m;message m;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);/*等待一个空缓冲区别等待一个空缓冲

40、区别*/*等等待一个消息待一个消息*/buffert mod N:=m;m:=bufferu mod N;advance(in);advance(out);/*信号一个满缓冲区及信号一个满缓冲区及*/*信信号一个满缓冲区号一个满缓冲区*/*允许其它生产者允许其它生产者*/*允允许其它消费者许其它消费者*/consume(m);图图-利用定序器和事件计数器实现生利用定序器和事件计数器实现生产者和消费者问题产者和消费者问题eventcount E;sequencer T;Pboth(R,S)semaphore R,S;intq,r,s;q:=ticket(T);await(E,q);r:=tick

41、et(R.t);s:=ticket(S.t);advance(E);await(R.e,r+1-R.initial_value);await(R.e,r+1-R.initial_value);图图-利用定序器和事件计数器实现利用定序器和事件计数器实现Simultaneous P利用定序器和事件计数器实现利用定序器和事件计数器实现P和和VP(s)V(s)semaphore s;semaphore s;i n t i;advance(s.e);i:=ticket(s.t);await(s.e,i+1-s.initial_value);eventcount in,out;sequencer Ptic

42、ket,Cticket;buffer:array0.N of message;p r o d u c e r()consumer()int t,i:=1;intu,i:=1;message:m;message m;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);/*等待一个空缓冲区别等待一个空缓冲区别*/*等等待一个消息待

43、一个消息*/buffert mod N:=m;m:=bufferu mod N;advance(in);advance(out);/*信号一个满缓冲区及信号一个满缓冲区及*/*信信号一个满缓冲区号一个满缓冲区*/*允许其它生产者允许其它生产者*/*允允许其它消费者许其它消费者*/consume(m);图图-利用定序器和事件计数器实现生利用定序器和事件计数器实现生产者和消费者问题产者和消费者问题eventcount E;sequencer T;Pboth(R,S)semaphore R,S;intq,r,s;q:=ticket(T);await(E,q);r:=ticket(R.t);s:=ti

44、cket(S.t);advance(E);await(R.e,r+1-R.initial_value);await(R.e,r+1-R.initial_value);图图-利用定序器和事件计数器实现利用定序器和事件计数器实现Simultaneous P利用定序器和事件计数器实现利用定序器和事件计数器实现P和和VP(s)V(s)semaphore s;semaphore s;i n t i;advance(s.e);i:=ticket(s.t);await(s.e,i+1-s.initial_value);eventcount in,out;sequencer Pticket,Cticket;b

45、uffer:array0.N of message;p r o d u c e r()consumer()int t,i:=1;intu,i:=1;message:m;message m;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);/*等待一个空缓冲区别等待一个空缓冲区别*/*等等待一个消息待一个消息*/buffert

46、 mod N:=m;m:=bufferu mod N;advance(in);advance(out);/*信号一个满缓冲区及信号一个满缓冲区及*/*信信号一个满缓冲区号一个满缓冲区*/*允许其它生产者允许其它生产者*/*允允许其它消费者许其它消费者*/consume(m);图图-利用定序器和事件计数器实现生利用定序器和事件计数器实现生产者和消费者问题产者和消费者问题eventcount E;sequencer T;Pboth(R,S)semaphore R,S;intq,r,s;q:=ticket(T);await(E,q);r:=ticket(R.t);s:=ticket(S.t);adv

47、ance(E);await(R.e,r+1-R.initial_value);await(R.e,r+1-R.initial_value);图图-利用定序器和事件计数器实现利用定序器和事件计数器实现Simultaneous P利用定序器和事件计数器实现利用定序器和事件计数器实现P和和VP(s)V(s)semaphore s;semaphore s;i n t i;advance(s.e);i:=ticket(s.t);await(s.e,i+1-s.initial_value);eventcount in,out;sequencer Pticket,Cticket;buffer:array0.

48、N of message;p r o d u c e r()consumer()int t,i:=1;intu,i:=1;message:m;message m;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);/*等待一个空缓冲区别等待一个空缓冲区别*/*等等待一个消息待一个消息*/buffert mod N:=m;m:=

49、bufferu mod N;advance(in);advance(out);/*信号一个满缓冲区及信号一个满缓冲区及*/*信信号一个满缓冲区号一个满缓冲区*/*允许其它生产者允许其它生产者*/*允允许其它消费者许其它消费者*/consume(m);图图-利用定序器和事件计数器实现生利用定序器和事件计数器实现生产者和消费者问题产者和消费者问题eventcount E;sequencer T;Pboth(R,S)semaphore R,S;intq,r,s;q:=ticket(T);await(E,q);r:=ticket(R.t);s:=ticket(S.t);advance(E);await

50、(R.e,r+1-R.initial_value);await(R.e,r+1-R.initial_value);图图-利用定序器和事件计数器实现利用定序器和事件计数器实现Simultaneous P利用定序器和事件计数器实现利用定序器和事件计数器实现P和和VP(s)semaphore s;int i;i:=ticket(s.t);await(s.e,i+1-s.initial_value);V(s)semaphore s;advance(s.e);利用定序器和事件计数器利用定序器和事件计数器实现生产者和消费者问题实现生产者和消费者问题eventcount in,out;sequencer P