操作系统课件4-3

第四章互斥、同步与通讯并发进程(concurrentprocesses)进程互斥(mutualexclusion)进程同步(synchronization)进程高级通讯(communication)系统举例14.3.5管程（Monitor）PV操作：分散式同步机制：共享变量操作，PV操作，分散在整个系统中或各个进程中。缺点：可读性差；正确性不易保证；不易修改。优点：高效，灵活。管程：集中式同步工具：共享变量及其所有相关操作集中在一个摸块中。优点：可读性好；正确性易于保证；易于修改。缺点：不甚灵活，效率略低。24.3.5.1管程的提出前面各种互斥手段，虽能有效地实现互斥，但仍存在着一些缺点：1)进程同时进入临界区：将P(s)和V(s)操作颠倒：

V(S)

临界区

P(S)可能几个进程同时进入临界区，错误仅在几个进程同时活跃在临界区内才可能发现，且这种情况并非总是可再现的。34.3.5.1管程的提出2)产生死锁：将V(s)误写为P(s)

P(S)

临界区

P(S)

S被出错的进程连续两次执行P变成-1。使任何其它进程不能进入临界区不会有其它进程执行V操作，从而发生死锁3)同时进入临界区，永远不会唤醒：如遗漏P操作，使得多个进程同时进入临界区遗漏V操作，使其它进程无法进入临界区，永远不会唤醒。44.3.5.1管程的提出基于上述问题1971年由E.W.Dijkstra提出把所有进程对某一临界资源的同步操作集中，构成一个“秘书”进程凡要访问临界资源的都需先报告“秘书”，由秘书来实现诸进程的同步1973年P.B.Hansan和C.A.R.Hoare将“秘书”发展为管程概念，将同步操作分别集中于相应的管程中54.3.5.1管程的提出背景:Structuredprogramming基于管程的语言ConcurrentPascal(Hansen)Modula(With)MesaMod*ConcurrentEuclidXCY64.3.5.2管程形式把一组相关的数据结构和过程一并称为管程。Hansan定义：一个管程定义了一个数据结构和能为并发进程所执行(在该数据结构上)的一组操作，这组操作能同步进程并改变管程中的数据。管程由三部分组成：1）局部于管程的共享变量的说明2）对该数据结构进行的一组操作3）对局部于管程的数据设置初始值的语句74.3.5.2管程形式管程是管理进程间同步的机制，保证进程互斥地访问共享变量管程每次仅允许一个进程进入，提供方便的阻塞和唤醒进程的机构。管程提出时，C语言尚未流行，管程大多采用扩展的pascal语言描述84.3.5.2管程形式Typemonitor_name=MONITOR

共享变量说明

define

本管程内定义，本管程外使用的子程序名表；

use

本管程外定义，本管程内使用的子程序名表；Procedure过程名（形参表）；

局部变量说明

Begin

语句序列

End;…94.3.5.2管程形式(Cont.)Function

函数名（形参表）:返回值类型；局部变量说明

Begin

语句序列

End;...Begin

共享变量初始化语句序列End;104.3.5.2管程形式(Cont.)管程三个主要的特性:模块化：一个管程是一个模块抽象数据类型：管程是一种特殊的数据类型,不仅有数据,还有对数据进行操作的代码信息掩蔽：管程是半透明的,管程的内部过程(函数)实现了某些功能,这些功能是怎样实现的在外部是不可见的114.3.5.3管程语义管程的共享变量在管程外部不可见，外部只能通过调用管程中的外部子程序访问共享变量为保证对共享变量操作的数据完整性，规定管程互斥进入124.3.5.3管程语义管程用来管理资源，在管程中设有进程等待队列和相应的等待及唤醒操作当一个进入管程的进程执行等待操作时,它应当释放管程的互斥权当一个进入管程的进程执行唤醒操作时(如P唤醒Q)，管程中同时有两个处于活动状态的进程，有三种处理方法：P等待，Q继续，直到Q退出或等待(Hoare)Q等待，P继续，直到P退出或等待(Java)唤醒是管程中可执行的最后一个操作(Hansen)134.3.5.3管程语义管程互斥进入，当进程试图进入已被占用的管程时应在管程入口处等待在管程的入口处有一个进程等待队列,称作入口等待队列。14Hoare管程设施Hoare管程设施：入口等待队列：每个管程变量一个，用于排队进入；紧急等待队列：每个管程变量一个，用于唤醒等待；内部等待队列：varc:condition;条件变量可根据需要定义多个，用于设置等待条件。15条件变量操作利用管程实现进程同步，必须设置PV操作等待的原因有多个，为了区别，引入条件变量condition管程中对每个条件变量给出说明：

Varc:condition;

16内部等待队列wait(c)如紧急队列非空，唤醒第一个等待者，否则释放管程互斥权;执行此操作进程的PCB（线程）进入c链尾。相当于P操作。

