第2章进程管理2

《第2章进程管理2》由会员分享，可在线阅读，更多相关《第2章进程管理2（116页珍藏版）》请在装配图网上搜索。

1、2.3 进程的进程的同步与通信同步与通信 进程间的联系进程间的联系 进程的同步机制进程的同步机制信号量及信号量及wait-signal操作操作（解决进程同步互斥问题）旧称（解决进程同步互斥问题）旧称P-V操作操作2.3.1 进程同步的基本概念进程同步的基本概念1.进程之间的两种相互制约关系进程之间的两种相互制约关系 进程的并发执行虽然提高了资源利用率进程的并发执行虽然提高了资源利用率,但但由于进程的异步性由于进程的异步性,会给系统造成混乱。为了使会给系统造成混乱。为了使并发执行的各进程都能正确执行并发执行的各进程都能正确执行,使它们之间能使它们之间能有效地共享资源和相互合作有效地共享资源和相互

2、合作,必须研究并发执行必须研究并发执行的各进程之间的相互制约关系的各进程之间的相互制约关系,采取一定的措施采取一定的措施使系统中诸进程有条不紊的使系统中诸进程有条不紊的同步同步向前推进。进向前推进。进程之间有两种相互制约关系：程之间有两种相互制约关系：l 间接相互制约关系间接相互制约关系(资源共享关系资源共享关系)l 直接相互制约关系直接相互制约关系(功能合作关系功能合作关系)1)间接相互制约关系间接相互制约关系(资源共享关系、互斥关系资源共享关系、互斥关系)由于共享资源由于共享资源,使得系统中本来没有逻辑关使得系统中本来没有逻辑关系的进程系的进程,因相互竞争资源而产生了制约关系。因相互竞争资

3、源而产生了制约关系。例如例如:进程进程 P1和和P2在运行中都要使用打印在运行中都要使用打印机机,为了保证各进程输出的完整为了保证各进程输出的完整,打印机必须互打印机必须互斥访问斥访问(独占使用独占使用)。这样。这样,一旦系统将打印机分一旦系统将打印机分配给进程配给进程 P1,进程进程P2就必须等待就必须等待,直到直到P1用完打用完打印机并释放后印机并释放后,P2才能使用。才能使用。这种因共享资源而使并发执行的各进程之这种因共享资源而使并发执行的各进程之间产生的关系间产生的关系,叫做叫做间接制约关系间接制约关系,又叫做又叫做互斥互斥(mutual exclusion)关系关系。这种关系可用这种

4、关系可用“进程进程-资源资源-进程进程”来描述。来描述。2)直接制约关系直接制约关系(相互功能合作关系、同步关系相互功能合作关系、同步关系)通常通常,一个用户作业要涉及一组并发进程一个用户作业要涉及一组并发进程(输输入、计算和输出进程入、计算和输出进程),这些进程必须这些进程必须相互协作相互协作共同完成共同完成这项任务。这项任务。具体说具体说,在运行过程中在运行过程中,某进程可能要在某某进程可能要在某些同步点上等待另一伙伴些同步点上等待另一伙伴(协作进程协作进程)为它提供消为它提供消息息,在未获得消息之前在未获得消息之前,该进程处于等待状态该进程处于等待状态,获获得消息后被唤醒进入就绪态得消息

5、后被唤醒进入就绪态,此后此后,才能继续运才能继续运行。进程间的这种制约关系叫做行。进程间的这种制约关系叫做直接制约关系直接制约关系,又叫又叫同步同步(synchronism)关系关系。这种关系可用这种关系可用“进程进程-进程进程”来描述。来描述。3)进程通讯进程通讯 进程通讯进程通讯,就是指进程之间的信息交换。就是指进程之间的信息交换。处理处理进程的同步与互斥进程的同步与互斥两种两种关系所交换的信息关系所交换的信息量很少量很少，所以将它们称做进程的低级通信。，所以将它们称做进程的低级通信。例例:司机司机 P1 售票员售票员 P2 REPEAT REPEAT 启动启动 关门关门 正常行驶正常行驶

6、 售票售票 到站停到站停 开门开门 UNTIL FALSE UNTIL FALSE 同步与互斥表示了进程之间的相互依赖又相同步与互斥表示了进程之间的相互依赖又相互制约、相互合作又相互竞争的关系互制约、相互合作又相互竞争的关系2.临界资源和临界区临界资源和临界区 进程的互斥是由于共享资源而引起的进程的互斥是由于共享资源而引起的,为描为描述这类情况述这类情况,引入临界资源和临界区的概念。引入临界资源和临界区的概念。临界资源临界资源(互斥资源互斥资源)：critical resource 系统中一次只允许一个进程访问的资源系统中一次只允许一个进程访问的资源;这这些资源既包括些资源既包括I/O设备设备

7、,如打印机等资源如打印机等资源,也包括也包括软件资源软件资源,如共享变量、共享文件等。如共享变量、共享文件等。临界区临界区(互斥区互斥区):critical section 并发执行的进程并发执行的进程中中,访问临界资源的必须互访问临界资源的必须互斥执行的程序段斥执行的程序段叫叫临界区。临界区。临界区临界区分散在每个要分散在每个要并发执行的并发执行的进程中进程中,它它们都对某个共享的数据结构们都对某个共享的数据结构(共享资源共享资源)进行访问进行访问P1:P2:变量变量a是临界资源是临界资源 C1、C2、C3是临界区是临界区 对对a应互斥访问应互斥访问P3:C3)C1)C2)a:=a+1 pr

8、int(a)a:=a+1 print(a)if a 0then a:=a+1else a:=a-1共共 享享 变量变量临界区临界区2 2临界区临界区n n临界区临界区1 1Solution Requirements Mutual Exclusion Only one process can be in the critical section at any time Progress Decision on who enters CS cannot be indefinitely postponed No deadlock Bounded Waiting Bound on#times othe

