操作系统课件4_3

1、第四章第四章 互斥、同步与通讯互斥、同步与通讯l并发进程并发进程(concurrent processes)l进程互斥进程互斥(mutual exclusion)l进程同步进程同步(synchronization)l进程高级通讯进程高级通讯(communication)l系统举例系统举例14.3.5 管程（管程（Monitor）lPV操作：操作： l分散式同步机制：共享分散式同步机制：共享变量操作，变量操作，PV操作，操作，分散在整个系统中或各分散在整个系统中或各个进程中。个进程中。l缺点：缺点：l可读性差；可读性差；l正确性不易保证；正确性不易保证；l不易修改。不易修改。l优点：优点：l高效

2、，灵活。高效，灵活。l管程：管程：l集中式同步工具：共集中式同步工具：共享变量及其所有相关享变量及其所有相关操作集中在一个摸块操作集中在一个摸块中。中。l优点：优点：l可读性好；可读性好；l正确性易于保证；正确性易于保证；l易于修改。易于修改。l缺点：缺点：l不甚灵活，效率略不甚灵活，效率略低。低。24.3.5.1 管程的提出管程的提出l前面各种互斥手段，虽能有效地实现互斥，前面各种互斥手段，虽能有效地实现互斥，但仍存在着一些缺点：但仍存在着一些缺点：l1) 进程同时进入临界区：将进程同时进入临界区：将P(s)和和V(s)操作颠操作颠倒：倒：l V(S) 临界区临界区 P(S)l可能几个进程同

3、时进入临界区，错误仅在几个进程可能几个进程同时进入临界区，错误仅在几个进程同时活跃在临界区内才可能发现，且这种情况并非同时活跃在临界区内才可能发现，且这种情况并非总是可再现的。总是可再现的。34.3.5.1 管程的提出管程的提出l2) 产生死锁：将产生死锁：将V(s)误写为误写为P(s)l P(S) 临界区临界区 P(S)l S被出错的进程连续两次执行被出错的进程连续两次执行P变成变成-1。使任何其。使任何其它进程不能进入临界区它进程不能进入临界区l不会有其它进程执行不会有其它进程执行V操作，从而发生死锁操作，从而发生死锁l3) 同时进入临界区，永远不会唤醒：同时进入临界区，永远不会唤醒：l如

4、遗漏如遗漏P操作，使得多个进程同时进入临界区操作，使得多个进程同时进入临界区l遗漏遗漏V操作，使其它进程无法进入临界区，永远不操作，使其它进程无法进入临界区，永远不会唤醒。会唤醒。44.3.5.1 管程的提出管程的提出l基于上述问题基于上述问题l1971年由年由E.W.Dijkstra提出把所有进程对提出把所有进程对某某一临界资源的同步操作集中一临界资源的同步操作集中，构成一个，构成一个“秘秘书书”进程进程l凡要访问临界资源的都需先报告凡要访问临界资源的都需先报告“秘书秘书”，由秘书，由秘书来实现诸进程的同步来实现诸进程的同步l1973年年P.B.Hansan和和C.A.R.Hoare将将“秘

5、书秘书”发展为发展为管程管程概念，将同步操作分别集中于相概念，将同步操作分别集中于相应的管程中应的管程中 54.3.5.1 管程的提出管程的提出l背景背景: Structured programmingl基于管程的语言基于管程的语言lConcurrent Pascal (Hansen)lModula (With)lMesalMod*lConcurrent EuclidlXCY64.3.5.2 管程形式管程形式l把一组相关的数据结构和过程一并称为管把一组相关的数据结构和过程一并称为管程程。lHansan定义：一个管程定义了一个定义：一个管程定义了一个数据数据结构结构和能为并发进程所执行和能为并发

6、进程所执行(在该数据结构在该数据结构上上)的的一组操作一组操作，这组操作能同步进程并改，这组操作能同步进程并改变管程中的数据。变管程中的数据。l管程由管程由三部分组成三部分组成：l1）局部于管程的共享变量的说明）局部于管程的共享变量的说明l2）对该数据结构进行的一组操作）对该数据结构进行的一组操作l3）对局部于管程的数据设置初始值的语句）对局部于管程的数据设置初始值的语句74.3.5.2 管程形式管程形式l管程是管理进程间同步的机制管程是管理进程间同步的机制，保证进程，保证进程互斥地访问共享变量互斥地访问共享变量l管程每次仅允许一个进程进入，提供方便的管程每次仅允许一个进程进入，提供方便的阻塞

