《第3章并发控制互斥与同步》课件.ppt

第3章 并发控制——互斥与同步清华大学 本章知识点： 3.1 并发原理 3.2 互斥——软件解决方法 3.3 互斥——硬件解决方法 3.4 信号量 3.5 管程 3.6 消息传递 3.7 读者/写者问题 3.8 系统举例（略） 3.1 并发原理 在单处理机多道程序的系统中，进程的并发执行方式是插入执行，表面看起来进程如同是同时执行的。在多处理机系统中并发执行方式有插入执行和重叠执行。并发的存在要求操作系统必须能跟踪大量活跃进程,必须为每一活跃进程分配资源，必须保护每一进程的数据和物理资源不被其他进程侵犯，并且进程执行的结果与其他并发进程执行时的相对速度无关。 3.1.1 进程间的相互作用 进程之间常常相互作用，存在某种彼此依赖或相互制约的关系：同步和互斥关系。 根据进程意识到其他进程的存在程度不同，可将进程间的相互作用划分为：进程互不觉察、进程间接觉察、进程直接觉察。 3.1.2 进程间的相互竞争 并发进程在竞争使用同一资源时将产生冲突。进程间的竞争面临3个控制问题： 互斥 死锁 饥饿 竞争的控制不可避免地涉及到操作系统，因为是操作系统分配资源，另外，进程自身也必须能以某种方式表达互斥的要求 。 3.1.3 进程间的相互合作 1.通过共享合作 这些进程并不是通过名字察觉到对方，而是通过共享访问间接察觉。进程间通过共享方式进行合作。除互斥、死锁和饥饿外，保证数据的一致性也是一个潜在的控制问题。 3.1.3 进程间的相互合作 2.通过通信合作 进程通信是指进程之间可直接以较高的效率传递较多数据的信息交换方式。这种方式中采用的是通信机构，在进程通信时往往以消息形式传递信息。因为在消息传递中不存在共享，所以这种形式的合作不需要互斥，但是还存在死锁和饥饿问题。 3.1.4 互斥的要求 并发进程的成功完成需要有定义临界段和实现互斥的能力，这是任何并发进程方案的基础。解决互斥问题必须满足以下要求： 互斥执行 执行非临界段的进程不能受到其他进程的干扰 有限的等待 没有进程相对速度和数目的假设 进程进入到临界段中的时间有限 3.2 互斥——软件解决方法 软件方法对并发进程不提供任何支持，因此，无论是系统程序或应用程序，进程都要同其他进程合作以解决互斥，它们从程序设计语言和操作系统那里得不到任何支持。软件方法易引起较高的进程附和较多的错误，但有利于深刻理解并发的复杂性。 3.2.1 Dekker算法 Dekker算法的优点在于它描述了并发进程发展过程中遇到的大部分共同问题。任何互斥都必须依赖于一些硬件上的基本约束，其中最基本的约束是任一时刻只能有一个进程访问内存中某一位置。 3.2.1 Dekker算法 1.第1种途径 这种方法保证了互斥，但它只记住了允许哪个进程进入其临界段，未记住每个进程的状态。 3.2.1 Dekker算法 2.第2种途径 这种解决方法依赖于进程执行的相对速度 3.2.1 Dekker算法 3.第3种途径 这种方法保证了互斥但会导致死锁问题。 3.2.1 Dekker算法 4.第4种途径 3.2.1 Dekker算法 5.一个正确的解决方法 设计一个“指示”小屋，小屋内的黑板标明“turn”，当P0想进入其临界段时，置自己的flag为“true”，这时它去查看P1的flag，如果是“false”，则P0就立即进入自己的临界段，反之P0去查看“指示”小屋，如果turn=0，那么它知道自己应该坚持并不时去查看P1的小屋， P1将觉察到它应该放弃并在自己的黑板上写上“false”，以允许P0继续执行。 P0执行完临界段后，它将flag置为“false”以释放临界段，并且将turn置为1，将进入权交给P1 。 3.2.2 Peterson算法 Dekker算法可以解决互斥问题，但是，其复杂的程序难于理解，其正确性难于证明。Peterson给出了一个简单的方法。下面是一个两进程互斥的简单解决方法，进一步可将Peterson算法推广到多个进程的情况。 3.2.2 Peterson算法 3.3 互斥——硬件解决方法 完全利用软件方法来解决进程互斥进入临界区的问题有一定的难度，且有很大局限性，现在有许多计算机提供了一些可以解决临界区问题的特殊的硬件指令。硬件方法通过特殊的机器指令实现互斥，可以降低开销。 3.3.1 禁止中断 在单处理机中，禁止进程被中断即可保证互斥，通过操作系统内核定义的禁止和允许中断的原语就可获得这种能力。进程执行临界段时不能被中断。 优点： 在单处理机中可保证