操作系统Chapter04-1(new)

1、每课一句每课一句Punctuality: Showing esteem for others by Punctuality: Showing esteem for others by doing the right thing at the right time.doing the right thing at the right time.-Character First-Character First守时守时：在正确的时间做正确的事情，在正确的时间做正确的事情，表明对别人的尊重。表明对别人的尊重。品格第一品格第一Be the change you want to see in the wo

2、rld.Be the change you want to see in the world.如果你希望看到世界改变，那么第一如果你希望看到世界改变，那么第一个必须改变的就是你自己。个必须改变的就是你自己。-甘地甘地计算机操作系统计算机操作系统集美大学精品课程建设第四章第四章 互斥、同步与通讯互斥、同步与通讯MutualMutual Exclusion, Synchroni- Exclusion, Synchroni- zation and Communicationzation and Communication本章内容本章内容4.1 并发进程并发进程(concurrent processe

3、s)14.2 进程互斥进程互斥(mutual exclusion)2 4.3 进程同步进程同步(synchronization)34.4 进程高级通讯进程高级通讯(communication)4学习指导学习指导u互斥与同步是操作系统与并发程序设计的核心问互斥与同步是操作系统与并发程序设计的核心问题，为此操作系统必须提供用于实现同步的机制。题，为此操作系统必须提供用于实现同步的机制。从本质上来说，同步工具就是能用于进程（线程）从本质上来说，同步工具就是能用于进程（线程）等待或唤醒的机制，目前实现的同步机制各有特等待或唤醒的机制，目前实现的同步机制各有特点。学习这一部分不仅需要确切地理解并牢固地点

4、。学习这一部分不仅需要确切地理解并牢固地记住各种同步机制的定义，更重要的是学会使用记住各种同步机制的定义，更重要的是学会使用各种同步机制去解决实际同步问题。各种同步机制去解决实际同步问题。u本章是学习计算机操作系统中的重点之一本章是学习计算机操作系统中的重点之一; ;也是也是本课程的难点。不确定性和并发执行是操作系统本课程的难点。不确定性和并发执行是操作系统的特征：的特征：n进程（线程）由于运行顺序的不确定；n进程（线程）执行的开始时间的不确定；n从而可能导致执行结果的不确定；重点：重点：u什么是与时间有关的错误；什么是与时间有关的错误；u临界区的概念；临界区的概念；u什么是进程互斥、及其实现

5、；什么是进程互斥、及其实现；u什么是进程同步、及其实现；什么是进程同步、及其实现；uPV操作的概念及其实现；操作的概念及其实现；u用用PV操作解决经典问题；操作解决经典问题；u管程的概念及其原理管程的概念及其原理u会合的概念会合的概念难点：难点：u临界区的概念临界区的概念u软件互斥算法软件互斥算法uPV操作操作u用用PV操作解决经典问题操作解决经典问题u管程管程4.1 并发进程并发进程u前驱图前驱图前驱图是一个有向无环图。图中每个结点表示一个语前驱图是一个有向无环图。图中每个结点表示一个语句、或一个计算步骤、或一个进程。结点间的有向句、或一个计算步骤、或一个进程。结点间的有向边边“”表示偏序或

6、前驱关系，表示偏序或前驱关系，=(Pi,Pj)|Pi必须在必须在Pj启动之前已经完成启动之前已经完成。(Pi,Pj)可记成可记成PiPiPj,Pj,称称PiPi是是PjPj的前驱的前驱,Pj,Pj是是PiPi的后继的后继。P4P2P3P1P5P6P7P84.1 并发进程并发进程u4.1.1 顺序性与并发性顺序性与并发性n顺序性顺序性n内部顺序性：内部顺序性： P1: P2:n外部顺序性：外部顺序性：或者或者特征特征:1)顺序性：一条指令执行完再执行下一条指令；顺序性：一条指令执行完再执行下一条指令；2)封闭性：执行时不受外界因素影响；封闭性：执行时不受外界因素影响；3)可再现性：多次执行结果相