7、和唤醒进程的机构。阻塞和唤醒进程的机构。l管程提出时，管程提出时，C语言尚未流行，管程大多语言尚未流行，管程大多采用扩展的采用扩展的pascal语言描述语言描述84.3.5.2 管程形式管程形式Type monitor_name=MONITOR 共享变量说明共享变量说明 define 本管程内定义，本管程外使用的子程序名本管程内定义，本管程外使用的子程序名表；表； use 本管程外定义，本管程内使用的子程序名表；本管程外定义，本管程内使用的子程序名表；Procedure 过程名（形参表）；过程名（形参表）； 局部变量说明局部变量说明 Begin 语句序列语句序列 End; 94.3.5.2 管

8、程形式管程形式(Cont.)Function 函数名（形参表）函数名（形参表）:返回值类型；返回值类型； 局部变量说明局部变量说明 Begin 语句序列语句序列 End; . . . . . .Begin 共享变量初始化语句序列共享变量初始化语句序列 End;104.3.5.2 管程形式管程形式(Cont.)l管程三个主要的特性管程三个主要的特性:l模块化模块化：一个管程是一个模块：一个管程是一个模块l抽象数据类型抽象数据类型：管程是一种特殊的数据类型：管程是一种特殊的数据类型, 不仅有数据不仅有数据, 还有对数据进行操作的代码还有对数据进行操作的代码l信息掩蔽信息掩蔽：管程是半透明的：管程是

9、半透明的, 管程的内部过程管程的内部过程(函数函数)实现了某些功能实现了某些功能, 这些功能是怎样实现这些功能是怎样实现的在外部是不可见的的在外部是不可见的114.3.5.3 管程语义管程语义l管程的共享变量在管程外部不可见管程的共享变量在管程外部不可见，外部只能外部只能通过调用管程中的外部子程序访问共享变量通过调用管程中的外部子程序访问共享变量l为保证对共享变量操作的数据完整性，规定管程为保证对共享变量操作的数据完整性，规定管程互斥进入互斥进入124.3.5.3 管程语义管程语义l管程用来管理资源，在管程中设有进程等管程用来管理资源，在管程中设有进程等待队列和相应的等待及唤醒操作待队列和相应

10、的等待及唤醒操作l当一个进入管程的进程执行等待操作时当一个进入管程的进程执行等待操作时, 它应当释放管程的互斥权它应当释放管程的互斥权l当一个进入管程的进程执行唤醒操作时当一个进入管程的进程执行唤醒操作时(如如P唤醒唤醒Q)，管程中同时有两个处于活动状，管程中同时有两个处于活动状态的进程，有三种处理方法：态的进程，有三种处理方法：lP等待，等待，Q继续，直到继续，直到Q退出或等待退出或等待(Hoare)lQ等待，等待，P继续，直到继续，直到P退出或等待退出或等待(Java)l唤醒是管程中可执行的最后一个操作唤醒是管程中可执行的最后一个操作(Hansen)134.3.5.3 管程语义管程语义l管

11、程互斥进入，当进程试图进入已被占用管程互斥进入，当进程试图进入已被占用的管程时应在管程入口处等待的管程时应在管程入口处等待l在管程的入口处有一个进程等待队列在管程的入口处有一个进程等待队列, 称称作入口等待队列。作入口等待队列。14Hoare管程设施管程设施lHoare管程设施：管程设施： l入口等待队列：入口等待队列：l每个管程变量一个，用于排队进入；每个管程变量一个，用于排队进入；l紧急等待队列：紧急等待队列：l每个管程变量一个，用于唤醒等待；每个管程变量一个，用于唤醒等待；l内部等待队列：内部等待队列：lvar c: condition; 条件变量条件变量l可根据需要定义多个，用于设置等