signal(c)c链空，相当空操作。否则唤醒第一个执行此操作进程的PCB（线程）进入紧急队列。相当于V操作。1718进入与离开进入管程：申请管程互斥权。离开管程：如紧急等待队列非空，唤醒第一个等待者；否则开放管程。194.3.5.4管程的使用读者/写者问题（写优先）生产者和消费者问题哲学家就餐问题（anotherapproach)DiskheadschedulerSingleresourcemanagementSleepybarber’sproblem20例1.读者/写者问题(写者优先)rq:读队列，wq：写队列reading_count,write_count：读写进程个数Typereaers_writers=Monitor;Varrq,wq:condition;reading_count,write_count:integer;Definestart_read,finish_read,start_write,finish_write;21例1.读者/写者问题Procedurestart_read;BeginIfwrite_count>0Thenwait(rq);reading_count++;signal(rq);End;Procedurefinish_read;Beginreading_count--;Ifreading_count=0Thensignal(wq)End;22例1.读者/写者问题Procedurestart_writeBeginwrite_count++;If(write_count>1)or(reading_count>0)Thenwait(wq)End;Procedurefinish_write;Beginwrite_count--;Ifwrite_count>0Thensignal(wq)Elsesignal(rq)End;23例1.读者/写者问题Beginreading_count:=0;write_count:=0;End;Varrw:readers_writers;读者：写者：rw.start_read;rw.start_write;{reading}{writing}rw.finish_read;rw.finish_write;24例2.生产者和消费者问题notFull：表示是否允许将产品放入缓冲区中notEmpty：表示是否允许消费产品25例2.生产者和消费者问题26例2.生产者和消费者问题27例3.磁头引臂调度问题某单磁头磁盘系统共有200个磁道(柱面)，由外向内依次编号为0,…,199，如图4-10所示.当有多个磁盘块的I/O请求时，采用电梯算法调度，试用管程给出解法28例3.磁头引臂调度问题01……199updown磁头引臂扇区29调度算法FCFS（firstcomefirstserve）公平效率低SSTF（shortestseektimefirst）效率高磁道歧视SCAN（elevatoralgorithm）效率较高，较公平30Hansen管程实现SCAN算法外部过程：申请：require(dest:0..199)

释放：release()使用方式：

require(dest);{IO操作}--(管程外操作)release31Hansen管程实现SCAN算法资源状态用busy描述磁头引臂当前位置和移动方向分别用headpos和direction描述算法的关键是为每个磁道(柱面)设置一个等待队列cylinder，同时记录等待在每个队列上进程的个数32管程实现SCAN算法Typediskhead=MONITORVarbusy:boolean;headpos:0..199;direction:(up,down);cylinder:Array[0..199]Ofcondition;count:Array[0..199]Ofinteger;

Definerequire,release;33管程实现SCAN算法Procedurerequire(dest:0..199);BeginIfbusyThenBegincount[dest]:=count[dest]+1;wait(cylinder[dest])Endbusy:=true;Ifdest<headposThendirection:=downElseIfdest>headposThendirection:=up;headpos:=destEnd;34管程实现SCAN算法Procedureupscan;VarI:0..200;BeginI:=headpos;While(I<=199)and(count[I]=0)DoI:=I+1;IfI<=199ThenBegincount[I]:=count[I]-1;signal(cylinder[I])EndEnd;35管程实现SCAN算法Proceduredownscan;VarI:-1..199;BeginI:=headpos;While(I>=0)and(count[I]=0)DoI:=I-1;IfI>=0ThenBegincount[I]:=count[I]-1;signal(cylinder[I])EndEnd;36管程实现SCAN算法Procedurerelease;Beginbusy:=false;Ifdirection=upThenBeginupscan;downscanEndElseBegindownscan;upscanEndEnd;37管程实现SCAN算法Procedureinitialize;VarI:0..199;Beginbusy:=false;headpos:=0;direction:=up;ForI:=0To199Docount[I]:=0EndBegininitializeEnd;38例4.单一资源管理Typesingle_resource=MONITOR;Varbusy:boolean;q:condition;Definerequire,release;Procedurerequire;BeginIfbusyThenwait(q);busy:=trueEnd;39例4.单一资源管理Procedurerelease;Beginbusy:=false;signal(q);End;Beginbusy:=falseEnd;Varlp,tape:single_resource;Busyqlp:BusyqTape:申请lp:lp.require释放lp:lp.release申请tape:tape.require;释放tape:tape.release40例5.嗜眠理发师问题理发店如图4-11所示店中有一位理发师和一把理发椅，理发时顾客坐在此椅子上，不理发时理发师在此椅子上睡觉．室内有N个凳子，供顾客们等待理发时用.如果一位顾客进入理发店后发现所有凳子均已被占用，则他退出理发店理发店只有一扇门，一次只能进出一位顾客41例5.嗜眠理发师问题42例5.嗜眠理发师问题chair：理发师是否可以理发stool：是否有人等待理发

