吉林大学操作系统课件 第四章 互斥同步及通讯1

1、第四章第四章 互斥、同步与通讯互斥、同步与通讯n并发进程并发进程(concurrent processes)n进程互斥进程互斥(mutual exclusion)n进程同步进程同步(synchronization)n进程高级通讯进程高级通讯(communication)4.1并发进程并发进程n4.1.1前趋图的定义前趋图的定义n前趋图（前趋图（precedence graph）n有向无环图，图中每个结点表示一个语句、一个计算步骤、有向无环图，图中每个结点表示一个语句、一个计算步骤、或一个进程。或一个进程。n结点间的有向边表示偏序或前趋（结点间的有向边表示偏序或前趋（precedence rel

2、ation)关系关系“” 。n=（Pi，Pj）| Pj启动之前启动之前Pi必须已经完成必须已经完成。n（Pi，Pj）可记作可记作PiPj, 称称Pi是是Pj的前趋，的前趋，Pj是是Pi的的后继。后继。n在前趋图中，没有前趋的结点称为初始结点，没有后继的结在前趋图中，没有前趋的结点称为初始结点，没有后继的结点称为终止结点。点称为终止结点。n每个结点可以有一个权重每个结点可以有一个权重(weight)，它可以表示该结点所，它可以表示该结点所包含的程序量或计算时间。包含的程序量或计算时间。4.1并发进程并发进程n前趋图的例子前趋图的例子nP1P2，P1P3，P1P4，P2P5，P3P5，P4P5，P

3、4P6，P5P7，P6P714326574.1.2顺序程序及其特性顺序程序及其特性n4.1.2.1 程序的顺序执行程序的顺序执行n(1)内部顺序性：对于一个进程来说，它内部顺序性：对于一个进程来说，它的所有指令是按序执行的。的所有指令是按序执行的。nS1：a:=x+ynS2：b:=a-znS3：c:=a+bnS4：d:=c+5S1S2S3S44.1.2顺序程序及其特性顺序程序及其特性n(2)外部顺序性：对于多个进程来说，所外部顺序性：对于多个进程来说，所有进程的活动是依次执行的。有进程的活动是依次执行的。n例例: 输入输入(I)、计算、计算(C)、打印、打印(P)三个活动三个活动构成的进程，每

4、个进程的内部活动是顺序的，构成的进程，每个进程的内部活动是顺序的，即即IiCiPi，多个进程的活动也是顺序的。，多个进程的活动也是顺序的。I1C1P1I2C2P24.1.2顺序程序及其特性顺序程序及其特性n4.1.2.2顺序程序特性顺序程序特性:n (1)连续性连续性: 指令逐条执行指令逐条执行n (2)封闭性封闭性: 不受其它程序及外界因素影响不受其它程序及外界因素影响n (3)可再现性可再现性: 结果与推进速度无关结果与推进速度无关4.1.3 并发程序及其特性并发程序及其特性n4.1.3.1 程序的并发执行程序的并发执行n(1)内部并发性内部并发性: 指一个程序内部指一个程序内部的并发性。

5、例：的并发性。例：nS1：a:=x+2；nS2：b:=y+4；nS3：c:=a+b；nS4：d:=c+6；nS5：e:=c-d；214354.1.3 并发程序及其特性并发程序及其特性n4.1.3.1 程序的并发执行程序的并发执行n(2)外部并发性外部并发性: 指多个程序之间的并发性。指多个程序之间的并发性。I1I2I3I4C1C2C3C4P1P2P3P44.1.3 并发程序及其特性并发程序及其特性n4.1.3.2 并发程序的特性并发程序的特性n（1）间断性：程序交叉执行。）间断性：程序交叉执行。n（2）非封闭性：一个进程的运行环境可能）非封闭性：一个进程的运行环境可能被其它进程所改变，从而相互

6、影响。被其它进程所改变，从而相互影响。n（3）不可再现性：由于交叉的随机性，并）不可再现性：由于交叉的随机性，并发程序的多次执行可能对应不同的交叉，因发程序的多次执行可能对应不同的交叉，因而不能期望重新运行的程序能够再现上次运而不能期望重新运行的程序能够再现上次运行的结果。行的结果。4.1.3 并发程序及其特性并发程序及其特性n不可再现性的例子不可再现性的例子n进程进程P： 进程进程Q：nA1: N:=0； B1: PRINT（N）；）；nA2: N:=N+1； B2: N:=0；nA3: GOTO A2； B3: GOTO B1；n此例中进程此例中进程P累计计数，进程累计计数，进程Q将累计的