12、待条件。可根据需要定义多个，用于设置等待条件。15条件变量操作条件变量操作l利用管程实现进程同步，必须设置利用管程实现进程同步，必须设置PV操作操作l等待的原因有多个，为了区别，引入条件等待的原因有多个，为了区别，引入条件变量变量conditionl管程中对每个条件变量给出说明：管程中对每个条件变量给出说明： lVar c:condition;16内部等待队列内部等待队列lwait(c)l如紧急队列非空，唤醒第一个等待者，否则如紧急队列非空，唤醒第一个等待者，否则释放管程互斥权释放管程互斥权;l执行此操作进程的执行此操作进程的PCB（线程）进入（线程）进入c链尾。链尾。相当于相当于P操作。操作

13、。 lsignal(c)lc链空，相当空操作。否则唤醒第一个链空，相当空操作。否则唤醒第一个l执行此操作进程的执行此操作进程的PCB（线程）进入紧急队（线程）进入紧急队列。相当于列。相当于V操作。操作。1718进入与离开进入与离开l进入管程：进入管程：l申请管程互斥权。申请管程互斥权。l离开管程：离开管程：l如紧急等待队列非空，唤醒第一个等待者；如紧急等待队列非空，唤醒第一个等待者；否则开放管程。否则开放管程。194.3.5.4 管程的使用管程的使用l读者读者/写者问题（写优先）写者问题（写优先）l生产者和消费者问题生产者和消费者问题 l哲学家就餐问题（哲学家就餐问题（another appr

14、oach) lDisk head scheduler lSingle resource managementlSleepy barbers problem 20例例1. 读者读者/写者问题写者问题(写者优先写者优先)lrq:读队列，读队列，wq：写队列：写队列lreading_count,write_count：读写进程：读写进程个数个数lType reaers_writers = Monitor; Var rq,wq: condition; reading_count,write_count:integer; Define start_read,finish_read, start_writ

15、e,finish_write;21例例1. 读者读者/写者问题写者问题Procedure start_read; Begin If write_count0 Then wait(rq); reading_count+; signal(rq); End;Procedure finish_read; Begin reading_count-; If reading_count=0 Then signal(wq) End;22例例1. 读者读者/写者问题写者问题Procedure start_write Begin write_count+; If (write_count1) or (readin

16、g_count0) Then wait(wq) End; Procedure finish_write; Begin write_count-; If write_count0 Then signal(wq) Else signal(rq) End;23例例1. 读者读者/写者问题写者问题Begin reading_count:=0; write_count:=0;End;Var rw: readers_writers;读者：读者： 写者：写者：rw.start_read; rw.start_write;reading writingrw.finish_read; rw.finish_writ

17、e;24例例2. 生产者和消费者问题生产者和消费者问题lnotFull：表示是否允许将产品放入缓冲区中：表示是否允许将产品放入缓冲区中lnotEmpty：表示是否允许消费产品：表示是否允许消费产品25例例2. 生产者和消费者问题生产者和消费者问题26例例2. 生产者和消费者问题生产者和消费者问题27例例3. 磁头引臂调度问题磁头引臂调度问题l某单磁头磁盘系统共有某单磁头磁盘系统共有200个磁道个磁道(柱面柱面)，由外向内依次编号为由外向内依次编号为0,199，如图，如图4-10所示所示. 当有多个磁盘块的当有多个磁盘块的I/O请求时，采用请求时，采用电梯算法调度，试用管程给出解法电梯算法调度，

18、试用管程给出解法 28例例3. 磁头引臂调度问题磁头引臂调度问题0 1 199updown磁头磁头引臂引臂扇区扇区29调度算法调度算法lFCFS（first come first serve）l公平公平l效率低效率低lSSTF（shortest seek time first）l效率高效率高l磁道歧视磁道歧视lSCAN（elevator algorithm）l效率较高，较公平效率较高，较公平30Hansen管程实现管程实现SCAN算法算法外部过程：外部过程： 申请：申请：require(dest:0.199) 释放：释放：release()使用方式：使用方式： require(dest); I

