资源描述
操作系统教程(第4版),第三章并发进程,主讲教师：王慧娇E-mail:whj手机:13978321977QQ:248886622答疑时间：周二14:00-15:30,第三章并发进程,3.1并发进程3.2临界区管理3.3信号量与PV操作3.4管程3.5进程通信3.6死锁3.7Linux同步机制和通信机制3.8Windows2003同步机制和通信机制,3.1并发进程,3.1.1顺序程序设计3.1.2进程的并发性3.1.3进程的交互（InteractionAmongProcesses）：协作和竞争,前驱图(1),前驱图是一个有向无循环图，图中的每个结点可以表示一条语句、一个程序段或一个进程，结点间的有向边表示两个结点之间存在的偏序或前驱关系“”：（Pi,Pj）|Pi必须在Pj开始之前完成,前驱图(2),如果（Pi,Pj）（也可以写成PiPj），则称为Pi是Pj的直接前驱，而Pj是Pi的直接后继。若存在一个序列PiPjPk，则称Pi是Pk的前驱，而Pk是Pi的后继。在前驱图中，没有前驱的结点称为初始结点，没有后继的结点称为终止结点。,前驱图示例,3.1.1顺序程序设计,把一个具有独立功能的程序独占处理机直至最终结束的过程称为程序的顺序执行。如果完成一个任务需要若干不同的程序，则这些程序在时间上也按调用次序严格有序执行（程序外部的顺序性）顺序程序设计是把一个程序设计成一个顺序执行的程序模块，不同程序也按顺序执行。,程序的顺序执行,程序顺序执行的特点：,程序执行的顺序性程序环境的封闭性程序执行结果的确定性计算过程的可再现性,程序顺序执行的例子,while(1)input，process，output,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；SnCoendSn+1,并发的实质,并发的实质是一个处理器在几个进程之间的多路复用并发是对有限的物理资源强制行使多用户共享，消除计算机部件之间的互等现象，以提高系统资源利用率。,顺序执行,while(1)input，process，output,并发执行while(1)input，sendwhile(1)receive，process，sendwhile(1)receive，output,图,图,处理器利用率：（52*n）/（78*n+52+20）=67%,并发进程,并发进程分类：无关的，交互的。无关的并发进程：一组并发进程分别在不同的变量集合上操作，一个进程的执行与其他并发进程的进展无关。交互的并发进程，共享某些变量，一个进程的执行可能影响其他进程的执行结果，并发的进程之间具有制约关系。,程序并发执行的特点：,间断性失去封闭性不可再现性程序与计算不再一一对应,两个并发进程共用了一个公共变量N，N10,程序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+yS2:b:=z+1S3:c:=abS4: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设备同时工作,发挥硬部件的并行能力。对于多处理器系统,可让各进程在不同处理器上物理地并行，加快计算速度。简化了程序设计任务。,采用并发程序设计的目的,充分发挥硬件的并行性，提高系统效率。硬件能并行工作仅有了提高效率的可能性，硬部件并行性的实现需要软件技术去利用和发挥，这种软件技术就是并发程序设计。并发程序设计是多道程序设计的基础，多道程序的实质就是把并发程序设计引入到系统中。,与时间有关的错误,对于一组交往的并发进程，执行的相对速度无法相互控制，各种与时间有关的错误就可能出现。与时间有关错误的表现形式：结果不唯一永远等待,（结果不唯一）购买车票问题,processTi(i=1,2)varXi:integer;begin按旅客定票要求找到Aj；Xi:=Aj;ifXi=1thenbeginXi:=Xi-1;Aj:=Xi;输出一张票；endelse输出票已售完；end;,设有如下执行顺序：T1:x1:=Ajx1=m(m0)T2:x2:=Ajx2=m(m0)T2:x2:=x2-1;Aj:=x2Aj=m-1T1:x1:=x1-1;Aj:=x1Aj=m-1结果：把同一张票买给了两位不同的旅客,（结果不唯一）购买车票问题,（永远等待）内存管理问题,procedureborrow(varB:integer)beginifBxthen申请进程进入等待队列等主存资源x:=x-B;修改主存分配表，申请进程获得主存资源end;procedurereturn(varB:integer)beginx:=x+B;修改主存分配表释放等主存资源的进程end;,（永远等待）内存管理问题,1.process1调用borrow，结果BX2.process2调用return，执行到“释放等待主存资源的进程”，没有进程等待，退出3.process1执行“进程进入等待主存资源队列”4.如果以后没有其他process再来归还主存5.结果process1处于永远等待状态,3.1.3进程的交往：竞争与协作（1）,系统中的多个进程之间彼此无关系统中的多个进程之间彼此相关资源竞争的两个控制问题：一个是死锁(Deadlock)问题，一个是饥饿(Starvation)问题，既要解决饥饿问题，又要解决死锁问题。,进程的交往：竞争与协作(2)进程互斥(MutualExclusion),进程互斥是指若干个进程因相互争夺独占型资源时所产生的竞争制约关系。,进程的交往：竞争与协作(3)协作关系(1),某些进程为完成同一任务需要分工协作。进程同步指为完成共同任务的并发进程基于某个条件来协调它们的活动，因为需要在某些位置上排定执行的先后次序而等待、传递信号或消息所产生的协作制约关系。,进程的交往：竞争与协作(4)协作关系(2),进程同步指两个以上进程基于某个条件来协调它们的活动。一个进程的执行依赖于协作进程的消息或信号，当一个进程没有得到来自于协作进程的消息或信号时需等待，直到消息或信号到达才被唤醒。,进程的交往：竞争与协作(5),进程互斥关系是一种特殊的进程同步关系，即逐次使用互斥共享资源，是对进程使用资源次序上的一种协调。,结论,当程序并发执行时，系统处于一个复杂的动态组合状态，各程序执行的相对速度不定，程序员极不容易看到两个同样的结果，且在众多的结果中应该只有一个是正确的答案，而其他则是错误的。为了保证得到唯一正确的结果，需要实现并发程序执行时的同步。,
展开阅读全文