华南理工大学操作系统课件第3章并发控制

计算机操作系统第3章并发控制——互斥与同步1本章知识点：3.1并发原理3.2互斥——软件解决方法3.3互斥——硬件解决方法

3.4信号量3.5管程3.6消息传递3.7读者/写者问题3.8系统举例（略）

23.1并发原理操作系统设计的核心是进程管理：在单处理机系统中，并发执行方式：

微观串行，宏观并行。在多处理机系统中，并发执行方式 宏观并行，也有微观并行。分布式环境，多进程管理并发的存在，要求操作系统必须能跟踪大量活跃进程,必须为每一活跃进程分配资源，必须保护每一进程的数据和物理资源不被其他进程侵犯，并且进程执行的结果与其他并发进程执行时的相对速度无关（P73例echo）。3回顾：程序结果的不可再现性程序A程序BN=N+1;print(N);N=0;设某时刻N=n;程序A执行结果：程序A程序Bn+1n+101、进程的中断可在任何地方2、访问了共享变量有效控制对共享资源的访问原因：方法：43.1并发原理并发系统中的各个进程，由于资源共享、进程合作，而产生进程之间的相互制约；3.1.1进程间的相互作用3.1.2进程间的相互竞争3.1.3进程间的相互合作3.1.4互斥53.1.1进程间的相互作用进程之间常常相互作用，存在某种彼此依赖或相互制约的关系。例如并发进程在竞争使用同一资源时将产生冲突。可将进程间的相互作用划分为：进程互不觉察： 由OS分配资源进程间接觉察： 共享方式合作进程直接觉察： 直接通信，协同工作63.1.2进程间的相互竞争

并发进程在竞争使用同一资源时将产生冲突。进程间的竞争面临3个控制问题：互斥死锁饥饿竞争的控制不可避免地涉及到操作系统，因为是操作系统分配资源，另外，进程自身也必须能以某种方式表达互斥的要求，例如在使用某一资源之前先将其加锁。7互斥临界资源CriticalResource:

每次仅允许一个进程使用的资源。如打印机，共享变量临界区CriticalSection：

每个进程中访问临界资源的那段代码。互斥MutualExclusion：不允许两个以上的共享该资源的并发进程，同时进入临界区，称为互斥。进程进入临界区之前，必须提出申请，经允许后方可进入，进入后加锁，使其他进程无法进入，退出临界区时解锁。8互斥（间接作用）9a:=a-1print(a)a:=a+1print(a)P1互斥P2互斥Ifa<0thena:=a+1elsea:=a-1P3互斥互斥（间接作用）10互斥的两个后果死锁(deadlock)

是指多个进程互不相让，都得不到足够资源。饥饿(starvation)

是指某些进程一直得不到资源，或得到资源的概率很小。113.1.3进程间的相互合作1.通过共享合作

这些进程并不是通过名字察觉到对方，而是通过共享访问间接察觉。进程间通过共享方式进行合作。除互斥、死锁和饥饿外，

保证数据的一致性也是一个潜在的控制问题。123.1.3进程间的相互合作2.通过通信合作进程通信是指进程之间，可直接以较高的效率，传递较多数据的信息交换方式。这种方式中采用的是通信机构，在进程通信时往往以消息形式传递信息。

因为在消息传递中不存在共享，所以这种形式的合作不需要互斥，但是还存在死锁和饥饿问题。

133.1.4互斥问题的解决原则

互斥原则 P67任何两个进程不能同时处于临界区通用性原则不应对CPU的速度和数目进行任何假设有效性原则临界区外的进程不应阻塞其他进程合理性原则不得使进程在临界区外无限制的等待当进程无法进入临界区时，应放弃CPU资源进程通信1空闲让进；2忙则等待；

3让权等待；4有限等待；143.2互斥——软件解决方法

软件方法对并发进程不提供任何支持， 不需要硬件、操作系统、程序设计语言的支持。软件方法易引起较高的进程负荷，和较多的错误，但有利于同学们深刻理解并发的复杂性。其基本思路：

在进入区，检查和设置一些标志，如果已有进程在临界区，则在进入区通过循环检查进行等待；在退出区，修改标志，允许其他进程进入。主要问题：

设置什么标志

如何检查标志Busy-waiting忙等待，浪费了处理器时间。15类PASCAL描述语句与C对比begin…endrepeat...Foreverrepeat...untilPwhilePdo begin…endfunctionname1(...):typeprocedurename2(...)vari,j:integer;varx:array[0..9]ofinteger;i:=1;<>,=,and,or,not{…}for(;;)或while1do{...}do{...}while!PwhilePdo{...}typename1(...)voidname2(...)inti,j;intx[10];i=1;!=,＝＝,&&,||,!163.2.1Dekker算法描述了并发进程发展过程中，遇到的大部分共同问题。“爱斯基摩人的小屋协议”:门和小屋很小,每次只能容纳一个人进入,小屋内有一个标志黑板写着编号。进程申请进入临界区,必须首先进入小屋并检查黑板标志是否是它的编号：