19、O操作操作 -(管程外操作管程外操作) release31Hansen管程实现管程实现SCAN算法算法l资源状态用资源状态用busy描述描述l磁头引臂当前位置和移动方向分别用磁头引臂当前位置和移动方向分别用headpos和和direction描述描述l算法的关键是为每个磁道算法的关键是为每个磁道(柱面柱面)设置一个设置一个等待队列等待队列cylinder，同时记录等待在每个，同时记录等待在每个队列上进程的个数队列上进程的个数 32管程实现管程实现SCAN算法算法Type diskhead=MONITOR Var busy:boolean; headpos:0.199; direction:(u

20、p,down); cylinder:Array0.199Of condition; count:Array0.199Of integer; Define require, release;33管程实现管程实现SCAN算法算法 Procedure require(dest:0.199); Begin If busy Then Begin countdest:=countdest+1; wait(cylinderdest) End busy:=true; If destheadpos Then direction:=up; headpos:=dest End; 34管程实现管程实现SCAN算法算法

21、 Procedure upscan; Var I:0.200; Begin I:=headpos; While (I=199)and(countI=0) Do I:=I+1; If I=0)and(countI=0) Do I:=I-1; If I=0 Then Begin countI:=countI-1; signal(cylinderI) End End;36管程实现管程实现SCAN算法算法Procedure release; Begin busy:=false; If direction=up Then Begin upscan; downscan End Else Begin dow

22、nscan; upscan End End;37管程实现管程实现SCAN算法算法Procedure initialize; Var I: 0.199; Begin busy:=false; headpos:=0; direction:=up; For I:=0 To 199 Do countI:=0 EndBegin initialize End; 38例例4. 单一资源管理单一资源管理Type single_resource=MONITOR; Var busy:boolean; q:condition; Define require,release; Procedure require; B

23、egin If busy Then wait(q); busy:=true End;39例例4. 单一资源管理单一资源管理Procedure release; Begin busy:=false; signal(q); End;Begin busy:=false End;Var lp, tape:single_resource;Busyqlp:BusyqTape:申请申请lp: lp.require释放释放lp: lp.release申请申请tape: tape.require;释放释放tape: tape.release40例例5. 嗜眠理发师问题嗜眠理发师问题 l理发店如图理发店如图4-1

24、1所示所示l店中有一位理发师和一把理发椅，理发时顾店中有一位理发师和一把理发椅，理发时顾客坐在此椅子上，不理发时理发师在此椅子客坐在此椅子上，不理发时理发师在此椅子上睡觉上睡觉l室内有室内有N个凳子，供顾客们等待理发时用个凳子，供顾客们等待理发时用.l如果一位顾客进入理发店后发现所有凳子均如果一位顾客进入理发店后发现所有凳子均已被占用，则他退出理发店已被占用，则他退出理发店l理发店只有一扇门，理发店只有一扇门， 一次只能进出一位顾客一次只能进出一位顾客 41例例5. 嗜眠理发师问题嗜眠理发师问题42例例5. 嗜眠理发师问题嗜眠理发师问题lchair ：理发师是否可以理发：理发师是否可以理发ls

25、tool ：是否有人等待理发：是否有人等待理发4344例例5. 嗜眠理发师问题嗜眠理发师问题454.3.5.5 管程与管程与PV操作的等价性操作的等价性用用PV操作可以构造管程操作可以构造管程用管程可以构造用管程可以构造PV操作操作46用管程构造用管程构造PV操作操作TYPE semaphore=MONITOR(init_value) VAR c:condition; count: integer;DEFINE P,V;PROCEDURE P; BEGIN count:=count-1; IF count0 THEN wait(c); END;PROCEDURE V; BEGIN count:

26、=count+1; IF count 0 THEN BEGIN urgent_count:=urgent_count-1; V(urgent) ELSE V(mutex);P(s);49用用PV操作构造管程操作构造管程管程管程信号灯与信号灯与PV操作操作唤醒操作唤醒操作Signal(c)IF count0 THEN BEGIN count:=count-1; urgent_count:=urgent_count+1; V(s); P(urgent) END进入管程进入管程P(mutex);离开管程离开管程IF urgent_count0 THEN BEGIN urgent_count:=urg

