chapter3_进程同步、通信与死锁16-1

1、第第3章章进程同步、通信与死锁进程同步、通信与死锁n3.1 3.1 并发进程并发进程n3.2 3.2 临界区管理临界区管理n3.3 3.3 经典的进程同步问题经典的进程同步问题n3.4 3.4 管程和进程通信管程和进程通信n3.63.6死锁死锁n顺序程序执行、并发程序执行顺序程序执行、并发程序执行 输入：输入：计算：计算：输出：输出： t0 t1 t2 t3 t4 t5 t6tttI1三个程序并发执行的前驱图三个程序并发执行的前驱图I2I3C1C2C3P1P2P3时间时间:5个个t并行并行并行并行并行并行前驱关系前驱关系执行顺序执行顺序顺序程序设计(2)n顺序程序设计具有如下的特点：n 程序执

2、行的顺序性n 程序环境的封闭性n 程序执行结果的确定性n 计算过程的可再现性顺序程序设计(3) 顺序程序设计的例顺序程序设计的例 while(1) input，process，output 7878输入机输入机处理器处理器磁带机磁带机130130150150228228280280300300378378430430450450时时 间间处理器利用率：处理器利用率：52/(78+52+20)35%52/(78+52+20)35%顺序程序设计(4)顺序程序设计串行工作顺序程序设计串行工作 i1p1o1i2p2o2顺序程序设计(5)顺序程序设计的优缺点n顺序程序设计的顺序性、封闭性、确定性和再现性

3、给程序的编制、调试带来很大方便，其缺点是计算机系统效率不高。进程的并发性(1)n进程执行的并发性：一组进程的执行在时间上是重叠的n并发性举例：例如：有两个进程A(a1、a2、a3)和B(b1、b2、b3)并发执行 进程的并发性(2)n从宏观上看，并发性反映一个时间段中几个进程都在同一处理器上，处于运行还未运行结束状态，n从微观上看，任一时刻仅有一个进程在处理器上运行。进程的并发性(3)n并发的实质是一个处理器在几个进程之间的多路复用，并发是对有限的物理资源强制行使多用户共享，消除计算机部件之间的互等现象，以提高系统资源利用率。n并发程序设计:一个程序被分成若干可同时执行的小程序,每个小程序及其

4、处理的数据组成一个进程.并发进程分类：无关的，交往的。n无关的并发进程：一组并发进程分别在不同的变量集合上操作，一个进程的执行与其他并发进程的进展无关。无关的并发进程(2) 并发进程的无关性是进程的执行与时间无关的一个充分条件，又称为Bernstein条件。 无关的并发进程(3) Bernstein条件：条件： R(pi)=a1,a2,an，程序pi在执行期间引用的变量集 W(pi)=b1,b2,bm，程序pi在执行期间改变的变量集 若 两 个 程 序 的 变 量 集 交 集 之 和 为 空 集 ： R(p1)W(p2)R(p2)W(p1)W(p1)W(p2)= 则并发进程的执行与时间无关。无

5、关的并发进程(4) 例如，有如下四条语句： S1: a := x + y S2: b := z + 1 S3: c := a b S4: w := c + 1 于是有：R(S1)=x,y ,R(S2)=z，R(S3)=a,b，R(S4)=c；W(S1)=a, W(S2)=b，W(S3)=c，W(S4)=w。 S1和S2可并发执行，满足Bernstein条件。其他语句并发执行可能会产生与时间有关的错误。无关的并发进程(5) 两个无关的进程并发执行的例两个无关的进程并发执行的例处理器利用率：处理器利用率：(52+42)/(78+52+20)63%(52+42)/(78+52+20)63%7878输

6、入机输入机处理器处理器磁带机磁带机130130150150228228280280300300378378430430450450时时 间间磁带机磁带机打印机打印机20206262170170320320交往的并发进程(1)n交往的并发进程：一组并发进程共享某些变量，一个进程的执行可能影响其他并发进程的结果。 并发程序设计的例子 while(1) input，send while(1) receive，process，send while(1) receive，output 处理器利用率处理器利用率：（52 * n） /（78*n+52+20）= 67%7878输入机输入机处理器处理器磁带机磁

7、带机130130150150228228306306208208286286384384364364时时 间间交往的并发进程(2)并发程序设计n并发程序设计是：把一个程序设计成若干个可同时执行的程序模块的方法。n并发程序设计的特征： 并行性、 共享性、 制约性、 交互性。 交往的并发进程交往的并发进程(3)(3)并发程序设计的优点并发程序设计的优点对于单处理器系统,可让处理器和各I/O设备同时工作,发挥硬部件的并行能力。对于多处理器系统,可让各进程在不同处理器上物理地并行，加快计算速度。简化了程序设计任务。 交往的并发进程(4)采用并发程序设计的目的n充分发挥硬件的并行性，提高系统效率。硬件能

