软件操作系统教学（ANDREW S. TANENBAUM）MOS-3e-0211.pptVIP

Mutual Exclusion with Busy Waiting Mutual Exclusion with Busy Waiting Mutual Exclusion with Busy Waiting S=1：用于数据库互斥信号量 SRW=1：用于读者写者公共变量的互斥信号量 R：正在读的读者数量 R1：准备读的读者数量 W：正在写或准备写的写者数量 SR=1：用于读者公共变量的互斥信号量 SR1=0：用于准备读的信号量 读者 P(SR) P(SRW) IF(W!=0) (R1++; V(SRW)； V(SR）；P(SR1)；) IF(R==0) {R++；P(S)；V(SR)；V(SRW)；} ELSE {R++；V(SR)；V(SRW)；} 读操作 P(SR) R--; IF(R--==0) V(SRW)； V(SR) 写者 P(SRW) W++； V(SRW) P(S) 写操作 P(SRW) W--; IF(W==0R1!=0) V(SR1); V(SRW) V(S) Int a[5]={0},I Semaphore　b[5]={0},s; procedure test(I) {if(a[i]==1a[(i-1)%5]!=2 a[(i+1)%5]!=2) {a[i]=2;v(b[i]);}} Procedure philosopher(I) {p(s); a[i]=1;test[i]; V[s]; P(b[i]); pick_up_fork(I);pick_up_fork((I+1)mod 5); {Eating}; put_down_fork(I);put_down_fork((I+1)mod 5); P(s); A[i]=0;test((i-1)%5); 0;test((i+1)%5); V(s); 管程的共享变量在管程外部不可见，外部只能通过调用管程中的外部子程序访问共享变量； 为保证对共享变量操作的数据完整性，规定管程互斥进入； 管程中有等待/唤醒机制，等待时释放管程的互斥权，唤醒时（P唤醒Q）： P等待，Q继续，直到Q退出或等待；(Hoare) Q等待，P继续，直到P退出或等待；(Java) 唤醒是管程中可执行的最后一个操作。（Hansen) Hoare管程设施 入口等待队列： 每个管程变量一个，用于排队进入； 紧急等待队列： 每个管程变量一个，用于唤醒等待； 内部等待队列： var c: condition; 可根据需要定义多个，用于设置等待条件。 管程队列 进入与离开 进入管程： 申请管程互斥权。 离开管程： 如紧急等待队列非空，唤醒第一个等待者；否则开放管程。 条件变量操作 Var c:condition; wait(c): 如紧急队列非空，唤醒第一个等待者，否则释放管程互斥权; 执行此操作的进程（线程）进入c链尾。 signal(c): 如c链空，相当空操作。 否则唤醒第一个，执行此操作的进程（线程）进入紧急队列。 例1.生产消费问题 Type producer_consumer = MONITOR Var B:Array[0..n-1]Of integer; count, in, out: integer; pq, cq:condition; define put_in, get_out; Procedure put_in(item:integer); Begin If(count==n)Then wait(pq); B[in]:=item; in:=(in+1)%n; count++; signal(cq); End; 例1.生产消费问题 Procedure get_out(Var item:integer) Begin If(count==0)Then wait(cq); item:=B[out]; out:=(out+1)%n; count--; signal(pq); End; Begin in:=0; out:=0; count:=0; End; 例2. 读者/写者问题 例2. 读者/写者问题 例2. 读者/写者问题 例2. 读者/写者问题 例3. 哲学家就餐问题 例3. 哲学家就餐问题 例3. 哲学家就餐问题 例3. 哲学家就餐问题 例3. 哲学家就餐问题 例3. 哲学家就餐问题 Figure 2-35. A solution to