7、结果打印出来。将累计的结果打印出来。希望打印出的数是累计数的和。希望打印出的数是累计数的和。n两个进程并发执行时有许多可能的交叉两个进程并发执行时有许多可能的交叉:n如进程如进程P循环循环5次进程次进程Q循环循环1次，然后进程次，然后进程P又循环又循环3次进程次进程Q循环循环1次，则输出结果是次，则输出结果是5，3；n如进程如进程P循环循环2次进程次进程Q循环循环1次，然后进程次，然后进程P又循环又循环6次进程次进程Q循环循环1次，则输出结果是次，则输出结果是2，6。两次执行结果完全不同。两次执行结果完全不同。n进程进程Q执行完执行完B1后被中断，进程后被中断，进程P对对N执行加执行加1操作，

8、然后进操作，然后进程程Q执行执行B2，在这种情况下进程，在这种情况下进程P的累计数将被丢失。的累计数将被丢失。4.1.4 程序并发执行的条件程序并发执行的条件n 在失去封闭性的条件下，保持可再现性。在失去封闭性的条件下，保持可再现性。nR(pi)=a1,a2,am表示程序表示程序pi在执行期间所在执行期间所需读取的所有变量的集合，称为需读取的所有变量的集合，称为“读集读集”；nW(pi)=b1,b2,bn表示程序表示程序pi在执行期间所在执行期间所需改变的所有变量的集合，称为需改变的所有变量的集合，称为“写集写集”。n若有两条语句若有两条语句c=a+b和和v=c-1，则它们的，则它们的“读集读

9、集”和和“写集写集”分别为：分别为：nR(c:=a+b)=a,b，R(v:=c-1)=cnW(c:=a+b)=c，W(v:=c-1)=v4.1.4 程序并发执行的条件程序并发执行的条件n若两个程序若两个程序p1，p2满足如下条件，则能满足如下条件，则能够保持可再现性，因而可以并发执行。够保持可再现性，因而可以并发执行。该条件是该条件是1966年首先由年首先由Bernstein提出提出的，称为的，称为Bernstein条件。条件。n R(p1)W(p2)R(p2)W(p1)W(p1)W(p2)=4.1.4 程序并发执行的条件程序并发执行的条件n例如，有如下四条语句：例如，有如下四条语句：n S1

10、: a:=x+yn S2: b:=z+1n S3: c:=a-bn S4: w:=c+1nR(S1)=x,y，R(S2)=z，R(S3)=a,b，R(S4)=cnW(S1)=a，W(S2)=b，W(S3)=c，W(S4)=wn可见，可见，R(S1)W(S2)R(S2)W(S1)W(S1)W(S2)=，因而，因而S1和和S2可以并发执行；而可以并发执行；而S1 和和S3不能并发不能并发执行，因为执行，因为W(S1)R(S3)=a；S2和和S3也不能并也不能并发执行，因为发执行，因为W(S2) R(S3)=b；同样，；同样，S3和和S4不能并发执行，因为不能并发执行，因为W(S3)R(S4)=c。

11、4.1.5 并发程序的表示并发程序的表示ncobegin (concurrent begin)coend (concurrent end)n即S1、S2、Sn为n条语句，若它们可以并发执行，则用并发语句表示为： cobegin S1、S2；Sn coend；nparbeginparendn即S1、S2、Sn为n条语句，若它们可以并发执行，则用并发语句表示为： parbegin S1、S2；Sn parend；n遇到上述语句时，操作系统同时创建n个进程或线程，分别执行S1、S2、Sn这n条语句，当它们都结束时并发或并行语句结束。4.1.6 与时间有关的错误与时间有关的错误例：图书借阅系统例：图书

