《并发控制互斥与同步》由会员分享，可在线阅读，更多相关《并发控制互斥与同步（75页珍藏版）》请在金锄头文库上搜索。
1、第3章 并发控制互斥与同步 本章知识点：n3.1 并发原理 n3.2 互斥软件解决方法n3.3 互斥硬件解决方法 n3.4 信号量n3.5 管程n3.6 消息传递n3.7 读者/写者问题n3.8 系统举例（略） 13.1 并发原理 在单处理机多道程序的系统中，进程 的并发执行方式是插入执行（图3.1a）， 表面看起来进程如同是同时执行的。在多 处理机系统中并发执行方式有插入执行和 重叠执行（图3.1b） 。并发的存在要求操 作系统必须能跟踪大量活跃进程,必须为 每一活跃进程分配资源，必须保护每一进 程的数据和物理资源不被其他进程侵犯， 并且进程执行的结果与其他并发进程执行 时的相对速度无关（P
2、73 例 echo）。23.1.1 进程间的相互作用进程之间常常相互作用，存在某种 彼此依赖或相互制约（直接或间接） 的关系，表现为同步和互斥关系。根据进程意识到其他进程的存在程 度不同，可将进程间的相互作用划分 为：进程互不觉察、进程间接觉察、 进程直接觉察（见表3.1）。33.1.2 进程间的相互竞争 并发进程在竞争使用同一资源时将产生冲突 。进程间的竞争面临3个控制问题：n互斥临界资源、临界区的概念n死锁例如、系统中只有1个输入设备、1个输出 设备，而进程P1占有输入设备、申请输出设备； 进程P2占有输出设备、申请输入设备。n饥饿P77例竞争的控制不可避免地涉及到操作系统，因为 是操作系
3、统分配资源，另外，进程自身也必须能 以某种方式表达互斥的要求 。43.1.3 进程间的相互合作 1.通过共享合作这些进程并不是通过名字察觉到对方 ，而是通过共享访问间接察觉。进程间 通过共享方式进行合作。除互斥、死锁 和饥饿外，保证数据的一致性也是一个 潜在的控制问题（见P78例）。53.1.3 进程间的相互合作2.通过通信合作进程通信是指进程之间可直接以较 高的效率传递较多数据的信息交换方式 （例如、信箱通信）。这种方式中采用 的是通信机构，在进程通信时往往以消 息形式传递信息。因为在消息传递 中 不存在共享，所以这种形式的合作不需 要互斥，但是还存在死锁和饥饿问题 。 63.1.4 互斥的
4、要求 并发进程的成功完成需要有定义临界段和实 现互斥的能力，这是任何并发进程方案的基础 。解决互斥问题必须满足以下要求：n互斥执行 n执行非临界段的进程不能受到其他进程的干扰 n有限等待n有空让进 n没有进程相对速度和数目的假设 n进程进入到临界段中的时间有限 73.2 互斥软件解决方法软件方法对并发进程不提供任何支持 ，因此，无论是系统程序或应用程序， 进程都要同其他进程合作以解决互斥， 它们从程序设计语言和操作系统那里得 不到任何支持。软件方法易引起较高的 进程负荷和较多的错误，但有利于深刻 理解并发的复杂性。83.2.1 Dekker算法Dekker算法的优点在于它描述了 并发进程发展过
5、程中遇到的大部分 共同问题。任何互斥都必须依赖于 一些硬件上的基本约束，其中最基 本的约束是任一时刻只能有一个进 程访问内存中某一位置。 93.2.1 Dekker算法n1.第1种途径：两进程解法 (算法 1)l设两个进程共享一个整型变量 turnl如果变量 turn 的值为 i ，则进程 Pi 可以在其临界区内执行l当 Pi 退出临界区，它置 turn 的值为 jl确保仅有一个进程可以在它的临界区 内l存在进程推进问题l如果 turn 的值是 j，而进程 j 并不需要进 入临界区；当进程 i 试图进入临界区时， 它将被阻塞。 103.2.1 Dekker算法 这种方法保证了互斥，但它只记住了
6、允许哪 个进程进入其临界段，未记住每个进程的状态。 如果有一个进程以后不进临界区，则另一个进程 也无法进入。 var turn: 01; turn为共享的全局变量 PROCESS 0 PROCESS 1 while turn0 do nothing while turn1 do nothing；critical section; critical section; turn: =1; turn: =0; 113.2.1 Dekker算法2.第2种途径有可能两个进程同时进入临界区。这种解 决方法依赖于进程执行的相对速度。共享的全局变量是：var flag: array01of boolean;
7、它被初始化为false PROCESS 0 PROCESS 1 while flag1do nothing; while flag0do nothing; flag0: =true; flag1: =true; critical section; critical section; flag0: =false; flag1: =false; 123.2.1 Dekker算法n3.第3种途径：两进程解法 (算法 3) l用一个布尔类型的数组 flagl 数组元素初始化为 false；lflagi = false；lflagj = false；l当进程 Pi 要进入它的临界区，先置 flagi为真
8、flagi = true； l进入临界区前，Pi 确信 Pj 没有准备进入临界区while(flagj=true)；l存在有限等待问题l两个进程可能同时设置它们的标志为 true ， 那么就会在各自的 while 语句内无穷循环 133.2.1 Dekker算法这种方法保证了互斥但会导致死锁问题。 PROCESS 0 PROCESS 1 flag0: =true; flag1: =true; while flag1 do nothing; while flag0 do nothing; critical section; critical section; flag0: =false; fla
9、g1: =false; 143.2.1 Dekker算法4.第4种途径（接近正确，但还有缺陷；书上有错 ）PROCESS 0 PROCESS 1 flag0: =true; flag1: =true; while flag1 do while flag0 do begin beginflag0: =false; flag1: =false;delay for a short time; delay for a short time;flag0: =true; flag1: =true; end; end; critical section; critical section; flag0: =
10、false； flag1: =false; 153.2.1 Dekker算法5.第五种途径(一个正确的解决方法) 用变量turn表示哪个进程坚持进入临界区设计一个“指示”小屋，小屋内的黑板标明“turn”， 当P0想进入其临界段时，置自己的flag为“true”，这时 它去查看P1的flag，如果是“false”，则P0就立即进入自 己的临界段，反之P0去查看“指示”小屋，如果turn=0 ，那么它知道自己应该坚持并不时去查看P1的小屋， P1将觉察到它应该放弃并在自己的黑板上写上“false” ，以允许P0继续执行。 P0执行完临界段后，它将flag 置为“false”以释放临界段，并且将t
11、urn置为1，将进入 权交给P1 。163.2.2 Peterson算法 Dekker算法（正确的解法）可以 解决互斥问题，但是，其复杂的程序 难于理解，其正确性难于证明。 Peterson给出了一个简单的方法。下 面是一个两进程互斥的简单解决方法 ，进一步可将Peterson 算法推广到多 个进程的情况。 173.2.2 Peterson算法n结合前面的算法 3l用 flag 数组标志和一个 turn 变量lturn变量确保不会死锁l满足互斥，有空让进和有限等待的需 求l仅解决两个进程的临界区问题l参见下面的代码n(本书解决 n 个进程的临界区问题)183.2.2 Peterson算法For
12、 process For process i i flagi = true; / I want to go critical turn = j; / but you go first if you want while (flagj / wait while j is in critical critical section/ go critical flagi = false; / Im done193.2.2 Peterson算法For process For process j j flagj = true; / I want to go critical turn = i; / but you go first if you want while (flagi / wait while i is in critical critical section/ go critical flagj = false; / Im done203.2.2 Peterson算法var flag: array01 of boolean; flag1: =true;turn: 01; turn: =0; procedure P0; while flag0 and turn=0 do nothing; begin