是,离开小屋,进入临界区,执行完毕,退出临界区,并返回小屋,修改黑板标志为其他进程

否,反复进入小屋,检查黑板标志,直到标志是它的编号173.2.1Dekker算法11.第1种途径

这种方法保证了互斥。问题:Pi一定要等待Pj进入过后，才可以再次进入!(临界资源利用率不高，如果Pi死机了Pj就再也不能进入临界区)

varturn:0..1;{turn为共享的全局变量，表示黑板的编号}PROCESS0 PROCESS1……whileturn≠0 whileturn≠1

do{nothing} do{nothing}；〈criticalsection〉; 〈criticalsection〉;turn:=1; turn:=0;……183.2.1Dekker算法22.第2种途径

varflag:array[0..1]of

boolean;它被初始化为falsePROCESS0 PROCESS1……whileflag[1] whileflag[0]

do{nothing} do{nothing}；flag[0]:=true;flag[1]:=true;〈criticalsection〉; 〈criticalsection〉;flag[0]:=false; flag[1]:=false;… …flag[i]表示Pi在CS中问题:当进程Pi刚检测完标志位flag[j]时，还没有设置flag[i]:=true切换发生在此处，则都可进入临界段!先设置，再检测？193.2.1Dekker算法33.第3种途径PROCESS0 PROCESS1……flag[0]:=true; flag[1]:=true;whileflag[1] whileflag[0]

do{nothing} do{nothing}；

〈criticalsection〉; 〈criticalsection〉;flag[0]:=false; flag[1]:=false;… …问题：设置了flag[i]:=true

，切换发生在此处，两个进程各自标志位为true，检测的结果是互相等待而阻塞了自己flag[i]表示Pi想进入CS设置和检测中间发生进程切换，则产生问题！203.2.1Dekker算法44.第4种途径PROCESS0 PROCESS1… …flag[0]:=true; flag[1]:=true;whileflag[1]do

whileflag[0]do

begin

beginflag[0]:=false; flag[1]:=false;〈delayforashorttime〉; 〈delayforashorttime〉;flag[0]:=true; flag[1]:=true;end;end;〈criticalsection〉; 〈criticalsection〉;flag[0]:=false； flag[1]:=false;… …213.2.1Dekker算法44.第4种途径PROCESS0 … flag[0]:=true; whileflag[1]do

begin

flag[0]:=false; 〈delayforashorttime〉; flag[0]:=true; end;

〈criticalsection〉; flag[0]:=false；

… P0想要进入CS考虑途径3情形，可能切换到P1，先撤销flag[0]标志，礼让P1先进入CS若P1进入CS，P0while循环P1退出CS后，P0退出while循环，进入CS223.2.1Dekker算法44.第4种途径问题：P0:置flag[0]=true; P1:置flag[1]=true;

P0:执行whileflag[1]; P1:执行whileflag[0];

P0:置flag[0]=false; P1:置flag[1]=false;

P0:延迟; P1:延迟; P0:置flag[0]=true; P1:置flag[1]=true;

…检查其它进程,然后重置,再检查,再重置…,互斥礼让：重置序列可以无线延伸,任何一个进程都不能进入自己的临界区。(不是死锁，只要进程相对速度稍有变化就会打破循环)233.2.1Dekker算法55.一个正确的解决方法设计一个“指示”小屋，小屋内的黑板标明“turn”，当P0想进入其临界段时，置自己的flag为“true”， 然后去查看P1的flag， 如果是“false”，则P0就立即进入自己的临界段， 如果是“true”，则P0去查看turn， 如果turn=0，那么它知道自己应该坚持 并不时去查看P1的小屋，P1将觉察到 （因为turn=0）它应该放弃并在自己的 黑板上写上“false”，以允许P0继续执行。

P0执行完临界段后，它将flag置为“false”以释放临界段，并且将turn置为1，将进入权交给P1

。243.2.1Dekker算法5varflag:array[0..1]ofboolean;turn:0..1;//准许进入临界区标志变量beginflag[0]:=false; flag[1]:=false;turn:=1; //设P1可加入临界区parbeginp0;p1; //并发程序parendend主要思想:设置两个变量:

1.turn:指出应该哪一个进入临界区 turn=0表示P0可以进入

