孙钟秀操作系统并发进程.ppt

操作系统教程(第4版)第三章 并发进程主讲教师：王慧娇 E-mail: whj@ : 13978321977 : 248886622 答疑时间：周二14:00-15:30第三章 并发进程3.1 并发进程 3.2 临界区管理 3.3 信号量与PV操作 3.4 管程 3.5 进程通信 3.6 死锁 3.7 Linux同步机制和通信机制 3.8 Windows 2003同步机制和通信机制3.1并发进程3.1.1 顺序程序设计 3.1.2 进程的并发性 3.1.3 进程的交互（Interaction Among Processes）：协作和竞争 前驱图(1)• 前驱图是一个有向无循环图，图中的每个 结点可以表示一条语句、一个程序段或一 个进程，结点间的有向边表示两个结点之 间存在的偏序或前驱关系“→”： • →＝{（Pi,Pj）| Pi必须在Pj 开始之前 完成}前驱图(2)• 如果（Pi,Pj）∈→（也可以写成 Pi→Pj），则称为Pi是Pj 的直接前驱， 而Pj 是Pi 的直接后继若存在一个序 列Pi→Pj→…→Pk ，则称Pi是Pk 的前 驱，而Pk 是Pi 的后继。

在前驱图中， 没有前驱的结点称为初始结点，没有后 继的结点称为终止结点前驱图示例3.1.1顺序程序设计§ 把一个具有独立功能的程序独占处理机直 至最终结束的过程称为程序的顺序执行 § 如果完成一个任务需要若干不同的程序， 则这些程序在时间上也按调用次序严格有序 执行（程序外部的顺序性） § 顺序程序设计是把一个程序设计成一个顺 序执行的程序模块，不同程序也按顺序执行 程序的顺序执行(a) 程序的顺序执行(b) 三条语句的顺序执行I1C1P1I2C2P2S1S2S3程序顺序执行的特点：–程序执行的顺序性 –程序环境的封闭性 –程序执行结果的确定性 –计算过程的可再现性程序顺序执行的例子while(1) { input，process，output }78输入机处理器磁带机130 150228280300378430450 时 间处理器利用率：52/(78+52+20)≈35%3.1.2 进程的并发性• 程序的并发执行：若干个程序段同时在 系统中运行，这些程序段的执行在时间上 是重叠的，一个程序段的执行尚未结束， 另一个程序段的执行已经开始，即使这种 重叠是很小的一部分，也称这几个程序段 是并发执行的。

并发性举例• 例如：有两个进程A(a1、a2、a3)和B(b1、b2 、b3) 执行 • 顺序执行： a1、a2、a3、 b1、b2、b3 • 交替执行：a1、 b1、 a2、 b2、 a3、 b3 • 从宏观上看，并发性反映一个时间段中几个 进程都在同一处理器上，处于运行还未运行 结束状态 • 从微观上看，任一时刻仅有一个进程在处理 器上运行表示并发执行的语句S0；CobeginS1；S2；…；SnCoend Sn+1 并发的实质※并发的实质是一个处理器在几个进程 之间的多路复用※并发是对有限的物理资源强制行使多 用户共享，消除计算机部件之间的互等 现象，以提高系统资源利用率顺序执行while(1) { input，process，output }并发执行while(1) { input，send }while(1) { receive，process，send }while(1) { receive，output }图图78输入机处理器磁带机130150228306208286384364 时 间处理器利用率：（52 * n） /（78*n+52+20）= 67%并发进程•并发进程分类：无关的，交互的。

•无关的并发进程：一组并发进程分别 在不同的变量集合上操作，一个进程的 执行与其他并发进程的进展无关 •交互的并发进程，共享某些变量，一 个进程的执行可能影响其他进程的执行 结果，并发的进程之间具有制约关系程序并发执行的特点：• 间断性 • 失去封闭性 • 不可再现性 • 程序与计算不再一一对应两个并发进程共用了一个公共变量N，N＝10程序A . . N=N+1; . .程序B . Print(N); N=0; . .（1） Print(N); N=N+1; N=0; （2 ）N=N+1; N=0; Print(N); （3） N=N+1; Print(N); N=0;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条件举例例如，有如下四条语句：S1: a := x + y S2: b := z + 1S3: 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条件 其他语句并发执行可能会产生与时间有关 的错误并发程序设计的优点§对于单处理器系统,可让处理器 和各I/O设备同时工作,发挥硬部 件的并行能力 §对于多处理器系统,可让各进程 在不同处理器上物理地并行，加 快计算速度 §简化了程序设计任务 采用并发程序设计的目的 Ø 充分发挥硬件的并行性，提高系统 效率硬件能并行工作仅有了提高效率 的可能性，硬部件并行性的实现需要软 件技术去利用和发挥，这种软件技术就 是并发程序设计 Ø 并发程序设计是多道程序设计的基 础，多道程序的实质就是把并发程序设 计引入到系统中与时间有关的错误• 对于一组交往的并发进程，执行的相 对速度无法相互控制，各种与时间有 关的错误就可能出现。

• 与时间有关错误的表现形式：–结果不唯一–永远等待（结果不唯一）购买车票问题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;设有如下执行顺序： T1: x1:=Aj x1=m(m>0) T2: x2:=Aj x2=m(m>0) T2: x2:=x2-1; Aj:=x2 Aj=m-1 T1: x1:=x1-1; Aj:=x1 Aj=m-1 结果：把同一张票买给了两位不同的旅客（结果不唯一）购买车票问题（永远等待）内存管理问题procedure borrow (var B:integer)beginif B>x then{申请进程进入等待队列等主存资源}x:=x-B;{修改主存分配表，申请进程获得主存资源}end;procedure return (var B:integer)beginx:=x+B;{修改主存分配表}{释放等主存资源的进程}end;（永远等待）内存管理问题1.process1调用borrow，结果B>X 2.process2调用return，执行到“释放等待主 存资源的进程”，没有进程等待，退出 3.process1执行“进程进入等待主存资源队列 ” 4.如果以后没有其他process再来归还主存 5.结果process1处于永远等待状态3.1.3进程的交往：竞争与协作（1 ）•系统中的多个进程之间彼此无关 •系统中的多个进程之间彼此相关 资源竞争的两个控制问题： •一个是死锁(Deadlock)问题， •一个是饥饿(Starvation) 问题， 既要解决饥饿问题，又要解决死锁 问题。

进程的交往：竞争与协作(2) 进程互斥(Mutual Exclusion)进程互斥是指若干个进程因相 互争夺独占型资源时所产生的 竞争制约关系进程的交往：竞争与协作(3) 协作关系(1)• 某些进程为完成同一任务需要分工协作 • 进程同步指为完成共同任务的并发进 程基于某个条件来协调 它们的活动，因 为需要在某些位置上排定执行的先后次 序而等待、传递 信号或消息所产生的协 作制约关系进程的交往：竞争与协作(4) 协作关系(2)• 进程同步指两个以上进程基于某个 条件来协调 它们的活动一个进程 的执行依赖于协作进程的消息或信 号，当一个进程没有得到来自于协 作进程的消息或信号时需等待，直 到消息或信号到达才被唤醒进程的交往：竞争与协作(5)•进程互斥关系是一种特殊的进 程同步关系，即逐次使用互斥 共享资源，是对进程使用资源 次序上的一种协调结论• 当程序并发执行时，系统处于一个复杂 的动态组合状态，各程序执行的相对速 度不定，程序员极不容易看到两个同样 的结果，且在众多的结果中应该只有一 个是正确的答案，而其他则是错误的 • 为了保证得到唯一正确的结果，需要实 现并发程序执行时的同步。