12、借阅系统 （x: :某种某种书册数，设当前书册数，设当前x=1.=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关于就绪队列的整队问题关于就绪队列的整队问题 设有A,B,C,D四个就绪进程,优先级依次为2,10,30,35,分析插队过程中出现的情况. 关于就绪队列的整队问题关于就绪队列的整队问题关于就绪队列的整队问题关于就绪队列的整

13、队问题分析(1)若有E进程,优先数为25处于就绪状态,则要求加入就绪队列,调整队子程序执行,该程序判断E应加入B,C之间,则执行 R:=C; B:=E ; E:=R(2)若在 时进程F因完成I/O由等待状态变为就绪,其优先级为15,整队子程序被中断,转入执行中服程序,则出现丢失一个进程 R:=C; B:=F; F:=R结论:该错误因共享就绪队列引起,对就绪队列操作不当,也是与时间相关的错误导致结果不唯一.两进程申请两个独占性资源两进程申请两个独占性资源n设有两个进程P1,P2,系统中有两类独占性资源如打印机和输入机,两进程的活动为: P1 P2 申请打印机 申请输入机 申请输入机 申请打印机

14、执行 执行 退出 退出两进程申请两个独占性资源两进程申请两个独占性资源n分析: (1)若P1推进到,P2推进,则P1,P2均等待对方释放资源形成永久等待.该错误也与推进速度有关是与时间相关的错误.4.1.5 与时间有关的错误与时间有关的错误(Cont.)错误原因之1： 进程执行不正确的交叉(interleave);错误原因之2： 同时对一个公共变量(x)操作，其中一个进程的操作没有结束，另一个进程也对公共变量进行操作，使得公共变量处于一种不确定的状态，用数据库的术语说就是失去了变量x的数据完整性。Remarks: 上述错误并不是一定发生，而是与进程的推进速度有关，速度是时间的函数，因为这类错误

15、称为与时间相关的错误 某些交叉结果不正确;必须去掉导致不正确结果的交叉。4.2 进程互斥进程互斥(mutual exclusion)n4.2.1 共享变量与临界区共享变量与临界区n4.2.2 临界区域与进程互斥临界区域与进程互斥n4.2.3 进程互斥的实现进程互斥的实现n4.2.4 多处理机环境下的互斥多处理机环境下的互斥4.2.1 共享变量与临界区域共享变量与临界区域n共享变量共享变量（shared variable）n多个进程都需要访问的变量。多个进程都需要访问的变量。n临界区域临界区域（critical region）n访问共享变量的程序段访问共享变量的程序段。把临界区与其所对应的共享变