7、同；可再现性：多次执行结果相同；a1a2a3b1b2b3a1a2a3b1b2b3b1b2b3a1a2a34.1.1 顺序性与并发性顺序性与并发性n并发性并发性n内部并发性：内部并发性： P1: P2:n外部并发性：外部并发性：特征：特征：1）交叉性）交叉性(间断性间断性)：产生交叉执行；：产生交叉执行；2）非封闭性：进程间相互影响；）非封闭性：进程间相互影响；3）不可再现性：不同的交叉产生不同的结果；）不可再现性：不同的交叉产生不同的结果；a1a2a3b1b2b3b1b2b3a1a2a3a1a2a3b1b2b3程序并发执行条件程序并发执行条件u读集读集:程序程序p1在执行期间所读取变量的集合在

8、执行期间所读取变量的集合R(p1)=a1,a2,anu写集：程序写集：程序p1在执行期间所修改变量的集合在执行期间所修改变量的集合W(p1)=b1,b2,bn例如程序例如程序p： x=a-b; y=c-5;其读集其读集R(p)=a,b,c,W(p)=x,y 程序并发执行条件程序并发执行条件Bernstein条件：条件：程序p1和p2满足下面条件，则能够保持可再现，因而可以并发执行例如：例如：S1: a=x-y;S2: b=z+1;S3: v=a+b;S4: w=v+1;请问S1和S2是否可并发执行？S3和S4是否可以并发执行？S2和S3是否可以并发执行？122112()()()()()()Rp

9、WpRpWpWpWp 并发程序表示：并发程序表示：u并发语句表示：并发语句表示：cobegin s1;s2;s3;sn coend;u并行语句表示：并行语句表示：parbegin s1;s2;s3;sn parend;表示同时启动进程（线程）表示同时启动进程（线程）s1、s2、s3、sn 等。等。并发进程给操作系统带来许多问题，包括互斥、并发进程给操作系统带来许多问题，包括互斥、死锁、饥饿等。死锁、饥饿等。4.1.2 与时间有关的错误与时间有关的错误例：图书借阅系统例：图书借阅系统 （x: :某种某种书册数，设当前书册数，设当前x=1.=1.）终端终端1： 终端终端2：CYCLE CYCLE

10、等待借书者；等待借书者； 等待借书者；等待借书者； IF x=1 Then IF x=1 Then Begin Begin x:=x-1; x:=x-1; 借书借书 借书借书 End End Else 无书无书 Else 无书无书 End End 1234上述可能发生错误，也可能不发生错误，完全取决于各个进程上述可能发生错误，也可能不发生错误，完全取决于各个进程的推进速度。而推进速度是时间的函数，故称此类错误为与时的推进速度。而推进速度是时间的函数，故称此类错误为与时间有关的错误。间有关的错误。4.1.2 与时间有关的错误与时间有关的错误(Cont.)u错误原因之错误原因之1： 进程执行交叉进

11、程执行交叉(interleave);u错误原因之错误原因之2： 涉及公共变量涉及公共变量(x)。uRemarks: 某些交叉结果不正确某些交叉结果不正确; 必须去掉导致不正确结果的交叉。必须去掉导致不正确结果的交叉。4.2 进程互斥进程互斥(mutual exclusion)4.2.1 共享变量与临界区共享变量与临界区14.2.2 临界区域与进程互斥临界区域与进程互斥2 4.2.3 进程互斥的实现进程互斥的实现34.2.4 多处理机环境下的互斥多处理机环境下的互斥44.2.1 共享变量与临界区域共享变量与临界区域u共享变量（共享变量（shared variable）n多个进程多个进程(或线程或

12、线程)都需要访问的变量。都需要访问的变量。n临界资源临界资源u临界区域（临界区域（critical region/sectionCR/CS）n访问共享变量的程序段访问共享变量的程序段。 一组公共变量一组公共变量CR1CR2CRn.In concurrent programming a critical section is a piece of code that accesses a shared resource (data structure or device) that must not be concurrently accessed by more than one thread

13、 of execution.临界区表示临界区表示u共享变量共享变量: shared u临界区域临界区域: region do 语句语句u例子：例子：shared B:array0,.,n-1of integer;region B do region B do begin begin (访问B) .（访问B）. end; end;4.2.2 临界区域与进程互斥临界区域与进程互斥u定义：定义：多个进程不能同时进入关于同一组共享多个进程不能同时进入关于同一组共享变量的临界区域，否则可能发生与时间有关的变量的临界区域，否则可能发生与时间有关的错误，这种现象称为错误，这种现象称为进程互斥进程互斥u二层涵