8、并行工作仅有了提高效率的可能性，硬部件并行性的实现需要软件技术去利用和发挥，这种软件技术就是并发程序设计。n并发程序设计是多道程序设计的基础，多道程序的实质就是把并发程序设计引入到系统中。交往的并发进程(5)与时间有关的错误与时间有关的错误n对于一组交往的并发进程，执行的相对速度无法相互控制，各种与时间有关的错误就可能出现。n与时间有关错误的表现形式：n结果不唯一n永远等待（结果不唯一）机票问题（结果不唯一）机票问题process Ti ( i = 1, 2 ) var Xi:integer;begin按旅客定票要求找到按旅客定票要求找到Aj；Xi := Aj;if Xi=1 then beg

9、in Xi:=Xi-1; Aj:=Xi;输出一张票输出一张票；endelse 输出票已售完输出票已售完；end;（永远等待）内存管理问题（永远等待）内存管理问题procedure borrow (var B:integer) begin if Bx then 申请进程进入等待队列等主存资源申请进程进入等待队列等主存资源 x:=x-B; 修改主存分配表，申请进程获得主存资源修改主存分配表，申请进程获得主存资源 end;procedure return (var B:integer) begin x:=x+B; 修改主存分配表修改主存分配表 释放等主存资源的进程释放等主存资源的进程 end;一一.

10、 .进程同步的基本概念进程同步的基本概念1.1.两种形式的制约关系两种形式的制约关系2.2.临界资源、临界区临界资源、临界区3.3.同步机制应遵循的规则同步机制应遵循的规则二二. .信号量机制与信号量机制与P P、V V操作操作1.1.整型信号量整型信号量2.2.记录型信号量记录型信号量返回目录返回目录3.2 3.2 进程同步进程同步进程的交往：竞争与协作(1)n 并发进程之间的竞争关系n 进程的互斥n系统中的多个进程之间彼此无关n 并发进程之间的协作关系n 进程的同步n系统中的多个进程之间彼此相关 资源竞争的两个控制问题：资源竞争的两个控制问题： 一个是死锁(Deadlock)问题， 一个是

11、饥饿(Starvation) 问题，既要解决饥饿问题，又要解决死锁问题。进程互斥进程互斥(Mutual Exclusion)(Mutual Exclusion)进程互斥：进程互斥：进程之间通过竞争系统某些资源产生的关进程之间通过竞争系统某些资源产生的关系称为间接制约关系系称为间接制约关系，它们之间是通过某种“媒介”而产生了“关系”。(间接制约关系间接制约关系)进程互斥进程互斥指若干进程要使用同一共享资源时，任何时刻最多允许一个进程使用，其他进程必须等待，直到占有资源的进程释放该资源。返回第二种是协作关系第二种是协作关系 进程同步进程同步指两个以上进程基于某个条件来协调它们的活动。一个进程的执行

12、依赖于协作进程的消息或信号，当一个进程没有得到来自于协作进程的消息或信号时需等待，直到消息或信号到达才被唤醒。n进程同步：进程同步：进程之间为了共同完成某项任务，或者协作完成，有意识彼此相互“交换信息”。如前分别将I、C和和P都看成是进程都看成是进程。(直接制约关系直接制约关系) 返回同同 步步互互 斥斥进程进程- -进程进程进程进程- -资源资源- -进程进程时间次序上受到某种限制时间次序上受到某种限制竞争到某一物理资源时竞争到某一物理资源时不允许进程工作不允许进程工作相互清楚对方的存在及作相互清楚对方的存在及作用，交换信息用，交换信息不一定清楚其进程情况不一定清楚其进程情况往往指有几个进程