turn=1表示P1可以进入

2.Flag:指出当前哪一个在临界区

Flag=false表示P0当前在临界区

Flag=true表示P1当前在临界区253.2.1Dekker算法5ProcedureP0;beginrepeatflag[0]:=true;//P0希望进入临界区.whileflag[1]do//查P1进程标志ifturn=1then//表明P1在临界区beginflag[0]:=false;whileturn=1do{nothing};//当turn=0,表明P0可以进入临界区flag[0]:=true;//设标志为真,end;//P0进入临界区

〈criticalsection〉;turn:=1;//指定P1进程可进临界区flag[0]:=false;foreverendProcedureP1;beginrepeatflag[1]:=true;whileflag[0]doifturn=0thenbeginflag[1]:=false;whileturn=0do{nothing};flag[1]:=trueend;

〈criticalsection〉;turn:=0;flag[1]:=false;foreverend263.2.1Dekker算法5ProcedureP0;beginrepeatflag[0]:=true;//P0希望进入临界区.whileflag[1]do//查P1进程标志ifturn=1then//表明P1在临界区beginflag[0]:=false;whileturn=1do{nothing};//当turn=0,表明P0可以进入临界区flag[0]:=true;//设标志为真,end;//P0进入临界区

〈criticalsection〉;turn:=1;//指定P1进程可进临界区flag[0]:=false;foreverendturnflag[0]flag[1]turn结果TT0T1F0F1273.2.2Peterson算法Dekker算法可以解决互斥问题，但其复杂的程序难于理解，其正确性难于证明。Peterson给出了一个简单的方法。turn解决同时的冲突,Flag指示进程是否在临界区.对两参量同时控制,交替进入临界区执行.283.2.2Peterson算法flag[0]flag[1]turn结果TT0T1F0F1procedureP0;

begin

repeat

flag[0]:=true;//P0希望进临界区

turn:=1;

whileflag[1]andturn=1 do{nothing};

<criticalsection>;flag[0]:=false;

<remainder>

forever

end;

procedureP1;

begin

repeat

flag[1]:=true;

turn:=0;

whileflag[0]andturn=0 do{nothing};

<criticalsection>;flag[1]:=false;

<remainder>

forever

end;

flag[0]flag[1]turn结果TT1T0F1F029互斥——软件解法的缺点

1.忙等待

2.实现过于复杂

3.需要高的编程技巧303.3互斥——硬件解决方法

提供了可以解决临界区问题的特殊的硬件指令。硬件方法通过特殊的机器指令实现互斥，可以降低开销。1、中断屏蔽方法（禁止中断）

不允许进程切换2、硬件指令方法用一条指令完成设置和检测，保证读与写不被打断。313.3.1禁止中断在单处理机中，禁止进程被中断即可保证互斥，通过操作系统内核定义的禁止和允许中断的原语，就可获得这种能力。进程执行临界段时不能被中断。屏蔽中断；进程P的临界段；开中断；优点： 简单，有效，在单处理机中可保证互斥。缺点： 代价较高，使执行效率显著降低 在多处理机系统中，禁止中断不能保证互斥323.3.2使用机器指令1.特殊的机器指令

在多处理机系统中，多个处理机共享一个共同的主存，这里并没有主/从关系，也没有实现互斥的中断机制。特殊的硬件指令：TestandSet指令：允许在一个存储周期内去测试和修改一个字的内容，Exchange指令：允许在一个存储周期内交换两个字的内容33Test_and_Set指令functiontestset(vari:integer):boolean;begin

ifi=0then

begin

i:=1;

testset:=true;

end

elsetestset:=false;end.原语，执行过程不能被中断34用硬件方法解决互斥programmutualexclusion;constn=2;(*numberofprocesses*);varbolt:integer;procedureP(i:integer);beginrepeatrepeat{nothing}//忙等待，浪费CPU时间untiltestset(bolt);//当bolt为0时,进入临界区,<criticalsection>;bolt:=0;<remainder>;foreverend;begin(*mainprogram*)

bolt:=0;

parbegin

P(1);P(2);...P(n);

parend

end353.3.2使用机器指令2.机器指令方法的特性优点：可用于含有任意数量进程的单处理机或共享主存的多处理机；比较简单，易于验证；可支持多个临界段，每个临界段用各自的变量加以定义。缺点：采用busy-waiting技术，进程等待进入临界段时耗费处理机时间；可能产生饥饿；可能产生死锁。36互斥互斥机制的基本要求：*描述能力*可以实现*效率高*使用方便都有缺点，有更好的互斥机制吗？操作系统、程序设计语言能提供支持？373.4信号量semaphore3.4.0信号量