14、义：二层涵义： （1）任何时刻最多只能有一个进程处于同一组共享变量的相同的临界区域； （2）任何时刻最多只能有一个进程处于同一组共享变量的不同的临界区域。uRemarks: 互斥是相对于公共变量而言的。嵌套临界区域嵌套临界区域 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;4.2.3 进程互斥的实现进程互斥的实现uMutex FrameworkRepeat crit

15、ical section remainder sectionUntil falseentry sectionexit section进入控制部分进入控制部分退出控制部分退出控制部分在任何一个时刻，只能有一个进程（线程）在临界区中！4.2.3 进程互斥的实现进程互斥的实现uRequirements:nmutual exclusion: 一次只允许一个进程活动在关于一次只允许一个进程活动在关于同一组公共变量的临界区中同一组公共变量的临界区中correctness；nprogress: 临界区空闲时，多个竞争者在有限时间内临界区空闲时，多个竞争者在有限时间内确定下一个进入者确定下一个进入者；nbou

16、nded waiting: 一个想要进入临界区的进程在等一个想要进入临界区的进程在等待有限个进程进入并离开临界区后获得进入临界区的待有限个进程进入并离开临界区后获得进入临界区的机会机会 fairness 。4.2.3 进程互斥的实现进程互斥的实现u临界资源管理应满足的调度原则：临界资源管理应满足的调度原则：n空闲让进空闲让进：所有临界区域空闲时，欲进入该临界区：所有临界区域空闲时，欲进入该临界区的进程可以立即进入；的进程可以立即进入；n忙则等待忙则等待：当一部分临界区域被占用，欲进入该临：当一部分临界区域被占用，欲进入该临界区的进程应等待；界区的进程应等待；n有限等待有限等待：一个进程离开临界

17、区域，应容许等待该：一个进程离开临界区域，应容许等待该区域的一个进程进入。区域的一个进程进入。n让权等待让权等待：当进程不能进入自己的临界区时，应立：当进程不能进入自己的临界区时，应立即释放处理机，以免进程陷入即释放处理机，以免进程陷入“忙等忙等”。 进程互斥的软件实现进程互斥的软件实现u完全用程序实现，不需特殊硬件指令支持。完全用程序实现，不需特殊硬件指令支持。u可用于单可用于单CPU和多和多CPU环境中。环境中。u有忙式等待问题。有忙式等待问题。Busy waiting“运行运行”或或“就绪就绪”Dekker互斥算法互斥算法u荷兰数学家荷兰数学家T. Dekker给出的软件互

18、斥算法。给出的软件互斥算法。定义：定义：int flag2;/初值为0int turn;/初值为0或1P0: do flag0=1; while flag1 do flag0=0; while turn=1 do skip; flag0=1; P1: do flag1=1; while flag0 do flag1=0; while turn=0 do skip; flag1=1; 进入控制部分Dekker互斥算法互斥算法u实现：实现：n互斥性n进展性n有限等待临界区临界区 turn=1; flag0=0; 其余代码；其余代码；while(1);临界区临界区 turn=0; flag1=0;

19、其余代码；其余代码；while(1);退出控制部分Peterson互斥算法互斥算法u1980年年G.L.Peterson给出的软件互斥算法给出的软件互斥算法u定义：定义：int flag2;/初值为0int turn;/初值为0或1P0: do flag0=1; turn=1; while flag1&turn=1 do skip;P1: do flag1=1; turn=0; while flag0&turn=0 do skip;进入控制部分Peterson互斥算法互斥算法u实现：实现：n互斥性n进展性n有限等待临界区 flag0=0; 其余代码；while(1);临界区 f