9、rs can enter CS,while I am waiting No livelock Also efficient(no extra resources),fair,simple,3.同步机制应遵循的原则同步机制应遵循的原则(进入临界区的原则进入临界区的原则)空闲让进：空闲让进：当无进程在临界区时，任何一个有权当无进程在临界区时，任何一个有权 使用临界区的进程可进入。使用临界区的进程可进入。(多中择一多中择一):当没有进程在临界区，而同时有多个当没有进程在临界区，而同时有多个 进程要求进入临界区，只能让其中之一进入进程要求进入临界区，只能让其中之一进入忙则等待：忙则等待：当有进程在临界

10、区时，其它试图进入当有进程在临界区时，其它试图进入 临界区的进程必须等待，即不许两个以上的临界区的进程必须等待，即不许两个以上的 进程同时进入临界区进程同时进入临界区有限等待有限等待：任何进入临界区的要求应在有限的时：任何进入临界区的要求应在有限的时 间内得到满足间内得到满足让权等待：让权等待：处于等待状态的进程应放弃占用处于等待状态的进程应放弃占用CPU 以免进程陷入以免进程陷入“忙等忙等”。硬件硬件 硬件指令硬件指令(原语不可中断原语不可中断)和屏蔽中断两种办法。和屏蔽中断两种办法。软件软件 编程解决编程解决:进入临界区之前附加一段检查的代进入临界区之前附加一段检查的代码码(进入区进入区)

11、,以保证互斥进入以保证互斥进入,在临界区后各附加在临界区后各附加程序程序(退出区退出区)恢复标志恢复标志,表明已从临界区退出表明已从临界区退出,其其它进程可进入。它进程可进入。缺点缺点:需要高的编程技巧需要高的编程技巧,忙等待忙等待。2.3.2 如何解决互斥问题如何解决互斥问题软件解法软件解法(1)var free:boolean;true:临界区空临界区空(初值初值)false:非空非空 proc p(n);每个并发进程每个并发进程 L:if free then begin free:=false;critical section end else goto L;free:=true;问题问

12、题:当当p(i)测试测试free为为true,还未将还未将free改为改为false时时,此时恰好此时恰好p(j)也测试也测试free,其值仍然是其值仍然是true,使使两个进程都进入临界区违反了两个进程都进入临界区违反了忙则等待忙则等待的原则。的原则。begin 主程序主程序 Parbegin p(1)；p(2)；p(n)；parendend；软件解法软件解法(2)var turn:boolean;当当turn=true时时P P可进入临界区可进入临界区,否则否则Q Q可进入临界区可进入临界区 P)Q)repeat until turn;repeat until not turn;criti

13、cal section critical section turn:=flase;turn:=true;问题问题:解决了解决了解法解法(1)的问题的问题,不会使两个进程都不会使两个进程都进入临界区进入临界区,但但P和和Q必须轮流必须轮流进入临界区进入临界区,当当P退退出临界区后出临界区后 turn=flase,此时临界区空闲此时临界区空闲,但但 P不不能再进入临界区能再进入临界区,违反了违反了空闲让进空闲让进的原则。的原则。软件解法：软件解法：(3)var pturn,qturn:boolean;初值为初值为false P进入临界区的条件进入临界区的条件:pturn¬ qturn Q进入

14、临界区的条件进入临界区的条件:not pturn&qturn P)Q)pturn:=true;qturn:=ture;while(qturn)do;while(pturn)do;critical section critical section pturn:=false;qturn:=false .问题问题:似乎解决了似乎解决了解法解法(2)的问题的问题,P和和Q不必轮流进入不必轮流进入临界区临界区,但当但当P和和Q同时执行同时执行 pturn=true;qturn=true;时时,临界区空闲临界区空闲,而而P和和Q都不能进入临界区都不能进入临界区,仍然违反仍然违反空闲让进空闲让进的原则。的原

15、则。软件解法软件解法(4):在解法在解法(3)基础上引入基础上引入turn枚举类型枚举类型(初值任意初值任意)var turn:(p,q)pturn,qturn:boolean;初值为初值为false P等待的条件等待的条件:qturn&turn=p Q等待的条件等待的条件:pturn&turn=q P)Q)pturn:=true;qturn:=ture;turn:=p;turn:=q;while(qturn&turn=p)do;while(pturn&turn=q)do;critical section critical section pturn:=false;qturn:=false .

16、可见软件法可见软件法需要很高的编程技巧需要很高的编程技巧,而且而且“忙等忙等”效率低效率低。var k:boolean;全局变量全局变量k=true表示资源已被占用表示资源已被占用func Lock(var target:boolean):boolean;TestandSetbegin 加锁原语或测试并设置原语不可中断加锁原语或测试并设置原语不可中断 Lock:=target;target:=trueend;proc p(n);每个并发进程每个并发进程 while Lock(k)do;critical section k:=false;开锁开锁 硬件解法硬件解法(1)用硬件指令用硬件指令“测试