16、量联系起来称为关于某一种共享变量的临界区 一组公共变量一组公共变量CR1CR2CRn.表示表示共享变量共享变量: shared 临界区域临界区域: region do 语句语句例子：例子：shared B:array0,.,n-1of integer; region B do region B do begin begin (访问访问B） .（访问（访问B）. end; end; 嵌套临界区域嵌套临界区域 shared x1,x2; shared y1,y2; region x1,x2 do region y1,y2 do begin begin . region y1,y2 do regio

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

18、临界区域享变量的不同的临界区域。Remarks: 互斥是相对于公共变量而言的。互斥是相对于公共变量而言的。4.2.3 进程互斥的实现进程互斥的实现nFrameworkRepeat critical section remainder sectionUntil falseentry sectionexit section4.2.3 进程互斥的实现进程互斥的实现nRequirements:nmutual exclusion(互斥进入互斥进入): 一次只允许一个进程一次只允许一个进程进入关于同一组公共变量的临界区进入关于同一组公共变量的临界区；nProgress(空闲让进空闲让进): 临界区空闲时，

19、放行一个进临界区空闲时，放行一个进入者入者；nbounded waiting(有限等待有限等待): 一个想要进入临界区一个想要进入临界区的进程在等待有限个进程进入并离开临界区后获得的进程在等待有限个进程进入并离开临界区后获得进入临界区的机会进入临界区的机会。n临界区的调度原则：n当关于某一组共享变量的所有临界区均为空闲时，一个要求进入该组共享变量某一临界区的进程应该能够立即进入；n当关于某一组共享变量的某一临界区被占用时，一个要求进入该组共享变量某一临界区的进程应当等待；n当一个进程离开关于某一组共享变量的某一临界区时，应当容许某一个等待进入该组共享变量某一临界区的进程进入；4.2.3.1 进

20、程互斥的软件实现进程互斥的软件实现n完全用程序实现，不需特殊硬件指令支完全用程序实现，不需特殊硬件指令支持。持。n可用于单可用于单CPU和多和多CPU环境中。环境中。n有忙式等待问题。有忙式等待问题。Busy waiting“运行运行”或或“就绪就绪”尝试尝试1int turn; P0: P1:do do while (turn=1) ; while(turn=0); 临界区代码临界区代码 临界区代码临界区代码 turn=1; turn=0; 其余代码其余代码 其余代码其余代码while(1); while(1);不满足进展性不满足进展性: P0和和P1必须交替进入临界区必须交替进入临界区.尝

21、试尝试2Boolean flag2;P0: P1:Do do while (flag1) ; while (flag0); flag0=true; flag1=true; 临界区临界区 临界区临界区 flag0=false; flag1=false; 其余代码其余代码 其余代码其余代码while(1); while(1);不满足互斥性不满足互斥性: flag0=flag1=false.尝试尝试3boolean flag2; (false,false)do do flag0=true; flag1=true; while (flag1); while(flag0); 临界区代码临界区代码 临界区

22、临界区 flag0=false; flag1=false; 其余代码其余代码 其余代码其余代码while(1); while(1);不满足进展性不满足进展性: flag0=flag1=true, 进程进程P1和进程和进程P2都不能都不能进入临界区进入临界区. Dekkel算法算法int flag2; (init 0)int turn; (0 or 1)do flag0=1; while(flag1) if(turn=1) flag0=0; while (turn=1) skip; flag0=1; 临界区临界区 turn=1; flag0=0; 其余代码其余代码while(1);P0：do f

23、lag1=1; while(flag0) if(turn=0) flag1=0; while (turn=0) skip; flag1=1; 临界区临界区 turn=0; flag1=0; 其余代码其余代码while(1);P1：Peterson算法算法boolean flag2;int turn;P0:Do flag0=true; turn=1; while (flag1 & turn=1); 临界区临界区 flag0=false; 其余代码其余代码while(1);P1:Do flag1=true; turn=0; while (flag0 & turn=0); 临界区临界

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

25、c)or(a=c and bd)Lamport面包店算法面包店算法Boolean choosing0,n-1;（false)Int number0,n-1; (0)Pi 进入进入：1. choosingi=true;2. numberi=maxnumber0,numbern-1+1;3. choosingi=false;4. For(j=0;jn;j+)5. While (choosingj) skip;6. While (numberj!=0)and7. (numberj,j)(numberi,i) skip;8. Lamport面包店算法面包店算法Boolean choosing0,n-1

26、;（false)Int number0,n-1; (0)Pi 进入进入：1. 2. numberi=maxnumber0,numbern-1+1;3. 4. For(j=0;jn;j+)5. 6. While (numberj!=0)and7. (numberj,j)(numberi,i) skip;8. (1)P1抓到1未赋值(2)P2抓到1进入临界区(3)P1抓到1进入临界区 Lamport面包店算法面包店算法(Cont.)Pi离开：离开： numberi=0：变量变量choosing的的作用：作用：P1：抓到：抓到1; P2：抓到：抓到1;P2进入后离开前进入后离开前P1进入进入,不满足

27、互斥性不满足互斥性.满足临界区管理原则满足临界区管理原则n互斥性互斥性(mutual exclusion)n多个进程竞争进入临界区时多个进程竞争进入临界区时, 下述条件之一成立下述条件之一成立: (1)一个进程一个进程抓到最小号抓到最小号, (2)若干进程抓到最小号若干进程抓到最小号. 情形情形(1)抓到最小号的进抓到最小号的进程获准进入临界区程获准进入临界区; 情形情形(2)编号最小抓到最小号的进程获准进编号最小抓到最小号的进程获准进入临界区入临界区, 其它进程将在第一个其它进程将在第一个while循环或第二个循环或第二个while循环循环处等待处等待, 因而满足互斥性因而满足互斥性.n进展

