第2章进程管理2ppt课件

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

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

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

4、ion)关系。关系。 这种关系可用这种关系可用“进程进程-资源资源-进程来描画。进程来描画。2)直接制约关系直接制约关系(相互功能协作关系、同步关系相互功能协作关系、同步关系) 通常通常, 一个用户作业要涉及一组并发进程一个用户作业要涉及一组并发进程(输输入、计算和输出进程入、计算和输出进程), 这些进程必需相互协作这些进程必需相互协作共同完成这项义务。共同完成这项义务。 详细说详细说, 在运转过程中在运转过程中, 某进程能够要在某某进程能够要在某些同步点上等待另一同伴些同步点上等待另一同伴(协作进程协作进程)为它提供音为它提供音讯讯, 在未获得音讯之前在未获得音讯之前, 该进程处于等待形状该

5、进程处于等待形状, 获获得音讯后被唤醒进入就绪态得音讯后被唤醒进入就绪态, 以后以后, 才干继续运才干继续运转。进程间的这种制约关系叫做直接制约关系转。进程间的这种制约关系叫做直接制约关系, 又叫同步又叫同步(synchronism)关系。关系。 这种关系可用这种关系可用“进程进程-进程来描画。进程来描画。3) 进程通讯进程通讯 进程通讯进程通讯, 就是指进程之间的信息交换。就是指进程之间的信息交换。处置进程的同步与互斥两种关系所交换的信息处置进程的同步与互斥两种关系所交换的信息量很少，所以将它们称做进程的低级通讯。量很少，所以将它们称做进程的低级通讯。例例: 司机司机 P1 售票员售票员 P

6、2 REPEAT REPEAT 启动启动 关门关门 正常行驶正常行驶 售票售票 到站停到站停 开门开门 UNTIL FALSE UNTIL FALSE 同步与互斥表示了进程之间的相互依赖又相同步与互斥表示了进程之间的相互依赖又相互制约、相互协作又相互竞争的关系互制约、相互协作又相互竞争的关系2. 临界资源和临界区临界资源和临界区 进程的互斥是由于共享资源而引起的进程的互斥是由于共享资源而引起的, 为描为描画这类情况画这类情况, 引入临界资源和临界区的概念。引入临界资源和临界区的概念。临界资源临界资源(互斥资源互斥资源)：critical resource 系统中一次只允许一个进程访问的资源系统

7、中一次只允许一个进程访问的资源; 这这些资源既包括些资源既包括I/O设备设备, 如打印机等资源如打印机等资源, 也包括也包括软件资源软件资源, 如共享变量、共享文件等。如共享变量、共享文件等。临界区临界区(互斥区互斥区): critical section 并发执行的进程中并发执行的进程中, 访问临界资源的必需互访问临界资源的必需互斥执行的程序段叫临界区。斥执行的程序段叫临界区。 临界区分散在每个要并发执行的进程中临界区分散在每个要并发执行的进程中, 它它们都对某个共享的数据构造们都对某个共享的数据构造(共享资源共享资源)进展访问进展访问P1 :P2 : 变量变量a是临界资源是临界资源 C1、

8、C2、C3是临界区是临界区 对对a应互斥访问应互斥访问P3 :C3 )C1 )C2 )a := a +1 print (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 indefi

9、nitely postponed No deadlock Bounded Waiting Bound on #times others 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); 每个并发

12、进程每个并发进程 L: if free then begin free:= false; critical section end else goto L; free:=true; 问题问题: 当当p(i)测试测试free为为true, 还未将还未将free改为改为false时时, 此时恰好此时恰好p(j)也测试也测试free, 其值依然是其值依然是true, 使使两个进程都进入临界区违反了忙那么等待的原那两个进程都进入临界区违反了忙那么等待的原那么。么。begin 主程序主程序 Parbegin p(1)；p(2)；p(n)； parendend；软件解法软件解法 (2) var turn:

13、 boolean; 当当turn=true时时P可进入临界区可进入临界区,否那么否那么Q可进可进入临界区入临界区 P) Q) repeat until turn; repeat until not turn; critical section critical section turn:=flase; turn:=true; 问题问题: 处理了解法处理了解法 (1) 的问题的问题,不会使两个进程都不会使两个进程都进入临界区进入临界区,但但P和和Q必需轮番进入临界区必需轮番进入临界区,当当P退退出临界区后出临界区后 turn=flase, 此时临界区空闲此时临界区空闲, 但但 P不不能再进入临界