17、并设置测试并设置”begin 主程序主程序 k:=false;初值表示资源可用初值表示资源可用 parbegin p(1)；p(2)；p(n)；parendend；var lock:boolean;每组共享定义一个全局变量每组共享定义一个全局变量 function swap(var a,b:boolean);交换指令不可中断交换指令不可中断var temp:boolean;begin temp:=a;a:=b;b:=temp end;proc p;每个并发进程每个并发进程 var key:boolean;定义一个局部变量定义一个局部变量 key:=true;repeat swap(lock,k

18、ey)until key=false;critical section 局部变量局部变量key存储存储lock的原值的原值 lock:=false;硬件解法硬件解法(2)(2)用硬件指令用硬件指令“交换交换”指令指令硬件解法硬件解法(3)(3)“开关中断开关中断”指令指令 CPU从某进程转接到另一进程是由于时钟中从某进程转接到另一进程是由于时钟中断断(时间片到时间片到)或其它中断引起的。当一个进程进或其它中断引起的。当一个进程进入临界区前入临界区前,关闭所有的中断关闭所有的中断,其它进程就不可能其它进程就不可能进入临界区。当进程退出临界区后进入临界区。当进程退出临界区后,再开中断。再开中断。此

19、后要进入临界区的进程就可进入。描述如下：此后要进入临界区的进程就可进入。描述如下：关中断关中断(disable)critical section开中断开中断(enable)开、关中断可以保证各进程互斥地进入临界区。开、关中断可以保证各进程互斥地进入临界区。这种这种方法简单方法简单,但系统要付出但系统要付出较高代价较高代价。缺点是：。缺点是：限制了处理机交叉执行程序的能力。限制了处理机交叉执行程序的能力。2.3.3 信号量机制信号量机制同步机制：同步机制：信号量及信号量及wait-signal操作；管程；条件临界操作；管程；条件临界域；路径表达式等（用于集中式系统中）域；路径表达式等（用于集中式

20、系统中）会合；通信顺序进程；分布进程；远程过会合；通信顺序进程；分布进程；远程过程调用等（适用于分布式系统中）程调用等（适用于分布式系统中）同步机制应满足的基本要求：同步机制应满足的基本要求：描述能力、可以实现、描述能力、可以实现、效率高、效率高、使用方便使用方便信号量信号量(Semaphores)共享资源的使用信号的量共享资源的使用信号的量:1965年荷兰学者年荷兰学者Dijkstra提出信号量机制，提出信号量机制，现已被广泛用于解决各种互斥和同步问题。现已被广泛用于解决各种互斥和同步问题。1.整型信号量：整型信号量：管理控制铁路交通的重要工具是信号灯。利用信号管理控制铁路交通的重要工具是信

21、号灯。利用信号灯的状态灯的状态(颜色颜色)控制火车的通行。单段铁路任何时刻只控制火车的通行。单段铁路任何时刻只允许一列火车通行允许一列火车通行(相当于临界区相当于临界区),遇红灯遇红灯(表示路段被表示路段被占用占用)应等待应等待,遇绿灯可进入遇绿灯可进入(同时红灯亮禁止其它火车同时红灯亮禁止其它火车进入进入),驶出后绿灯亮驶出后绿灯亮,信号灯标志路段资源的占用情况。信号灯标志路段资源的占用情况。为了管理各并发进程对共享资源的使用为了管理各并发进程对共享资源的使用,引入表示引入表示共享资源的使用信号的量共享资源的使用信号的量信号量信号量的概念的概念;它被定义它被定义为一个为一个整型量整型量 S;

22、S0 表示资源可用表示资源可用(无进程在无进程在临界区相当于绿灯亮临界区相当于绿灯亮);某进程企图进入临界区时某进程企图进入临界区时,若若S0允许进入允许进入;信号量信号量 S 只能通过两个只能通过两个标准原子操作标准原子操作(不可中断不可中断)wait(S)和和signal(S)来访问。过来访问。过去它们被称为去它们被称为P-V操作操作,可描述为：可描述为：wait(S)：while S=0 do;有进程在临界区空循环有进程在临界区空循环 S:=S-1;signal(S)：S:=S+1;进入区执行进入区执行wait(S)操作操作,退出区执行退出区执行signal(S),例如例如:var s:

23、integer;s:=1;parbegin p1:begin p2:begin wait(s);wait(s);临界区代码临界区代码 临界区代码临界区代码 signal(s);signal(s);end;end;parendwait(S)操作中操作中,当当S0表示该资源可用的数目表示该资源可用的数目,S.value0 的绝对值表示在该资源的等待链表中已阻塞的绝对值表示在该资源的等待链表中已阻塞进程的数目进程的数目,S.L则为该链队列头指针则为该链队列头指针。若。若S.value初值初值为为1则转化为互斥则转化为互斥信号量。信号量。相应的相应的 wait(S)signal(S)操作可描述为：操作

24、可描述为：procedure wait(s:semaphore);begin s.value:=s.value-1;先减先减1再判断再判断 if s.value0 then block(s.L)end;其中其中:block(s.L)原语是将该进程自我阻塞原语是将该进程自我阻塞,置为等待状置为等待状 态态,并将它的并将它的PCB插到信号量队列插到信号量队列s.L的末尾。的末尾。将来被唤醒后将来被唤醒后,运行应从运行应从wait之后开始。之后开始。procedure signal(s:semaphore);begin s.value:=s.value+1;if s.value=0 then wak

25、eup(s.L)end;s.value=0 表示有等待表示有等待s的进程的进程其中其中:wakeup(s.L)原语是唤醒信号量等待队列原语是唤醒信号量等待队列s.L中的中的 第一个进程第一个进程,将其改为就绪态插入就绪队列。将其改为就绪态插入就绪队列。(等待队列中的进程都已执行过等待队列中的进程都已执行过wait操作操作)P(S)V(S)P(S)V(S)P(S)V(S)互斥区互斥区P1P2Pn利用信号量实现进程之间的互斥利用信号量实现进程之间的互斥 用记录型信号量用记录型信号量S解决解决n个进程互斥地进入临界区个进程互斥地进入临界区的问题的问题,S取值范围是取值范围是+1-(n-1);S的值为