28、性进展性(progress)n当仅有一个进程想进入临界区时当仅有一个进程想进入临界区时, 该进程可以立即进入该进程可以立即进入; 当有多当有多个进程想进入临界区时其二元组个进程想进入临界区时其二元组(numberi,i)最小的进程获最小的进程获准进入准进入, 因而确定进入临界区进程的决策将在有限时间内确定因而确定进入临界区进程的决策将在有限时间内确定.n有限等待性有限等待性(bounded waiting)n对任意一个想要进入临界区的进程对任意一个想要进入临界区的进程Pi, 设其抓到号码为设其抓到号码为numberi, 按二元组按二元组(numberi,i)次序排在次序排在Pi之前的竞争进之前

29、的竞争进程数量是有限的程数量是有限的, 在最坏情况下在最坏情况下Pi将等待将等待n-1个排在其前面的进个排在其前面的进程进入并离开临界区后获得进入临界区的资格程进入并离开临界区后获得进入临界区的资格, 因而满足有限因而满足有限等待性等待性.Eisenberg/Mcguire算法算法enum flag0,n-1 (idle, want_in, in_cs); int turn; /0.n-1; 初始任意初始任意0 i turnn-1先于先于i先于先于iflagi=idle: 进程进程Pi不想进入临界区不想进入临界区flagi=want_in: 进程进程Pi想进入临界区想进入临界区flagi=in

30、_cs: 进程进程Pi想进入或已进入临界区想进入或已进入临界区Eisenberg/Mcguire算法算法Pi进入进入:Do flagi=want_in; j=turn; While (j!=i) If (flagj != idle) j=turn Else j=(j+1)% n; flagi=in_cs; j=0; While (jn)and(j=i or flagj!=in_cs) do j+;while (j!=n);turn=i;Eisenberg/Mcguire算法算法Pi离开：离开：j=(turn+1)% n;While (flagj=idle) j=(j+1)% n;turn=j;

31、flagi=idle;CS满足临界区管理原则满足临界区管理原则n互斥性互斥性n仅当仅当flagi=in_cs, 且对所有且对所有j!=i, flagj!=in_cs时时, 进进程程Pi才进入临界区域才进入临界区域, 因而满足互斥性因而满足互斥性.n进展性进展性n临界区空闲时临界区空闲时, 排在序列排在序列turn, turn+1, , n-1,0,1, 2,turn-1最前面的申请进入临界区的进程获准进入临界区最前面的申请进入临界区的进程获准进入临界区, 因而满足进展性因而满足进展性.n有限等待性有限等待性n进程离开临界区时进程离开临界区时,按循环次序按循环次序turn+1, , n-1,0,

32、1, 2,turn-1确定唯一一个竞争进程为其后继确定唯一一个竞争进程为其后继, 所以一个进程所以一个进程最多等待最多等待n-1个进程进入并离开临界区后一定能进入临界区个进程进入并离开临界区后一定能进入临界区, 因而满足有限等待性因而满足有限等待性.4.2.3.2 进程互斥的硬件实现进程互斥的硬件实现1. 硬件提供硬件提供“测试并建立测试并建立”指令指令 int test_and_set(int &target) int temp; temp=target; *target=1; return(temp);. 对一组公共变量，对一组公共变量，int lock;（初始（初始=0); Pi

33、进入：进入：While test_and_set(&lock); Pi离开：离开：lock=0;满足互斥性，进展性，不满足有限等待性。满足互斥性，进展性，不满足有限等待性。4.2.3.2 进程互斥的硬件实现进程互斥的硬件实现满足有限等待性：满足有限等待性：全局变量：全局变量： int waitingn; int lock;局部变量：局部变量：int j; int key; waitingi=1; key=1;While(waitingi&key) key=test_and_set(&lock);waitingi=0;临界区临界区J=(i+1)%n;While(j!=i)

34、&(!waitingj) j=(j+1)%n;If(j=i) lock=0;Else waitingj=0;其余部分其余部分4.2.3.2 进程互斥的硬件实现进程互斥的硬件实现2. 硬件提供硬件提供“交换交换”指令指令 void swap(int &a,&b) int temp; temp:=*a; *a:=*b; *b:=temp; ; 对对一组公共变量一组公共变量：int lock (初始初始=0); 对一个进程空间对一个进程空间：int key; Pi进入进入：key=1; do swap(&lock,&key) while (key=1); Pi