14、区能再进入临界区, 违反了空闲让进的原那么。违反了空闲让进的原那么。 软件解法：软件解法：(3) var pturn,qturn: boolean;初值为初值为false P进入临界区的条件进入临界区的条件: pturn & not qturn Q进入临界区的条件进入临界区的条件: not pturn & qturn P) Q) pturn:=true; qturn:=ture; while(qturn) do ; while(pturn) do ; critical section critical section pturn:=false; qturn:=false . .问题问题: 似乎

15、处理了解法似乎处理了解法 (2)的问题的问题, P和和Q不用轮番进入不用轮番进入临界区临界区, 但当但当P和和Q同时执行同时执行 pturn=true; qturn=true;时时, 临界区空闲临界区空闲, 而而P和和Q都不能进入临界区都不能进入临界区, 依然违反依然违反空闲让进的原那么。空闲让进的原那么。 软件解法软件解法(4) : 在解法在解法(3)根底上引入根底上引入turn枚举类型枚举类型(初值恣意初值恣意) var turn: (p,q) pturn,qturn: boolean;初值为初值为false P等待的条件等待的条件: qturn & turn=p Q等待的条件等待的条件:

16、 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 . . 可见软件法需求很高的编程技巧可见软件法需求很高的编程技巧,而且而且“忙等效忙等效率低率低 。var k:boolean; 全局变量全局变量k=true表示资源已被占用表示资源已被占用func Lock(var target:boole

17、an):boolean; TestandSetbegin 加锁原语或测试并设置原语不可中断加锁原语或测试并设置原语不可中断 Lock :=target; target:=trueend;proc p(n); 每个并发进程每个并发进程 while Lock(k) do ; critical section k:=false; 开锁开锁 硬件解法硬件解法 (1) 用硬件指令用硬件指令“测试并设置测试并设置begin 主程序主程序 k:=false ; 初值表示资源可用初值表示资源可用 parbegin p(1)；p(2)；p(n)； parendend；var lock:boolean; 每组共享

18、定义一个全局变量每组共享定义一个全局变量 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, key) until key=false; critical section 部分变量部分变量key存储存储lock的原值的原值 lock:=false; 硬件解法硬件解法(2)(2)用硬件指令

19、用硬件指令“交换指令交换指令硬件解法硬件解法(3)(3)“开关中断指令开关中断指令 CPU从某进程转接到另一进程是由于时钟中从某进程转接到另一进程是由于时钟中断断(时间片到时间片到) 或其它中断引起的。当一个进程进或其它中断引起的。当一个进程进入临界区前入临界区前, 封锁一切的中断封锁一切的中断, 其它进程就不能够其它进程就不能够进入临界区。当进程退出临界区后进入临界区。当进程退出临界区后, 再开中断。再开中断。以后要进入临界区的进程就可进入。描画如下：以后要进入临界区的进程就可进入。描画如下：关中断关中断(disable) critical section开中断开中断(enable) 开、关

20、中断可以保证各进程互斥地进入临界区。开、关中断可以保证各进程互斥地进入临界区。这种方法简单这种方法简单, 但系统要付出较高代价。缺陷是：但系统要付出较高代价。缺陷是：限制了处置机交叉执行程序的才干。限制了处置机交叉执行程序的才干。2.3.3 信号量机制信号量机制同步机制：同步机制： 信号量及信号量及wait-signal操作；管程；条件临界操作；管程；条件临界域；途径表达式等用于集中式系统中域；途径表达式等用于集中式系统中 会合；通讯顺序进程；分布进程；远程过会合；通讯顺序进程；分布进程；远程过程调用等适用于分布式系统中程调用等适用于分布式系统中同步机制应满足的根本要求：同步机制应满足的根本要

21、求： 描画才干、可以实现、描画才干、可以实现、 效率高、效率高、 运用方便运用方便信号量信号量(Semaphores)共享资源的运用信号的量共享资源的运用信号的量: 1965年荷兰学者年荷兰学者Dijkstra提出信号量机制，提出信号量机制，现已被广泛用于处理各种互斥和同步问题。现已被广泛用于处理各种互斥和同步问题。1. 整型信号量：整型信号量： 管理控制铁路交通的重要工具是信号灯。利管理控制铁路交通的重要工具是信号灯。利用信号灯的形状用信号灯的形状(颜色颜色)控制火车的通行。单段铁控制火车的通行。单段铁路任何时辰只允许一列火车通行路任何时辰只允许一列火车通行(相当于临界区相当于临界区), 遇

