页数：173页文件大小：523.6 KB来源： 计算机操作系统ppt课件
本课件从并发进程与临界区出发，比较软件与硬件互斥方案，重点讲解信号灯与P/V操作、生产者消费者、读者写者等经典同步问题，并介绍管程、会合、消息传递等高级同步与通信机制。
4.1并发进程( Concurrent Processes )4.2进程互斥( Mutual Exclusion )4.3进程同步( Synchronization )4.4进程高级通信( Communication )4.5系统举例
4.1.1前驱图的定义定义：前驱图是一个有向无环图。图中每个结点表示一条语句、一个计算步骤或一个进程。结点间的有向边表示偏序或前驱关系“→”，关系→={(Pi,Pj)|Pi必须在Pj启动之前已经完成}(Pi,Pj)∈→记作Pi→Pj，称Pi是Pj的前驱，Pj是Pi的后继。前驱图中，没有前驱的结点称为初始节点；没有后继的结点称为终止节点。每个结点可以有权重，表示该结点的程序量或计算时间。偏序关系：具有反身性、反对称性、传递性。
4.1.1前驱图的定义例.对如下前驱关系：P1→P2, P1→P3, P1→P4,P2→P5, P3→P5, P4→P5, P4→P6,P5→P7,P6→P7,P6→P8前驱图如下：P1P4P3P2P5P6P7P
1.程序的并发执行内部并发性:指一个程序内部的并发性；如下程序段：S1: a := x+2;S2: b := y+4;S3: c := a+b;S4: d := c-6;S5: e := c+6;S6: f := c-e;外部并发性:多个程序的并发性。（P83：图4-5）4.1.3并发程序及其特性S1S2S3S6S4S
4.1.5并发程序的表示设S1、S2、……、Sn为n个程序段，则用如下形式的并发语句：cobegin S1; S2;……; Sn coend;或parbegin S1; S2;……; Sn parend;表示S1、S2、……、Sn的并发执行。遇到并发语句，系统会同时创建n个进程（线程）分别执行S1、S2、……、Sn。
2:进程P2…………do{等待借书者；if x >= 1{x := x–1 ;借书} else无书}while(1);…………终端1:进程P1…………do{等待借书者；if x >= 1{x := x–1 ;借书} else无书} while(1);…………例：图书借阅系统(x:某种书册数,设当前x = 1)
4.2.2临界区域与进程互斥进程互斥:两个或两个以上进程不能同时进入关于同一组共享变量的临界区域，否则可能发生与时间有关的错误，这种现象称为进程互斥。含义:⑴任何时刻最多只能有一个进程处于同一组共享变量的相同的临界区域；⑵任何时刻最多只能有一个进程处于同一组共享变量的不同的临界区域。Remarks:互斥是相对于公共变量而言的。
临界区框架(Framework)Do {critical sectionremainder code} while(1);entry sectionexit section4.2.3进程互斥的实现实现互斥就是要编写entry section和exit section两部分。
(1) Dekker互斥算法int flag[ 2 ]; int turn; P0进程：do{flag[0]=1;whlie (flag[1]) doif(turn==1) {flag[0]=0;whlie(turn==1) do continue;flag[0]=1;}临界区；turn=1;flag[0]=0;其余代码；}while(1)P1进程：do{flag[1]=1;whlie (flag[0]) doif(turn==0) {flag[1]=0;whlie(turn==0) do continue;flag[1]=1;}临界区；turn=0;flag[1]=0;其余代码；}while(1)实现两个进程互斥的软件解法。
(2) Peterson互斥算法int flag[ 2 ]; int turn; P0进程：do{flag[0]=1; turn=1;whlie (flag[1]&&turn==1) docontinue;临界区；flag[0]=0;其余代码；}while(1)实现两个进程互斥的软件解法。P1进程：do{flag[1]=1; turn=0;whlie (flag[0]&&turn==0) docontinue;临界区；flag[1]=0;其余代码；}while(1)
(3) Lamport面包店算法int choosing [ n ] = { 0, 0, 0, …… , 0 };int number [ n ] = { 0, 0, 0, ……, 0 };算法4.1 [ Pi进入]：choosing [ i ] = 1;number[ i ] = max{ number[0], …, number[n-1] }+1;choosing [ i ] = 0 ;for ( j = 0 ; j < n ; j++ ){while ( choosing [ j ] ) do continue;while (( number [ j ] != 0 ) &&(number [ j ], j ) < ( number [ i ], i )) do continue;}number[i] = 0;//Pi退出临界区C R
(4) Eisenberg-Mcguire算法数据结构：enum state { idle, want_in, in_cs } ;enum stateflag [ n ];intturn ;flag[i] == idle:进程Pi空闲，不想进入临界区；flag[i] == want_in:进程Pi想进入临界区;flag[i] == in_cs:进程Pi想进入或已进入临界区;
进程Pi进入临界区算法思想（entry section）：Step1:检查编号为turn, …, n-1, 0, 1, …, i-1的优先于Pi的进程是否空闲(idle),如不空闲则转Step1；Step2:依次检查编号从0～i-1, i+1, …, n-1的进程是否在临界区,如有任何一个进程在临界区,则转Step1;Step3:进入临界区turn＝i .先于i先于i0iturnn-
进程Pi退出临界区算法思想（exit section）：Step1[找下一个竞争进程]从turn+1 (即i+1)开始找到一个非空闲( idle )的进程Pj ;Step2[指定下一个竞争进程j ]turn = j ;Step3[进程Pi退出临界区]flag [i] = idle .注意：Step1中,可能找到的j = i,即除进程Pi之外,其它进程都空闲。但由于Step3中将Pi的进程状态置为空闲idle ,能保证其它进程进入临界区。
Pi进入:do { flag [ i ] = want_in ; j = turn ;while ( j != i ) doif (flag [j] != idle )j = turn; else j = (j+1)%n ;flag [i] = in_cs ; j = 0 ;while ((j<n)&&(j == i||flag[j]!=in_cs )) do j++;}while ( j ! = n );turn = i ;C RPi离开：j = ( turn + 1 ) % n ;while ( flag [ j ] == idle ) do j = ( j + 1 ) % n;turn =j ;flag [ i ] = idle ;4.2.3.1进程互斥的软件实现(4) Eisenberg/Mcguire算法Pi进入的Step1.Pi进入的Step2.
(1)硬件提供“测试并设置”指令int test_and_set ( int *target ){ int temp;temp = *target ;*target = 1;return ( temp ) ;}
(2)硬件提供“交换”指令void swap( int *a,*b){ int temp;temp = *a ;*a = *b ;*b = temp ;}
(3)硬件提供“关中断”和“开中断”指令关中断( CLI ){ Critical Region }开中断( STI )Remarks:⑴开/关中断只在单CPU系统中有效;⑵影响并发性;⑶效率高，无忙式等待，简单易行。
4.2.4多处理机环境下互斥[问题例]多CPU下，test_and_set不能解决互斥。内存CPU2initial: 0Bus4. Write 13. Write 12. Read 01. Read 0lockCPU1
2.多CPU互斥的解决多CPU互斥算法：b = 1 ;while ( b ){ lock ( bus ) ;b = test_and_set ( &lock ) ;unlock ( bus ) ;}lock=0;CR
3.Consider the following program:int blocked [ 2 ] ;int turn ; void P ( int id ){ do { blocked [ id ] = 1 ;while ( turn != id ) do{ while ( blocked [1-id ] )do continue;turn = id ;}<Critical Section>blocked [ id ] = 0 ;<Remainder>} whlie ( 1 ) ;}void main ( ){ blocked [ 0 ] = 0 ;blocked [ 1 ] = 0 ;turn = 0 ;parbeginP(0); P(1)parend ;}Assignment #1This is a software solution to the mutual exclusionproblem proposed byHyman. It is interesting to notethat even theCommunication of the ACMwas fooledon this one.Find a counter exampleto demonstrate that this solution is incorrect.
3.Consider the following program:int blocked [ 1 ] ;int turn ; void P ( int id ){ do { blocked [ id ] = 1 ;while ( turn != id )do{ while ( blocked [1-id ] ) docontinue;turn = id ;}<Critical Section>blocked [ id ] = 0 ;<Remainder>} whlie ( 1 ) ;}Assignment #1当P(1)执行完第二个while,还未执行turn = id ;P(0)执行到第一个while。此时：turn=0，P(0)能进入CS；而P(1)执行完turn = id后，外层while条件为假，P(1)也能进入CS .P(1)执行完第二个while,还未执行turn = id ;P(0)执行到第一个while
：司机—售票员问题⑴关门后才能启动汽车;⑵到站停车后方能开车门。4.3进程同步司机活动：do{启动车辆；正常行驶；到站停车；} while (1)售票员活动：do {关车门；售票；开车门；} while (1)
：一组进程，为协调其推进速度，在某些关键点处需要相互等待与相互唤醒，进程之间这种相互制约的关系称为进程同步，简称同步(Synchronization)。定义：一组进程，如果它们单独不能正常运行，但并发可以正常运行，称这种现象为进程合作(Cooperation)。参与合作的进程称作合作进程(Cooperating Process)。P1:synchronize先P2:后
4.3.3.1信号量与P/V操作的定义⒈信号量类型的定义：typedef struct{ int value ;pointer_to_PCB queue ;} semaphore ;semaphores;Remarks:⑴semaphoreis pre-defined data type;⑵Variablescan be declared as needed .
信号量变量及进程队列例：semaphore S ;4.3.3.1信号量与P/V操作的定义S.valueS.queueS.valueS.queuePCBPCBPCB……FIFO
P操作原语:void P ( semaphore *s ){ s-> value--;if (s-> value < 0 )asleep (s-> queue);}asleep( s-> queue):⑴执行此操作进程的PCB入s-> queue的队尾(状态改为等待) ;⑵转处理机调度程序。Primitive: a piece of codeun-interruptible4.3.3.1信号量与P/V操作的定义
V操作原语：void V ( semaphore *s ){ s-> value ++ ;if (s-> value <= 0)wakeup (s->queue);}wakeup(s-> queue) :s-> queue链头PCB出等待队列，进入就绪队列(状态改为就绪)。4.3.3.1信号量与P/V操作的定义注意：P / V操作的参数S是指针型信号量，在调用P / V操作时其参数应该用&S取地址的形式，为简便起见，后面只用S的形式直接调用。
1.用信号量实现进程互斥问题描述：4.3.3.3信号量与PV操作的应用shared int x, y, z ;CR1CR2CRn
2.用信号灯实现进程同步问题描述：4.3.3.3信号量与PV操作的应用后动作P1:P2:先动作
借书系统互斥的实现:Semaphore mutex ; ( initial mutex.value = 1 )终端1：do{等待借书者;P (mutex) ;if (x >= 1){ x = x–1 ;V(mutex);借书;}else {V(mutex);无书;}} while ( 1 )4.3.3.3信号量与PV操作的应用终端2：do{等待借书者；P (mutex) ;if (x >= 1){ x = x–1 ;V(mutex) ;借书;}else {V(mutex);无书;}} while ( 1 )
4.3.3.3信号量与PV操作的应用例4-1:(同步例子)司机-售票员问题司机活动：售票员活动：do { do {启动车辆；关车门；正常行驶；售票；到站停车；开车门；} while (1) } while(1)要求：（1）关门后才能启动汽车；（
4.3.3.3信号量与PV操作的应用司机-售票员问题的同步实现：semaphore s1 , s2 ; ( initial value 0 )司机活动：售票员活动：do { do {P ( S1 )；关车门；启动车辆；V ( S1 )；正常行驶；售票；到站停车；P ( S2 )；V ( S2 )；开车门；} while (1) } while(1)
例4-2.生产者/消费者问题预备知识：组合资源：若干相对独立的资源构成的资源集合,其中每个相对独立的资源称为子资源。同种组合资源：相同类型子资源构成的组合资源。同种组合资源的管理：semaphore S; (初值=子资源个数)例子：2台打印机semaphore S; S.value=2;申请打印机：P ( S )；释放打印机：V ( S )；
自动机描述2…10-1-2P(S)P(S)P(S)P(S)P(S)V(S)V(S)V(S)V(S)V(S)S.value=空闲资源数S.queue=空|S.value|=等待进程数空闲资源数=0...P(S):申请一台打印机,分配,空闲打印机减1;P(S):申请一台打印机,等待,等待进程数加1。例4-2.生产者/消费者问题
V(S):释放一台打印机,唤醒一个等待者,打印机分给被唤醒进程,等待进程数减1;V(S):释放一台打印机,空闲打印机数量增1。自动机描述例4-2.生产者/消费者问题2…10-1-2P(S)P(S)P(S)P(S)P(S)V(S)V(S)V(S)V(S)V(S)S.value=空闲资源数S.queue=空|S.value|=等待进程数空闲资源数=0...
箱子B，容量kitem B [ k ] ;生产者生产物品放入B中B中取物品消费例4-2.生产者/消费者问题问题描述k-1……210消费者Producers and consumers problem，or bounded buffer’problem.
环形缓冲区10K-1in(in+1)mod kout(out+1)mod k例4-2.生产者/消费者问题问题描述
生产者活动：消费者活动：do { do {加工一件物品;箱中取一物品;物品放入箱中;消耗这件物品;} while ( 1 ) } while ( 1 )例4-2.生产者/消费者问题问题分析资源：箱子(同种组合)资源：物品(同种组合)semaphore S1 ; semaphore S2 ;S1.value = k ; S2.value = 0 ;放前: P ( S1 )取前: P ( S2 )放后: V ( S2 )取后: V ( S1 )
生产者活动：消费者活动：do { do {加工一件物品;P ( S2 ) ;P ( S1 ) ;箱中取一物品;物品放入箱中;V ( S1 ) ;V ( S2 ) ;消耗这件物品;} while ( 1 ) } while ( 1 )例4-2.生产者/消费者问题同步的实现对B和in，out的互斥：semaphore mutex ; ( mutex.value = 1 )
例4-2.生产者/消费者问题互斥的实现生产者活动：消费者活动：do { do {加工一件物品;P ( S2 ) ;P ( S1 ) ;P ( mutex ) ;P ( mutex ) ;箱中取一物品;物品放入箱中;V ( mutex ) ;V ( mutex ) ;V ( S1 ) ;V ( S2 ) ;消耗这件物品;} while ( 1 ) } while ( 1 )
例4-2.生产者/消费者问题程序itemType buffer [ k ] ;semaphore S1, S2, mutex;int in, out;void producer ( ){ while(1){ produceItem(&item);P ( S1 ) ;P ( mutex ) ;buffer [ in ] = item;in = ( in + 1 ) % k;V ( mutex ) ;V ( S2 ) ;}}void consumer ( ){ while(1){ P ( S2 ) ;P ( mutex ) ;x = buffer [ out ] ;out = ( out + 1 ) % k;V ( mutex ) ;V ( S1 ) ;<consume x>;} while ( 1 ) ;}
void producer_consumer ( ){ S1.value = k ; S2.value = 0 ;mutex . value = 1 ;in = out = 0 ;fork ( producer, 0 ) ; … , fork ( producer, m-1 ) ;fork ( consumer, 0 ) ; … , fork ( consumer, n-1 ) ;}例4-2.生产者/消费者问题程序
例4-2.生产者/消费者问题并发性提高策略生产者和消费者:不操作buffer的相同分量生产者的共享变量:buffer [ in ] , in消费者的共享变量:buffer [ out ] , out并且in = out :满或空,semaphoremutex1 , mutex2 ; ( init 1 )
生产者活动：消费者活动：do { do {加工一件物品P ( S2 ) ;P ( S1 ) ;P ( mutex2 ) ;P ( mutex1 ) ;箱中取一物品物品放入箱中;V ( mutex2 ) ;V ( mutex1 ) ;V ( S1 ) ;V ( S2 ) ;消耗这件物品} while ( 1 ) } while ( 1 )例4-2.生产者/消费者问题并发性提高策略
例4-3.读者/写者问题P. T. Courtois 1971. Communication of the ACM, Vol.14, 667-669.ACM:Association for Computing Machinery要求:⑴R–R可以同时;⑵R–W不可同时;⑶W–W不可同时。Problem Statement:accessingReaders and writers problemR1RmW1Wn共享数据
semaphore r_w_w ; ( init value: 1 )void reader ( ) void writer ( ){ P ( r_w_w ) ; { P ( r_w_w ) ;<read operations> <write operations>V ( r_w_w ) ; V ( r_w_w ) ;} }例4-3.读者/写者问题Solution1:不考虑R-R不互斥分析:不满足要求⑴,即R–R不能同时。改进:最先进入的R执行P ;最后离开的R执行V ;
int readCount = 0 ; ( initial value is 0 )void reader ( ){ readCount ++ ;if ( readCount == 1 ) P ( r_w_w ) ;<read operations>read_count--;if ( readCount == 0 ) V ( r_w_w ) ;}问题：对readCount操作的互斥问题。例4-3.读者/写者问题Solution2:考虑R-R不互斥
semaphore mutex = 1 ;int readCount = 0 ;void reader ( ){P ( mutex ) ;readCount ++ ;if ( readCount == 1 ) P ( r_w_w ) ;V ( mutex ) ;<read operations>P ( mutex ) ;readCount--;if ( readCount == 0 ) V ( r_w_w ) ;V ( mutex ) ;}例4-3.读者/写者问题Solution2:考虑R-R不互斥
void writer ( ){ while (1) {<other actions>P ( r_w_w ) ;<write operations>V ( r_w_w ) ;<othes actions>}}例4-3.读者/写者问题程序
void reader ( ){ while (1) {<other actions>P ( mutex ) ;readCount ++ ;if ( readCount == 1 ) P ( r_w_w ) ;V ( mutex ) ;<read operations>P ( mutex ) ;readCount--;if ( readCount == 0 ) V ( r_w_w ) ;V ( mutex ) ;<other actions>}}例4-3.读者/写者问题程序
int readCount = 0 ;semaphore r_w_w . value = 1 ;semaphore mutex . value = 1 ;void reader_writer ( ){ cobeginfork ( reader, 0 ) ; …… fork ( reader, m-1 ) ;fork ( writer, 0 ) ; …… fork ( writer, n–1 ) ;coend}例4-3.读者/写者问题程序
问题:读者源源不断，readCount不归0 ,写者会被饿死，即饥饿(starvation)。策略:一旦有写者等待,新到达读者等待,正在读的读者都结束后,写者进入,即写者优先。例4-3.读者/写者问题程序分析
semaphore r_w_w=1, mutex=1,mutex1=1,read_q=1;int readCount=0, writeCount=0 ;void writer ( ){P ( mutex1 ) ;writeCount ++ ;if ( writeCount == 1 )P ( read_q );V ( mutex1 ) ;P ( r_w_w ) ; <write oerationps> V ( r_w_w ) ;P ( mutex1 ) ;writeCount--;if ( writeCount == 0 )V ( read_q );V ( mutex1 ) ;}例4-3.读者/写者问题Solution3:写者优先
void reader ( ){P ( read_q );P ( mutex ) ;readCount ++ ;if ( readCount == 1 ) P ( r_w_w ) ;V ( mutex ) ;V ( read_q )<read operations>P ( mutex ) ;readCount--;if ( readCount == 0 ) V ( r_w_w ) ;V ( mutex ) ;}例4-3.读者/写者问题Solution3:写者优先
enum state {free,used} ;enum state lp [ 3 ] ;semaphore S ;semaphore mutex ;例4-4.三台打印机管理int require ( ){P (S) ;P (mutex) ;for (i = 0; i<3; i++)if (lp[i]==free) break;lp[i] = used ;V (mutex) ;return (i) ;}void release ( int i ){ P (mutex);lp [i] = free ;V (mutex);V (S) ;}注意：执行for循环时P (S)已经通过，一定存在空闲（free）的打印机i。
例4-5.吸烟者问题Cigarette Smokers’ ProblemPatil S. S.Limitations and Capabilities ofDijkstra’s semaphore primitives for coordinationamong processes.MIT project MACComputation Structure Group Memo 57, MIT,Cambridge, Mass, 1977.
例4-5.吸烟者问题材料：烟草、卷烟纸和火柴供应者：⑴不吸烟；⑵有足够多的烟草、卷烟纸和火柴；⑶每次随机地将三种材料的两种各一样放到桌子上，供有另一种材料的吸烟者吸烟。吸烟者：⑴每位吸烟者只有一种吸烟材料，且彼此拥有材料各不相同；⑵每位吸烟者需要三种材料齐全才能吸烟。问题：实现供应者和吸烟者之间的同步。房间内有一位材料供应者和
例4-5.吸烟者问题Traditional semaphoresemaphore tobacco ; semaphore match ; semaphore wrapper ; semaphore mutex ; 说明:⑴tobacco、match、wrapper分别表示烟草、火柴和卷烟纸的队列状况，并用于供应者与吸烟者之间的同步；⑵mutex用于X、Y、Z三个供应者之间的互斥。
process XP(mutex);V(tobacco);V(match);process CP(tobacco);P(match);smoke;V(mutex);process AP(match);P(wrapper);smoke;V(mutex);process BP(wrapper);P(tobacco);smoke;V(mutex);process YP(mutex);V(match);V(wrapper);process ZP(mutex);V(wrapper);V(tobacco);Solution1:例4-5.吸烟者问题Traditional semaphore
Solution1存在的问题:供应者进程都供应特定的两种材料，并且分别供应给固定的吸烟者进程，Solution1存在另外两个吸烟者进程取单一材料的情况。解决方法⑴:某供应者进程执行(提供特定两种材料)时，应通知相应吸烟者进程；解决方法⑵:引进并发P、V操作SP和SV。semaphore mutex_A ; semaphore mutex_B ; semaphore mutex_C ; 解决方法⑴:例4-5.吸烟者问题Traditional semaphore
例4-5.吸烟者问题解决方法⑴：process XP(mutex);V(tobacco);V(match);V(mutex_C);process CP(mutex_C);P(tobacco);P(match);smoke;V(mutex);process AP(mutex_A);P(match);P(wrapper);smoke;V(mutex);process BP(mutex_B);P(wrapper);P(tobacco);smoke;V(mutex);process YP(mutex);V(match);V(wrapper);V(mutex_A);process ZP(mutex);V(wrapper);V(tobacco);V(mutex_B);
Semantics:SP操作对多个信号量变量同时执行P操作。if∀i (1≤i≤n)Si.value≥dithenfor (i=1;i<=n;i++) Si= Si-di;else⑴place the executing process in the waitingqueue for the first Siwith Si＜di;⑵set the program counter to the beginning ofthe SP operation so that all conditions will bereexamined when the process is reactivated.例4-5.吸烟者问题SimultaneousP-operationSyntax:SP ( S1[, t1, d1], … , Sn[, tn, dn]);其中:Si为信号灯变量, ti为Si的初始值, di为Si. value的增量值。
Semantics:if∀i (1≤i≤n)Si.value{ Si.value= Si.value + di；place all PCB in the Siqueue to the ready list ;}例4-5.吸烟者问题SimultaneousV-operationSyntax:SV ( S1, d1; … , Sn, dn);其中:Si为信号灯变量, di为Si. value的增量值。
例4-5.吸烟者问题解决方法⑵: SP操作semaphore tobacco, match, wrapper;semaphore mutex ;process Xdo {P(mutex);SV(tobacco,1；match,1);} while(1);process Ydo {P(mutex);SV(match,1; wrapper,1);} while(1);process Zdo {P(mutex);SV(wrapper,1; tobacco,1);} while(1);
process CloopSP(tobacco,1;match,1);smoke; V(mutex);endloopprocess AloopSP(match,1;wrapper,1);smoke; V(mutex);endloopprocess BloopSP(wrapper,1;tobacco,1);smoke; V(mutex);endloop例4-5.吸烟者问题解决方法⑵: SP操作
进程描述:void supplier ( ){ P (mutex ) ;V ( random ( A_smoke, B_smoke, C_smoke ) ) ;}void smoker_A ( ){ P (A_smoke); <A smoke>; V (mutex); }void smoker_B ( ){ P (B_smoke); <B smoke>; V (mutex); }void smoker_C ( ){ P (c_smoke); <c smoke>; V (mutex); }例4.吸烟者问题另一解法
例.嗜睡理发师问题数据定义：#defineCHAIRS10intwaiting=0;semaphorecustomers;semaphorebarbers;semaphoremutex;customers.value = 0;barbers.value = 0;mutex.value=1;
例.嗜睡理发师问题void barber ( ){ while ( 1 ){ P(cutomers);P(mutex);waiting--;V(mutex);V(barbers);<cut-hair>;}}理发师进程：
例.嗜睡理发师问题void customer ( ){P (mutex);if ( waiting <CHAIRS){ waiting++;V (mutex);V (customers);P (barbers);<get_haircut>;}elseV ( mutex ) ;}顾客进程：
4.3.4条件临界区CCR实现互斥例子void producer ( ){ do{<produce a product>P ( S1 ) ;V ( S2 ) ;} while ( 1 )}void consumer ( ){ do{ P ( S2 ) ;V ( S1 ) ;<consume x>;}while ( 1 )}P ( mutex ) ;B [ in ] =product;in = ( in + 1 ) % k;V ( mutex ) ;P ( mutex ) ;x = B [ out ] ;out = ( out + 1 ) % k;V ( mutex ) ;Region B when true do{ B [ in ] = product ;in = ( in + 1 ) % k; }Region B when true do{ x = B [ out ] ;out = ( out + 1 ) % k ; }
4-6简单批处理中，作业输入、执行、打印结果三个部分同步的条件临界区程序实现。问题分析：作业的输入和执行涉及输入缓冲区的互斥和同步；作业的执行和打印涉及输出缓冲区的互斥和同步。Program batch;type buffer=recordslots: array[0..n-1] of T;head, tail: 0..n-1 initial (0,0);size: 0..n initial (0);end;var inbuff: buffer(cardimage);outbuff: buffer(lineimage);resource ib: inbuff; ob: outbuff;Cobeginprocess reader;var card: cardimage;loop<readcardfrom cardreader>regionibwheninbuff.size<ndoinbuff.slots[inbuff.tail]:=card;inbuff.size:=inbuff.size+1;inbuff.tail:=(inbuff.tail+1)mod n;enddoendloopendprocess
4.3.4条件临界区process executer;var card: cardimage;line: lineimage;loopregionibwheninbuff.size>0docard:=inbuff.slots[inbuff.head];inbuff.size:=inbuff.size-1;inbuff.head:=(inbuff.head+1)mod n;enddo<process card and generateline>regionobwhenoutbuff.size<ndooutbuff.slots[outbuff.tail]:=line;outbuff.size:=outbuff.size+1;outbuff.tail:=(iutbuff.tail+1)mod n;enddoendloopendprocessprocess printer;var line: lineimage;loopregionobwhenoutbuff.size>0doline:=outbuff.slots[outbuff.head];outbuff.size:=outbuff.size-1;outbuff.head:=(outbuff.head+1)mod n;enddo<printlineon lineprinter>endloopendprocesscoend
4.3.5.2管程形式type<monitor_name> =MONITOR;<共享变量说明>;define<本管程内定义的外部过程(函数)名表>;use<本管程外定义,本管程内使用的过程/函数名表>;procedure<过程名> (<形参表>);<局部变量说明>;begin <语句序列> end;…………function<函数名> (<形参表>) : <返回值类型>;<局部变量说明>;Begin <语句序列>End;……………begin <共享变量初始化语句序列>end;
typeSSU=MONITOR;varbusy:boolean;busy_q:condition;definerequire,release;usewait,signal；procedurerequire();beginifbusy=truethenwait(busy_q);busy:=ture；end;procedurerelease();beginbusy:=false；signal(busy_q);end;beginbusy:=false；end
PCBPCBPCB…PCBPCBPCB…PCBPCBPCB…ConditionC1…………………………………ConditionCnUrgentPCBPCBPCB…Entry queueMonitor
4.3.5.3管程语义管程构成管程等待队列condition c1wait(c1)condition cn……………urgent queuesignal管程定义共享变量条件变量define、use列表过程(函数)1过程(函数)k……………初始化代码signal(c1)wait(cn)signal(cn)wait,结束入口等待队列
例4-7.读者/写者问题typereaders_and_writers= Monitor ;var rq , wq :condition;reading_count : integer ;write_count : integer ;definestart_read , finish_read ,start_write , finish_write ;
例4-7.读者/写者问题procedure start_read;beginif write_count > 0thenwait ( rq );reading_count ++;signal ( rq ) ;end ;procedure finish_read;beginreading_count--;if reading_count = 0thensignal ( wq );end ;写者优先
procedure start_writebeginwrite_count++;if (write_count>1) or(reading_count>0)thenwait ( wq );end ;procedure finish_writebeginwrite_count--;if write_count > 0thensignal ( wq );elsesignal ( rq );end ;例4-7.读者/写者问题写者优先
beginreading_count := 0 ;write_count := 0 ;end ;var rw :readers_and_writers;读者进程：rw.start_read;{reading}rw.finish_read;写者进程：rw.start_write;{writing}rw.finish_write;例4-7.读者/写者问题
Hansen管程实现SCAN算法：唤醒是管程中可执行的最后一个操作。外部过程：申请：require ( dest : 0 .. 199 )释放：release ( )使用方式：require ( dest ) ;{ I/O操作}(管程外操作)release ( ) ;例4-8.磁头引臂调度问题
typedisk_head_schedul= MONITOR ;var busy : boolean ;headpos : 0..199 ;direction : (up, down) ;cylinder : array[0..199] ofcondition;//每个磁道一个等待队列;count : array[0..199] of integer ;//每个磁道等待队列中等待I/O的进程个数;definerequire, release;例4-8.磁头引臂调度问题管程实现SCAN算法
例4-8.磁头引臂调度问题管程实现SCAN算法procedure require ( dest: 0..199 ) ;beginif busy=true thenbegincount [dest]++ ;wait (cylinder[dest]);end;busy :=true;if dest < headposthen direction :=down;else if dest > headposthen direction :=up;headpos := dest ;end;根据dest和磁头当前位置headpos,确定磁头引臂动作方向。
例4-8.磁头引臂调度问题管程实现SCAN算法procedure upscan;var i : 0 .. 200 ;begini := headpos ;while (i <= 199) and (count [ i ] = 0) do i++ ;if i <= 199 thenbegincount [i]--;signal ( cylinder [i] );endend;从当前磁头位置向内扫描,直到找到一个有I/O请求的磁道。唤醒i磁道等待I/O的一个进程，退出管程。
例4-8.磁头引臂调度问题管程实现SCAN算法procedure downscan ;var i :-1 .. 199 ;begini := headpos ;while ( i >= 0 ) and (count [i] = 0) do i--;if i >= 0 thenbegincount [ i ]--;signal (cylinder [ i ] );endend;从当前磁头位置向外扫描,直到找到一个有I/O请求的磁道。唤醒i磁道等待I/O的一个进程，退出管程。
procedure release ;beginbusy :=false;if direction =upthen beginupscan ; downscanendelse begindownscan ; upscanendend;例4-8.磁头引臂调度问题管程实现SCAN算法procedure initialize ;var i: 0..199;beginbusy :=false; headpos := 0; direction :=up;for i := 0 to 199 do count [ i ] := 0 ;endbegin initialize end;
例4-9.嗜眠理发师问题…凳子(n个)理发椅理发店Sleepy barber’s problem
TYPEsleepy_barber= MONITOR ;VAR chair :condition;stool :condition;count : 0 .. n ;definesleep , enter , leave ;例4-9.嗜眠理发师问题procedure sleep ;beginif count = 0thenwait (chair);end ;procedure leave ;begincount := count-1 ;if count <> 0thensignal (stool);end ;
procedure enter (varfull : Boolean ) ;beginif count = nthen full :=true;else beginfull :=false;count := count + 1 ;if count = 1thensignal (chair);elsewait (stool);end ;end ;例4-9.嗜眠理发师问题
理发师活动:Repeatspy.sleep ;<Cut-hair> ;Until false ;顾客活动:Repeatspy.enter (full) ;Until not full ;<Cut-hair >;spy.leave ;例4-9.嗜眠理发师问题begin count :=0 ; endvar full : Boolean;(初值false)var spy : sleepy_barber;
理发师活动:Repeatspy.sleep ;<Cut-hair>;spy.leave ;Until false ;顾客活动:Repeatspy.enter (full) ;Until not full ;<Cut-hair> ;例4-9.嗜眠理发师问题问题：当最后一位顾客理完发还没执行spy.leave,而理发师进程执行spy.sleep时,由于此时count=1,因此理发师进程又进入Cut-hair.
例.生产消费问题typeproducer_consumer= MONITOR;var B: array [ 0 .. n-1 ] of product ;count , in , out : integer ;pq , cq : condition ;define put_in , get_out ;procedure put_in ( item : product ) ;beginif count = n thenwait ( pq );B [ in ] := item ;in:= ( in + 1 ) mod n ;count++;signal (cq);end;
例.生产消费问题procedure get_out ( var item : product )beginif count = 0 thenwait ( cq );item := B [ out ] ; out := ( out + 1 ) mod n ;count--;signal ( pq );end;begin in:=0; out:=0; count:=0; end;var pc: producer_consumer;生产者活动：do {加工一件物品item;pc.put_in ( item );} while ( 1 )消费者活动：do { pc.get_out ( item);消耗物品item;} while ( 1 )
例.哲学家就餐问题哲学家活动：repeat思考;L:取左叉;if右叉空闲thenbegin取右叉;进食;放左叉，放右叉;end;elsebegin放左叉; goto L;end;untilfalse
例.哲学家就餐问题typedining_philosophers= MONITOR ;var fork: array[0..4] of (free, used) ;q: array[0..4] ofcondition;definepick_up, try_pick_up, put_down ;procedure pick_up (I: 0..4) ;beginif fork [I] =usedthenwait (q [I]);fork [I] :=used;end ;
function try_pick_up(I: 0..4): boolean ;beginif fork[I] =usedthentry_pick_up :=false;elsebeginfork[I] :=used;try_pick_up :=true;endend ;例.哲学家就餐问题
procedure put_down(I: 0..4) ;beginfork[I] :=free;signal (q [I]) ;end ;beginvar I: 0..4 ;for I := 0 to 4 do fork[I] :=free;end例.哲学家就餐问题
varforks :dining_philosophers;I号哲学家活动：repeat< thinking > ;with_two_forks := false ;repeatforks.pick_up (I) ;if forks.try_pick_up ((I+1) mod 5)thenwith_two_forks := true ;elseforks.put_down ( I ) ;untilwith_two_forks;例.哲学家就餐问题
< Eating > ;forks.put_down (I) ;forks.put_down ((I+1) mod 5) ;Until false;例.哲学家就餐问题问题：各哲学家总是同时拿左叉会出现饿死；
例.单一资源管理typesingle_resource= MONITOR ;var busy : boolean ;queue : condition ;definerequire , release ;Single resourcemanagementprocedure require;beginif busy =truethenwait (queue );busy :=true;end ;procedure release ;beginbusy :=false;signal (queue );end;
begin busy :=falseend ;var lp, tape : single_resource;申请tape :tape.require;释放tape :tape.release;例.单一资源管理PCBPCBPCB…lp.queuePCBPCBPCB…tape.queue申请lp :lp . require ;释放lp :lp . release ;
TYPE semaphore = MONITOR ( init_value )；VAR c : condition ; count : integer ;defineP , V ;procedure V ;begincount := count + 1 ;if count <= 0then signal ( c ) ;end ;4.3.5.5管程与P/V操作的等价性⑴用管程构造P/V操作假定系统中已有管程同步机制，现用它构造P/V操作。procedure P ;begincount := count–1 ;if count < 0 then wait ( c ) ;end ;Procedure initbegin count:=init_value; end ;
管程信号量与P/V操作VAR s : semaphore ;VAR s : semaphore ;init s ( init_value ) ;s.Value := init_value ;s . P ;P ( s ) ;s . V ;V ( s ) ;4.3.5.5管程与P/V操作的等价性P/V操作与管程对应关系⑴用管程构造P/V操作
信号量与PV操作管程一个入口等待队列mutex: semaphore(1)一个紧急等待队列urgent : semaphore (0)一个紧急等待计数urgent_count : integer(0)一个管程实例一个信号灯变量Sc: semaphore (0)一个计数变量c_count : integer (0)一个条件变量var c: condition;if urgent_count > 0thenbeginurgent_count--;V(urgent) ;endelse V(mutex);c_count++ ; P ( Sc ) ;等待操作wait ( c )4.3.5.5管程与P/V操作的等价性(1)用P/V操作构造管程
信号灯与PV操作管程if c_count > 0 thenbeginc_count--;V(Sc);urgent_count ++ ;P(urgent);end唤醒操作signal ( c )P ( mutex ) ;进入管程if urgent_count > 0then beginurgent_count--;V(urgent) ;endelse V ( mutex ) ;离开管程4.3.5.5管程与P/V操作的等价性(2)用P/V操作构造管程
Entry set and wait set4.3.5.7 Java语言中的“管程”ObjectLockownerentry setwait setAcquire locknotify, notifyAllwait
Java“管程”例1：生产/消费问题public classBounded Buffer{ public BoundedBuffer ( ){ count=0; in=0; out=0;buffer = new Object [ BUFFER_SIZE ] ;}private static finalintBUFFER_SIZE=5;privateintcount, in, out;privateObject[]buffer;
publicsynchronizedvoid enter(Object item){ while ( count == BUFFER_SIZE )try{ wait();//被唤醒后重新检测等待条件}catch (InterruptedException e){ }count++;buffer [ in ] = item ;in = ( in+1 ) % BUFFER_SIZE ;notify ( ) ;}Java“管程”例1：生产/消费问题
publicsynchronizedObject remove( ){ while ( count == 0 ){try{ wait();}catch (InterruptedException e){ }}count--;item = buffer [ out ] ;out = ( out + 1 ) % BUFFER_SIZE ;notify ( ) ;return ( item );}} Java“管程”例1：生产/消费问题
Java“管程”例1：生产/消费问题生产者活动：do {加工一件物品item;pc.enter( item );} while ( 1 )消费者活动：do { item=pc.remove;消耗物品item;} while ( 1 )Bounded Bufferpc;
public classDatabase{public Database ( ){ readcount = 0 ;dbReading = false ; dbWriting = false ;}private intreadercount;private booleandbReading;private booleandbWriting;Java“管程”例2：读者/写者问题
publicsynchronizedvoid startRead( ){ while ( dbWriting == true )try{ wait ( ) ;}catch(InterruptedException e){}readcount ++ ;if ( readcount == 1 ) dbReading = true ;}publicsynchronizedvoid endRead(){ readcount--;if ( readcount == 0 ) dbReading = false ;notifyAll () ;}Java“管程”例2：读者/写者问题
publicsynchronizedvoid startWrite( ){ while(dbReading==true||dbWriting==true)try{ wait();}catch (InterruptedException e) { }dbWriting=true;}publicsynchronizedvoid endWrite( ){dbWriting=false;notifyAll();}} Java“管程”例2：读者/写者问题
Assignment #31. P143: #17,#182.用Hoare管程实现电梯算法。
下载地址：{{downurl}}
{{{a}}}
{{#b}}{{{b}}}
{{/b}} {{/title}} {{#nolog}}登陆注册
{{/nolog}} {{#djsx}}点我刷新
{{/djsx}} {{#gocz}} {{/gocz}} {{#ffqr}} {{/ffqr}}