35、离开离开：lock=0;4.2.3.2进程互斥的硬件实现进程互斥的硬件实现Remarks：(1) test_and_set指令和指令和swap指令是原子的，指令是原子的，不可中断的不可中断的(在单在单CPU情况下情况下)。(2) test_and_set实际上是：将内存中一个单实际上是：将内存中一个单元的内容取出，再送一个新值。元的内容取出，再送一个新值。(3) swap实际上是：交换内存两个单元的内容实际上是：交换内存两个单元的内容。4.2.3.2进程互斥的硬件实现进程互斥的硬件实现3. 硬件提供硬件提供“关中断关中断”和和“开中断开中断”指令指令 关中断关中断 Critical Regio

36、n 开中断开中断Remarks: (1) 开关中断只在单开关中断只在单CPU系统中有效系统中有效;(why?) (2) 影响并发性。影响并发性。4.2.4 多处理机环境下互斥多处理机环境下互斥n单单CPU, 指令间交叉指令间交叉, test_and_set, swap指令是原子的指令是原子的;n多多CPU, 指令周期间交叉指令周期间交叉, test_and_set, swap指令不是原子的指令不是原子的;4.2.4 多处理机环境下互斥多处理机环境下互斥内存内存Word 1000initial: 0CPU1CPU2Bus1. Read 03. Write 1 2. Read 04. Write

37、14.2.4 多处理机环境下互斥多处理机环境下互斥TS指令指令，Swap指令指令: first lock the busbus request protocol: 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进程互斥进程互斥n经典经典UNIX系统系统n机制机制n关中断互斥关中断互斥( (提高处理机优先级提高处理机优先级) )n特点特点n简单

38、简单n开销小开销小n影响并发性影响并发性n关中断后代码很短关中断后代码很短n在在SMP系统中采用自旋锁系统中采用自旋锁作业作业 #2Consider the following program:var blocked: array0.1of boolean; turn:0.1;procedure P(id:integer);begin repeat blockedid:=true; while turnid do begin while blocked1-id do nothing turn:=id end; blockedid:=false; until falseend;begin blo

39、cked0:=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. 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

40、this one.4.3 进程同步进程同步4.3.1 进程同步的概念进程同步的概念例：司机例：司机-售票员问题售票员问题 司机活动：司机活动： 售票员活动：售票员活动： do do 启动车辆启动车辆 关车门关车门 正常行驶正常行驶 售售 票票 到站停车到站停车 开车门开车门 while( (1) ) while( (1) )4.3.1 进程同步的概念进程同步的概念定义：定义：一组进程，为协调其推进速度，在某些一组进程，为协调其推进速度，在某些关键点处需要相互等待与相互唤醒，进程之间关键点处需要相互等待与相互唤醒，进程之间这种相互制约的关系称为进程同步。这种相互制约的关系称为进程同步。P1:P2

41、:synchronize后先4.3.2 进程同步机制进程同步机制n定义：定义：n用于实现进程同步的工具称为同步机制用于实现进程同步的工具称为同步机制（synchronization mechanism）n一组进程，如果它们单独不能正常进行，但一组进程，如果它们单独不能正常进行，但并发可以正常进行，称这种现象为进程合作并发可以正常进行，称这种现象为进程合作n参与合作的进程称作合作进程参与合作的进程称作合作进程4.3.2 进程同步机制进程同步机制n同步机制要求：同步机制要求：n描述能力够用描述能力够用;n可实现可实现;n高效高效;n使用方便使用方便.典型同步机制典型同步机制 n信号量与信号量与PV

42、操作操作( (semaphore and PV operations) )n管程管程( (monitor) )n会合会合( (rendezvous) )n条件临界区条件临界区( (conditional critical region) )n路径表达式路径表达式( (path expression) )n事件事件( (event, ,traditional UNIX) )4.3.3 信号量与信号量与PV操作操作E.W.Dijkstra, 1965.4.3.3.1 信号量与信号量与PV操作的定义操作的定义 Typedef semaphore struct int value; PCBpointe