26、负时的值为负时,说明有说明有一个进程正在临界区执行一个进程正在临界区执行,其它欲进入临界区的进程其它欲进入临界区的进程排在等待排在等待S的队列中的队列中,等待的进程数等于信号量值的绝等待的进程数等于信号量值的绝对值。对应于这种互斥信号量的初始值只能为对值。对应于这种互斥信号量的初始值只能为1。var s:semaphore:=1;为表达方便简写为表达方便简写,只写整数部分只写整数部分parbegin 含义是含义是s.value的初值设为的初值设为1 p1:begin p2:begin wait(s);wait(s);临界区代码临界区代码 临界区代码临界区代码 signal(s);signal(

27、s);end;end;p3:p4:parend 若若p2先进入临界区此时先进入临界区此时s=0,p1要进入要进入,执行执行wait(s);自我阻塞插入等待队列此时自我阻塞插入等待队列此时s=-1,之后之后 p4也要进入也要进入,执执行行wait(s);自我阻塞插入等待队列此时自我阻塞插入等待队列此时 s=-2;接着接着 p2出出临界区临界区s=-1,并将并将p1唤醒唤醒,p1就可以进入临界区就可以进入临界区(等待队等待队列中的进程已执行过列中的进程已执行过wait,唤醒后从唤醒后从wait之后继续之后继续)。信号量的使用：信号量的使用：必须置一次且只能必须置一次且只能置一次初值置一次初值,初值

28、不能为负数初值不能为负数 对信号量对信号量S只只允许用允许用wait、signal 操作操作访问访问。wait-signal操作为原语操作操作为原语操作 原语原语(primitive or atomic action)是由若干条机是由若干条机器指令构成的完成某种特定功能的一段程序器指令构成的完成某种特定功能的一段程序,具有不具有不可分割性可分割性,在执行过程中不允许被中断。在执行过程中不允许被中断。原语实现时必须：开关中断原语实现时必须：开关中断3.AND型信号量型信号量 当某进程要先获得多种临界资源后才能执行时当某进程要先获得多种临界资源后才能执行时,容容易处于僵持状态易处于僵持状态(死锁死

29、锁);如果对多种临界资源要么全部如果对多种临界资源要么全部分配到进程分配到进程,要么一种也不分配要么一种也不分配;则可避免死锁的发生。则可避免死锁的发生。为此在为此在wait 操作中增加操作中增加AND条件条件,称之为称之为AND同步机同步机制或同时制或同时wait 操作操作,改名为改名为Swait操作：操作：Swait(S1,S2,Sn)if S11 and and Sn1 then for i:=1 to n do Si:=Si 1 else 自我阻塞自我阻塞,插到第一个插到第一个Si1的队列的队列Si.L,并将程序计数定位到并将程序计数定位到Swait操作的操作的起点起点;相应相应:Ss

30、ignal(S1,S2,Sn)for i:=1 to n do Si:=Si+1;唤醒唤醒Si.L的的所有所有进程进程 4.信号量集信号量集 在记录型信号量机制中，当一次需要在记录型信号量机制中，当一次需要d个某类资源个某类资源时应同时申请时应同时申请d个资源，该类资源的可用数低于某下限个资源，该类资源的可用数低于某下限值值t时不予分配，这样就需要对时不予分配，这样就需要对AND型信号量机制加以型信号量机制加以扩充，形成信号量集机制。扩充，形成信号量集机制。Swait操作如下：操作如下：Swait(S1,t1,d1,Sn,tn,dn)if S1t1 and and Sntn then for

31、i:=1 to n do Si:=Sidi else 自我阻塞自我阻塞,插到第一个插到第一个Si=1时时,允许多进程进入临界允许多进程进入临界区区,S=0时阻止所有进程进入临界区时阻止所有进程进入临界区,相当于一个开关。相当于一个开关。几种几种信号量的信号量的对比对比:记录型信号量记录型信号量 整型整型信号量信号量 有有等待队列等待队列 无无等待队列等待队列 wait操作操作先减后判断先减后判断 wait操作操作先判断后减先判断后减 无资源则无资源则自我阻塞自我阻塞 无资源则无资源则“忙等忙等”signal操作释放资源后操作释放资源后 signal操作释放资源后操作释放资源后 有等待进程则有等

32、待进程则唤醒唤醒 无唤醒无唤醒操作操作有何差别有何差别?记录型信号量记录型信号量 一般信号量集一般信号量集 一种资源一种资源 多种资源多种资源 每次申请每次申请一个一个 每次每种申请每次每种申请di个个少于少于1个个不分配不分配 少于少于ti个个不分配不分配先减后判断先减后判断 先判断后减先判断后减自我阻塞后程序计数定自我阻塞后程序计数定 自我阻塞后程序计数定自我阻塞后程序计数定 位到位到wait()操作之后操作之后 位到位到Swait()操作的起点操作的起点 signal唤醒第一个进程唤醒第一个进程 Ssignal唤醒各种唤醒各种-所有所有 记录型信号量记录型信号量 AND信号量信号量 一种

33、一种资源资源 多种多种资源资源 先减先减后判断后判断 先判断先判断后减后减自我阻塞后程序计数定自我阻塞后程序计数定 自我阻塞后程序计数定自我阻塞后程序计数定 位到位到wait()操作操作之后之后 位到位到Swait()操作的操作的起点起点 signal唤醒唤醒第一个第一个进程进程 Ssignal唤醒唤醒各种各种-所有所有【习题】P68 18,19,212.3.4 信号量应用信号量应用1.利用信号量实现前趋关系利用信号量实现前趋关系 当进程当进程P1中有语句中有语句S1,进程进程P2中有语句中有语句S2两个并两个并发执行希望发执行希望S1执行后再执行执行后再执行S2,要实现这种前趋关系要实现这种