20、lag1=0; 其余代码；while(1);退出控制部分Lamport面包店算法面包店算法算法思想算法思想：设置一个发号者，按：设置一个发号者，按0,1,2, 发号。想进入发号。想进入临界区的进程抓号，抓到号之后按由小到大的次序依临界区的进程抓号，抓到号之后按由小到大的次序依次进入。次进入。Problem: 两个进程可能抓到相同的号。两个进程可能抓到相同的号。Why? ? 为保证抓到不同的号，需要互斥机制。为保证抓到不同的号，需要互斥机制。Resolution: : 若抓到相同的号，按进程编号依次进入。若抓到相同的号，按进程编号依次进入。Definition: (a,b)(c,d) iff (

21、ac)or(a=c and bd)k=max(a0,a1,，an-1),0in-1,kaiLamport面包店算法面包店算法P0P1P2PiPn-1Lamport面包店算法面包店算法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.

22、While (numberj0)and7. (numberj,j)(numberi,i) Do skip8. Endfor (1)Pi抓到号码=已发的最大号码+1(2)P2抓到1进入临界区(3)P3抓到2进入临界区？Lamport面包店算法面包店算法(Cont.)Pi离开：离开： numberi:=0：变量变量choosing的的作用：作用：P1：抓到：抓到1; P2：抓到：抓到1; 正确次序：正确次序：P1，P2，P3P3：抓到：抓到2; 可能按可能按P2,P3,P1次序进入次序进入?Lamport面包店算法面包店算法(Cont.)uDefine: 不能进入等待状态的等待称为忙式等不能进入等

23、待状态的等待称为忙式等待待(Busy Waiting)。u特征：特征：n进程正在Running或Ready状态；n进程每次运行空耗资源；u阻塞式等待：进程因得不到共享资源将进入阻塞式等待：进程因得不到共享资源将进入阻塞状态，让出阻塞状态，让出CPUBlocked Waiting and Busy Waiting:1)相同点：进程都不具备继续推进的条件；相同点：进程都不具备继续推进的条件；2)不同点：不同点： Blocked waiting 主动放弃主动放弃CPU； Busy Waiting不主动放弃不主动放弃CPU，尽管，尽管CPU可能可能被剥夺；被剥夺；Eisenberg/Mcguire A

24、lgorithmVar 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_cs: 进程进程Pi想进入或已进入临界区想进入或已进入临界区Critical SectionEisenberg/Mcguire算法算法uPi进入进入:uRepeatu flagi:=want_in;u j:=turn;u While ji dou If fla

25、gjidle Then j:=turn /等待进程等待进程j为为idle状态状态u Else j:=(j+1)mod n; /下一个进程下一个进程u flagi:=in_cs;/把本进程标志为把本进程标志为in_cs状态状态u j:=0; u While (jn)and(j=i or flagjin_cs) do u j:=j+1; uUntil (j=n)and(turn=i or flagturn=idle);uturn:=i;P1P2PiPnNotes：1）当前退出临界区的进程把turn赋为i值；2）所有j 到 i 进程均为idle。思考题：为什么需要第二个循环进行检查？思考题：为什么需

26、要第二个循环进行检查？Eisenberg/Mcguire算法算法Pi离开：离开：j:=(turn+1)mod n;While (flagj=idle)do j:=(j+1)mod n;turn:=j;flagi:=idle;CS检测下一个想进入临界区的进程，即flagj=want_in的进程Turn为下一个想进入临界区的进程,允许该进程获得进入的权利把本进程标识为idle进程算法实现算法实现:1)对所有对所有ji, flagj in_cs时时Pi才能进入才能进入CS;2)仅当仅当flagi=in_cs时时,Pi才做上述检测。才做上述检测。3)存在低效的存在低效的“忙式等待忙式等待”。检测到lo