43、r queue; ; semaphore s;Remarks:(1) semaphore is pre-defined data type,(2) s can be declared as needed, eg. semaphore s1,s2; 信号灯变量信号灯变量S.valueS.queueS.valueS.queuePCBPCBPCBVar S:semaphore;FIFOP操作原语操作原语P操作原语：操作原语：void P(semaphore*s) s-value-; If s-valuequeue) asleep(s-queue):(1) 执行此操作进程的执行此操作进程的PCB入入s

44、-queue尾（状态改为等尾（状态改为等待）；待）；(2) 转处理机调度程序。转处理机调度程序。 Primitive: a piece of code un-interruptibleV操作原语操作原语V操作原语：操作原语：void V(semaphore *s) s-value+; if (s-valuequeue); wakeup(s-queue)S-queue链头链头PCB出等待队列，进入就绪队列（状态改出等待队列，进入就绪队列（状态改为就绪）。为就绪）。 Primitive: a piece of code un-interruptible规定和结论规定和结论n对于信号量变量的规定：对

45、于信号量变量的规定：n必须置一次初值，只能置一次初值，初值必须置一次初值，只能置一次初值，初值=0;n只能执行只能执行P操作和操作和V操作，所有其它操作非法。操作，所有其它操作非法。n几个有用的结论几个有用的结论：n当当s-value=0时，时，s-queue为空；为空；n当当s-valuevalue|为队列为队列s-queue的长度；的长度；n当当s-value初=1时，可以实现进程互斥；时，可以实现进程互斥；n当当s-value初=0时，可以实现进程时，可以实现进程间的简单间的简单同步同步；n当当s-value为非1的正整数时，可以用来管理同种组合资源，时，可以用来管理同种组合资源，申请资

46、源执行一次申请资源执行一次P操作，归还资源执行一次操作，归还资源执行一次V操作；操作；用开关中断实现用开关中断实现P、V操作操作void P(semaphore *s) disable interrupt; s-value-; if (s-valuequeue) enable interrupt; goto CPU dispatcher; else enable interrupt; 用开关中断实现用开关中断实现P、V操作操作void V(semaphore *s) disable interrupt; s-value+; if (s-value0) wakeup(s-queue) enabl