34、前趋关系只需共享一个公用信号量只需共享一个公用信号量S并赋初值并赋初值0,将将signal(S)放在放在语句语句S1后后,而在而在S2之前插入之前插入wait(S)。即。即:P1:S1;signal(S);P2:wait(S);S2;用多个信号量用多个信号量可实现右边前趋图可实现右边前趋图表示的前趋关系表示的前趋关系:S1S3S5S2S4S6var a,b,c,d,e,f,g:semaphore:=0,0,0,0,0,0,0;见见p 45parbegin begin s1;signal(a);signal(b);end;begin wait(a);s2;signal(c);signal(d);

35、end;begin wait(b);s3;signal(e);end;begin wait(c);s4;signal(f);end;begin wait(d);s5;signal(g);end;begin wait(e);wait(f);wait(g);s6;end;parendS1S3S5S2S4S6abdcegf司机进程司机进程:REPEAT启动启动驾驶驾驶停车停车UNTIL 售票员进程售票员进程:REPEAT关门关门售票售票开门开门UNTIL 2.用信号量的用信号量的wait-signal操作操作 解决司机售票员的同步问题解决司机售票员的同步问题 司机启动必须在售票员关门之后司机启动必须

36、在售票员关门之后,用信号量用信号量s1实现实现,售票员开门又必须在司机停车之后售票员开门又必须在司机停车之后,用信号量用信号量s2来实来实现现,初始状态初始状态:车停在车站车停在车站,车门打开着。车门打开着。Var s1,s2:semaphore:=0,0;司机进程司机进程:REPEAT wait(s1);启动启动驾驶驾驶停车停车 signal(s2);UNTIL 售票员进程售票员进程:REPEAT关门关门 signal(s1);售票售票 wait(s2);开门开门UNTIL 3.信号量和信号量和wait-signal操作讨论操作讨论1)信号量的物理含义：信号量的物理含义：S0表示有表示有S个

37、资源可用个资源可用S=0表示无资源可用表示无资源可用S0 时时生产者生产者进程进程(Pp)才能送产品到缓才能送产品到缓冲区冲区;同样同样,只有当只有当S20时时消费者消费者进程进程(Pc)才能从缓冲才能从缓冲区取产品。区取产品。生产者生产者消费者消费者进程间的同步算法如下进程间的同步算法如下:Pc：Pp：Repeat Repeat 生产一个产品；生产一个产品；wait(s2);wait(s1);从缓冲区取产品；从缓冲区取产品；送产品到缓冲区；送产品到缓冲区；signal(s1);signal(s2);消费产品消费产品Until false;Until false;2.n个缓冲区的同步：个缓冲区

38、的同步：s1用来表示空缓冲区个数初值为用来表示空缓冲区个数初值为n;s2用来表示装用来表示装有产品的缓冲个数有产品的缓冲个数,其初始值为其初始值为0。n缓冲区的缓冲区的生产者生产者消费者消费者进程之间的同步算法如下：进程之间的同步算法如下：Var in:=0;out:=0；Pp：Pc：Repeat Repeat 生产产品；生产产品；wait(s2)；wait(s1)；从从Bufferout取产品取产品;往往Buffer in中放产品；中放产品；signal(s1)；signal(s2)；out:=(out+1)mod n；in:=(in+1)mod n；消费产品；消费产品；Until fals

39、e;Until false;要不要对缓冲区要不要对缓冲区(临界临界资源资源)进行互斥操作？进行互斥操作？3.多个生产者和多个多个生产者和多个消费者消费者进程并发进程并发 当有多个生产者进程和多个当有多个生产者进程和多个消费者消费者进程并进程并发执行时发执行时,由于缓冲区由于缓冲区Bufferin和和Bufferout以及以及 in和和out 都是临界资源所以要对它们进行都是临界资源所以要对它们进行互斥操作。互斥操作。可利用互斥信号量可利用互斥信号量s0实现诸进程对缓冲区实现诸进程对缓冲区的互斥操作。此时的互斥操作。此时,n缓冲区的缓冲区的生生进程进程消费者消费者进程之间的同步算法如下：进程之间

40、的同步算法如下：Var s0,s1,s2:semaphore:=1,n,0;信号量信号量p 46 Buffer:array0.n-1 of item;临界资源临界资源 in,out:integer:=0,0;是临界资源不是信号量是临界资源不是信号量 PPi：PCi：Repeat Repeat 生产产品；生产产品；wait(s2)；wait(s1)；wait(s0)；wait(s0)；从从Bufferout取产品取产品;往往Bufferin中放产品；中放产品；out:=(out+1)mod n;in:=(in+1)mod n;signal(s0);signal(s0);signal(s1);si

41、gnal(s2);消费产品；消费产品；Until false;Until false;次序不能颠倒次序不能颠倒 次序不能颠倒次序不能颠倒 Swait(s1,s0)Swait(s2,s0)Ssignal(s0,s2)Ssignal(s0,s1)利用利用AND信号量机制信号量机制生产者生产者消费者消费者进程的互进程的互斥信号量斥信号量s0能否各用一个能否各用一个2.3.3.哲学家就餐问题哲学家就餐问题 五个哲学家围坐在一圆桌旁五个哲学家围坐在一圆桌旁,桌中央有一盘通心桌中央有一盘通心粉粉,每人面前有一只空盘子每人面前有一只空盘子,每两人之间放一只筷子。每两人之间放一只筷子。每个人的行为是思考每个人