4344例5.嗜眠理发师问题454.3.5.5管程与PV操作的等价性用PV操作可以构造管程用管程可以构造PV操作46用管程构造PV操作TYPEsemaphore=MONITOR(init_value)VARc:condition;count:integer;DEFINEP,V;PROCEDUREP;BEGINcount:=count-1;IFcount<0THENwait(c);END;PROCEDUREV;BEGINcount:=count+1;IFcount<=0THENsignal(c);END;BEGINcount:=init_value;END;47用管程构造PV操作(Cont.)信号灯与PV操作管程VARs:semaphore;VARs:semaphore;s.value:=init_value;Inits(init_value);P(s);s.P;V(s);s.V;48用PV操作构造管程管程信号灯与PV操作一个管程实例一个入口等待队列mutex:semaphore(1)一个紧急等待队列urgent:semaphore(0)一个紧急等待计数urgent_count:integer(0)一个条件变量c:condition;一个信号灯变量s:semaphore(0)一个计数变量count:integer(0)等待操作wait(c)count:=count+1;IFurgent_count>0THENBEGINurgent_count:=urgent_count-1;V(urgent)ELSEV(mutex);P(s);49用PV操作构造管程管程信号灯与PV操作唤醒操作Signal(c)IFcount>0THENBEGINcount:=count-1;urgent_count:=urgent_count+1;V(s);P(urgent)END进入管程P(mutex);离开管程IFurgent_count>0THENBEGINurgent_count:=urgent_count-1;V(urgent)ENDELSEV(mutex);504.3.5.6管程的嵌套调用问题Wait(c)P:M1M2MnMn-1...问题：1.是否允许嵌套；

2.若允许，如何处理互斥权。方法：1.禁止嵌套（Modula)2.允许嵌套，等待时释放当前管程互斥权；

3.允许嵌套，等待时释放所有管程互斥权；

4.允许嵌套，调用时释放路经管程互斥权51Java语言中的“管程”类似管程的对象object每个object有一个互斥锁lock，一般未用；说明为synchronized的method启用互斥锁；每个object内部有一个等待队列；wait()method:释放lock,状态改为blocked,进入waitset.notify()method:在waitset中取任意线程，移到entryset,状态改为runnable.(Signalandcontinue)notifyAll()method:Waitset所有线程移到entryset,状态改为runnable.52EntrysetandwaitsetObjectLockownerEntrysetwaitsetwaitAcquirelocknotify,notifyAll53Entrysetandwaitset锁的持有者执行wait操作,状态改为blocked,释放所持有的锁,进入waitset;若entryset非空,选择其一进入同步方法.锁的持有者执行notify操作,任选waitset上的一个线程,入entryset,状态改为runnable.锁的持有者执行notifyAll操作,waitset上的所有线程出waitset,入entryset,状态改为runnable.54例子：生产/消费问题--Javapublicsynchronizedvoidenter(Objectitem){while(count==BUFFER_SIZE){try{wait();//被唤醒后重新检测等待条件

}catch(InterruptedExceptione){}}++count;buffer[in]=item;in=(in+1)%BUFFER_SIZE;notify();}55例子：生产/消费问题--java

publicsynchronizedObjectremove(){while(count==0){try{wait();}catch(InterruptedExceptione){}}--count;item=buffer[out];out=(out+1)%BUFFER_SIZE;notify();return(item);}56例子：生产/消费问题--java

privatestaticfinalintNAP_TIME=5;privatestaticfinalintBUFFER_SIZE=5;privateintcountin,out;privateObject[]buffer;}57读者／写者问题-JavasolutionMultiplenotificationnotifyAll()--唤醒waitset集合中所有线程,进入entryset。publicclassDatabase{publicDatabase(){Readcount=0;dbReading=false;dbWriting=false;}publicsynchronizedintstartRead(){//}58读者／写者问题-Javasolution

publicsynchronizedintendRead(){//}publicsynchronizedstartWrite(){//}publicsynchronizedendWrite(){//}privateintreaderCount;privatebooleandbReading;privatebooleandbWriting;}59读者／写者问题-JavasolutionpublicsynchronizedvoidstartRead(){while(dbWriting==true){try{wait();}catch(InterruptedExceptione){}++readCount;if(readCount==1)dbReading=true;}60读者／写者问题-Javasolution

publicsynchronizedvoidendRead(){--readCount;if(readCount==0)dbReading=false;notifyAll();}61读者／写者问题-Javasolution

publicsynchronizedvoidstartWrite(){while(dbReading==true||dbWriting==true){try{wait();}catch(InterruptedExceptione){}}