操作系统第四章1

1、l并发进程并发进程(concurrent processes)l进程互斥进程互斥(mutual exclusion)l进程同步进程同步(synchronization)l进程高级通讯进程高级通讯(communication)l4.1.1 顺序性与并发性顺序性与并发性顺序性顺序性l内部顺序性内部顺序性：P1: a1,a2,a3; P2: b1,b2,b3l外部顺序性外部顺序性：a1,a2,a3,b1,b2,b3; b1,b2,b3,a1,a2,a3并发性并发性l内部并发性内部并发性：P2: b1,b2,b3; P2: b1,b3,b2l外部并发性外部并发性：a1,b1,b2,a2,a3,b3;

2、b1,b2,a1,b3,a2,a3例：图书借阅系统例：图书借阅系统 （x:某种某种书册数，设当前书册数，设当前x=1.）终端终端1： 终端终端2：CYCLE CYCLE 等待借书者等待借书者； 等待借书者等待借书者； IF x=1 Then IF x=1 Then Begin Begin x:=x-1; x:=x-1; 借书借书 借书借书 End End Else 无书无书 Else 无书无书 End End 1234错误原因之错误原因之1： 进程执行交叉进程执行交叉(interleave);错误原因之错误原因之2： 涉及公共变量涉及公共变量(x)。 注意: 某些交叉结果不正确某些交叉结果不正

3、确; 必须去掉导致不正确结果的交叉必须去掉导致不正确结果的交叉。l4.2.1 共享变量与临界区共享变量与临界区l4.2.2 临界区域与进程互斥临界区域与进程互斥l4.2.3 进程互斥的实现进程互斥的实现l4.2.4 多处理机环境下的互斥多处理机环境下的互斥l共享变量共享变量（shared variable）多个进程都需要访问的变量。多个进程都需要访问的变量。l临界区域临界区域（critical region）访问共享变量的程序段访问共享变量的程序段。 一组公共变量一组公共变量CR1CR2CRn.共享变量共享变量: shared 临界区域临界区域: region do 语句语句例子：例子：sha

4、red B:array0,.,n-1of integer; region B do region B do begin begin (访问访问B） .（访问访问B）. end; end; 定义定义：多个进程不能同时进入关于同一组共享变量的临多个进程不能同时进入关于同一组共享变量的临界区域，否则可能发生与时间有关的错误，这种现象称界区域，否则可能发生与时间有关的错误，这种现象称为进程互斥为进程互斥二层涵义：二层涵义： （1）任何时刻最多只能有一个进程处于同一组共）任何时刻最多只能有一个进程处于同一组共享变量的相同的临界区域；享变量的相同的临界区域； （2）任何时刻最多只能有一个进程处于同一组共）

5、任何时刻最多只能有一个进程处于同一组共享变量的不同的临界区域享变量的不同的临界区域。注意注意: 互斥是相对于公共变量而言的。互斥是相对于公共变量而言的。 shared x1,x2; shared y1,y2; region x1,x2 do region y1,y2 do begin begin . region y1,y2 do region x1,x2 do begin begin . . end end end; end;lFrameworkRepeat critical section remainder sectionUntil falseentry sectionexit sect

6、ionl需求:mutual exclusion: 一次只允许一个进程活动在关于一次只允许一个进程活动在关于同一组公共变量的临界区中同一组公共变量的临界区中；progress: 临界区空闲时，多个竞争者在有限时间临界区空闲时，多个竞争者在有限时间内确定下一个进入者内确定下一个进入者；bounded waiting: 一个想要进入临界区的进程在等一个想要进入临界区的进程在等待有限个进程进入并离开临界区后可以获得进入临待有限个进程进入并离开临界区后可以获得进入临界区的机会界区的机会。l完全用程序实现，不需特殊硬件指令支完全用程序实现，不需特殊硬件指令支持。持。l可用于单可用于单CPU和多和多CPU环

7、境中。环境中。l有忙式等待问题。有忙式等待问题。Busy waiting“运行运行”或或“就绪就绪”算法思想算法思想：设置一个发号者，按：设置一个发号者，按0,1,2, 发号。想进入临发号。想进入临界区的进程抓号，抓到号之后按由小到大的次序依次进入界区的进程抓号，抓到号之后按由小到大的次序依次进入。Problem: 两个进程可能抓到相同的号。两个进程可能抓到相同的号。Why? 为保证抓到不同的号，需要互斥机制。为保证抓到不同的号，需要互斥机制。Resolution: 若抓到相同的号，按进程编号依次进入。若抓到相同的号，按进程编号依次进入。Definition: (a,b)(c,d) iff (

8、ac)or(a=c and bd)VAR choosing: Array0,n-1Of Boolean;（false) number: Array0,n-1Of integer; (0)Pi 进入进入：1. choosingi:=true;2. numberi:=maxnumber0,numbern-1+1;3. choosingi:=false;4. For j:=0 To n-1 Do5. While choosingj Do skip;6. While (numberj0)and7. (numberj,j)(numberi,i) Do skip8. Endfor (1)P1抓到1未赋值(

9、2)P2抓到1进入临界区(3)P3抓到2进入临界区Pi离开：离开： numberi:=0：变量变量choosing的的作用：作用：P1：抓到：抓到1; P2：抓到：抓到1; 正确次序：正确次序：P1，P2，P3P3：抓到：抓到2; 可能按可能按P2,P3,P1次序进入次序进入！Var flag Array0,n-1Of (idle, want_in, in_cs); turn: 0.n-1; 初始任意初始任意0 i turnn-1先于先于i先于先于iflagi=idle: 进程进程Pi不想进入临界区不想进入临界区flagi=want_in: 进程进程Pi想进入临界区想进入临界区flagi=in