27、ck为false即可进入临界区，同时设lock为true 进程互斥的硬件实现进程互斥的硬件实现1. 硬件提供硬件提供“测试并建立测试并建立 TS”指令指令 int test_and_set(int *target) int temp; temp=*target; *target=1; return(temp); 对一组公共变量，对一组公共变量，int lock=0（初始（初始=false); Pi进入：进入：While(test_and_set(&lock) skip; 临界区临界区 Pi离开：离开：lock=0;思考题：思考题：如果不是原子指令，能如果不是原子指令，能否

28、实现互斥，为什么？否实现互斥，为什么？ 进程互斥的硬件实现进程互斥的硬件实现2. 硬件提供硬件提供“交换交换”指令指令 void swap(int *a,int *b) int temp; temp=*a; *a=*b; *b=temp; 对对一组公共变量：一组公共变量：int lock=0(初始初始=false); 对一个进程空间：对一个进程空间：int key; Pi进入进入：key=1; do swap(&lock,&key) until(key=0); CS Pi离开离开：lock=0;进程互斥的硬件实现进程互斥的硬件实现Remarks：(1

29、) test_and_set指令和指令和swap指令是原子的，不指令是原子的，不可中断的。可中断的。(2) test_and_set实际上是：将内存中一个单元实际上是：将内存中一个单元的内容取出，再送一个新值。的内容取出，再送一个新值。(3) swap实际上是：交换内存两个单元的内容实际上是：交换内存两个单元的内容。(4) 上述算法实现互斥，但不能满足有限等待，算上述算法实现互斥，但不能满足有限等待，算法法4.6(P96)如何实现有限等待？如何实现有限等待？(作业作业)进程互斥的硬件实现进程互斥的硬件实现3. 硬件提供硬件提供“关中断关中断”和和“开中断开中断”指令指令 关中断关

30、中断 Critical Region 开中断开中断Remarks: (1) 开关中断只在单开关中断只在单CPU系统中有效系统中有效;(why?) (2) 影响并发性。影响并发性。 (3) 只能操作系统使用只能操作系统使用,用户进程不能使用用户进程不能使用.4.2.4 多处理机环境下互斥多处理机环境下互斥内存内存Word 1000initial: 0CPU1CPU2Bus1. Read 03. Write 1 2. Read 04. Write 14.2.4 多处理机环境下互斥多处理机环境下互斥TS指令指令，Swap指令指令: first lock the busbus request prot

31、ocol: modern buses have these facilities earlier ones didnt4.2.4 多处理机环境下互斥多处理机环境下互斥b=1;while(b) lock(bus); b = test_and_set(&lock); unlock(bus);lock=0;CR自旋锁自旋锁u忙式等待锁称为自旋锁。忙式等待锁称为自旋锁。u在在SMP系统中，允许多个处理机同时执行目态系统中，允许多个处理机同时执行目态程序，而一次只允许一个处理机执行操作系统程序，而一次只允许一个处理机执行操作系统代码代码利用自旋锁。利用自旋锁。u自旋锁是低效的；自旋锁是低效的；A

32、ssignment #1u 进程切换时需要保存哪些现场信息？请尽量考进程切换时需要保存哪些现场信息？请尽量考虑完全。虑完全。u 进程切换时，现场信息为何不能保存在下降进进程切换时，现场信息为何不能保存在下降进程的系统栈中程的系统栈中, ,而必须传送到而必须传送到PCBPCB中？中？u 算法算法4-6(P96)4-6(P96)和算法和算法4-7(P98)4-7(P98)如何实现有限等如何实现有限等待？待？Assignment #1Consider the following program:var blocked: array0.1of boolean; turn:0.1;procedure P

33、(id:integer);begin repeat blockedid:=true; while turnid do begin while blocked1-id do nothing turn:=id end; blockedid:=false; until falseend;begin blocked0:=false; blocked1:=false; turn:=0; parbegin P(0); P(1) parend;end. This is a software solution to the mutual exclusion problem proposed by Hyman.

34、 Find a counter example to demonstrate that this solution is incorrect. It is interesting to note that even the Communication of the ACM was fooled on this one.4.3 进程同步进程同步(Synchronization)4.3.1 进程同步的概念进程同步的概念例：司机例：司机-售票员问题售票员问题 司机活动：司机活动： 售票员活动：售票员活动： do do 启动车辆启动车辆 关车门关车门 正常行驶正常行驶 售售 票票 到站停车到站停车 开

35、车门开车门 while( (1) ) while( (1) )同步点同步点4.3.1 进程同步的概念进程同步的概念u定义：定义：一组进程，为协调其推进速度，在某些一组进程，为协调其推进速度，在某些关键点处需要相互等待与相互唤醒，进程之间关键点处需要相互等待与相互唤醒，进程之间这种相互制约的关系称为进程同步。这种相互制约的关系称为进程同步。P1:P2:synchronize后操作先操作AB4.3.2 进程同步机制进程同步机制u定义：定义：用于实现进程同步的工具称为同步机制用于实现进程同步的工具称为同步机制或同步设施或同步设施(synchronization mechanism)u同步机制要求：同

36、步机制要求：n描述能力够用描述能力够用;n可实现可实现;n高效高效;n使用方便使用方便.典型同步机制典型同步机制 u信号灯与信号灯与PV操作操作( (semaphore and PV operations) )u管程管程( (monitor) )u会合会合( (rendezvous) )u条件临界区条件临界区( (conditional critical region) )u路径表达式路径表达式( (path expression) )u事件事件( (traditional UNIX) )4.3.3 信号灯与信号灯与PV操作操作E.W.Dijkstra, 1965.艾兹格艾兹格W迪科斯彻迪科斯

37、彻 (Edsger Wybe Dijkstra),1930年年5月月11日日2002年年8月月6日日, 荷兰电脑科学家荷兰电脑科学家 信号灯与信号灯与PV操作的定义操作的定义 typedef struct int value; pointer_to_PCB: queue; semaphore; semaphore s;Remarks:(1) semaphore is pre-defined data type,(2) s can be declared as needed, eg. semaphore s1,s2; 所谓“信号灯”是一个具有非负初值的整型变量，并且有一个队列与它关

38、联。因此定义一个信号灯变量时，要给出它的初值Value和queue指针。信号灯变量信号灯变量S.valueS.queueS.valueS.queuePCBPCBPCBsemaphore S;FIFORemarks: 1）S.queue为指向等待队列首的指针。为指向等待队列首的指针。 2）队列的长度与）队列的长度与S.value的值有关。的值有关。P操作原语操作原语(Primitive)P操作原语：操作原语：void P(semaphore *s) s-value-; if(s-valuequeue);asleep(s-queue):(1) 执行此操作的执行此操作的进程的进程的PCBPCB入入s

39、-queue尾尾(状态改为状态改为等待等待)；(2) 转处理机调度程序。转处理机调度程序。(3)P操作实际为申请资源，如有空闲资源直接进入使用操作实际为申请资源，如有空闲资源直接进入使用，否则排队等待。，否则排队等待。 Primitive: a piece of code un-interruptible什么是操作原语？在在Linux对应对应sem_wait()V操作原语操作原语V操作原语：操作原语：void V(semaphore *s)s-value+; if(s-valuequeue);wakeup(s-queue):1)s-queue链头链头PCB出等待队列，进入就绪出等待队列，进入就