22、红灯遇红灯(表示路段被占用表示路段被占用)应等待应等待, 遇绿灯可进入遇绿灯可进入 (同时红灯亮制止其它火车进入同时红灯亮制止其它火车进入), 驶出后绿灯亮驶出后绿灯亮,信号灯标志路段资源的占用情况。信号灯标志路段资源的占用情况。 为了管理各并发进程对共享资源的运用为了管理各并发进程对共享资源的运用, 引引入表示共享资源的运用信号的量入表示共享资源的运用信号的量信号量的概信号量的概念念; 它被定义为一个整型量它被定义为一个整型量 S; S0 表示资源可用表示资源可用 (无进程在临界区相当于绿灯亮无进程在临界区相当于绿灯亮); 某进程企图进入临界区时某进程企图进入临界区时, 假设假设S0允许进入

23、允许进入; 信号量信号量 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:integer; s:=1;parbegin p1: begin p2: begin wait(s); wait(s); 临界区代码临界区

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

25、.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 wakeup(s.L)end; s.value =0 表示有等待表示有等待s

26、的进程的进程其中其中: 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的值为负时的值为负时, 阐明有阐明有一个进程正在临界区执行一

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

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

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

30、于僵持形状(死锁死锁); 假设对多种临界假设对多种临界资源要么全部分配到进程资源要么全部分配到进程, 要么一种也不分配要么一种也不分配; 那么可防止死锁的发生。为此在那么可防止死锁的发生。为此在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, 并将程序计数定位到并将程序计数定位到Sw

31、ait操作的起点操作的起点;相应相应: Ssignal(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,

32、dn) if S1t1 and and Sntn then for i:=1 to n do Si:= Sidi else 自我阻塞自我阻塞, 插到第一个插到第一个Si=1时时, 允许多进程进允许多进程进入临界区入临界区, S=0时阻止一切进程进入临界区时阻止一切进程进入临界区, 相当相当于一个开关。于一个开关。几种信号量的对比几种信号量的对比: 记录型信号量记录型信号量 整型信号量整型信号量 有等待队列有等待队列 无等待队列无等待队列 wait操作先减后判别操作先减后判别 wait操作先判别操作先判别后减后减 无资源那么自我阻塞无资源那么自我阻塞 无资源那么无资源那么“忙忙等等 signal

33、操作释放资源后操作释放资源后 signal操作释放操作释放资源后资源后 有等待进程那么唤醒有等待进程那么唤醒 无唤醒操作无唤醒操作有何差别有何差别? 记录型信号量记录型信号量 普通讯号量集普通讯号量集 一种资源一种资源 多种资源多种资源 每次恳求一个每次恳求一个 每次每种恳求每次每种恳求di个个少于少于1个不分配个不分配 少于少于ti个不分配个不分配先减后判别先减后判别 先判别后减先判别后减自我阻塞后程序计数定自我阻塞后程序计数定 自我阻塞后程序计自我阻塞后程序计数定数定 位到位到wait()操作之后操作之后 位到位到Swait()操作的操作的起点起点 signal唤醒第一个进程唤醒第一个进程

34、 Ssignal唤醒各种唤醒各种-一切一切 记录型信号量记录型信号量 AND信号量信号量 一种资源一种资源 多种资源多种资源 先减后判别先减后判别 先判别后减先判别后减自我阻塞后程序计数定自我阻塞后程序计数定 自我阻塞后程序计自我阻塞后程序计数定数定 位到位到wait()操作之后操作之后 位到位到Swait()操作的操作的起点起点 signal唤醒第一个进程唤醒第一个进程 Ssignal唤醒各种唤醒各种-一切一切【习题】P68 18,19, 212.3.4 信号量运用信号量运用1.利用信号量实现前趋关系利用信号量实现前趋关系 当进程当进程P1中有语句中有语句S1, 进程进程P2中有语句中有语句

35、S2两个并发执行希望两个并发执行希望S1执行后再执行执行后再执行S2, 要实现要实现这种前趋关系只需共享一个公用信号量这种前趋关系只需共享一个公用信号量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