10、_cs: 进程进程Pi想进入或已进入临界区想进入或已进入临界区Pi进入进入:Repeat flagi:=want_in; j:=turn; While ji do If flagjidle Then j:=turn Else j:=(j+1)mod n; flagi:=in_cs; j:=0; While (jn)and(j=i or flagjin_cs) do j:=j+1;Until (j=n)and(turn=i or flagturn=idle);turn:=i;Pi离开：离开：j:=(turn+1)mod n;While (flagj=idle)do j:=(j+1)mod n;t

11、urn:=j;flagi:=idle;CS1. 硬件提供硬件提供“测试并建立测试并建立”指令指令 Function test_and_set(var target:Boolean):Boolean; Begin test_and_set:=target; target:=true End. 对一组公共变量对一组公共变量，var lock:Boolean（初始初始=false); Pi进入进入：While test_and_set(lock)Do skip; Pi离开离开：lock:=false;2. 硬件提供硬件提供“交换交换”指令指令 Procedure swap(var a,b:boole

12、an) var temp: boolean; Begin temp:=a; a:=b; b:=temp End; 对一组公共变量对一组公共变量：var lock: boolean(初始初始=false); 对一个进程空间对一个进程空间：var key: boolean; Pi进入进入：key:=true; Repeat swap(lock,key) Until key=false; Pi离开离开：lock:=false;Remarks：(1) test_and_set指令和指令和swap指令是原子的，指令是原子的，不可中断的。不可中断的。(2) test_and_set实际上是：将内存中一个单

13、实际上是：将内存中一个单元的内容取出，再送一个新值。元的内容取出，再送一个新值。(3) swap实际上是：交换内存两个单元的内容实际上是：交换内存两个单元的内容。3. 硬件提供硬件提供“关中断关中断”和和“开中断开中断”指指令令 关中断关中断 Critical Region 开中断开中断Remarks: (1) 开关中断只在单开关中断只在单CPU系统中有效系统中有效;(why?) (2) 影响并发性。影响并发性。内存内存Word 1000initial: 0CPU1CPU2Bus1. Read 03. Write 1 2. Read 04. Write 1TS指令指令，Swap指令指令: fi

14、rst lock the busbus request protocol: modern buses have these facilities earlier ones didntb=1;while(b) lock(bus); b = test_and_set(&lock); unlock(bus);lock=0;CR4.3.1 进程同步的概念进程同步的概念例：司机例：司机-乘客问题乘客问题 司机活动：司机活动：(P1) 乘客活动：乘客活动：(P2) do do 启动车辆启动车辆 上上 车车 正常行驶正常行驶 投投 币币 到站停车到站停车 乘乘 车车 下下 车车 while( (1) ) w

15、hile( (1) )定义：定义：一组进程，为协调其推进速度，在某些一组进程，为协调其推进速度，在某些关键点处需要相互等待与相互唤醒，进程之间关键点处需要相互等待与相互唤醒，进程之间这种相互制约的关系称为进程同步。这种相互制约的关系称为进程同步。P1:P2:synchronize后先l定义：定义：用于实现进程同步的工具称为同用于实现进程同步的工具称为同步机制步机制（synchronization mechanism）l同步机制要求：同步机制要求：描述能力够用描述能力够用;可实现可实现;高效高效;使用方便使用方便.l信号灯与PV操作(semaphore and PV operations)l管程

16、(monitor)l会合(rendezvous)l条件临界区(conditional critical region)l路径表达式(path expression)l事件(traditional UNIX)4.3.3.1 信号灯与信号灯与PV操作的定义操作的定义 TYPE semaphore=RECORD value: integer; queue: PCB pointer; END; VAR s: semaphore;备注:(1) semaphore 是一个提前定义好的数据类型.(2) s 是一个信号灯变量,使用前必须先声明. 例如: var s1,s2:semaphore; S.value