47、e interrupt; else enable interrupt; 用开关中断实现用开关中断实现P、V操作操作nasleep(s-queue):set this process status to blocked;place this process in s-queue.nwakeup(s-queue):remove a process from s-queue;place the process in ready list.用用TS、swap指令实现指令实现P、V操作操作void P(semaphore *s) while(TS(s-flag); s-value-; if (s-val

48、uequeue) s-flag=0; goto CPU dispatcher; else s-flag=0; 用用TS、swap指令实现指令实现P、V操作操作void V(semaphore *s) while(TS(s-flag); s-value+; if (s-value0) wakeup(s-queue) s-flag=0; else s-flag=0;Var mutex: semaphore; (初值初值=1） shared x,y,z:integer; CR1 CR2 CRn用信号灯实现进程互斥用信号灯实现进程互斥Var mutex: semaphore; (初值初值=1） sha

49、red x,y,z:integer;P(mutex) P(mutex) P(mutex) CR1 CR2 CRnV(mutex) V(mutex) V(mutex)互斥例子：借书系统互斥例子：借书系统(revisited)Var mutex:semaphore; (initial value is 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 E

50、nd互斥例子：借书系统互斥例子：借书系统(revisited)Var mutex:semaphore; (initial value is 1)终端终端1： 终端终端2：CYCLE CYCLE 等待借书者等待借书者； 等待借书者等待借书者； P(mutex) P(mutex) IF x=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、V实现进程同步实现进程同步

51、后动作后动作先动作先动作 P1:P2:用信号灯实现进程同步用信号灯实现进程同步 P(S)后动作后动作先动作先动作 V(S)P1:P2:用信号量、用信号量、P、V实现进程同步实现进程同步例子：司机例子：司机-售票员问题：售票员问题：司机活动：司机活动： 售票员活动：售票员活动： Do Do 关车门关车门 启动车辆启动车辆 正常行驶正常行驶 售售 票票 到站停车到站停车 开车门开车门 While(1) While(1)用信号量、用信号量、P、V实现进程同步实现进程同步例子：司机例子：司机-售票员问题：售票员问题：VAR s1,s2: semaphore; (initial value 0)司机活动

52、：司机活动： 售票员活动：售票员活动： Do Do P(S1) 关车门关车门 启动车辆启动车辆 V(S1) 正常行驶正常行驶 售售 票票 到站停车到站停车 P(S2) V(S2) 开车门开车门 While(1) While(1)Classical synchronization problems1. Producers and consumers problem2. Readers and writers problem3. Dining philosophers problem4. Cigarette smokers problem5. Sleepy barbers problemetc.

53、例例1. 生产者生产者/消费者问题消费者问题预备知识：预备知识：组合资源组合资源：若干相对独立的资源构成的资源集合，其中：若干相对独立的资源构成的资源集合，其中每个相对独立的资源称为子资源。每个相对独立的资源称为子资源。同种组合资源同种组合资源：相同类型子资源构成的组合资源。：相同类型子资源构成的组合资源。管理：管理：Var S:semaphore; (初值初值=子资源个数）子资源个数）例子：例子：2台打印机台打印机 Var S:semaphore; S.value=2; 申请：申请：P（S）；）； 释放：释放：V（S）；）；自动机描述自动机描述210-1-2P(S)P(S)P(S)P(S)P

54、(S)V(S) V(S) V(S) V(S) V(S) S-value=空闲资源空闲资源数数 S-queue=空空|S-value|=等待进程等待进程数数 空闲资源数空闲资源数=0.P(S): 申请一台打印机申请一台打印机, 分配分配, 空闲打印机减空闲打印机减1P(S): 申请一台打印机申请一台打印机, 等待等待, 等待进程数加等待进程数加1 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.V

55、(S): 释放一台打印机释放一台打印机, 唤醒一个等待者唤醒一个等待者, 打印机分给被唤醒进程打印机分给被唤醒进程, 等待进程数减等待进程数减1V(S): 释放一台打印机释放一台打印机, 空闲打印机数量增空闲打印机数量增1 例例1. 生产者生产者/消费者问题消费者问题 0 1 k-1箱子，容量箱子，容量k B:Array0.k-1Of item生产者生产者消费者消费者生产物品生产物品放入放入B中中B中取物品中取物品消费之消费之环形缓冲区环形缓冲区10K-1in(in+1)mod kout(out+1)mod k问题分析生产者活动生产者活动： 消费者活动消费者活动： do do 加工一件物品加工

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

57、) V(S2) 消耗这件物品消耗这件物品 While(1) While(1)对对B和和in,out的互斥的互斥：Var mutex:semaphore; (mutex.value=1)互斥互斥生产者活动：生产者活动： 消费者活动：消费者活动： Do Do 加工一件物品加工一件物品 P(S2) P(S1) P(mutex) P(mutex) 箱中取一物品箱中取一物品 物品放入箱中物品放入箱中 V(mutex) V(mutex) V(S1) V(S2) 消耗这件物品消耗这件物品 While(1) While(1)考虑死锁考虑死锁生产者活动：生产者活动： 消费者活动：消费者活动： Do Do 加工一

58、件物品加工一件物品 P(mutex) P(mutex) P(S2) P(S1) 箱中取一物品箱中取一物品 物品放入箱中物品放入箱中 V(S1) V(S2) V(mutex) V(mutex) 消耗这件物品消耗这件物品 While(1) While(1)程序Program 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

59、)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;程序程序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.并发性提高策略并发性提高策略生产者和消费者：不操作生

60、产者和消费者：不操作B的相同分量的相同分量生产者的共享变量生产者的共享变量： Bin, in消费者的共享变量消费者的共享变量： Bout, outin=out: 满或空,Var mutex1,mutex2:semaphore; (init 1)并发性提高策略并发性提高策略生产者活动：生产者活动： 消费者活动：消费者活动： Repeat Repeat 加工一件物品加工一件物品 P(S2) P(S1) P(mutex2) P(mutex1) 箱中取一物品箱中取一物品 物品放入箱中物品放入箱中 V(mutex2) V(mutex1) V(S1) V(S2) 消耗这件物品消耗这件物品 Until false Until false例例2. 读者读者/写者问题写者问题P. T. Court