36、; signal(a); signal(b); end;begin wait(a); s2; signal(c); signal(d); 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关门关门

37、售票售票开门开门UNTIL 2.用信号量的用信号量的wait-signal操作操作 处理司机售票员的同步问题处理司机售票员的同步问题 司机启动必需在售票员关门之后司机启动必需在售票员关门之后, 用信号量用信号量s1实现实现,售票员开门又必需在司机停车之后售票员开门又必需在司机停车之后, 用信号量用信号量s2来实来实现现, 初始形状初始形状: 车停在车站车停在车站,车门翻开着。车门翻开着。 Var s1,s2:semaphore:=0,0; 司机进程司机进程:REPEAT wait(s1);启动启动驾驶驾驶停车停车 signal(s2);UNTIL 售票员进程售票员进程:REPEAT关门关门 s

38、ignal(s1);售票售票 wait(s2);开门开门UNTIL 3. 信号量和信号量和wait-signal操作讨论操作讨论1) 信号量的物理含义：信号量的物理含义：S0表示有表示有S个资源可用个资源可用S=0表示无资源可用表示无资源可用S0 时消费者进程时消费者进程 (Pp) 才干送产品到缓才干送产品到缓冲区冲区; 同样同样, 只需当只需当S20时消费者进程时消费者进程 (Pc)才干从缓冲才干从缓冲区取产品。消费者区取产品。消费者消费者进程间的同步算法如下消费者进程间的同步算法如下:Pc： Pp：Repeat Repeat 消费一个产品；消费一个产品； wait(s2); wait(s1

39、); 从缓冲区取产品；从缓冲区取产品； 送产品到缓冲区；送产品到缓冲区； signal(s1); signal(s2); 消费产品消费产品Until false; Until false;2. n个缓冲区的同步：个缓冲区的同步： s1用来表示空缓冲区个数初值为用来表示空缓冲区个数初值为n; s2用来用来表示装有产品的缓冲个数表示装有产品的缓冲个数, 其初始值为其初始值为0。 n缓缓冲区的消费者冲区的消费者消费者进程之间的同步算法如下：消费者进程之间的同步算法如下：Var in:=0; out:=0；Pp： Pc： Repeat Repeat 消费产品；消费产品； wait(s2)； wait(

40、s1)； 从从Bufferout取产取产品品; 往往Buffer in中放产品；中放产品； signal(s1)； signal(s2)； out:=(out+1) mod n； in:=(in+1) mod n； 消费产品；消费产品； Until false; Until false;要不要对缓冲区要不要对缓冲区(临界临界资源资源)进展互斥操作？进展互斥操作？3.多个消费者和多个消费者进程并发多个消费者和多个消费者进程并发 当有多个消费者进程和多个消费者进程并当有多个消费者进程和多个消费者进程并发执行时发执行时, 由于缓冲区由于缓冲区Bufferin和和Bufferout以及以及 in和和o

41、ut 都是临界资源所以要对它们进展都是临界资源所以要对它们进展互斥操作。互斥操作。 可利用互斥信号量可利用互斥信号量s0实现诸进程对缓冲区实现诸进程对缓冲区的互斥操作。此时的互斥操作。此时, n缓冲区的生进程缓冲区的生进程消费者消费者进程之间的同步算法如下：进程之间的同步算法如下：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 消费产品；消费产品

42、； 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); signal(s2); 消费产品；消费产品； Until false; Until false; 次序不能颠倒次序不能颠倒 次序不能颠倒次序不能颠倒 Swait(s1, s0) Swait(s2, s0) Ssignal(s0, s2) Ssignal(s0, s1) 利用利用AND信

43、号量机制信号量机制消费者消费者消费者进程的互消费者进程的互斥信号量斥信号量s0s0能否各用一个能否各用一个2.3.3.哲学家就餐问题哲学家就餐问题 五个哲学家围坐在一圆桌旁五个哲学家围坐在一圆桌旁, 桌中央有一盘通心桌中央有一盘通心粉粉, 每人面前有一只空盘子每人面前有一只空盘子, 每两人之间放一只筷子。每两人之间放一只筷子。 每个人的行为是思索每个人的行为是思索, 感到饥饿感到饥饿, 然后吃通心粉。然后吃通心粉。 为了吃通心粉为了吃通心粉, 每个人必需拿到两只筷子每个人必需拿到两只筷子, 并且并且每个人只能直接从本人的左边或右边去取筷子。每个人只能直接从本人的左边或右边去取筷子。var c:

44、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 当每人都已取到左筷子要取右筷子时发生死锁。当每人都已取到左筷子要取右筷子时发生死锁。 为防止死锁发生可采取的几种措施：为防止死锁发生可采取的几种措施：最多允许最多允许4个哲学家同时坐在桌子周围。个哲学家同时坐在桌子周围。仅当一个哲学家左右两边的筷子都可用时仅当一个哲学家左右两边的筷子都可用时,

45、才允许才允许他拿筷子。利用他拿筷子。利用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;0321414320 规定奇数号哲学家先拿右边的再拿左边的规定奇数号哲学家先拿右边的再拿左边的, 偶偶数号哲学家相反数号哲学家相反; 1, 2号哲学家先竞争号哲学家先竞争2号筷号筷; 3,4号哲学家先竞争号哲学家先竞争4号筷号筷; 0号先拿号先拿0号筷。号筷。 v

46、ar 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); signal(ci+1); Until false; Until false; 0 1 2 3 4 0 1 2 3 42.4.3.读者写者问题读者写者问题有两组并发进程有两组并

47、发进程: 读者和写者读者和写者,共享一组数据区共享一组数据区, 为了保证读为了保证读写的正确性和数据的一致性写的正确性和数据的一致性要求：要求： 当有读者进程读文件时当有读者进程读文件时, 不允许任何写者进不允许任何写者进程写，但允许多读者同时读程写，但允许多读者同时读 当有写者进程写时当有写者进程写时, 不允许任何其它写者进不允许任何其它写者进程写程写, 也不允许任何读者进展读。也不允许任何读者进展读。(或要求或要求:) 不允许读者、写者同时操作不允许读者、写者同时操作 不允许多个写者同时操作不允许多个写者同时操作1. 利用记录型信号量处理读者利用记录型信号量处理读者写者问题写者问题为理处理

48、读者为理处理读者写者问题写者问题, 需设置两个信号量：需设置两个信号量： (1) 读互斥信号量读互斥信号量rs, 用于使读者互斥地访问用于使读者互斥地访问共享变量共享变量n, 这里这里n是记录有多少读者正在读是记录有多少读者正在读; (2)写互斥信号量写互斥信号量ws, 用于实现读写互斥和写用于实现读写互斥和写写互斥地访问共享文件。读者写互斥地访问共享文件。读者写者问题进展写者问题进展如下描画：如下描画：读者：读者：Repeatwait(rs);if n=0 then wait(ws);n:=n+1;signal(rs); 读读wait(rs);n:=n-1;if n=0 then signa

49、l(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写者：写者：Repeat Swait(mx,1,1,L,RN,0); 写操作写操作; Ssignal(mx,1);Unt

50、il false2. 利用信号量集机制处理读者利用信号量集机制处理读者写者问题写者问题(p50) 添加限制添加限制,最多只允许最多只允许RN个读者同时读个读者同时读;添添加信号量加信号量L其初值为其初值为RN;每个读者进入时每个读者进入时,执行执行Swait(L,1,1)操作使操作使L减减1,读者数增到读者数增到RN时时L=0,读者数再增读者数再增1时被阻塞。时被阻塞。Var L, mx:semaphore:= RN, 1; 信号量信号量 无写者无写者mx=1,任何任何读者都可进入读者都可进入无写者无写者mx=1, 又无又无读者读者L=RN才可进才可进【作业】 p68 22,23,24,26思

51、索题思索题:1. 音讯缓冲问题。音讯缓冲问题。 音讯缓冲区为音讯缓冲区为k个个, 有有m个发送进程个发送进程, n个接纳进个接纳进程程, 每个接纳进程对发送来的音讯都必需取一次。每个接纳进程对发送来的音讯都必需取一次。 2. 理发师睡觉问题理发师睡觉问题 理发店里有一位理发师理发店里有一位理发师, 一把理发椅和一把理发椅和N把供把供等候理发的顾客坐的椅子。等候理发的顾客坐的椅子。 假设没有顾客假设没有顾客, 那么理发师便在理发椅上睡觉。那么理发师便在理发椅上睡觉。当一个顾客到来时当一个顾客到来时, 他必需先唤醒理发师。他必需先唤醒理发师。 假设顾客到来时理发师正在理发假设顾客到来时理发师正在理

52、发, 那么假设有那么假设有空椅子空椅子, 可坐下来等可坐下来等; 否那么分开。否那么分开。留意留意: 顾客和理发师的理发动作是同时的顾客和理发师的理发动作是同时的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() wait(m);

53、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

54、*/V(customer);P(barber);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)