17、S.queueS.valueS.queuePCBPCBPCBVar S:semaphore;FIFOP操作原语操作原语：Procedure P(var s:semaphore) s.value:=s.value-1; If s.value0 Then asleep(s.queue)Endasleep(s.queue):(1) 执行此操作进程的执行此操作进程的PCB入入s.queue尾（状态改为等待）；尾（状态改为等待）；(2) 转处理机调度程序。转处理机调度程序。 Primitive: a piece of code un-interruptibleV操作原语：操作原语：Procedure V

18、(var s:semaphore) s.value:=s.value+1; If s.value=0;只能执行只能执行P操作和操作和V操作，所有其它操作非法。操作，所有其它操作非法。l几个有用的结论几个有用的结论：当当s.value=0时，时，s.queue为空；为空；当当s.value=1 Then IF x=1 Then Begin Begin x:=x-1; x:=x-1; V(mutex) V(mutex) 借书借书 借书借书 End End Else V(mutex);无书无书; Else V(mutex);无书无书; End End P(S)后动作后动作先动作先动作 V(S)P1:

19、P2:例子：司机例子：司机-乘客问题：乘客问题：VAR s1,s2: semaphore; (initial value 0)司机活动：司机活动： 乘客活动：乘客活动： Repeat Repeat P(S1) 上上 车车 启动车辆启动车辆 投投 币币 正常行驶正常行驶 V(S1) 到站停车到站停车 乘乘 车车 V(S2) P(S2) 下下 车车 Until false Until false1. 生产者消费者问题2. 读者写者问题预备知识：组合资源：若干相对独立的资源构成的资源集合，其中每个相对独立的资源称为子资源。同种组合资源：相同类型子资源构成的组合资源。管理：Var S:semaphor

20、e; (初值=子资源个数）例子：2台打印机 Var S:semaphore; S.value=2; 申请：P（S）； 释放：V（S）；2 210-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. 0 1 k-1箱子，容量箱子，容量k B:Array0.k-1Of item生产者生产者消费者消费者生产物品生产物品放入放入B中中从从B中取物品中取物品消费之消费之10K-1in(in+1)mod kout(out+1)mod k生产者活动生产者活动： 消费者活

21、动消费者活动： do do 加工一件物品加工一件物品 箱中取一物品箱中取一物品 物品放入箱中物品放入箱中 消耗这件物品消耗这件物品 while(1) while(1)资源：箱子（同种组合）资源：箱子（同种组合） 资源：物品（同种组合）资源：物品（同种组合）Var S1:semaphore; Var S2:semaphore; S1.value=k; S2.value=0;放前：放前：P（S1） 取前：取前：P（S2）放后：放后：V（S2） 取后：取后：V（S1）生产者活动生产者活动： 消费者活动消费者活动： Repeat Repeat 加工一件物品加工一件物品 P(S2) P(S1) 箱中取一

22、物品箱中取一物品 物品放入箱中物品放入箱中 V(S1) V(S2) 消耗这件物品消耗这件物品 Until false Until false对对B和和in,out的互斥的互斥：Var mutex:semaphore; (mutex.value=1)生产者活动：生产者活动： 消费者活动：消费者活动： Repeat Repeat 加工一件物品加工一件物品 P(S2) P(S1) P(mutex) P(mutex) 箱中取一物品箱中取一物品 物品放入箱中物品放入箱中 V(mutex) V(mutex) V(S1) V(S2) 消耗这件物品消耗这件物品 Until false Until falseP

23、rogram producers_consumers;Var B:Array0,k-1Of item; S1,S2,mutex:semaphore; in,out:0.k-1;Procedure producer cycle produce a product P(S1); P(mutex); Bin:=product; in:=(in+1)mod k; V(mutex); V(S2) endProcedure consumer cycle P(s2); P(mutex); x:=Bout; out:=(out+1)mod k; V(mutex); V(S1); consume x; end;

24、Begin S1.value:=k; S2.value:=0; mutex.value:=1; in:=0; out:=0; Cobegin P1: producer; , Pm: producer; C1: consumer; , Cn: consumer; Coend;End.生产者和消费者：不操作生产者和消费者：不操作B的相同分量的相同分量生产者的共享变量： Bin， in消费者的共享变量： Bout，outin=out: 满或空,Var mutex1,mutex2:semaphore; (init 1)生产者活动：生产者活动： 消费者活动：消费者活动： Repeat Repeat 加工

25、一件物品加工一件物品 P(S2) P(S1) P(mutex2) P(mutex1) 箱中取一物品箱中取一物品 物品放入箱中物品放入箱中 V(mutex2) V(mutex1) V(S1) V(S2) 消耗这件物品消耗这件物品 Until false Until falseP. T. Courtois 1971Communication of the ACM, Vol.14, 667-669.ACM: Association for Computing Machinery解法1：写者可能饿死解法2：写者优先Problem Statement: 一组公共数据DB R1 Rm W1 . Wn要求：

26、（1）R-R可以同时 （2）R-W不可同时 （3）W-W不可同时accessingVar r_w_w:semaphore; (initial value: 1)Reader： Writer: P（r_w_w); P(r_w_w) 读操作 写操作 V（r_w_w); V（r_w_w)分析：（1）写者活动正确；（2）R-R不能同时。改进：最先进入的R执行P；最后离开的R执行V；Var read_count:integer; (initial value is 0)Reader: read_count:=read_count+1; If read_count=1 Then P(r_w_w); 读操作

