《第三章同步通信与死锁》由会员分享，可在线阅读，更多相关《第三章同步通信与死锁（22页珍藏版）》请在金锄头文库上搜索。
1、第三章 同步、通信与死锁2010年年10月月第三章 并发进程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进程的交互：协作和竞争 进程的顺序性v一个进程在顺序处理器上的执行是严格按序的，一个进程只有当一个操作结束后，才能开始后继操作v顺序程序设计是把一个程序设计成一个顺序执行的程序模块，顺序的含义不但指一个程序模块内部，也指两个程序模块之间。顺序程序设计特点 程序执行的顺序性 程序环境的
2、封闭性 程序执行结果的确定性 计算过程的可再现性进程的并发性(1)v进程执行的并发性：一组进程的执行在时间上是重叠的。v并发性举例：有两个进程A(a1、a2、a3)和B(b1、b2、b3)并发执行。 v从宏观上看，并发性反映一个时间段中几个进程都在同一处理器上，处于运行还未运行结束状态。v从微观上看，任一时刻仅有一个进程在处理器上运行。进程的并发性(2) 进程i1 i1p1p1i ip po oo1o1i2i2p2p2o2o2i3i3p3p3o3o3t1 t1t2t2t3t3时间时间并行工作并行工作i4i4t4t4i5i5P4P4进程的并发性(3)v并发的实质是一个处理器在几个进程之间的多路复
3、用，并发是对有限的物理资源强制行使多用户共享，消除计算机部件之间的互等现象，以提高系统资源利用率。无关的并发进程v并发进程分类：无关的，交往的。v无关的并发进程：一组并发进程分别在不同的变量集合上操作，一个进程的执行与其他并发进程的进展无关。v并发进程的无关性是进程的执行与时间无关的一个充分条件，又称为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)= 则并发进程的执行与时间
4、无关。Bernstein条件举例 例如，有如下四条语句： 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条件。其他语句并发执行可能会产生与时间有关的错误。交往的并发进程v交往的并发进程：一组并发进程共享某些变量，一个进程的执行可能影响其他并发进程的结果。并发程序设计的优点对于单处理器系统,可让处理器和各I/O设备同时工作,发挥硬部件的
5、并行能力。对于多处理器系统,可让各进程在不同处理器上物理地并行，加快计算速度。简化了程序设计任务。 采用并发程序设计的目的v充分发挥硬件的并行性，提高系统效率。硬件能并行工作仅有了提高效率的可能性，硬部件并行性的实现需要软件技术去利用和发挥，这种软件技术就是并发程序设计。v并发程序设计是多道程序设计的基础，多道程序的实质就是把并发程序设计引入到系统中。与时间有关的错误v对于一组交往的并发进程，执行的相对速度无法相互控制，各种与时间有关的错误就可能出现。v与时间有关错误的表现形式：结果不唯一永远等待 （结果不唯一）机票问题 / /飞机票售票问题飞机票售票问题vvoid T1( ) void T2
6、( ) void T1( ) void T2( ) v 按旅客订票要求找到按旅客订票要求找到AjAj; ; 按旅客订票要求找到按旅客订票要求找到AjAj; ;v intint X1= X1=AjAj; ; intint X2= X2=AjAj; ;v if(X1=1) if(X2=1) if(X1=1) if(X2=1) v X1-; X2-; X1-; X2-; v AjAj=X1; =X1; AjAj=X2;=X2;v 输出一张票输出一张票; ; 输出一张票输出一张票; ;v velse else elseelsev 输出信息输出信息 票已售完票已售完; ; 输出信息输出信息 票已售完票已
7、售完;v （永远等待）主存管理问题 申请和归还主存资源问题申请和归还主存资源问题vintint X=memory; /memory X=memory; /memory为初始主存容量为初始主存容量vvoidvoid borrow(intborrow(int B) void B) void return(intreturn(int B) B) v while(Bwhile(BX) X=X+B;X) X=X+B;v 进程进入等待主存资源队列进程进入等待主存资源队列; ; 修改主存分配表修改主存分配表; ;v X=X-B ; X=X-B ; 释放等主存资源进程释放等主存资源进程; ; v 修改主存分配
8、表，进程获得主存资源修改主存分配表，进程获得主存资源; ; v 进程的交往：竞争与协作(1)第一种是竞争关系 v系统中的多个进程之间彼此无关v系统中的多个进程之间彼此相关 资源竞争的两个控制问题： 一个是死锁(Deadlock)问题， 一个是饥饿(Starvation)问题，既要解决饥饿问题，又要解决死锁问题。进程的交往：竞争与协作(2)进程互斥进程互斥(Mutual Exclusion)(Mutual Exclusion) 进程互斥是指若干个进程因相互争夺独占型资源时所产生的竞争制约关系。进程的交往：竞争与协作(3)第二种是协作关系(1) 某些进程为完成同一任务需要分工协作。 进程同步指为完成共同任务的并发进程基于某个条件来协调它们的活动，因为需要在某些位置上排定执行的先后次序而等待、传递信号或消息所产生的协作制约关系。进程的交往：竞争与协作(4)第二种是协作关系(2) 进程同步指两个以上进程基于某个条件来协调它们的活动。一个进程的执行依赖于协作进程的消息或信号，当一个进程没有得到来自于协作进程的消息或信号时需等待，直到消息或信号到达才被唤醒。 进程的交往：竞争与协作(5)v进程互斥关系是一种特殊的进程同步关系，即逐次使用互斥共享资源，是对进程使用资源次序上的一种协调。