55、 mod n; count:=count+1;if ne.queue then ne.signal; 消费者队非空那么唤醒消费者队非空那么唤醒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设置进程和管程的目的不同设置进

56、程和管程的目的不同2系统管理数据构造系统管理数据构造 进程：进程：PCB 管程：等待队列管程：等待队列3管程被进程调用管程被进程调用4管程是操作系统的固有成分，无创建和吊销管程是操作系统的固有成分，无创建和吊销2.6 进程通讯进程通讯 2.6.1 概述概述 利用信号量的利用信号量的 wait-signal 操作实现进程的互斥和操作实现进程的互斥和同步是进程间的低级通讯同步是进程间的低级通讯; 在进程互斥中在进程互斥中, 进程经过修进程经过修正信号量相互阐明临界资源能否可用正信号量相互阐明临界资源能否可用; 在进程同步中在进程同步中, 信号量相互阐明配合信息非常有效信号量相互阐明配合信息非常有效

57、; 但作为通讯工具但作为通讯工具, 那么不够理想。那么不够理想。wait-signal操作为低级通讯原语操作为低级通讯原语, 每次每次只能传送简单的信号只能传送简单的信号, 效率低效率低, 而且通讯对用户不透而且通讯对用户不透明明, 实现起来比较费事实现起来比较费事, 不适宜于传送交换大量信息。不适宜于传送交换大量信息。 假设要在进程间传送大量信息假设要在进程间传送大量信息, 可直接利用系统提可直接利用系统提供的一组通讯命令来实现进程的高级通讯原语供的一组通讯命令来实现进程的高级通讯原语,它们隐它们隐藏了进程通讯的实现细节藏了进程通讯的实现细节, 通讯对用户是透明的通讯对用户是透明的, 是高是

58、高效方便的公用通讯方式。效方便的公用通讯方式。进程通讯的方式进程通讯的方式1.共享内存系统共享内存系统(Shared-Memory System) 相互通讯的进程间共享某些数据构造或共相互通讯的进程间共享某些数据构造或共享存储区享存储区, 进程之间经过它们进展通讯。进程之间经过它们进展通讯。 1) 诸进程共享某些数据构造诸进程共享某些数据构造(数组数组, 有界缓有界缓冲区等冲区等)数据构造的设置和同步处置都是由用数据构造的设置和同步处置都是由用户来完成的户来完成的, 添加了用户的负担添加了用户的负担, 效率低效率低, 仅用仅用于传送少量数据。于传送少量数据。 2) 诸进程共享存储区诸进程共享存

59、储区(数据量大数据量大), 进程向系进程向系统恳求共享存储区中的一个分区统恳求共享存储区中的一个分区, 并指定该分并指定该分区的关键字区的关键字, 并将该分区衔接到本进程上对其并将该分区衔接到本进程上对其进展写。另一进程可根据关键字将该分区衔接进展写。另一进程可根据关键字将该分区衔接到本人之上对其进展读到本人之上对其进展读/写写, 经过同一分区的读经过同一分区的读/写写, 实现两进程间的信息交换。实现两进程间的信息交换。2.音讯传送系统音讯传送系统(Message passing system)3.管道管道(Pipe)通讯通讯共享文件方式共享文件方式音讯传送系统音讯传送系统(Message p

60、assing system) 以格式化的音讯以格式化的音讯(message)为通讯单位为通讯单位; 利利用系统为进程提供的两个高级通讯原语用系统为进程提供的两个高级通讯原语 send和和receive 进展通讯。隐藏了通讯的实现细节进展通讯。隐藏了通讯的实现细节, 对用户是透明的对用户是透明的, 运用非常方便运用非常方便, 是运用最广是运用最广泛的进程通讯机制。泛的进程通讯机制。 send：当要进展音讯传送时执行：当要进展音讯传送时执行 send receive：当接纳者要接纳音讯时执行：当接纳者要接纳音讯时执行 receive 音讯传送系统可分为直接方式和间接方式。音讯传送系统可分为直接方式