40、绪队列（状态改为就绪）。队列（状态改为就绪）。2)V操作实际上是释放资源，一旦进程释放资源操作实际上是释放资源，一旦进程释放资源，便唤醒一个正在，便唤醒一个正在s-queue中等待的进程。中等待的进程。 在在Linux中中,对应对应sem_post()Linux系统中的系统中的semaphore机制机制u定义信号灯变量：定义信号灯变量：sem_t 变量名列表；变量名列表；其预定义结构在其预定义结构在semaphore.h中；中；如：如：sem_t driver;u信号灯初始化：信号灯初始化：sem_init(sem_t *,P1,P2)如：如：sem_init(&driver,0,0)

41、;P1进程共享（进程共享（!=0）或单个进程中的线程使用（）或单个进程中的线程使用（=0）。）。P2信号量的初始值；信号量的初始值；Linux系统中的系统中的semaphore机制机制usem_wait(sem_t *): 信号灯的信号灯的P操作；操作；usem_post(sem_t*): 信号灯的信号灯的V操作；操作；u注意：如果是多个进程使用信号灯互斥或同步注意：如果是多个进程使用信号灯互斥或同步，在信号灯初始化时的参数，在信号灯初始化时的参数p1要求非要求非0，且最，且最好在子进程创建之前。好在子进程创建之前。Windows信号量对象信号量对象uCreateSemaphore: 创建信号

42、灯对象；创建信号灯对象；uOpenSemaphore: 打开信号灯对象；打开信号灯对象；u等待信号灯对象：等待信号灯对象：nWaitForSingleObject: 在指定的时间内等待指定的对象为可用；nWaitForMultipleObjects:在指定的时间内等待指定的对象为可用；Windows互斥对象互斥对象uCreateMutex: 创建一个互斥对象，供线程创建一个互斥对象，供线程互斥使用；互斥使用；uReleaseMutex: 释放一个互斥对象。释放一个互斥对象。u详细请见：详细请见：“22Windows环环境下实验境下实验”中的详细说明。中的详细说