27、 read_count:=read_count-1; If read_count=0 Then V(r_w_w);问题：对Read_count操作的互斥问题。Var mutex:semaphore; (initial value is 1) Reader: P(mutex); read_count:=read_count+1; If read_count=1 Then P(r_w_w); V(mutex); 读操作 P(mutex); read_count:=read_count-1; If read_count=0 Then V(r_w_w); V(mutex); 读者等待在何处？ 读者如何

28、被唤醒？Program readers_writers;Var r_w_w: semaphore; mutex:semaphore; read_count: integer;procedure writer;begin P(r_w_w); write ops V(r_w_w)end;Procedure reader;begin P(mutex); read_count:=read_count+1; If read_count=1 Then P(r_w_w); V(mutex); read ops P(mutex); read_count:=read_count-1; If read_count

29、=0 Then V(r_w_w); V(mutex);end;begin read_count:=0; r_w_w.value:=1; mutex.value:=1; cobegin r1: reader; ; rm: reader; w1: writer; ,; wn: writer coendend.问题问题：读者源源不断，：读者源源不断，read_count不归不归0，写者，写者会被饿死。会被饿死。策略策略：一旦有写者等待，新到达读者等待，正在：一旦有写者等待，新到达读者等待，正在读的读者都结束后，写者进入。读的读者都结束后，写者进入。 Further improvement is le

30、ft to interested students.l背景PV操作低级，容易用错l条件临界区形式region V when B do Sl执行S条件没有其它进程处于与V相关的条件临界区中进入S时B为truel实现互斥region v when true do slCCR与PV操作的等价性(证明从略）用CCR可以实现PV操作用PV操作可以实现CCRlPV操作： 分散式同步机制：共享变量操作，PV操作，分散在整个系统中或各个进程中。缺点：l可读性差；l正确性不易保证；l不易修改。优点：l高效，灵活。l管程：集中式同步工具：共享变量及其所有相关操作集中在一个摸块中。优点：l可读性好；l正确性易于保证

31、；l易于修改。缺点：l不甚灵活，效率略低。l70年代初, ByE.W.Dijkstra, C.A.R.Hoare, P.B.Hansen.l背景: 结构化程序设计与软件工程l基于管程的语言Concurrent Pascal (Hansen)Modula (With)MesaMod*Concurrent EuclidXCYJava: synchronized methodl构造操作系统的PCM方法P：processC：classM：monitorType monitor_name=MONITOR 共享变量说明 define 本管程内定义，本管程外使用的子程序名表； use 本管程外定义，本管程内

32、使用的子程序名表；Procedure 过程名（形参表）； 局部变量说明 Begin 语句序列 End; Function 函数名（形参表）:返回值类型； 局部变量说明 Begin 语句序列 End; .Begin 共享变量初始化语句序列 End;语言特点语言特点： (1) 模块化; (2) 抽象数据类型; (3) 信息掩蔽.l管程的共享变量在管程外部不可见，外部只能通过调用管程中的外部子程序访问共享变量；l为保证对共享变量操作的数据完整性，规定管程互斥进入；l管程内有等待/唤醒机制，等待时释放管程的互斥权，唤醒时（P唤醒Q）：P等待，Q继续，直到Q退出或等待；(Hoare)Q等待，P继续，直到

33、P退出或等待；(Java)唤醒是管程中可执行的最后一个操作。（Hansen)l入口等待队列：每个管程变量一个，用于排队进入；l紧急等待队列：每个管程变量一个，用于唤醒等待；l内部等待队列：var c: condition; 可根据需要定义多个，用于设置等待条件。PCBPCBc1PCBPCBc2PCBPCBPCBPCB入口队列紧急队列Monitorl进入管程：申请管程互斥权。l离开管程：如紧急等待队列非空，唤醒第一个等待者；否则开放管程。lVar c:condition;lwait(c):如紧急队列非空，唤醒第一个等待者，否则释放管程互斥权;执行此操作的进程（线程）进入c链尾。lsignal(c):如c链空，相当空操作。否则唤醒第一个，执行此操作的进程（线程）进入紧急队列的队尾。l读者/写者问题（写优先） 写者优先写者优先Type reaers_writers = Monitor; Var rq,wq: condition; reading_count,write_count:integer; De