《操作系统教程(第3版)解析》由会员分享，可在线阅读，更多相关《操作系统教程(第3版)解析（257页珍藏版）》请在金锄头文库上搜索。
1、操作系统教程(第3版)第三章 并发进程,面向21世纪课程教材 高等教育出版社 2003年8月,第三章 并发进程,3.1 并发进程 3.2 临界区管理 3.3 信号量与PV操作 3.4 管程 3.5 进程通信 3.6 死锁,3.1并发进程,3.1.1顺序程序设计 3.1.2进程的并发性 3.1.3与时间有关的错误 3.1.4进程的交互（Interaction Among Processes）：协作和竞争,进程的顺序性,一个进程在顺序处理器上的执行是严格按序的，一个进程只有当一个操作结束后，才能开始后继操作 顺序程序设计是把一个程序设计成一个顺序执行的程序模块，顺序的含义不但指一个程序模块内部，也
2、指两个程序模块之间。,顺序程序设计特点,程序执行的顺序性 程序环境的封闭性 程序执行结果的确定性 计算过程的可再现性,顺序程序设计例子,while(1) input，process，output ,进程的并发性(1),进程执行的并发性：一组进程的执行在时间上是重叠的 并发性举例：例如：有两个进程A(a1、a2、a3)和B(b1、b2、b3)并发执行 从宏观上看，并发性反映一个时间段中几个进程都在同一处理器上，处于运行还未运行结束状态， 从微观上看，任一时刻仅有一个进程在处理器上运行。,进程的并发性(2),并发的实质是一个处理器在几个进程之间的多路复用，并发是对有限的物理资源强制行使多用户共享，
3、消除计算机部件之间的互等现象，以提高系统资源利用率。,无关的并发进程,并发进程分类：无关的，交往的。 无关的并发进程：一组并发进程分别在不同的变量集合上操作，一个进程的执行与其他并发进程的进展无关。 并发进程的无关性是进程的执行与时间无关的一个充分条件，又称为Bernstein条件。,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)= 则并发进程的执行与时间无关。,Bernstein条件举例,例如，有
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条件。其他语句并发执行可能会产生与时间有关的错误。,交往的并发进程(1),交往的并发进程：一组并发进程共享某些变量，一个进程的执行可能影响其他并发进程的结果。,并发程序设计的例子,while(1) input，send while(1) receive，process，se
5、nd while(1) receive，output ,处理器利用率：（52 * n） /（78*n+52+20）= 67%,并发程序设计特征,并发程序设计是：把一个程序设计成若干个可同时执行的程序模块的方法。 并发程序设计的特征： 并发性、 共享性、 制约性、 交互性。,并发程序设计的优点,对于单处理器系统,可让处理器和各I/O设备同时工作,发挥硬部件的并行能力。 对于多处理器系统,可让各进程在不同处理器上物理地并行，加快计算速度。 简化了程序设计任务。,采用并发程序设计的目的,充分发挥硬件的并行性，提高系统效率。硬件能并行工作仅有了提高效率的可能性，硬部件并行性的实现需要软件技术去利用和发
6、挥，这种软件技术就是并发程序设计。 并发程序设计是多道程序设计的基础，多道程序的实质就是把并发程序设计引入到系统中。,与时间有关的错误,对于一组交往的并发进程，执行的相对速度无法相互控制，各种与时间有关的错误就可能出现。 与时间有关错误的表现形式： 结果不唯一 永远等待,（结果不唯一）机票问题,process Ti ( i = 1, 2 ) var Xi:integer; begin 按旅客定票要求找到Aj； Xi := Aj; if Xi=1 then begin Xi:=Xi-1; Aj:=Xi;输出一张票；end else 输出票已售完； end;,（永远等待）内存管理问题,proced
7、ure borrow (var B:integer) begin if Bx then 申请进程进入等待队列等主存资源 x:=x-B; 修改主存分配表，申请进程获得主存资源 end; procedure return (var B:integer) begin x:=x+B; 修改主存分配表 释放等主存资源的进程 end;,进程的交往：竞争与协作(1)第一种是竞争关系,系统中的多个进程之间彼此无关 系统中的多个进程之间彼此相关 资源竞争的两个控制问题： 一个是死锁(Deadlock)问题， 一个是饥饿(Starvation) 问题，既要解决饥饿问题，又要解决死锁问题。,进程的交往：竞争与协作(
8、2)进程互斥(Mutual Exclusion),解决进程间竞争关系(间接制约关系)的手段。 进程互斥指若干进程要使用同一共享资源时，任何时刻最多允许一个进程使用，其他进程必须等待，直到占有资源的进程释放该资源。,进程的交往：竞争与协作(3)第二种是协作关系(1),某些进程为完成同一任务需要分工协作。 进程的同步是解决进程间协作关系(直接制约关系)的手段。,进程的交往：竞争与协作(4)第二种是协作关系(2), 进程同步指两个以上进程基于某个条件来协调它们的活动。一个进程的执行依赖于协作进程的消息或信号，当一个进程没有得到来自于协作进程的消息或信号时需等待，直到消息或信号到达才被唤醒。,进程的交
9、往：竞争与协作(5)第二种是协作关系(3),进程互斥关系是一种特殊的进程同步关系，即逐次使用互斥共享资源，是对进程使用资源次序上的一种协调。,3.2 临界区管理,3.2.1 互斥与临界区 3.2.2 实现临界区管理的几种尝试 3.2.3 实现临界区管理的软件方法 3.2.4 实现临界区管理的硬件设施,3.2.1互斥与临界区(1),并发进程中与共享变量有关的程序段叫“临界区”(Critical Section) ， 共享变量代表的资源叫“临界资源”(Critical Resource)。 与同一变量有关的临界区分散在各进程的程序段中，而各进程的执行速度不可预知。 如果保证进程在临界区执行时，不让
10、另一个进程进入临界区，即各进程对共享变量的访问是互斥的，就不会造成与时间有关的错误。,互斥与临界区(2),临界区的调度原则： 一次至多允许一个进程进入临界区内 一个进程不能无限地停留在临界区内 一个进程不能无限地等待进入临界区 即-有空让进、无空等待、 择一而入、算法可行。,临界区管理的尝试 (1),inside1,inside2:Boolean inside1 := false; /* P1不在其临界区内 */ inside2 := false; /* P2不在其临界区内 */ cobegin process P1 Begin while inside2 do begin end; insi
11、de1 := true; 临界区; inside1 := false; end; process P2 begin while inside1 do begin end; inside2 = true; 临界区; inside2 := false; end; coend,临界区管理的尝试 (2),inside1,inside2:boolean; inside1 := false; /* P1不在其临界区内 */ inside2 := false; /* P2不在其临界区内 */ cobegin process P1 begin inside1 := true; while inside2 do
12、 begin end; 临界区; inside1 := false; end; process P2 begin inside2 := true; while inside1 do begin end; 临界区; inside2 := false; end; coend,Dekker算法(1),Dekker算法用一个指示器turn来指示应该哪一个进程进入临界区。 var inside : array1.2 of boolean; turn :integer; turn := 1 or 2; inside1:=false; inside2:=false;,cobegin process P1 b
13、egin inside1:=true; while inside2 do if turn=2 then begin inside1:=false; while turn=2 do begin end; inside1:=true; end 临界区; turn = 2； inside1:=false; end;,Dekker算法(2),Dekker算法(3),process P2 begin inside2:=true; while inside1 do if turn=1 then begin inside2:=false; while turn=1 do begin end; inside2
14、:=true; end 临界区; turn = 1； inside2:=false; end; coend,Peterson算法(1),var inside:array1.2 of boolean; turn:integer; turn := 1 or 2; inside1 := false;/* P1不在其临界区内 */ inside2 := false;/* P2不在其临界区内 */,Peterson算法(2),cobegin process P1 begin inside1:= true; turn := 2; while (inside2 and turn=2) do begin en
15、d; 临界区; inside1 := false; end;,Peterson算法(3),process P2 begin inside2 := true; turn := 1; while (inside1 and turn=1) do begin end; 临界区; inside2 := false; end; coend,实现临界区管理的硬件设施,关中断 测试并建立指令 对换指令,关中断,实现互斥的最简单方法 关中断方法的缺点,测试并建立指令(1),TS指令的处理过程 TS(x): 若x=true，则x:=false； return true；否则 return false； TS指令管
16、理临界区时，可把一个临区与一个布尔变量s相连，由于变量s代表了临界资源的状态，可把它看成一把锁。,测试并建立指令(2),s : boolean; s := true; process Pi /* i = 1,2,n */ pi : boolean; begin repeat pi := TS(s) until pi； 临界区; s := true； end;,对换指令(1),对换（Swap）指令的功能是交换两个字的内容： 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; repeat swap(lock, pi) until pi = false； 临界区;
