并发控制互斥与同步

《并发控制互斥与同步》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第3章并发控制——互斥与同步清华大学本章知识点：3.1并发原理3.2互斥——软件解决方法3.3互斥——硬件解决方法3.4信号量3.5管程3.6消息传递3.7读者/写者问题3.8系统举例（略）13.1并发原理在单处理机多道程序的系统中，进程的并发执行方式是插入执行，表面看起来进程如同是同时执行的。在多处理机系统中并发执行方式有插入执行和重叠执行。并发的存在要求操作系统必须能跟踪大量活跃进程,必须为每一活跃进程分配资源，必须保护每一进程的数据和物理资源不被其他进程侵犯，并且进程执行的结果与其他并发进程执行时的相对速度无关。23.1.1进程间的相互作用进程之间常常

2、相互作用，存在某种彼此依赖或相互制约的关系：同步和互斥关系。根据进程意识到其他进程的存在程度不同，可将进程间的相互作用划分为：进程互不觉察、进程间接觉察、进程直接觉察。33.1.2进程间的相互竞争并发进程在竞争使用同一资源时将产生冲突。进程间的竞争面临3个控制问题：互斥死锁饥饿竞争的控制不可避免地涉及到操作系统，因为是操作系统分配资源，另外，进程自身也必须能以某种方式表达互斥的要求。43.1.3进程间的相互合作1.通过共享合作这些进程并不是通过名字察觉到对方，而是通过共享访问间接察觉。进程间通过共享方式进行合作。除互斥、死锁和饥饿外，保证数据的一致性也是一个潜

3、在的控制问题。53.1.3进程间的相互合作2.通过通信合作进程通信是指进程之间可直接以较高的效率传递较多数据的信息交换方式。这种方式中采用的是通信机构，在进程通信时往往以消息形式传递信息。因为在消息传递中不存在共享，所以这种形式的合作不需要互斥，但是还存在死锁和饥饿问题。63.1.4互斥的要求并发进程的成功完成需要有定义临界段和实现互斥的能力，这是任何并发进程方案的基础。解决互斥问题必须满足以下要求：互斥执行执行非临界段的进程不能受到其他进程的干扰有限的等待没有进程相对速度和数目的假设进程进入到临界段中的时间有限73.2互斥——软件解决方法软件方法对并发进程不

4、提供任何支持，因此，无论是系统程序或应用程序，进程都要同其他进程合作以解决互斥，它们从程序设计语言和操作系统那里得不到任何支持。软件方法易引起较高的进程附和较多的错误，但有利于深刻理解并发的复杂性。83.2.1Dekker算法Dekker算法的优点在于它描述了并发进程发展过程中遇到的大部分共同问题。任何互斥都必须依赖于一些硬件上的基本约束，其中最基本的约束是任一时刻只能有一个进程访问内存中某一位置。93.2.1Dekker算法1.第1种途径这种方法保证了互斥，但它只记住了允许哪个进程进入其临界段，未记住每个进程的状态。varturn:0..1;{turn为共享

5、的全局变量}PROCESS0PROCESS1……whileturn≠0do{nothing}whileturn≠1do{nothing}；〈criticalsection〉;〈criticalsection〉;turn:=1;turn:=0;……103.2.1Dekker算法2.第2种途径这种解决方法依赖于进程执行的相对速度共享的全局变量是：varflag:array[0..1]ofboolean;它被初始化为falsePROCESS0PROCESS1……whileflag[1]do{nothing};whileflag[0]do{nothing};flag[

6、0]:=true;flag[1]:=true;〈criticalsection〉;〈criticalsection〉;flag[0]:=false;flag[1]:=false;……113.2.1Dekker算法3.第3种途径这种方法保证了互斥但会导致死锁问题。PROCESS0PROCESS1……flag[0]:=true;flag[1]:=true;whileflag[1]do{nothing};whileflag[0]do{nothing};〈criticalsection〉;〈criticalsection〉;flag[0]:=false;flag[1]

7、:=false;……123.2.1Dekker算法4.第4种途径PROCESS0PROCESS1……flag[0]:=true;flag[1]:=true;whileflag[1]do{nothing};whileflag[0]do{nothing};beginbeginflag[0]:=false;flag[1]:=false;〈delayforashorttime〉;〈delayforashorttime〉;flag[0]:=true;flag[1]:=true;end;end;〈criticalsection〉;〈criticalsection〉;fla

8、g[0]:=false；flag[1]