信号量机制、操作、物理意义3.4.1用信号量解决互斥问题3.4.2用信号量解决生产者/消费者问题

不考虑缓冲区长度，缓冲区有限长3.4.3信号量的实现

381965年，由荷兰学者Dijkstra提出(1972年获得ACM图灵奖，2002年8月去世）。所以P、V分别是荷兰语的test(proberen)和increment(verhogen)）“信号量”：一种解决进程的同步与互斥的工具是一个具有非负初值的整型变量，并且有一个队列与它关联。

typesemaphore=record count:integer; queue:ListofPCB;end不是普通的变量，只能进行Wait、Signal操作3.4.0信号量封装39信号量上的同步原语Wait(S)：

s.count:=s.count-1;//将值减1，

ifs.count<0 thenbeing

该进程状态置为等待状态； 将该进程的PCB插入等待队列s.queue的末尾；

end；Signal(S)：

s.count:=s.count+1;//将值减1，

ifs.count=<0 thenbeing

从等待队列s.queue摘下一个等待进程； 将该进程置入就绪队列；

end；40信号量的物理意义S>0时，表示该类资源的可用资源数S<=0时，表示已无此类资源可供分配，请求资源的进程，将被阻塞在相应的信号量S的等待队列中。

S的绝对值=该信号量上等待的进程数。

41Wait操作的物理意义S>0时，每执行一次Wait操作，意味着请求分配一个单位的该类资源，即S:=S-1；S＝0时，执行Wait操作，此时已无资源可分配，故进程被阻塞；S<0时，执行Wait操作，说明前面已经有进程在等待着分配资源了。

S的绝对值=该信号量上等待的进程数。42Signal操作的物理意义每执行一次Signal操作，意味着进程释放一个单位的该类可用资源，即S:=S+1。S<=0，根据前面的分析，此时S等待队列中有因等待该资源而被阻塞的进程，故把队列中的一个进程唤醒，转入就绪队列。433.4.1用信号量解决互斥问题Mutex互斥信号量（mutualexclusion），Programmutualexclusion;Constn=4;//(进程数)VarMutex

:semaphore(:=1);ProcedureP(I:integer);BeginRepeat

Wait(Mutex

);<CS>;

Signal(Mutex

);<remaider>ForeverEndBegin(*mainprogram*)Parbegin P(1);p(2);….p(n);

parend;EndMutex.Count取值含义:1,0,-1,-2?min?Max?

44用信号量实现互斥wait(s)p1s10-1-2-101criticalsignal(s)wait(s)criticalsignal(s)p2wait(s)criticalsignal(s)p3semaphoreWait操作信号量非负，P1进入临界区Wait操作信号量为负，P2阻塞Wait操作信号量为负，P3阻塞Signal操作后信号量非正，从等待队列中唤醒一个进程Signal操作后信号量非正，从等待队列中唤醒一个进程Signal操作后信号量为正，表示已无进程在临界区45二元信号量P77仅允许取值为0与1，定义更严格，实现更简单。与一般信号量(允许取值为非负整数)有同等的表达能力value:(0,1);

waitB(s):ifs.value=1

then

s.value=0;

elsebegin

将本进程放入s.queue;

阻塞本进程;

end;

signalB(s):

ifs.queueisempty

then

s.Value:=1;

elsebegin

从s.queue摘下一个等待进程;

将该进程放入就绪队列;

end；46思考题

管理临界区时，信号量的初值一般应定义为（）。 A.–1B.0C.1D.任意值

在下面的叙述中，正确的是（）。A.临界资源是非共享资源B.临界资源是任意共享资源C.临界资源是互斥共享资源D.临界资源是同时共享资源

对进程间互斥地使用临界资源，进程可以（）A.互斥地进入临界区B.互斥地进入各自的临界区C.互斥地进入同一临界区D.互斥地进入各自的同类资源的临界区

设两个进程共用一个临界资源的互斥信号量mutex，当mutex＝1时表示（）。当mutex＝-1时表示（）。A.一个进程进入了临界区，另一个进程等待

B.没有一个进程进入临界区

C.两个进程都进入了临界区

D.两个进程都在等待47判断题1．一个临界资源可以对应多个临界区。2．互斥地使用临界资源是通过互斥地进入临界区实现的。3．同步信号量的初值一般为1。4．进程A、B共享变量x，需要互斥执行；进程B、C共享变量y，B、C也需要互斥执行，因此，进程A、C必须互斥执行。5.单道程序系统中程序的执行也需要同步和互斥。483.4.2用信号量解决生产者/消费者问题问题描述进程之间的要求先考虑缓冲区无限长二元信号量一般信号量再考虑有限缓冲时491）问题描述计算机系统中的常见问题模型：

要求：生产者向其中投放数据，消费者从中取出数据消费。生产者不能往“满”的缓冲区中放产品消费者不能从“空”的缓冲区中取产品共享一个缓冲池一组生产者一组消费者提供数据PnP3P2P1C1C2C3Cn

502）进程之间的要求缓冲区不能并行操作(必须互斥), 某时刻只允许一个实体(producerorconsumer)访问方法：使用互斥信号量控制producerandconsumer协调(同步)地读/写buffer, 即不能向满buffer写数据;不能在空buffer中取数据方法：使用另一个信号量来控制

513）先假设缓冲区无限长consumer:repeat

whilein≤out

do{nothing};//无产品

w:=b[out];

out:=out+1;

consumeitemw;

forever;producer:repeat

produceitemv;

b[in]:=v;

in:=in+1;

forever;没有同步的情况：takeappend52一、使用二元信号量programproducerconsumer;varn:integer;//n=in–out可取的产品数

s:(*binary*)semaphore(:=1);//互斥访问缓冲区delay:(*binary*)semaphore(:=0);//缓冲区空时,消费者等待begin(*mainprogram*)n:=0;

parbeginproducer;consumer

parend;end改变初始值可以吗？53基本处理语句procedureproducer;begin

repeat

produce;

append;n:=n+1;

foreverend;procedureconsumer;begin

repeat

take;n:=n-1;

consume;

foreverend;假设缓冲区无限长54互斥访问缓冲区、共享变量nprocedureproducer;begin

repeat

produce;

waitB(s);append;n:=n+1;

signalB(s);

foreverend;procedureconsumer;begin

repeat

waitB(s);

take;n:=n-1;

signalB(s);consume;

foreverend;初始时缓冲区为空，若consumer先执行？假设缓冲区无限长55解决当缓冲区空时,消费者等待procedureproducer;begin

repeatproduce;

waitB(s);append;n:=n+1;

ifn=1thensignalB(delay);

signalB(s);

foreverend;procedureconsumer;begin

waitB(delay);//仅执行一次

repeat

waitB(s);take;n:=n-1;

signalB(s);consume;

ifn=0thenwaitB(delay)

foreverend;假设缓冲区无限长56append后生产者通知消费者procedureproducer;begin

repeatproduce;

waitB(s);append;n:=n+1;

ifn=1thensignalB(delay);

signalB(s);

foreverend;procedureconsumer;begin

waitB(delay);//仅执行一次

repeat

waitB(s);take;n:=n-1;

signalB(s);consume;

ifn=0thenwaitB(delay)

foreverend;

问题：n是共享变量，对n的访问应该考虑并发问题假设缓冲区无限长57解决方法一：将signalB(s);移动后面procedureproducer;begin

repeatproduce;

waitB(s);append;n:=n+1;

ifn=1thensignalB(delay);

signalB(s);

foreverend;procedureconsumer;begin

waitB(delay);

repeat

waitB(s);take;n:=n-1;

//signalB(s);consume;

ifn=0thenwaitB(delay)

signalB(s);

foreverend;是否可行？

注意细节、逻辑问题假设缓冲区无限长58解决方法二：使用辅助变量mprocedureproducer;begin

repeatproduce;

waitB(s);append;n:=n+1;ifn=1thensignalB(delay);

signalB(s);

foreverend;procedureconsumer;varm:interger;begin

waitB(delay);

repeat

waitB(s);take;n:=n-1;m:=n;

signalB(s);consume;ifm=0thenwaitB(delay)

foreverend;假设缓冲区无限长59二、用一般信号量

procedureproducer;begin

repeat

produce;

append;

foreverend;procedureconsumer;begin

repeat

take;

consume;

foreverend;varn:semaphore(:=0);s:semaphore(:=1);

假设缓冲区无限长60用一般信号量解决生产者/消费者问题procedureproducer;begin

repeat

produce;wait(s);

append;

signal(s);

foreverend;procedureconsumer;begin

repeat

wait(s);

take;

signal(s);

consume;

foreverend;varn:semaphore(:=0);s:semaphore(:=1);

假设缓冲区无限长61用一般信号量解决生产者/消费者问题procedureproducer;begin

repeatproduce;wait(s);append;

signal(s);

signal(n);

foreverend;procedureconsumer;begin

repeat

wait(n);

wait(s);take;

signal(s);consume;

foreverend;varn:semaphore(:=0);s:semaphore(:=1);

如果交换这两句的次序会怎样？假设缓冲区无限长624）缓冲区有限长解题过程分析有什么同步问题（应该设置什么信号量）；缓冲区互斥访问in：一组生产者共用的指向空缓冲区头的指针；out：一组消费者共用的指向满缓冲区头的指针。生产者不能往“满”的缓冲区中放产品full-满缓冲区资源信号量。消费者不能从“空”的缓冲区中取产品empty-空缓冲区资源信号量；给信号量赋初值（常用的互斥和同步信号量值的大小）；

full:=0;empty:=n;mutex:=1;inout634）缓冲区有限长consumer:beginrepeat

m:=buffer(out);out:=(out+1)modn;

consumem; //产品

forever endproducer:beginrepeatProducem;//产品

buffer(in):=m;in:=(in+1)modn;

forever endVarmutex，empty,full:Semaphore;buffer:array[0..n-1]ofmessage;

mutex:=1;empty:=n;full:=0;in,out:0..n-1;644）缓冲区有限长consumer:beginrepeat

wait(mutex);

m:=buffer(out);out:=(out+1)modn;

signal(mutex);

consumem; forever endproducer:beginrepeatProducem;

wait(mutex);

buffer(in):=m;in:=(in+1)modn;

signal(mutex);

forever endVarmutex，empty,full:Semaphore;buffer:array[0..n-1]ofmessage;

mutex:=1;empty:=n;full:=0;in,out:0..n-1;654）缓冲区有限长consumer:beginrepeat

wait(full);wait(mutex); m:=buffer(out);out:=(out+1)modn;signal(mutex);

signal(empty); consumem; forever endproducer:beginrepeatProducem;

wait(empty);

wait(mutex);

buffer(in):=m;in:=(in+1)modn;

signal(mutex);

signal(full);

forever endVarmutex，empty,full:Semaphore;buffer:array[0..n-1]ofmessage;

mutex:=1;empty:=n;full:=0;in,out:0..n-1;66使用信号量解决进程同步问题问题描述分析问题中的同步关系/要求设置所需信号量及初值放置恰当的Wait/Signal操作作业：对生产者/消费者问题回答步骤1，2，3 用伪代码完成步骤467对信号量的操作可以分为三种情况：

1）把信号量视为一个加锁标志位，实现对一个共享变量的互斥访问。

WAIT(mutex);//mutex的初始值为1访问该共享数据

SIGNAL(mutex); 非临界区

2）把信号量视为是某种类型的共享资源的剩余个数，实现对一类共享资源的访问。

WAIT(resource);//resource的初始值为该资源的个数N使用该资源；

SIGNAL(resource); 非临界区

3）把信号量作为进程间的同步工具

WAIT(S1);临界区C1；

SIGNAL(S2);临界区C2；68例子1：某超市门口为顾客准备了100辆手推车，每位顾客在进去买东西时取一辆推车，在买完东西结完帐以后再把推车还回去。试用WAIT、SIGNAL操作正确实现顾客进程的同步互斥关系。分析：把手推车视为某种资源，每个顾客为一个要互斥访问该资源的进程。

S_CartNum：semaphore;//空闲的手推车数量，初值为100Procedureconsumer//顾客进程Begin

WAIT(S_CartNum);买东西；结帐；

SIGNAL(S_CartNum);End69例子2：两个进程PA、PB通过两个FIFO（先进先出）缓冲区队列Q1、Q2连接。PA从Q2取消息，处理后往Q1发消息，PB从Q1取消息，处理后往Q2发消息。假设每个缓冲区长度等于传送消息长度.Q1队列长度为n，Q2队列长度为m.开始时Q1中装满了消息。PA:

WAIT(S_MessageNum_Q2);从Q2当中取出一条消息；

SIGNAL(S_BuffNum_Q2);处理消息；生成新的消息；

WAIT(S_BuffNum_Q1);把该消息发送到Q1当中；

SIGNAL(S_MessageNum_Q1);PB:

WAIT(S_MessageNum_Q1);从Q1当中取出一条消息；

SIGNAL(S_BuffNum_Q1);处理消息；生成新的消息；

WAIT(S_BuffNum_Q2);把该消息发送到Q2当中；

SIGNAL(S_MessageNum_Q2);semaphoreS_BuffNum_Q1;//Q1队列当中的空闲缓冲区个数，初值为0semaphoreS_BuffNum_Q2;//Q2队列当中的空闲缓冲区个数，初值为msemaphoreS_MessageNum_Q1;//Q1队列当中的消息数量，初值为nsemaphoreS_MessageNum_Q2;//Q2队列当中的消息数量，初值为070例子：在一栋学生公寓里，只有一间浴室，而且这间浴室非常小，每一次只能容纳一个人。公寓里既住着男生也住着女生，他们不得不分享这间浴室。因此，楼长制定了以下的浴室使用规则：（1）每一次只能有一个人在使用；（2）女生的优先级要高于男生，即如果同时有男生和女生在等待使用浴室，则女生优先；（3）对于相同性别的人来说，采用先来先使用的原则。713.4.3信号量的实现wait和signal操作都必须作为原子操作实现。信号量本身是共享变量，应互斥访问重要程度、使用频繁远比临界段要去高用硬件方法或固件方法都可解决这一问题，而且还有其他解决方法。尽管wait和signal操作执行的时间较短，但因包含了忙--等，故忙--等占用的时间是主要的。

对单处理机系统而言，可以在wait和signal操作期间屏蔽中断，而且这些操作的执行时间相对较短。72C#中的同步方法Lock语句的代码区是临界区lock(myLock){//临界区}Mutex类Mutexmut；mut=newMutex();mut.waitOne();//临界区mut.releaseMutex();Monitor类73回顾：并发问题互斥原因：进程切换不可预测，它取决于其他进程的活动、操作系统处理中断的方式以及操作系统的调度策略。共享变量进程间的相互作用1）进程间相互独立（不察觉）2）进程间通过共享合作（间接察觉）3）进程间通过通信合作（直接察觉）741）进程间相互独立虽然进程间没有数据共享，所做事情也互不联系，但计算机中有些临界资源比如I/O设备、存储器、CPU时间和时钟等等都需要通过竞争得到，你占用的时候就得保证别人没法占用，因此首先得解决这种互斥的需求。要处理好这种临界资源的调度策略，处理不当就有可能发生死锁和饥饿2）进程间通过共享合作进程间虽然执行的过程是相互独立的，互不知道对方的执行情况，但互相之间有共享的数据。因此除了有以上互斥需求和死锁饥饿的可能，另外还会有数据一致性的问题。当多个进程非原子性操作同一个数据时候，互相之间操作时序不当就有可能造成数据不一致3）进程间通过通信合作这种情况下进程间通过消息互相通信，知晓各自的执行情况，不共享任何资源，因此就可以避免互斥和数据不一致问题，但仍然存在死锁和饥饿的问题75使用信号量编写程序的困难

（1）临界区操作的代码以及进入和退出临界区的操作代码，均要由用户编写。 （2）所有wait、signal操作部分都分散在用户编写的各程序代码中，由进程来执行。这样系统无法有效地控制和管理这些wait、signal操作。 （3）用户编程时难免会发生不正确地使用wait、signal操作的错误，这种错误会给系统带来不堪设想的后果（如死锁）；编译程序和操作系统都无法发现和纠正此类错误。

解决思路：封装、信息隐藏763.5管程引入管程的目的：更简便,更可靠地解决进程之间的同步,互斥问题

方法：

为每个共享资源设立一个秘书(管程monitor)；把互斥和资源保护的细节封装在管程的内部，外部程序只需对管程的正确使用就能保证避免并发问题，

773.5.1带信号量的管程管程是一种同步机制，是一组公共数据同与其有关的操作的集合。管程由三部分组成：局部于管程的共享变量说明。对该数据结构进行操作的一组过程。对局部于管程的数据设置初始值的语句。此外，还需为该管程赋予一个名字。面向对象技术中对象的特点783.5.1带信号量的管程管程最主要的特点如下：只能通过管程中的过程，而不能用其他外部过程，访问其局部数据变量。进程通过调用管程的过程而进入管程。每一时刻只能有一个进程在管程中执行，任何其他调用管程的进程将被挂起直至管程可用为止。同步手段： （1）cwait(c):等待操作，调用进程在条件c上挂起，管程可以被其他进程使用。 （2）csignal(c):发信号操作，在条件c上被cwait

挂起的进程被再次执行，如果没有这样的进程就什么都不做。注意：管程的cwait/csignal

操作与信号量中的wait/signal操作不同，如果在管程中的进程发信号并且没有一个进程等待条件变量，这个信号就丢失了。79管程的结构P88图3.7可以把管程想像成具有一个入口点，并保证一次只有一个进程可以进入。其他试图进入管程的进程，加入到挂起等待管程可用的进程队列中。当一个进程在管程中时，它可能会通过发送cwait(x)把自己暂时挂起在条件x上，随后它被放入等待条件改变以重新进入管程的进程队列中.803.5.2用管程解决生产者/消费者问题管程模块控制着缓冲区。管程包括两个条件变量：缓冲区中还有空位置时，变量notfull为true，缓冲区中还有数据存在，变量notempty为true。生产者只能通过管程中的过程append，向缓冲区添加字符，生产者不能直接访问缓冲区。monitorboundedbuffer;

buffer:array[0..N]ofchar;//spaceforNitems

nextin,nextout:integer;//bufferpointers

count:integer;//numberofitemsinbuffer

notfull,notempty:condition;//forsynchronization

begin

nextin:=0;nextout:=0;count:=0;//bufferinitiallyempty

notfull:=true;notempty:=false;

end813.5.2用管程解决生产者/消费者问题procedureappend(x:char);

begin

ifcount=

Nthencwait(notfull);

buffer[nextin]:=x;

nextin:=nextin+1modN;

count:=count+1;

csignal(notempty);

end;

proceduretake(x:char);

begin

Ifcount=0thencwait(notempty);

x:=buffer[nextout];

nextout:=(nextout+1)modN;

count:=count-1;

csignal(notfull);

end;

procedurepreducer;

varx:char;

begin

repeat

produce(x);

append(x);

forever

end;procedureconsumer;

varx:char;

begin

repeat

take(x);

consume(x);

forever

end823.6消息传递当进程互相交互时,必须满足两个基本要求：同步和通信：进程需要同步来实现互斥，进程间的协同需要交换信息.提供这些功能的一种方法是

消息传递

(messagepassing)。

适应性很强，能在分布式系统、共享存储器的多处理机系统以及单处理机系统等不同系统中实现。833.6.1消息传递原语消息传递的实际功能，以一对原语的形式提供:send(destination,message)

Destination可以是进程（直接寻址）或邮箱（间接寻址）。

有两种处理方式:

1,发送者进程被阻塞,直到这个消息被接收到为止.

2,发送者进程不阻塞,继续执行.

receive(source,message)

Source可以是进程（直接寻址）或邮箱（间接寻址）。

有两种处理方式:

1,如果消息在执行receive原语之前发送,则该消息能被接收.

2,如果receive原语没有接收到消息,则选择下列一种方式:

①该进程被阻塞直到一个消息到达

②该进程放弃接收,继续执行

843.6.2用消息传递实现同步 发送者和接受者，按阻塞和非阻塞有三种不同的组合：阻塞发送，阻塞接收： 严格同步方式，发送者和接受者都被阻塞，直到完成信息的传送。称为会合。无阻塞发送，阻塞接收： 最常用的组合方式，发送进程发送消息并再继续操作；接收进程阻塞，直到有消息可用。例如向打印机发送打印请求。无阻塞发送，无阻塞接收：

较常用的组合方式，发送进程发送消息并再继续操作；接收进程接收消息并再继续操作。853.6.3寻址方式Addressing1.直接寻址消息直接由发送方传给接收方：send原语中明确标明了目的进程。receive原语有两种方式：接收进程预先知道发送消息的源进程，不可能预先知道源进程。例如打印服务进程，可以从任何进程接受请求信息。863.6.3寻址方式2.间接寻址

不直接发送，而是先将消息送到共享的数据结构中暂存。暂存的地方是一个共享的数据结构，包括临时存放消息的队列（邮箱式端口）。这种方法有很大的灵活性：1:1;1:n;n:1;n:m。进程与邮箱的关系可以是静态的或动态的;端口通常与一个特定的进程相关联，通常由接收进程产生并为其所有。873.6.4消息格式依赖于：消息系统的用途，消息系统是在单机上运行，还是在分布式系统中运行。较短的定长消息可减小处理和存储的开销，如果有大量的数据需要传递，那么可以将数据存入文件并把文件作为消息传递，变长消息。883.6.4消息格式支持变长消息的操作系统中的消息格式

893.6.5排队规则QueuingDiscipling先进先出基于消息的类型标明消息的优先权；允许接收方检查消息队列并选择要接收的消息。903.6.6用消息传递实现互斥若采用Nonblockingsend,blockingreceive：多个进程共享邮箱mutex，初始化为仅包含一个空消息。当进程申请进入临界区，首先申请从mutex邮箱中接收一条消息：若邮箱空，则该进程阻塞；若进程收到邮箱中的消息，则进入临界区，执行完毕退出，释放邮箱mutex。这样消息就如同令牌一样在进程之间传递。如果仅有一个消息，那么它只可传递给一个进程，其他进程将被阻塞。如果邮箱为空，则所有的进程将被阻塞。当消息可用时，仅有一个阻塞进程被激活并得到消息。

913.6.6用消息传递实现互斥

Programmutualexclusion;ProcedureP(i:integer); constn=…;varmsg:message;Begin(*mainprogram*)Begin Creat-mailbox(mutex);repeat Send(mutex,null);… Parbeginreceive(mutex,msg); P(1);<criticalsection>; P(2);