42、的行为是思考,感到饥饿感到饥饿,然后吃通心粉。然后吃通心粉。为了吃通心粉为了吃通心粉,每个人必须拿到两只筷子每个人必须拿到两只筷子,并且并且每个人只能直接从自己的左边或右边去取筷子。每个人只能直接从自己的左边或右边去取筷子。var c:array0.4 of semphore:=(1,1,1,1,1);process i Repeat 思考；思考；wait(ci);wait(c(i+1)mod 5);进食；进食；signal(ci);signal(c(i+1)mod 5);Until false;0321414320 当每人都已取到左筷子要取右筷子时发生死锁。当每人都已取到左筷子要取右筷子时发

43、生死锁。为防止死锁发生可采取的几种措施：为防止死锁发生可采取的几种措施：1)最多允许最多允许4个哲学家同时坐在桌子周围。个哲学家同时坐在桌子周围。2)仅当一个哲学家左右两边的筷子都可用时仅当一个哲学家左右两边的筷子都可用时,才允才允许他拿筷子。利用许他拿筷子。利用AND信号量机制。信号量机制。var c:array0.4 of semphore:=(1,1,1,1,1);process iRepeat 思考；思考；Swait(ci,c(i+1)mod 5)；进食；进食；Ssignal(ci,c(i+1)mod 5)；Until false;03214143203)规定奇数号哲学家先拿右边的再拿

44、左边的规定奇数号哲学家先拿右边的再拿左边的,偶偶数号哲学家相反数号哲学家相反;1,2号哲学家先竞争号哲学家先竞争2号筷号筷;3,4号哲学家先竞争号哲学家先竞争4号筷号筷;0号先拿号先拿0号筷。号筷。var c:array0.4 of semphore:=(1,1,1,1,1);process i;i=2*k process i;i=2*k-1 Repeat Repeat 思考思考;思考思考;wait(ci);wait(ci+1);wait(c(i+1)mod 5);wait(ci);进食进食;进食进食;signal(c(i+1)mod 5);signal(ci);signal(ci);sign

45、al(ci+1);Until false;Until false;0 1 2 3 4 0 1 2 3 42.4.3.读者写者问题读者写者问题有两组并发进程有两组并发进程:读者和写者读者和写者,共享一组数据区共享一组数据区,为了保证读为了保证读写的正确性和数据的一致性写的正确性和数据的一致性要求：要求：当有读者进程读文件时当有读者进程读文件时,不允许任何写者不允许任何写者进程写，但允许多读者同时读进程写，但允许多读者同时读 当有写者进程写时当有写者进程写时,不允许任何其它写者不允许任何其它写者进程写进程写,也不允许任何读者进行读。也不允许任何读者进行读。(或要求或要求:)不允许读者、写者同时操作

46、不允许读者、写者同时操作 不允许多个写者同时操作不允许多个写者同时操作1.利用记录型信号量解决读者利用记录型信号量解决读者写者问题写者问题为了解决读者为了解决读者写者问题写者问题,需设置两个信号量：需设置两个信号量：(1)读互斥信号量读互斥信号量rs,用于使读者互斥地访问用于使读者互斥地访问共享变量共享变量n,这里这里n是记录有多少读者正在读是记录有多少读者正在读;(2)写互斥信号量写互斥信号量ws,用于实现读写互斥和写用于实现读写互斥和写写互斥地访问共享文件。读者写互斥地访问共享文件。读者写者问题进行写者问题进行如下描述：如下描述：读者：读者：Repeatwait(rs);if n=0 th

47、en wait(ws);n:=n+1;signal(rs);读读wait(rs);n:=n-1;if n=0 then signal(ws);signal(rs);Until false写者：写者：Repeat wait(ws);写写 signal(ws);Until falseVar rs,ws:semaphore:=1,1;读读,读读-写写-写互斥信号量写互斥信号量 n:integer:=0;读进程数读进程数n是临界资源不是信号量是临界资源不是信号量 读者：读者：RepeatSwait(L,1,1);Swait(mx,1,0);读操作读操作;Ssignal(L,1);Until false

48、写者：写者：Repeat Swait(mx,1,1,L,RN,0);写操作写操作;Ssignal(mx,1);Until false2.利用信号量集机制解决读者利用信号量集机制解决读者写者问题写者问题(p50)增加限制增加限制,最多只允许最多只允许RN个读者同时读个读者同时读;增加信号增加信号量量L其初值为其初值为RN;每个读者进入时每个读者进入时,执行执行Swait(L,1,1)操操作使作使L减减1,读者数增到读者数增到RN时时L=0,读者数再增读者数再增1时被阻塞。时被阻塞。Var L,mx:semaphore:=RN,1;信号量信号量 无写者无写者mx=1,任何任何读者都可进入读者都可进

49、入无写者无写者mx=1,又无又无读者读者L=RN才可进才可进【作业】p68 22,23,24,26思考题思考题:1.消息缓冲问题。消息缓冲问题。消息缓冲区为消息缓冲区为k个个,有有m个发送进程个发送进程,n个接收进个接收进程程,每个接收进程对发送来的消息都必须取一次。每个接收进程对发送来的消息都必须取一次。2.理发师睡觉问题理发师睡觉问题 理发店里有一位理发师理发店里有一位理发师,一把理发椅和一把理发椅和N把供把供等候理发的顾客坐的椅子。等候理发的顾客坐的椅子。如果没有顾客如果没有顾客,则理发师便在理发椅上睡觉。则理发师便在理发椅上睡觉。当一个顾客到来时当一个顾客到来时,他必须先唤醒理发师。他

50、必须先唤醒理发师。如果顾客到来时理发师正在理发如果顾客到来时理发师正在理发,则如果有空则如果有空椅子椅子,可坐下来等可坐下来等;否则离开。否则离开。注意注意:顾客和理发师的顾客和理发师的理发动作理发动作是同时的是同时的semphore c=0;/等候的顾客数等候的顾客数semphore b=0;/可理发师数可理发师数,b0时时|b|=等理发顾客数等理发顾客数semphore m=0;/互斥信号量互斥信号量int c0=0;/等候的顾客数等候的顾客数,临界资源临界资源ba()while(true)wait(c);wait(m);c0-;signal(m);signal(b);理发理发;cui()