13、共同完往往指有几个进程共同完成一个任务成一个任务往往指多个任务多个进往往指多个任务多个进程间通讯制约程间通讯制约例：生产与消费之间，发例：生产与消费之间，发送与接受之间，作者与读送与接受之间，作者与读者之间，供者与用者之间者之间，供者与用者之间例：交通十字路口，单例：交通十字路口，单轨火车的拨道岔轨火车的拨道岔同步与互斥的比较返回2 2、临界资源、临界区、临界资源、临界区临界资源临界资源 (critical resource(critical resource） 系统中某些资源一次只允许一个进程使用，系统中某些资源一次只允许一个进程使用，称这样的资源为临界资源或互斥资源或共享变量。称这样的资源

14、为临界资源或互斥资源或共享变量。临界区（互斥区）：临界区（互斥区）：critical sectioncritical section 在进程中涉及到临界资源的程序段叫在进程中涉及到临界资源的程序段叫临界区临界区简称简称CSCS 多个进程的临界区称为多个进程的临界区称为相关临界区相关临界区2 2、临界资源、临界区、临界资源、临界区 进程的互斥（间接作用）进程的互斥（间接作用）a := a +1 print (a)P1 互斥互斥a := a -1 print (a)P2互斥互斥If a 0then a := a +1else a:= a-1 P3互斥互斥2 2、临界资源、临界区、临界资源、临界区程

15、序程序 段段1共享变量共享变量程序程序 段段2程序程序 段段3n例例：有两个进程：有两个进程A A和和B B，它们共享一个变量，它们共享一个变量x x，且两个进程按，且两个进程按以下方式对变量以下方式对变量X X进行访问和修改进行访问和修改: : 其中其中R1R1和和R2R2为处理机中的两个为处理机中的两个寄存器。寄存器。A A与与B B均对均对X+1X+1，即，即X+2X+2。若按另一顺序对变量进行修改：若按另一顺序对变量进行修改：结果结果x x只加了只加了1 1。A: R1=X;B: R2=X;A: R1=R1+1; X=R1;B: R2=R2+1; X=R2;A: R1=X; R1=R1

16、+1; X=R1;B: R2=X; R2=R2+1; X=R2;（1 1）变量）变量X X必必需按临界资源需按临界资源处理。处理。（2 2）每个进）每个进程中访问临界程中访问临界资源的那段代资源的那段代码称为临界区码称为临界区2 2、临界资源、临界区、临界资源、临界区实现各进程互斥进入临界区实现各进程互斥进入临界区 进程须进程须在临界区前面增加一段用于进行上述检在临界区前面增加一段用于进行上述检查的代码，称为查的代码，称为进入区进入区(entry section)(entry section)。在临界区。在临界区后面加上一段称为后面加上一段称为退出区退出区(exit section)(exit

17、 section)的代码的代码While (1)While (1) 进入区代码进入区代码; ; 临界区代码临界区代码; ; 退出区代码退出区代码; ; 其余代码其余代码 ; ; 进入区进入区临界区临界区退出区退出区剩余区剩余区n要进入临界区的若干进程必须满足如下三个条件要进入临界区的若干进程必须满足如下三个条件：（1 1）一次只允许一个进程进入临界区）一次只允许一个进程进入临界区（2 2）如果有进程在临界区）如果有进程在临界区, ,试图进入此临界区的其他进程等待试图进入此临界区的其他进程等待（3 3）进入临界区的进程要在有限的时间内退出）进入临界区的进程要在有限的时间内退出, ,以便让等待队以

18、便让等待队列中的一个进程进入列中的一个进程进入. .n解决临界区（互斥）问题的原则：解决临界区（互斥）问题的原则： 2 2、临界资源、临界区、临界资源、临界区3 3、同步机制应遵循的规则、同步机制应遵循的规则q有空让进有空让进( (空闲让进）空闲让进）: :当无进程处于临界区时，当无进程处于临界区时，表明临界资源处于空闲状态，应允许一个请求进表明临界资源处于空闲状态，应允许一个请求进入临界区的进程立即进入自己的临界区，以有效入临界区的进程立即进入自己的临界区，以有效地利用临界资源。地利用临界资源。q互斥（忙则等待）互斥（忙则等待）: :当已有进程进入临界区时，表当已有进程进入临界区时，表明临界

19、资源正在被访问，因而其他试图进入临界明临界资源正在被访问，因而其他试图进入临界区的进程必须等待，以保证对临界资源的互斥访区的进程必须等待，以保证对临界资源的互斥访问。问。一、进程同步的基本概念一、进程同步的基本概念q算法可行算法可行: :对要求访问临界资源的进程，应保证在对要求访问临界资源的进程，应保证在有限时间内能进入自己的临界区，以免陷入有限时间内能进入自己的临界区，以免陷入“死等死等”状态状态; ;当进程不能进入自己的临界区时，应立即释当进程不能进入自己的临界区时，应立即释放处理机，以免进程陷入放处理机，以免进程陷入“忙等忙等”。q择一而入择一而入: :一次只能进入一个一次只能进入一个一

20、、进程同步的基本概念一、进程同步的基本概念3 3、同步机制应遵循的规则、同步机制应遵循的规则返回返回解决临界区（互斥）问题的方法：解决临界区（互斥）问题的方法：n1. 软件n2利用硬件方法解决进程互斥问题（1）禁止中断（2）专用机器指令n3信号量及原语 是机器指令的延伸，往往是为完成某些特定的功能而编制的一段系统程序。原语操作也称做“原子操作”（atomic action），即一个操作中的所有动作要么全做，要么全不做。n执行原语操作时，要屏蔽中断，以保证其操作的不可分割性。临界区管理的尝试 (1)ninside1,inside2:Booleaninside1,inside2:Booleanni

21、nside1 := false; /inside1 := false; /* * P1 P1不在其临界区内不在其临界区内 * */ /ninside2 := false; /inside2 := false; /* * P2 P2不在其临界区内不在其临界区内 * */ /ncobegincobeginnprocess P1process P1n Begin Beginnwhile inside2 do begin end; while inside2 do begin end; * * * *ninside1 := true;inside1 := true;n临界区临界区; ;ninside1

22、 := false;inside1 := false;n end; end;nprocess P2process P2n begin beginnwhile inside1 do begin end;while inside1 do begin end;ninside2 = true;inside2 = true;n临界区临界区; ;ninside2 := false;inside2 := false;n end; end;ncoendcoend临界区管理的尝试 (2)ninside1,inside2:boolean;inside1,inside2:boolean;ninside1 := fa

23、lse; /inside1 := false; /* * P1 P1不在其临界区内不在其临界区内 * */ /ninside2 := false; /inside2 := false; /* * P2 P2不在其临界区内不在其临界区内 * */ /ncobegincobeginnprocess P1process P1n begin beginninside1 := true;inside1 := true;nwhile inside2 do begin end;while inside2 do begin end;n临界区临界区; ;ninside1 := false;inside1 :=

24、false;n end; end;nprocess P2process P2n begin beginninside2 := true;inside2 := true;nwhile inside1 do begin end;while inside1 do begin end;n临界区临界区; ;ninside2 := false;inside2 := false;n end; end; coend coendPeterson算法(1)nvar inside:array1.2 of boolean;var inside:array1.2 of boolean;nturn:integer;tur

25、n:integer;nturn := 1 or 2; turn := 1 or 2; ninside1 := false;inside1 := false;/ /* * P1 P1不在其临界区内不在其临界区内 * */ /ninside2 := false;inside2 := false;/ /* * P2 P2不在其临界区内不在其临界区内 * */ /Peterson算法(2)ncobegincobeginnprocess P1process P1n begin beginninside1:= true;inside1:= true;nturn := 2;turn := 2;nwhile

26、(inside2 and turn=2)while (inside2 and turn=2)n do begin end; do begin end;n临界区临界区; ;ninside1 := false;inside1 := false;n end; end;Peterson算法(3)nprocess P2process P2n begin beginninside2 := true;inside2 := true;nturn := 1;turn := 1;nwhile (inside1 and turn=1)while (inside1 and turn=1)n do begin end;

27、 do begin end;n临界区临界区; ;ninside2 := false;inside2 := false;n end; end;ncoendcoendPeterson算法(4)n用对turn的置值和while语句来限制每次只有一个进程进入临界区；n进程执行完临界区程序后，修改insidei 状态使等待进入临界区的进程可在有限时间内进入。n算法满足临界区管理的三个条件。实现临界区实现临界区管理的硬件设施的硬件设施n 关中断n 测试并建立指令n 对换指令测试并建立指令(1) TS指令的处理过程: TS(x): 若x=true， 则x:=false； return true； 否则 re

28、turn false； TS指令管理临界区时，可把一个临界区与一个布尔变量s相连，由于变量s代表了临界资源的状态，可把它看成一把锁。 测试并建立指令(2)s : boolean;s : boolean;s := true;beginbeginprocess Pi() /process Pi() /* * i = 1,2, i = 1,2,n ,n * */ / while(!TS(S) while(!TS(S)；/上锁上锁 临界区临界区; s := true s := true；/开锁开锁 coendcoend;对换指令(1) 对换（对换（SwapSwap）指令）指令的功能是交换两个字的内容：

29、 Swap (a,b): temp:=a; a:=b; b:=temp;对换指令(2)lock : boolean;lock := false;process Pi /* i = 1,2,n */ pi : boolean;begin pi := true; do swap(lock, pi); while( pi )；临界区;swap(lock, pi);end;关中断n实现互斥的最简单方法之一n关中断方法的缺点返回三、信号量机制n信号量机制是荷兰科学家信号量机制是荷兰科学家E.W.DijkstraE.W.Dijkstra在在19651965年提出的一种同步机制，也称为年提出的一种同步机制，

30、也称为P P、V V操作。由操作。由最初的整型信号量发展为记录型信号量，进而最初的整型信号量发展为记录型信号量，进而发展为信号量集。发展为信号量集。n整型信号量整型信号量n记录型信号量记录型信号量1 1、整型信号量、整型信号量n整型信号量整型信号量非负整数，除了初始化外，只能通过两个非负整数，除了初始化外，只能通过两个原子操作原子操作waitwait和和signalsignal（P P，V V）来访问。）来访问。nwaitwait和和signalsignal操作描述操作描述： wait(S)wait(S)： while Swhile S 0 do no-op 0 do no-op 测试有无可用

31、资源测试有无可用资源 S:=S-1; S:=S-1; 可用资源数减一个单位可用资源数减一个单位 signal(S): S:=S+1;signal(S): S:=S+1;n主要问题主要问题：只要：只要S S 0 0， waitwait操作就不断地测试（盲等），操作就不断地测试（盲等），因而，未做到因而，未做到“让权等待让权等待”。 2 2、记录型信号量、记录型信号量n基本思想基本思想 1、设置一个代表资源数目的整型变量、设置一个代表资源数目的整型变量value（资源（资源信号量）信号量） 2、设置一链表、设置一链表L用于链接所有等待的进程用于链接所有等待的进程n记录型信号量的数据结构记录型信号量

32、的数据结构 Type semaphore=record value:integer; L: list of process; end2 2、记录型信号量、记录型信号量n P P、V V操作操作 除初始化外，仅能通过两个标准的原子操除初始化外，仅能通过两个标准的原子操作作wait(S)wait(S)和和signal(S)signal(S)来访问。很长时间以来访问。很长时间以来，这两个操作一直被称为来，这两个操作一直被称为P P、V V操作。操作。 原子操作原子操作（atomic actionatomic action）或简称）或简称“原原语语”(primitive)(primitive)：在执行

33、上不可中断的操作。：在执行上不可中断的操作。 2 2、记录型信号量、记录型信号量n P P、V V操作定义操作定义P(s) P(s) / /* *= wait(s)= wait(s)）* */ / s.value=s.value s.value=s.value; ; if (s.value 0) if (s.value 0) block(s.queue) block(s.queue) 该进程状态置为等待状该进程状态置为等待状态态将该进程的将该进程的PCBPCB插入相的插入相的等待队列末尾等待队列末尾s.queue;s.queue;2 2、记录型信号量、记录型信号量V(s) V(s) / /*

34、*=signal(s) =signal(s) * */ / s.value=s.value+; s.value=s.value+; if (s.value = 0) if (s.value 0 S0 表示有表示有S S个资源可用个资源可用S=0 S=0 表示无资源可用表示无资源可用S0 S0 则则 |S| |S| 表示表示S S等待队列中的进程个数等待队列中的进程个数2)2) P P、V V操作的含义操作的含义P(S):P(S):表示申请一个资源表示申请一个资源 V(S)V(S)：表示释放一个资源。信号量的初值应：表示释放一个资源。信号量的初值应0 0使用使用P, V操作实现互斥时应注意两点：

35、操作实现互斥时应注意两点： 在每个程序中用于实现互斥的P(mutex)和V(mutex)必须成对出现，即先做P，进入临界区；后做V，退出临界区。 互斥信号量mutex的初值一般为1。三、信号量的应用三、信号量的应用n利用信号量实现进程互斥利用信号量实现进程互斥Process1:while (true) P(mutex); critical section; V(mutex); remainder section; while (true) P(mutex); critical section; V(mutex); remainder section; Process2:三、信号量的应用三、信号

36、量的应用例例: :三个进程共用两个三个进程共用两个I/OI/O缓冲区。缓冲区。n解：设用信号量解：设用信号量S S表示共享资源，表示共享资源，S S初始值为初始值为2 2 P(mutex)V(mutex)P1P2P3互斥区互斥区P(mutex)P(mutex)V(mutex)V(mutex)三、信号量的应用三、信号量的应用n利用信号量实现前驱关系利用信号量实现前驱关系P1P2三、信号量的应用三、信号量的应用设置一个信号量设置一个信号量S S，其，其初值为初值为0 0, ,P1；V(S);P(S)；P2;如此即可实现先执行如此即可实现先执行P1P1，再执行，再执行P2P2三、信号量的应用三、信号

37、量的应用Eg: Eg: 设设S1,S2,S3,S4S1,S2,S3,S4为一组合作进程，其前趋图如为一组合作进程，其前趋图如图所示，用图所示，用P P、V V操作实现其同步。操作实现其同步。 var a,b,c,d:semaphore:=0,0,0,0; /*表示进程是否执行完表示进程是否执行完*/ main() cobegin s1(); s2(); s3(); s4(); coend s1s2s3s4abcdS1() v(a); S2() v(b); v(c); S3() p(a); p(b); v(d); S4() p(c); p(d); . n利用信号量实现前驱关系（同步例子）利用信号

38、量实现前驱关系（同步例子）三、信号量的应用三、信号量的应用思考：思考：已知一个求值公式（已知一个求值公式（A2/3BA2/3B）/ /（B+5AB+5A），），若若A A、B B已赋值，画出该公式求值过程的前趋图已赋值，画出该公式求值过程的前趋图 n利用信号量实现前驱关系（同步例子）利用信号量实现前驱关系（同步例子）三、信号量的应用三、信号量的应用n利用信号量实现同步利用信号量实现同步n有有A A、B B两进程，两进程，A A进程从卡片机读信息入缓冲进程从卡片机读信息入缓冲区，区，B B进程负责加工读进缓冲区的卡片进程负责加工读进缓冲区的卡片n解：设信号量解：设信号量S1S1：缓冲区中有否可供

39、加工的：缓冲区中有否可供加工的信息，初始值为信息，初始值为0 0；信号量；信号量S2S2：缓冲区是否为：缓冲区是否为空，初始值为空，初始值为1 1。三、信号量的应用三、信号量的应用n利用信号量实现同步举例利用信号量实现同步举例返回返回3.3 3.3 经典进程的同步问题经典进程的同步问题 在多道程序环境下，进程同步问题十分在多道程序环境下，进程同步问题十分重要，出现一系列经典的进程同步问题，其中重要，出现一系列经典的进程同步问题，其中有代表性有有代表性有：生产者生产者消费者问题消费者问题哲学家进餐问题哲学家进餐问题读者读者写者问题写者问题返回目录返回目录1 1、“生产者生产者消费者消费者”问问题

40、题 单缓冲区单缓冲区：生产者进程：生产者进程P P和消费者进程和消费者进程C C共用一个共用一个缓冲区，缓冲区，P P生产产品放入缓冲区，生产产品放入缓冲区，C C从缓冲区取产从缓冲区取产品来消费。品来消费。 消费者消费者生产者生产者1 1、“生产者生产者消费者消费者”问问题题u单缓冲区的同步问题单缓冲区的同步问题 P P进程不能往进程不能往“满满”的缓冲区中放产品，设置信的缓冲区中放产品，设置信号量为号量为emptyemptyC C进程不能从进程不能从“空空”的缓冲区中取产品，设置信的缓冲区中取产品，设置信号量号量fullfullu单缓冲区的互斥问题单缓冲区的互斥问题P P、C C进程不能同

41、时使用缓冲区进程不能同时使用缓冲区1 1、“生产者生产者消费者消费者”问问题题u单缓冲区的生产者单缓冲区的生产者消费者问题解消费者问题解P： C：while (true) while (true) 生产一个产品生产一个产品; P(full); P(empty) ; 从缓冲区取产品从缓冲区取产品; 送产品到缓冲区送产品到缓冲区; V(empty); V(full); 消费产品消费产品; ;empty初值为初值为1，full初值为初值为01 1、“生产者生产者消费者消费者”问问题题 多个缓冲区多个缓冲区：若干个生产者进程：若干个生产者进程P1, P2, , Pn，若干个消费者进程若干个消费者进程C

42、l，C2，Cm。它们通过。它们通过一个有界缓冲池一个有界缓冲池(k个个)联系。联系。 .PC生产者生产者消费者消费者k kk k个个 BufferBuffern nm m1 1、“生产者生产者消费者消费者”问问题题u多缓冲区的同步互斥问题多缓冲区的同步互斥问题 n同步同步：当缓冲池已放满了产品时：当缓冲池已放满了产品时( (供过于求供过于求) )，生产者进程必须等待；当缓冲池已空时生产者进程必须等待；当缓冲池已空时( (供供不应求不应求) )，消费者进程应等待。，消费者进程应等待。n互斥互斥：所有进程应互斥使用缓冲池这一临界：所有进程应互斥使用缓冲池这一临界资源。资源。u多缓冲区的生产者多缓冲

43、区的生产者消费者问题解法消费者问题解法1 1、“生产者生产者消费者消费者”问问题题 设置两个同步信号量及一个互斥信号量设置两个同步信号量及一个互斥信号量nempty：说明空缓冲单元的数目，其初值为有界缓冲区的说明空缓冲单元的数目，其初值为有界缓冲区的 大小大小n。nfull：说明满缓冲单元的数目（即产品数目），其初值为说明满缓冲单元的数目（即产品数目），其初值为0。nmutex: 说明该有界缓冲区是一临界资源，必须互斥使用，说明该有界缓冲区是一临界资源，必须互斥使用，其初值为其初值为1。1 1、“生产者生产者消费者消费者”问问题题u多缓冲区的生产者多缓冲区的生产者消费者问题解法消费者问题解法思

44、考：思考：P操作的顺序可换吗？操作的顺序可换吗？u“生产者生产者消费者消费者”问题的算法描述问题的算法描述 semaphore full=0; /*表示满缓冲区的数目表示满缓冲区的数目*/ semaphore empty=n; /*表示空缓冲区的数目表示空缓冲区的数目*/ semaphore mutex=1; /*表示对缓冲区进程操作的互斥表示对缓冲区进程操作的互斥信号量信号量*/Main() cobegin producer(); consumer(); coend 1 1、“生产者生产者消费者消费者”问问题题 while(true) 生产一个产品生产一个产品; P(empty); P(mu

45、tex); 将一个产品送入缓冲将一个产品送入缓冲区；区； V(mutex); V(full);Producer() while(true) p(full); P(mutex); 从缓冲区取走一个产品从缓冲区取走一个产品; V(mutex);V(empty); 消费一个产品；消费一个产品； Consumer()1 1、“生产者生产者消费者消费者”问问题题u“生产者生产者消费者消费者”问题的算法描述问题的算法描述u “生产者生产者- -消费者消费者”问题中应注意问题中应注意1.1.互斥信号量的互斥信号量的P,VP,V操作在每一程序中必须成对出现操作在每一程序中必须成对出现. .1 1、“生产者生产

46、者消费者消费者”问问题题2.2.资源信号量资源信号量(full,empty)(full,empty)也必须成对出现也必须成对出现, ,但可分但可分别处于不同的程序中别处于不同的程序中. .3.3.多个多个P P操作顺序不能颠倒操作顺序不能颠倒. .4.4.先执行资源信号量的先执行资源信号量的P P操作操作, ,再执行互斥信号量的再执行互斥信号量的P P操作操作, ,否则可能引起进程死锁否则可能引起进程死锁. .1 1、“生产者生产者消费者消费者”问问题题5.5.它是一个同步问题：它是一个同步问题： （1 1）消费者想要取产品，有界缓冲区中至少有一个）消费者想要取产品，有界缓冲区中至少有一个单元

47、是满的。单元是满的。 （2 2）生产者想要放产品，有界缓冲区中至少有一个）生产者想要放产品，有界缓冲区中至少有一个是空的。是空的。u “生产者生产者- -消费者消费者”问题中应注意问题中应注意返回返回6.6.它是一互斥问题它是一互斥问题 有界缓冲区是临界资源，因此，各生产者进程和各有界缓冲区是临界资源，因此，各生产者进程和各消费者进程必须互斥执行。消费者进程必须互斥执行。2 2、“哲学家进餐哲学家进餐”问问题题n5 5个哲学家围坐在圆桌旁，个哲学家围坐在圆桌旁，每人面前有一只空盘子，每每人面前有一只空盘子，每2 2人之间放一只筷子，如图所人之间放一只筷子，如图所示。示。n为了就餐，每个哲学家为

48、了就餐，每个哲学家必须拿到两只筷子，并且只必须拿到两只筷子，并且只能直接从自己的左边或右边能直接从自己的左边或右边去取筷子。去取筷子。 问题描述问题描述 semaphore stick5=1,1,1,1,1; /*分别表示分别表示5支筷子支筷子*/ Main() cobegin philosopher(0); philosopher(1); philosopher(2); philosopher(3); philosopher(4); coend 哲学家进餐问题的解决哲学家进餐问题的解决2 2、“哲学家进餐哲学家进餐”问问题题2 2、“哲学家进餐哲学家进餐”问问题题哲学家哲学家i i的活动为：

49、的活动为： void philosopher (int i) while (true) 思考；思考； P(chopsticki) ； /取左边筷子取左边筷子 P(chopstick(i+1) % 5) ； /取右边筷子取右边筷子 进食；进食； V(chopsticki) ； /放左边筷子放左边筷子 V(chopstick(i+1) % 5) ； /放右边筷子放右边筷子 哲学家进餐问题的解决哲学家进餐问题的解决2 2、“哲学家进餐哲学家进餐”问问题题如果：如果：5 5人同时拿起左边筷子，再企图人同时拿起左边筷子，再企图拿起右边的筷子时，会如何？拿起右边的筷子时，会如何？死锁！死锁！ 2 2、“哲

50、学家进餐哲学家进餐”问问题题 为防止死锁发生可采取的措施：为防止死锁发生可采取的措施：n最多允许最多允许4 4个哲学家同时坐在桌子周围个哲学家同时坐在桌子周围n仅当一个哲学家左右两边的筷子都可用时，才仅当一个哲学家左右两边的筷子都可用时，才允许他拿筷子允许他拿筷子n给所有哲学家编号，奇数号的哲学家必须首先给所有哲学家编号，奇数号的哲学家必须首先拿左边的筷子，偶数号的哲学家则反之拿左边的筷子，偶数号的哲学家则反之返回返回3 3、“读者读者写者写者”问题问题问题描述：问题描述： 多个进程访问一个共享数据对象（如数据文件或记录以及内存和多个进程访问一个共享数据对象（如数据文件或记录以及内存和寄存器）

51、寄存器）, ,为该类问题建立一个通用模型。其中，为该类问题建立一个通用模型。其中，readerreader进程只能读，进程只能读，writer writer 进程要求写或修改。允许多个读进程同时读数据，但绝不允进程要求写或修改。允许多个读进程同时读数据，但绝不允许一个许一个writerwriter进程与其它的进程与其它的readerreader进程或进程或writerwriter进程同时访问，即进程同时访问，即writerwriter进程必须与其它进程互斥访问共享对象。进程必须与其它进程互斥访问共享对象。 如一个联网售票系统如一个联网售票系统: :数据的查询和更新非常频繁数据的查询和更新非常频

52、繁, ,必然有多个进必然有多个进程试图查询或修改同一条记录的情况程试图查询或修改同一条记录的情况, ,多个进程同时查询多个进程同时查询( (读读) )是允许是允许的的, ,但是不允许一个正在修改更新数据库但是不允许一个正在修改更新数据库( (写写) )的进程工作的同时其他的进程工作的同时其他修改修改( (写写) )或查询或查询( (读读) )发生发生, ,否则可能一票多售否则可能一票多售. .3 3、“读者读者写者写者”问题问题分析分析: :n有两组并发进程有两组并发进程: : 读者和写者读者和写者，共享一组数据区共享一组数据区 要求：要求：n允许多个读者同时执行读操作允许多个读者同时执行读操

53、作n不允许读者、写者同时操作不允许读者、写者同时操作n不允许多个写者同时操作不允许多个写者同时操作如果用生产者消费者的方法来严格互斥任何如果用生产者消费者的方法来严格互斥任何读者写者进程读者写者进程, ,可以保证数据更新的正确性可以保证数据更新的正确性. .但对查询不利但对查询不利. . (与生产与生产-消费的异同消费的异同)3 3、“读者读者写者写者”问题问题读者读者-写者问题有两种类型：写者问题有两种类型：n解法解法1 1：读者优先读者优先 只要有一个读者存在，不管只要有一个读者存在，不管有否写者请求，后续读者都可以执行读过程。有否写者请求，后续读者都可以执行读过程。 n解法解法2 2：读

54、写平等读写平等 即一旦有写者到达，后续的即一旦有写者到达，后续的读者必须等待，无论是否有读者在读。读者必须等待，无论是否有读者在读。s写者优先写者优先。只要有一个写者请求，读者就要等。只要有一个写者请求，读者就要等待，直到所有写者退出。待，直到所有写者退出。返回返回设置一个共享变量和两个信号量：设置一个共享变量和两个信号量：n共享变量共享变量ReadcountReadcount：记录当前正在读数据集的：记录当前正在读数据集的读进程数目，初值为读进程数目，初值为0 0。n读互斥信号量读互斥信号量Rmutex Rmutex ：表示读进程互斥地访问：表示读进程互斥地访问共享变量共享变量readcou

55、ntreadcount，初值为，初值为1.1.n写互斥信号量写互斥信号量wmutexwmutex：表示写进程与其它进程：表示写进程与其它进程（读、写）互斥地访问数据集，初值为（读、写）互斥地访问数据集，初值为1.1.3 3、“读者读者写者写者”问题问题读者优读者优先先semaphore rmutex=1; semaphore wmutex=1; int readcount=0; Main() cobegin reader(); writer(); coend 3 3、“读者读者写者写者”问题问题读者优读者优先先 while(true) while(true) p(rmutex);p(rmute

56、x); if(readcount= =1) if(readcount= =1) p(wmutexp(wmutex);/);/* *第一位读者阻止写者第一位读者阻止写者* */ / readcount+; readcount+; V(rmutex);V(rmutex); 读数据集；读数据集； p(rmutex);p(rmutex); readcount-; readcount-; if(readcount= =0) if(readcount= =0) v(wmutexv(wmutex);/);/* *第末位读者允许写者进第末位读者允许写者进* */ / V(rmutex);V(rmutex);

57、reader() while(true) p(wmutex); / /* *阻止其它进程（读、写）进阻止其它进程（读、写）进* */ / 写数据集；写数据集； V(wmutex); / /* *允许其它进程（读、写）进允许其它进程（读、写）进* */ /writer()3 3、“读者读者写者写者”问题问题读写平读写平等等为了提高写者的优先级为了提高写者的优先级，我们增加一个信号量，我们增加一个信号量w w，用，用以在写进程到达时封锁后续的读者进程。相应的以在写进程到达时封锁后续的读者进程。相应的控制算法如下：控制算法如下： BEGINBEGIN integer rmutex, wmutex,

58、rc, integer rmutex, wmutex, rc, w;w; rmutex:=1; rmutex:=1; wmutex:=1; wmutex:=1; rc:=0; rc:=0; w:=1; w:=1; BEGINBEGIN P(w);P(w); P(rmutex); P(rmutex); rc:=rc+1; rc:=rc+1; IF rc=1 THEN P(wmutex); IF rc=1 THEN P(wmutex); V(rmutex); V(rmutex); V(w);V(w); Reading the FILE; Reading the FILE; P(rmutex); P

59、(rmutex); rc:=rc-1; rc:=rc-1; IF rc=0 THEN V(wmutex); IF rc=0 THEN V(wmutex); V(rmutex); V(rmutex);END; END; readerBEGINBEGIN P(w);P(w); P(wmutex); P(wmutex); Writeing the FILE; Writeing the FILE; V(wmutex); V(wmutex); V(w);V(w);END;END;COEND COEND Writer返回返回3、“读者读者写者写者”问题问题写者优先写者优先Const readcount,w

60、ritecount:integerVar x,y,z,rsem,wrem:=semaphoreReader:BeginRepeat P(z); P(rsem);P(x); Readcount:= Readcount+1; If Readcount=1 then P(wsem);V(x); V(rsem); V(z);读数据读数据;P(x);Readcount:=readcount-1;If readcount=0 then V(wsem);V(x);Forever;End;Writer:BeginRepeatP(y); Writecount:=writecount+1; If writecou