43、明。规定和结论规定和结论u对于信号灯变量的规定：对于信号灯变量的规定：n必须置一次初值，只能置一次初值，初值必须置一次初值，只能置一次初值，初值=0;n只能执行只能执行P操作和操作和V操作，所有其它操作非法。操作，所有其它操作非法。u几个有用的结论：几个有用的结论：n当当s-value=0时，时，s.queue为空；为空；n当当s-valuevalue初=1时，可以实现进程互斥；时，可以实现进程互斥；n当当s-value初=0时，可以实现进程同步。时，可以实现进程同步。信号量与信号量与PV操作的实现操作的实现void P(semaphore *s) disable interrupt; s-v

44、alue; if(s-valuequeue; enable interrupt; goto CPU dispatcher; else enable interrupt; void V(semaphore *s) disable interrupt; s-value+; if(s-valuequeue; place it on ready queue; enable interrupt; 信号量与信号量与PV操作的实现操作的实现void P(semaphore *s) while(TS(s-flag); s-value; if(s-valuequeue; s-flag=0; goto CPU d

45、ispatcher; else s-flag=0; void V(semaphore *s) while(TS(s-flag); s-value+; if(s-valuequeue; place it on ready queue; s-flag=0; 用信号灯实现进程互斥用信号灯实现进程互斥semaphore mutex; (初值=1） shared int x,y,z; CR1 CR2 CRn用信号灯实现进程互斥用信号灯实现进程互斥semaphore mutex; (初值=1） shared int x,y,z:;P(mutex) P(mutex) P(mutex) CR1 CR2 CRn

46、V(mutex) V(mutex) V(mutex)mutex-value初始为初始为1实现临界资源的互斥访问。实现临界资源的互斥访问。互斥例子：借书系统互斥例子：借书系统(revisited)semaphore mutex; (initial value is 1)终端终端1： 终端终端2：do do 等待借书者等待借书者； 等待借书者等待借书者； P(mutex) P(mutex) if(x=1) if(x=1) x=x-1; x=x-1; V(mutex) V(mutex) 借书借书 借书借书 else V(mutex);/无书无书; else V(mutex);/无书无书; while

47、(1);while(1);用信号灯实现进程同步用信号灯实现进程同步 P(S)后动作后动作先动作先动作 V(S)P1:P2:同步点同步点用信号灯实现进程同步用信号灯实现进程同步例子：司机例子：司机-售票员问题：售票员问题：semaphore s1,s2; (initial value 0)司机活动：司机活动： 售票员活动：售票员活动： do do P(S1) 关车门关车门 启动车辆启动车辆 V(S1) 正常行驶正常行驶 售售 票票 到站停车到站停车 P(S2) V(S2) 开车门开车门 while(1); while(1);Classical synchronization problems1.

48、 Producers and consumers problem2. Readers and writers problem3. Dining philosophers problem4. Cigarette smokers problem5. Sleepy barbers problem ( or Barbershop problem)etc. 例例1. 生产者生产者/消费者问题消费者问题u预备知识：预备知识：u组合资源组合资源：若干相对独立的资源构成的资源集合，其：若干相对独立的资源构成的资源集合，其中每个相对独立的资源称为子资源。中每个相对独立的资源称为子资源。u同种组合资源同种组合资源

49、：相同类型子资源构成的组合资源。：相同类型子资源构成的组合资源。u管理：管理：semaphore S; (S.value=子资源个数）子资源个数）u例子：例子：2台打印机台打印机semaphore S; 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.例例1. 生产者生产者/消费者问题消费者问题 0 1 k-1箱子，

50、容量箱子，容量kitemtype Bk;生产者生产者消费者消费者生产物品生产物品放入放入B中中B中取物品中取物品消费之消费之有界缓冲区问题有界缓冲区问题(Bounded Buffers Problem)环形缓冲区环形缓冲区0in(in+1)mod kout(out+1)mod kS1.value 表示目表示目前有多少空位置前有多少空位置可以存放物品。可以存放物品。S2.value表示目前有表示目前有多少物品可以供消多少物品可以供消费。费。有限缓冲区问题有限缓冲区问题!1K-1in当前放物品的位置；当前放物品的位置；out当前取物品的位置；当前取物品的位置；问题分析问题分析(analyzing)

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

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

53、物品; while(1); while(1);算法描述算法描述 itemtype Bn;/shared variables semaphore S1,S2,mutex; int in,out;/shared variablesvoid producer( ) while(1) produceitem(&item); P(S1); P(mutex); Bin:= item; in:=(in+1) % k; V(mutex); V(S2); void consumer( ) while(1) P(s2); P(mutex); x:=Bout; out:=(out+1) % k; V(mut

54、ex); V(S1); consume x; 算法描述算法描述Void main() S1.value:=k; S2.value:=0; mutex.value:=1; in:=0; out:=0; fork(producer,0); ,fork(producer,m-1); fork(consumer,0); , fork(consumer,n-1);问题问题:多个生产者同时操作多个生产者同时操作Bin; 多个消费者同时操作多个消费者同时操作Bout;并发性提高策略并发性提高策略生产者和消费者：不操作生产者和消费者：不操作B的相同分量的相同分量生产者的共享变量：生产者的共享变量： Bin，

55、in消费者的共享变量：消费者的共享变量： Bout，outin=out: 满或空满或空,semaphore mutex1,mutex2; (init 1)并发性提高策略并发性提高策略u放物品、取物品各定义一个信号灯放物品、取物品各定义一个信号灯semaphore mutex1,mutex2;(init 1)生产者活动：生产者活动： 消费者活动：消费者活动： do do 加工一件物品加工一件物品 P(S2) P(S1) P(mutex2) P(mutex1) 箱中取一物品箱中取一物品 物品放入箱中物品放入箱中 V(mutex2) V(mutex1) (S1) V(S2) 消耗这件物品消耗这件物品

56、 while(1); while(1); P(mutex2) P(mutex1) V(mutex2) V(mutex1) 改进生产者改进生产者消费者程序消费者程序(算法描述算法描述)void producer( ) while(1) produceitem(&item); P(S1); P(mutex1); Bin:= item; in:=(in+1) % k; V(mutex1); V(S2) void consumer( ) while(1) P(s2); P(mutex2); x:=Bout; out:=(out+1) % k; V(mutex2); V(S1); consume

57、 x; itemtype Bk; semaphore S1,S2,mutex1,mutex2;(k,0,1,1) int in,out;例例2. 读者读者/写者问题写者问题uReaders and Writers ProblemProblem Statement: 一组公共数据一组公共数据DB R1 Rm W1 . Wn要求要求：（：（1）R-R可以同时可以同时 （2）R-W不可同时不可同时 （3）W-W不可同时不可同时accessing例例2. 读者读者/写者问题写者问题uP. T. Courtois(P. T.库尔托伊斯库尔托伊斯) 1971nCommunication of the AC

58、M, Vol.14, 667-669.nACM: Association for Computing Machineryu解法解法1：写者可能饿死：写者可能饿死u解法解法2：写者优先：写者优先Solution1: 不考虑不考虑R-R不互斥不互斥semaphore r_w_w; (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；最后离开的；最后离开的

59、R执行执行V；Solution2: 考虑考虑R-R不互斥不互斥semaphore r_w_w; (initial value is 1)int read_count; (initial value is 0)Reader: read_count+; if( read_count=1) P(r_w_w); 读操作读操作 read_count-; if(read_count=0) V(r_w_w);问题：对问题：对read_count操作的互斥问题。操作的互斥问题。read_count对于对于reader是共享变量！是共享变量！Solution3: 正确解法正确解法Reader: P(mutex)

60、; read_count+; if(read_count=1) P(r_w_w); V(mutex); 读操作读操作 P(mutex); read_count-; if(read_count=0) V(r_w_w); V(mutex); 读者等待在何处？ 读者如何被唤醒？Writer: P(r_w_w); 写操作写操作 V(r_w_w);semaphore r_w_w; (initial value is 1)int read_count; (initial value is 0)semaphore mutex; (initial value is 1)算法描述算法描述/readers_writers program; semaphore r_w_w; se