51、wait(m);if(c0N)c0+;signal(m);signal(c);wait(b);理发理发;else signal(m);main()cobegin ba();cu1();cu2();coend Sleeping Barber ProblemOne SolutionBarberP(customer);/*cut hair*/V(barber);Shared:semaphore customer,barber;int waiting;Init:customer=0;barber=1;waiting=0;Customer/*get haircut*/V(customer);P(barb

52、er);One SolutionBarberdo P(customer);P(mutex);waiting-;/*cut hair*/V(mutex);V(barber);while(true);Shared:semaphore customer,barber;int waiting;Init:customer=0;barber=1;waiting=0;CustomerP(mutex);if(waiting=n then nf.wait;满则等待满则等待bufferin:=nextp;in:=(in+1)mod n;count:=count+1;if ne.queue then ne.sign

53、al;消费者队非空则唤醒消费者队非空则唤醒end;proceduer entry get(item);从缓冲区取产品过程从缓冲区取产品过程beginif count=0 then ne.wait;空则等待空则等待nextc:=bufferout;out:=(out+1)mod n;count:=count-1;if nf.queue then nf.signal;生产者队非空则唤醒生产者队非空则唤醒end;管程和进程的异同点：管程和进程的异同点：（1）设置进程和管程的目的不同）设置进程和管程的目的不同（2）系统管理数据结构）系统管理数据结构 进程：进程：PCB 管程：等待队列管程：等待队列（3

54、）管程被进程调用）管程被进程调用（4）管程是操作系统的固有成分，无创建和撤消）管程是操作系统的固有成分，无创建和撤消2.6 进程通信进程通信 2.6.1 概述概述 利用信号量的利用信号量的 wait-signal 操作实现进程的互斥和操作实现进程的互斥和同步是进程间的低级通讯同步是进程间的低级通讯;在进程互斥中在进程互斥中,进程通过修进程通过修改信号量相互表明临界资源是否可用改信号量相互表明临界资源是否可用;在进程同步中在进程同步中,信号量相互表明配合信息非常有效信号量相互表明配合信息非常有效;但作为通信工具但作为通信工具,则不够理想。则不够理想。wait-signal操作为低级通讯原语操作为

55、低级通讯原语,每次只每次只能传递简单的信号能传递简单的信号,效率低效率低,而且通信对用户而且通信对用户不透明不透明,实现起来比较麻烦实现起来比较麻烦,不适合于传递交换大量信息。不适合于传递交换大量信息。若要在进程间传递大量信息若要在进程间传递大量信息,可直接利用系统提供可直接利用系统提供的一组通信命令来实现进程的高级通讯原语的一组通信命令来实现进程的高级通讯原语,它们隐藏它们隐藏了进程通讯的实现细节了进程通讯的实现细节,通信对用户是透明的通信对用户是透明的,是是高效高效方便方便的专用通信方式。的专用通信方式。进程通信的方式进程通信的方式1.共享内存系统共享内存系统(Shared-Memory

56、System)相互通信的进程间共享某些数据结构或共享存储相互通信的进程间共享某些数据结构或共享存储区区,进程之间通过它们进行通信。进程之间通过它们进行通信。1)诸进程共享某些数据结构诸进程共享某些数据结构(数组数组,有界缓冲区等有界缓冲区等)数据结构的设置和同步处理都是由用户来完成的数据结构的设置和同步处理都是由用户来完成的,增增加了用户的负担加了用户的负担,效率低效率低,仅用于传递少量数据。仅用于传递少量数据。2)诸进程共享存储区诸进程共享存储区(数据量大数据量大),进程向系统申请进程向系统申请共享存储区中的一个分区共享存储区中的一个分区,并指定该分区的关键字并指定该分区的关键字,并并将该分

57、区连接到本进程上对其进行写。另一进程可根将该分区连接到本进程上对其进行写。另一进程可根据关键字将该分区连接到自己之上对其进行读据关键字将该分区连接到自己之上对其进行读/写写,通通过同一分区的读过同一分区的读/写写,实现两进程间的信息交换。实现两进程间的信息交换。2.消息传递系统消息传递系统(Message passing system)3.管道管道(Pipe)通信通信共享文件模式共享文件模式消息传递系统消息传递系统(Message passing system)以格式化的消息以格式化的消息(message)为通信单位为通信单位;利用系统利用系统为进程提供的两个高级通讯原语为进程提供的两个高级通

58、讯原语 send和和receive 进行进行通信。隐藏了通讯的实现细节通信。隐藏了通讯的实现细节,对用户是对用户是透明的透明的,使使用非常用非常方便方便,是使用最广泛的进程通信机制。是使用最广泛的进程通信机制。send：当要进行消息传递时执行：当要进行消息传递时执行 send receive：当接收者要接收消息时执行：当接收者要接收消息时执行 receive 消息传递系统可分为直接方式和间接方式。消息传递系统可分为直接方式和间接方式。2.6.2 消息传递通信的实现方法消息传递通信的实现方法1.直接通信方式：直接通信方式：发送进程直接发消息给接收进程发送进程直接发消息给接收进程,要求指明对方名字

59、要求指明对方名字 发送原语发送原语:Send(Receiver,message)接收原语接收原语:Receive(Sender,message)有时接收者要接收多个消息有时接收者要接收多个消息,事先不知道发送者。事先不知道发送者。接收改为接收改为:Receive(id,message)id返回发送进程名返回发送进程名2.间接方式间接方式(信箱通信信箱通信)：发消息时不指定接收进程的名字发消息时不指定接收进程的名字,而是指定一个中而是指定一个中间媒介间媒介,即信箱。进程间通过信箱实现通信即信箱。进程间通过信箱实现通信,既可以实既可以实现实时通信现实时通信,又可以实现非实时通信。又可以实现非实时通