27、ent_count-1; V(urgent) ENDELSE V(mutex);504.3.5.6 管程的嵌套调用问题管程的嵌套调用问题Wait(c)P:M1M2MnMn-1.问题：问题：1. 是否允许嵌套；是否允许嵌套； 2. 若允许，如何处理互斥权。若允许，如何处理互斥权。方法：方法：1. 禁止嵌套（禁止嵌套（Modula) 2. 允许嵌套，等待时释放当前管程互斥权允许嵌套，等待时释放当前管程互斥权； 3. 允许嵌套，等待时释放所有管程互斥权；允许嵌套，等待时释放所有管程互斥权； 4. 允许嵌套，调用时释放路经管程互斥权允许嵌套，调用时释放路经管程互斥权51Java语言中的语言中的“管程管

28、程”l类似管程的对象类似管程的对象objectl每个每个object有一个互斥锁有一个互斥锁lock，一般未用；，一般未用；l说明为说明为synchronized的的method启用互斥锁；启用互斥锁；l每个每个object内部有一个等待队列；内部有一个等待队列；lwait() method: l释放释放lock, 状态改为状态改为blocked, 进入进入wait set.lnotify() method:l在在wait set中取任意线程，移到中取任意线程，移到entry set,状态改为状态改为runnable. (Signal and continue)lnotifyAll() met

29、hod:lWait set所有线程移到所有线程移到entry set, 状态改为状态改为runnable.52Entry set and wait setlObjectlLock lownerlEntry setlwait setlwaitlAcquire locklnotify, notifyAll53Entry set and wait setl锁的持有者执行锁的持有者执行wait操作操作, 状态改为状态改为blocked,释放所持有的锁释放所持有的锁, 进入进入wait set; 若若entry set非空非空,选择其一进入同步方法选择其一进入同步方法.l锁的持有者执行锁的持有者执行no

30、tify操作操作, 任选任选wait set上的一个线程上的一个线程, 入入entry set, 状态改为状态改为runnable. l锁的持有者执行锁的持有者执行notifyAll操作操作, wait set上上的所有线程出的所有线程出wait set, 入入entry set, 状态状态改为改为runnable.54例子：生产例子：生产/消费问题消费问题-Javalpublic synchronized void enter(Object item) l while (count=BUFFER_SIZE) l try wait(); /被唤醒后重新检测等待条件被唤醒后重新检测等待条件l c

31、atch (InterruptedException e) l l +count;l bufferin=item;l in=(in+1)% BUFFER_SIZE;l notify();l 55例子：生产例子：生产/消费问题消费问题-javal public synchronized Object remove() l while (count=0) l try wait();l catch (InterruptedException e) l l -count;l item=bufferout;l out=(out+1)% BUFFER_SIZE;l notify();l return(it

32、em);l 56例子：生产例子：生产/消费问题消费问题-javal private static final int NAP_TIME=5;l private static final int BUFFER_SIZE=5;l private int count in,out;l private Object buffer;l57读者写者问题读者写者问题-Java solutionlMultiple notificationlnotifyAll() - 唤醒唤醒wait set集合中所有线程集合中所有线程, 进入进入entry set。lpublic class Database l publi

33、c Database() l Readcount=0;l dbReading=false;l dbWriting=false;l l public synchronized int startRead() l / l 58读者写者问题读者写者问题-Java solutionl public synchronized int endRead() l /l l public synchronized startWrite() l /l l public synchronized endWrite() l /l l private int readerCount;l private boolean

34、dbReading;l private boolean dbWriting;l59读者写者问题读者写者问题-Java solutionlpublic synchronized void startRead() l while (dbWriting=true) l try l wait();l catch(InterruptedException e)l +readCount;l if (readCount=1)l dbReading=true;l60读者写者问题读者写者问题-Java solutionl public synchronized void endRead() l -readCount;l if(readCount=0)l dbReading=false;l notifyAll();l61读者写者问题读者写者问题-Java solutionl public synchronized void startWrite() l while(dbReading=true|dbWriting=true) l try l wait();l catch(InterruptedException e) l l dbWriting=true;l l public synchronized void endWrite()l dbWriting=false;l n