分布式操作系统.ppt

第二章. 进程管理及并发控制和同步,第1节 进程的定义和特征 第2节 进程的状态和进程控制块 第3节 进程控制 第4节 进程的同步与互斥 第5节 并发执行的描述方式 第6节 基于共享变量的同步操作原理 第7节 基于消息传递的同步操作原语 第8节 进程调度,进程的定义和特征,1. 进程的定义 2. 进程的特征 3. 进程的结构,进程的定义,进程（process）或任务（task）这 一术语是在六十年代初期，首先在 麻省理工学院（MIT）的MULTICS 系统和IBM公司的CTSS/360系统中 引入的，其后有许多人对进程下过 各式各样的定义，下面列举几种比 较能反映进程实质的定义：,进程的定义,进程是程序的一次执行，亦即进程是在指定的内存区域中的一组指令序列的执行过程。 进程（或任务task）是可以和别的计算并发（concurrent）执行的计算。 进程可以定义为一个数据结构和能在其上进行操作的一个程序。 进程是程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位 进程（process）是一个具有独立功能的程序关于相关的数据集在处理机上的执行过程。,进程的特征,进程具有 顺序性 动态性 并发性 独立性和 异步性等特征。 进程的最基本的特征是并发性。,顺序性,一个进程的顺序性是指每个进程 在顺序处理机上的执行是严格按 次序进行的，即只有当其中的一 个操作结束后，才能开始其后续 操作.,动态性,进程的动态性是指它是程序的一 次执行过程，表现为它是由“创 建（ create）”而产生，由调度 程序“调度”而运行，因“等待 事件”而阻塞，最后，由“撤消 （destroy）”而消亡。可见，进 程是有一定生命期的，是动态地 产生，运行和消亡的。,并发性,进程的并发性是指多个进程 可以同时在一个系统中并发 地执行。,独立性,进程的独立性是指它可以作为系 统进行资源分配和调度的独立单 位,异步性,进程的异步性是指系统中的 活动的进程总是按照各自独 立的、不可预测的速度运行。,进程的结构,为了描述进程的运动变化过程 并使之能独立地运行，应该为 每个进程配置一个进程控制块 （process control block简记为 PCB）。,进程的结构,三部分所组成： 一个程序段 相应的数据段 一个进程控制块 在UNIX系统中，把这三部分统 称为进程映像（image）。而将 进程定义为“进程映像的执行。,进程的状态,就绪状态（Ready） 运行状态（Running） 阻塞状态（Blocked）,进程的状态,进程的状态(UNIX),进程控制块,进程标识符（Identification） 进程的当前状态（Status） 处理机状态保护区 进程的起始地址 资源清单 进程优先数 队列指针(pointer)或链接字(link) 进程族的联系 计账信息,为了对于进程进行控制，操作系 统内必须设置一个机构，它具有 上述进程控制及进程通讯和资源 管理等功能。这样的机构称为操 作系统的内核（Kernel）,原语,所谓原语（Primitive）是机器指 令的延伸，它由若干条指令组成， 用以完成特定功能的一段程序。 为了保证原语操作的正确性，原 语在执行期间是原子的，亦即原 语在执行期间是不可分割的。,原语,创建原语（Create Primitive） 悬挂原语（Suspend Primitive） 激活原语（Activate Primitive） 阻塞原语（Block Primitive） 唤醒原语（Wakeup Primitive） 撤消原语（Destroy Primitive）,对进程之间共享资源的控制必 须满足下列要求：,安全性（safety） 活动性（liveness） 公正性（fairness）,安全性（safety）,在任意一个给定时刻只允许至多 一个进程使用一个共享资源，不 允许两个及两个以上进程同时使 用同样的共享资源。否则，进程 对共享资源操作的结果往往是破 坏性的。,活动性（liveness）,活动性表现为两个方面， 一方面任意一个进程在使用共享资源时， 必须在有限时间内释放，不能无限期地 占用而导致其它进程永远无法使用； 另一方面当某个进程欲使用共享资源时， 则应在有限时间内达到目的，而不应该 互相阻止导致彼此永远都不能使用。,公正性（fairness）,对进程使用共享资源的次序不作不公正的规定。当某个进程欲使用共享资源时，只要其它进程不在使用该共享资源，就应该允许该进程使用。并且任意一个要求使用共享资源的进程不能无限期地等待，总应该在某个公正的时间界限内获得该资源。,第4节 进程的同步与互斥,进程之间常常相互作用，并存在 某种彼此依赖或互相制约的关系 这些关系按其性质可分为 同步（synchronization）和 互斥（mutual exclusion）关系。,进程的同步,一进程运行到某点时，要求另一伙伴进程 它提供信息，在未得到这一信息时，该 进程等待，直至收到这一信息后，才能继 续执行。它们彼此都清楚对方的存在及作 用，而且每一进程还可能直接依赖于本组 进程中其它成员所产生（或所提供）的数 据。这是进程间的一种直接交互关系，表 现了进程间协同工作的特性，因此称为进 程间的同步关系。,临界资源,并发进程可以共享系统中的各种资源，但系统中的有些资源具有一次仅允许一个进程所使用的属性。我们称这类资源为临界资源（critical resources）。,进程的互斥,若一进程在使用临界资源时，则其它欲占用者必须等待，仅当使用者释放后，等待的进程才可使用它。这就导致了若干进程因竞争临界资源而不得互斥地执行的情况。进程间的这种现象就称为进程的互斥。,临界区,在操作系统中把访问临界资源的那段程序称为临界段或临界区（critical section）。 临界段问题实质上是一个互斥问题。,临界段应遵循下面的原则：,当有多个进程都希望进入它们的临界段时，它们不应相互封锁，而应在有限时间内让其中之一进入临界段。 每次至多只有一个进程进入临界段中。 当某一进程已进入临界段，其它试图进入该临界段的进程必须等待。 位于临界段中的进程只能在其中逗留有限的时间一旦它离开临界段，则应允许某个等待进入临界段的进程进入其中。,同步机制,进程的同步是通过同步机制实现 的。同步机制主要有两个作用： 第一，它能够推迟一个进程的执行直至给定的条件成立。 第二，它可用来保证一个语句序列是一个不可分割的操作。,1. 忙等待busy waiting）,为了唤醒一个条件，进程给一个共 享变量置值，为了等待那个条件， 进程反复地测试那个共享变量直至 获得所需要的值。由于等待条件的 进程必须反复地测试那个共享变量， 因此称采用这种方式阻塞进程执行 的技术为忙等待。,计算机硬件配置指令,测试与设置(Test and Set 简记为TS) function Test-and-Set(var target : boolean) : boolean; Test-and-Set := target; target := TRUE; end;,利用测试与设置的同步,lock(mutex)： while (TS(mutex) ; unlock(mutex)： mutex := FALSE;,计算机硬件配置指令,对换（Swap）指令 该对换指令对换内存两个单元的内容。 procedure Swap(var a, b : boolean); var temp : boolean; begin temp := a; a := b; b := temp end;,利用对换指令的同步,lock(mutex): key := TRUE; repeat Swap(mutex, key) until key = FALSE; unlock(mutex): mutex := FALSE;,Dekker的软件解（1968）,int turn; boolean flag2; process(i) int i; while (TRUE) compute; flagi := TRUE; while (flag(i+1) mod 2) if (turn = i) continue; flagi := FALSE;,Dekker的软件解,while (turn i) ; goto try; ; critical_section; turn := (turn+1) mod 2; flagi := FALSE; ; ; turn := 0; flag0 := FALSE; flag1 := FALSE; Process(0) AND process(1);,Peterson的软件解 198l,#include prototypes.h #define FALSE 0 #define TRUE 1 #define N 2 /* number of process */ int turn; /* whose turn is it */ int interestedN; /* all values initially 0 (FALSE) */,vold enter-region(int process) /* process: who is entering (0 or 1) */ int other; /* */ other = 1 - process; interestedprocess = TRUE; turn = process; while (turn = = process /* null statement */ ,void leave-region(int process) /* process: who is leaving (0 or 1) */ interestedprocess = FALSE; /* indicate departure from critical region */ ,int turn; boolean flag2; process(i) int i; while (TRUE) compute; flagi := TRUE; while (flagi+1 mod 2)(turn = i+1 mod 2) ; critical_section; turn := (turn+1) mod 2; flagi := FALSE; ; ;,turn := 0; flag0 := FALSE; flag1 := FALSE; Process(0) AND process(1);,2. 信号量及其P、V操作,信号量（semaphore）Dijkstra， 1963是一个整型变量，与其相关 的两个操作是P、V操作。它是最 早提出的同步操作原话，P、V操 作的名称源于荷兰字Prolagen （试图降低）和Verhogen（升起)。,信号量及其P、V操作,定义 2.1 一个信号量s是一个非负 整型变量，它仅仅可以由下列的 两个不可分的（即原子的）访问 例程之一来测试和修改：,P(s)和V(s)操作,P(s): while s 0 do ; s := s -1; V(s): s := s +1 主要缺点是忙等待,P(s)操作,type semaphore = record value : integer; L : list of process; end; 信号量的value初值表示系统中某类资 源的数目。因此，这类 信号量又称资 源信号量。,P(s)操作,P(semaphore S) S.value S.value l; If S.value 0 then 阻塞该进程，并把它置入S.L等 待队列中；操作系统重新调度; else该进程继续执行; ,V(s)操作,V(semaphore S) S.value = S.value l; If S.value 0 then 从S.L等待队列中取出一进程; 将其状态改为“就绪”，并且 放入就绪队列; else该进程继续执行; ,互斥问题,为了解决互斥问题，每个临界段 前后分别放一个P、V操作，它们 都操作在同一信号量上，所有互 斥的临界段利用相同的信号量， 且该信号量的初值为1。,program mutex-example; var mutex : semaphore initial(1);,process P1; 1oop P(mutex); 临界段; V(mutex); 非临界段; end end; end.,process P2; 1oop P(mutex); 临界段; V(mutex); 非临界段; end end;,program synch-example; var s1, s2 : semaphore initial(0,0);,process P1; 1oop send(message); V(s1); P(s2); ; end; ; end; end.,process P2; 1oop P(s1); receive(message); V(s2); ; end; ; end;,有界缓冲区（生产者和消费者）问题,假设一个系统包含两个进程，其中之一 产生信息，称之为生产者进程（producer process），另一个使用生产者进程所产 生的信息，称之为消费者进程（consumer process）。两个进程可以交换所需信息， 使生产者进程从一个空缓冲池（buffer pool）中得到一个空缓冲区，将信息填写 其中，然后再把它放到满缓冲池之中。,有界缓冲区（生产者和消费者）问题,消费者进程从满缓冲池内取出满缓冲区， 从满缓冲区复制出信息，然后再把它放到 空缓冲池之中，以便再循环利用。我们不 喜欢给生产者和消费者进程以无限个缓冲 区；而只分配N个缓冲区给它们以交换信 息。下列程序表示了生产者和消费者进程 的程序。,有界缓冲区（生产者和消费者）问题,Semaphore s = 1; Semaphore full = 0; Semaphore empty = N; buf_type bufferN;,producer( ) AND consumer( );,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; int read_count = 0; 读者计数器 semaphore s = 1; semaphore write_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); ; ; /* There could be many readers and many writers */ reader( ) AND writer( )；,作者进程优先策略,resource_type *resource; int read_count = 0 write_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 := 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); ; ; /* There could be many readers and many writers */ reader( ) AND writer( )；,AND同步机制,在许多并行程序中，进程们必须在某个条 件集合上而不是仅在单个条件上同步。 下面的哲学家用餐问题就是一个很好 的例子。,哲学家用餐问题,Dijkstra引入了五个哲学家问题。假定五 个哲学家围住在餐桌旁每人前面放了一个 盘子，在相邻的两个盘子之间放了一只筷 子，当哲学家在思考时，他不使用盘子和 筷子，但是当哲学家决定吃时，他必须拿 到他面前盘子的左右两只筷子才能吃。我 们规定在一个给定的时刻，哲学家只能拿 一只筷子。哲学家们就这样交替地思考和 吃。是一个典型的信号量解。不幸地，这 个解是不安全的，因为当所有的同时决定 吃时，出现死锁。,semaphore fork5; 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（simultaneous P）操作。 同时P操作具有形式为： Psimultaneous(S1, S2, Sn) 同时V操作具有形式为： Vsimultaneous(S1, S2, Sn),Psimultaneous(S1, S2, Sn),if (S11)(S2 1)(Sn 1) then for i := 1 to n do Si := Si - 1; endfor else 把进程放在首先找到Si1相联的等待队列 中，并置该进程的程序计数器为此操作的 开始。 endif,Vsimultaneous(S1, S2, Sn),for i := 1 to n do Si := Si + 1; 把与 Si 相联的等待队列中所有的进程 移到就绪队列。 endfor,当n = 2时 Psimultaneous的一种实现,/* Shared variables */ int S1, R1; semaphore mutex; semaphore block; /* Initialize semaphores */ mutex := 1; block := 0;,P(S, R) P(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),if (S1t1)(S2t2)(Sntn) then for i := 1 to n do Si := Si - di; endfor else 把进程放在首先找到Si ti相联的等待队列 中，并置该进程的程序计数器为此操作的 开始。 endif,Vsimultaneous(S1,d1,S2,d2,Sn,dn),for i := 1 to n do Si := Si + di; 把与 Si 相联的等待队列中所有的进程 移到就绪队列。 endfor,条件临界域,虽然信号量基本上可用于解决差不多 任何类型的同步问题，但P、V操作是 非结构化的原语，因此在使用它们时 极易出错，执行临界段之前必须先执 行一个P操作。在退出临界段时再执 行一个V操作（在相同的信号量上）。 忽略一个P或V操作或者意外地让P操 作在一个信号量上而让V操作在另一 个信号量上就会乱套，在这种情况下， 互斥执行的特性不再会得到保证。,条件临界域,此外，在运用信号量时，程序员可能会 忘记将所有涉及到共享变量的语句包括 在临界段中，显然，这也可能破坏临界 段所需要的互斥执行。使用信号量的另 一困难是条件同步互斥都是使用相同形 式的原语对偶来编码的，从而难以弄清 一对给定的P、V操作的目的。因为互斥 和条件同步是不同的概念，它们应该有 不同的表示形式。,条件临界域,条件临界域（conditional critical region） Hoare，1972；Brinch Hansen，1972 通过提供结构化的表示法来描述同步而 弥补了上述不足。共享变量明显地归纳 为一组，并且予以命名，称为资源 resource），每个共享变量至多只处于 一个resource中且只能在命名该resource 的条件临界域（简记为CCR）语句中存 取。,条件临界域,一个包含变量v1，v2，vn的resource R说明为 resource R: v1，v2，vn; R中的变量只能由命名R的CCR语句存 取。这种语句形如： region R when B do S; 其中，B是一个布尔表达式，S是一组语 句，局部于正在执行的进程的局部变量 也可以出现在CCR语句中。互斥是通过 保证执行不同的CCR语句来实现的。,条件临界域,即每个命名相同resource的语句是不重 迭的。条件同步是通过CCR语句中明显 地给出的布尔条件加以保证。CCR语句 阻塞执行它的进程直至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 : 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 N do inpbuff.slotsinpbuff.tail := card; inpbuff.size := inpbuff.size + 1; inpbuff.tail := (inpbuff.tail + 1) mod N end end end;,条件临界域,process executer; var card : cardimage; line : lineimage; loop region ib when inpbuff.size 0 do card := inpbuff.slotsinpbuff.head; inpbuff.size := inpbuff.size - 1; inpbuff.head := (inpbuff.head + 1) mod N end; process card and generate line;,条件临界域,region ob when outbuff.size N do outbuff.slotsoutbuff.tail := line; outbuff.size := outbuff.size + 1; outbuff.tail := (outbuff.tail + 1) mod N end end end;,条件临界域,process printer; var line : lineimage; loop 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语句中的条件可以包含 对局部变量的访问，而且每个进程都必 须计算它自己的条件。在一个含有多道 程序的处理机上，这种计算的结果导致 若干内容的切换（频繁地保存和恢复进 程状态），其中的许多工作可能是无效 的，因为活跃的进程仍然可能发现相应 的条件为false。若每个进程都在它自己 的处理机上运行且内存是共享的，则 CCR语句很容易利用忙等待技术实现。,条件临界域,Edison语言Brinch Hansen，1981 包含有CCR语句，该语言是专为多处 理机系统设计的。CCR语句的一些变 种也在DPBrinch Hansen，1978和 ArgueLiskov，Scheifler，1982中使 用了。,管程（monitor）,管程（monitor）Dijkstra，1968；Brinch Hansen，1973；Hoare，1974是指一组公 共数据同与其有关的操作的集合。只有引 用管程中的操作才能访问管程中的数据。 一个进程引用管程中操作时，只有在管程 中的各操作均不处于活跃状态时才被响应， 当管程中一个操作已执行完毕或在执行中 处于等待状态时，它就不是活跃状态。管 程将公共数据同与其有关的操作集中在一 起，使得并发程序容易理解，也易于保证 程序的正确性。因此，管程是一种结构化 的同步机制。,管程（monitor）,定义（Hoare的定义）管程是一个 抽象数据类型，在任何给定的时刻 仅仅一个进程能够执行管程内的过 程。,管程（monitor）,局部于管程的变量仅能被该管程中 的过程所访问。一个管程与外部世 界的通信是通过其所含过程的参数 进行的。管程本身是一个静态的被 动的对象。一个进程执行管程的唯 一方式是通过调用管程中的过程来 体现的。执行给定管程中的过程保 证是互斥进行的，这确保了局部于 该管程的变量（即该管程首部说明 的量）是决不能并发存取的。,条件变量（condition variable）,“条件变量”（condition variable）用 于推迟管程中正在执行的进程，它只 能在管程中说明。定义在条件变量上 的两个操作是signal和wait。如果cond 是一条件变量，那么执行 cond.wait 将引起引用者阻塞在cond上，并撤消 它的互斥控制。,条件变量（condition variable）,执行 cond.signal 的工作过程如下：若没有进程阻塞在 cond上，则该引用者继续执行，否则， 该引用者暂时被挂起，并且重新激活 阻塞在cond上的一个进程；仅当该管 程中不存在其它正在执行的进程时， 才允许由于signal操作而挂起的进程继 续执行。,有界缓冲区管程,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 then 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 from 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; 1oop call outbuff. fetch(line); print line on lineprinter; end end; end.,优先wait 语句,有时程序设计者希望控制唤醒被推 迟进程的次序，为此，可使用 “优先wait”语句： cond.wait(p) 它与cond.wait的语义基本相同，主 要差别在于阻塞在条件变量cond上 的进程此时是按P的递增次序予以 唤醒。,管程（monitor）,并发PASCAL是支持管程的第一个 程序设计语言，该语言己被用于编 写若干操作系统，例如Solo，（一 个单用户操作系统），Job stream （处理PASCAL程序的一个批处理 操作系统）以及一个实时处理控制 系统。ModulaWirih，1977也含 有类似管程的模块。,定序器和事件计数器 Sequencers and Eventcounts,定义一个事件计数器（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)， 将引起该进程在E v时被阻塞。即， if E v then 将调用的进程放在于E相关的等待队 列中，变成阻塞状态， 调用进程调度程序； endif;,定序器,定义一个定序器（sequencer）是一个整 型变量，初始值为0，它取值于一个严格 单调增加的非负整数集合。仅仅ticket(T) 能够应用到定序器T上，它导致定序器T 增加并且返回定序器T增加前的值。对 ticket的调用是原子的，即定序器T被用 来在某个半序事件集合上放一个全序。,定序器,一个定序器相应于刚抵达的顾客所拿到 的服务号码，一个定序器的值是下一个 将要取的号码，可以将定序器看成一个 自动售票机。ticket操作对应于一个新 来的顾客取一个唯一的服务号码。一个 事件计数器可以看成是一个服务号码栈， 它的当前值是服务号码栈顶值。一个 await操作对应于一个顾客开始等待服 务。一个advance操作对应于一个初始 化服务，事件计数器被增加并且允许服 务下一个顾客（进程）。,定序器,一个进程执行临界区的操作序列为 await(E, ticket(S); 临界区； advance(E);,利用定序器和事件计数器实现P和V,Struct semaphore int initial_value; /* Initial value of the semaphore */ eventcount e; sequencer t; s;,利用定序器和事件计数器实现P和V,P(s) V(s) semaphore s; semaphore s; int i; advance(s.e); i := ticket(s.t); await(s.e, i+1-s.initial_value); eventcount in, out; sequencer Pticket, Cticket; buffer : array0N of message; producer( ) consumer( ) int t, i := 1; int u, 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 := bufferu mod N; advance(in); advance(out); /* 信号一个满缓冲区及 */ /* 信号一个满缓冲区*/ /* 允许其它生产者 */ /* 允许其它消费者 */ consume(m); 图 - 利用定序器和事件计数器实现生产者和消费者问题 eventcount E; sequencer T; Pboth(R,S) semaphore R, S; int q, 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); 图 - 利用定序器和事件计数器实现Simultaneous P,利用定序器和事件计数器实现P和V,P(s) V(s) semaphore s; semaphore s; int i; advance(s.e); i := ticket(s.t); await(s.e, i+1-s.initial_value); eventcount in, out; sequencer Pticket, Cticket; buffer : array0N of message; producer( ) consumer( ) int t, i := 1; int u, 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 := bufferu mod N; advance(in); advance(out); /* 信号一个满缓冲区及 */ /* 信号一个满缓冲区*/ /* 允许其它生产者 */ /* 允许其它消费者 */ consume(m); 图 - 利用定序器和事件计数器实现生产者和消费者问题 eventcount E; sequencer T; Pboth(R,S) semaphore R, S; int q, 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); 图 - 利用定序器和事件计数器实现Simultaneous P,利用定序器和事件计数器实现P和V,P(s) V(s) semaphore s; semaphore s; int i; advance(s.e); i := ticket(s.t); await(s.e, i+1-s.initial_value); eventcount in, out; sequencer Pticket, Cticket; buffer : array0N of message; producer( ) consumer( ) int t, i := 1; int u, 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 := bufferu mod N; advance(in); advance(out); /* 信号一个满缓冲区及 */ /* 信号一个满缓冲区*/ /* 允许其它生产者 */ /* 允许其它消费者 */ consume(m); 图 - 利用定序器和事件计数器实现生产者和消费者问题 eventcount E; sequencer T; Pboth(R,S) semaphore R, S; int q, 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_