60、信。原语原语:Send(MB,message);Receive(MB,message)信箱可分为由操作系统创建的公用信箱和由用户进信箱可分为由操作系统创建的公用信箱和由用户进程创建的程创建的 私用信箱、共享信箱。私用信箱、共享信箱。发送进程和接收进程间存在发送进程和接收进程间存在4种关系种关系:一对一一对一(专用专用),多对一多对一(客客/服服),多对多多对多(公公),一对多一对多(广播广播)。2.6.3 通信链路、消息格式和同步方式通信链路、消息格式和同步方式1.通信链路通信链路：建立通信链路方式：建立通信链路方式：先用显式先用显式“建立连接建立连接”命令建立通信链路命令建立通信链路,再通信

61、再通信,用用 完后可以显式方式拆除链路完后可以显式方式拆除链路,用在计算机网络中。用在计算机网络中。发送原语执行时系统自动连接发送原语执行时系统自动连接,用在单机系统中。用在单机系统中。链路连接方式链路连接方式:点点点点,多点多点 通信方式通信方式:单工单工,双工双工2.消息格式消息格式 消息头消息头:源和目的进程名源和目的进程名,消息类型长度编号消息类型长度编号,日期时间日期时间 消息正文消息正文:消息的实际内容消息的实际内容3.同步方式同步方式 紧密同步紧密同步(汇合汇合):无缓冲无缓冲,收发进程收发完后都被阻塞收发进程收发完后都被阻塞 平时接收进程阻塞平时接收进程阻塞:发送进程发消息时将

62、接收进程唤醒发送进程发消息时将接收进程唤醒 平时都不阻塞平时都不阻塞:只有当收发消息无法继续时才自我阻塞只有当收发消息无法继续时才自我阻塞2.6.4 消息缓冲队列通信机制：消息缓冲队列通信机制：由美国由美国Hansan提出提出,被广泛用于本地进程之间的通被广泛用于本地进程之间的通信信,发进程用发进程用send原语发送原语发送,收进程用收进程用receive原语接收。原语接收。1.数据结构：数据结构：Type MesBuf=record 消息缓冲区类型消息缓冲区类型 sender;发送者发送者 size;消息长度消息长度 text;消息正文消息正文 next;指向下一缓冲区的指针指向下一缓冲区的

63、指针 end;Type PCBlock=record PCB中增加通信的数据项中增加通信的数据项 mq;消息队列首指针消息队列首指针 mutex;消息队列互斥信号量消息队列互斥信号量 sm;消息队列资源信号量消息队列资源信号量 end;.send(B,m).sender:Asize:长度长度text:正文正文m发发送送区区进程进程A进程进程B.receive(A,B,n).sender:Asize:长度长度text:正文正文n接接收收区区PCB(B).mqmutexsmsender:Asize:长度长度text:正文正文 next:对称方式对称方式:发送者和接收者都知道对方的名字发送者和接收者

64、都知道对方的名字.send(B,m).sender:Asize:长度长度text:正文正文m发发送送区区进程进程A进程进程B.receive(B,n).sender:Asize:长度长度text:正文正文n接接收收区区PCB(B).mqmutexsmsender:Asize:长度长度text:正文正文 next:实际常用非对称方式实际常用非对称方式,接收前接收前,接收方不必知道发送方接收方不必知道发送方的名字的名字,接收到消息后从消息头才知道对方的名字。接收到消息后从消息头才知道对方的名字。2.Send原语原语:在操作系统空间设置一组缓冲区在操作系统空间设置一组缓冲区,当发送进程需要当发送进程

65、需要发送消息之前发送消息之前,先把待发送的消息正文和其它相关信息先把待发送的消息正文和其它相关信息填入在自己内存空间中设置的发送区填入在自己内存空间中设置的发送区a,然后调用发送原然后调用发送原语语send系统调用系统调用,产生自愿性中断产生自愿性中断,进入核心态进入核心态,OS按发按发送区送区a中所设的消息长度中所设的消息长度a.size为发送进程分配一个空缓为发送进程分配一个空缓冲区冲区,再将所发送的消息从发送区再将所发送的消息从发送区 copy到缓冲区中到缓冲区中,然然后后,将该载有消息的缓冲区链接到接收进程的消息链队将该载有消息的缓冲区链接到接收进程的消息链队列尾列尾,完成发送过程。之

66、后完成发送过程。之后,返回到用户态继续执行。返回到用户态继续执行。缓冲区和消息队列都是临界资源缓冲区和消息队列都是临界资源,分配空缓冲区要分配空缓冲区要用用wait-signal操作实现互斥操作实现互斥,对消息链队列修改时也要对消息链队列修改时也要用用wait-signal操作。操作。Send中要访问临界资源需用中要访问临界资源需用wait-signal操作操作:Procedure Send(r,a);r为接收进程为接收进程,a为发送区为发送区Begin getbuf(a.size,i);申请申请a.size大小的空缓冲区大小的空缓冲区i getbuf()中已用中已用wait-signal实现互斥实现互斥 i.sender:=a.sender;把消息从把消息从a处处copy到空缓冲区到空缓冲区i;i.size:=a.size;i.text:=a.text;i.next:=0;getid(PCBset,r,j);根据根据r获接收进程内部标识符获接收进程内部标识符jwait(j.mutex);insert(j.mq,i);把缓冲区把缓冲区i挂到接收进程挂到接收进程r的消息链尾的消息链尾si