并发控制互斥与同步.ppt

第3章 并发控制——互斥与同步 本章知识点： 3.1 并发原理 3.2 互斥——软件解决方法 3.3 互斥——硬件解决方法 3.4 信号量 3.5 管程 3.6 消息传递 3.7 读者/写者问题 3.8 系统举例（略） 3.1 并发原理 在单处理机多道程序的系统中，进程的并发执行方式是插入执行（图3.1a），表面看起来进程如同是同时执行的。在多处理机系统中并发执行方式有插入执行和重叠执行（图3.1b） 。并发的存在要求操作系统必须能跟踪大量活跃进程,必须为每一活跃进程分配资源，必须保护每一进程的数据和物理资源不被其他进程侵犯，并且进程执行的结果与其他并发进程执行时的相对速度无关（P73 例 echo）。 3.1.1 进程间的相互作用 进程之间常常相互作用，存在某种彼此依赖或相互制约（直接或间接）的关系，表现为同步和互斥关系。 根据进程意识到其他进程的存在程度不同，可将进程间的相互作用划分为：进程互不觉察、进程间接觉察、进程直接觉察（见表3.1）。 3.1.2 进程间的相互竞争 并发进程在竞争使用同一资源时将产生冲突。进程间的竞争面临3个控制问题： 互斥—临界资源、临界区的概念 死锁—例如、系统中只有1个输入设备、1个输出设备，而进程P1占有输入设备、申请输出设备；进程P2占有输出设备、申请输入设备。 饥饿—P77例 竞争的控制不可避免地涉及到操作系统，因为是操作系统分配资源，另外，进程自身也必须能以某种方式表达互斥的要求 。 3.1.3 进程间的相互合作 1.通过共享合作 这些进程并不是通过名字察觉到对方，而是通过共享访问间接察觉。进程间通过共享方式进行合作。除互斥、死锁和饥饿外，保证数据的一致性也是一个潜在的控制问题（见P78例）。 3.1.3 进程间的相互合作 2.通过通信合作 进程通信是指进程之间可直接以较高的效率传递较多数据的信息交换方式（例如、信箱通信）。这种方式中采用的是通信机构，在进程通信时往往以消息形式传递信息。因为在消息传递中不存在共享，所以这种形式的合作不需要互斥，但是还存在死锁和饥饿问题。 3.1.4 互斥的要求 并发进程的成功完成需要有定义临界段和实现互斥的能力，这是任何并发进程方案的基础。解决互斥问题必须满足以下要求： 互斥执行 执行非临界段的进程不能受到其他进程的干扰 有限等待 有空让进 没有进程相对速度和数目的假设 进程进入到临界段中的时间有限 3.2 互斥——软件解决方法 软件方法对并发进程不提供任何支持，因此，无论是系统程序或应用程序，进程都要同其他进程合作以解决互斥，它们从程序设计语言和操作系统那里得不到任何支持。软件方法易引起较高的进程负荷和较多的错误，但有利于深刻理解并发的复杂性。 3.2.1 Dekker算法 Dekker算法的优点在于它描述了并发进程发展过程中遇到的大部分共同问题。任何互斥都必须依赖于一些硬件上的基本约束，其中最基本的约束是任一时刻只能有一个进程访问内存中某一位置。 3.2.1 Dekker算法 1.第1种途径：两进程解法 (算法 1) 设两个进程共享一个整型变量 turn 如果变量 turn 的值为 i ，则进程 Pi 可以在其临界区内执行 当 Pi 退出临界区，它置 turn 的值为 j 确保仅有一个进程可以在它的临界区内 存在进程推进问题 如果 turn 的值是 j，而进程 j 并不需要进入临界区；当进程 i 试图进入临界区时，它将被阻塞。 3.2.1 Dekker算法 这种方法保证了互斥，但它只记住了允许哪个进程进入其临界段，未记住每个进程的状态。如果有一个进程以后不进临界区，则另一个进程也无法进入。 3.2.1 Dekker算法 2.第2种途径 有可能两个进程同时进入临界区。这种解决方法依赖于进程执行的相对速度。 3.2.1 Dekker算法 3.第3种途径：两进程解法 (算法 3) 用一个布尔类型的数组 flag 数组元素初始化为 false； flag[i] = false； flag[j] = false； 当进程 Pi 要进入它的临界区，先置 flag[i]为真 flag[i] = true； 进入临界区前，Pi 确信 Pj 没有准备进入临界区 while(flag[j]==true){}； 存在有限等待问题 两个进程可能同时设置它们的标志为 true ，那么就会在各自的 while 语句内无穷循环 3.2.1 Dekker算法 这种方法保证了互斥但会导致死锁问题。 3.2.1 Dekker算法 4.