计算机操作系统(第三章)_3.5(进程的互斥与同步).ppt

3. 哲学家进餐问题(the dining philosophers problem) 问题描述：（由Dijkstra首先提出并解决）5个哲学家围绕一张圆桌而坐，桌子上放着5支筷子，每两个哲学家之间放一支；哲学家的动作包括思考和进餐，进餐时需要同时拿起他左边和右边的两支筷子，思考时则同时将两支筷子放回原处。如何保证哲学家们的动作有序进行？如：不出现相邻者同时要求进餐；不出现有人永远拿不到筷子； 哲学家进餐.exe 第三章 进程管理 第*页 * * * * * 互斥的例子： 例1：进程A、B共享一台打印机，则当一进程占用打印机后，另一进程若也要使用打印机，则必须等待，直至它释放打印机。 例2：机票预订系统 A B 旅行社A查到某机座空； ： ： 旅行社B查到某机座空； 与其顾客商量； ： ： 旅行社A预订该机座； ： B预订该机座； 第三章 进程管理 第*页 * 并发进程互斥必须满足的原则 (1) 不能假设各并发进程的相对执行速度。即各并发进程享有平等的、独立的竞争共有资源的权利，且在不采取任何措施的条件下，在临界区内任一指令结束时，其他并发进程可以进入临界区。 (2) 并发进程中的某个进程不在临界区时，它不阻止其他进程进入临界区。(空闲让进） (3) 并发进程中的若干个进程申请进入临界区时，只能允许一个进程进入 (4) 并发进程中的某个进程申请进入临界区时开始，应在有限时间内得以进入临界区 准则(1)，(2)，(3)是保证各并发进程享有平等的、独立的竞争和使用公有资源的权利，且保证每一时刻至多只有一个进程在临界区。而准则(4)则是并发进程不发生死锁（将在后面讲述）的重要保证。 第三章 进程管理 第*页 * 进入临界区的准则： (1)每次至多有一个进程处于临界区； (2)当有若干个进程欲进入临界区时，应在有限 的时间内使其进入； (3)进程在临界区内仅逗留有限的时间。 第三章 进程管理 第*页 * 3.5.2 互斥的加锁实现 人们可能认为只需把临界区中的各个过程按不同的时间排列调用就行了，但由于用户程序执行开始的随机性，要求该组并发进程中的每个进程事先知道其他并发进程与系统的动作。不可能把临界区中的各个过程按不同的时间排列调用。因此，互斥的实现必须通过加锁的方式进行解决。 1、互斥的实现 当某个进程进入临界区之后，它将锁上临界区，直到它退出临界区时为止。并发进程在申请进入临界区时，首先测试该临界区是否是上锁的。如果该临界区已被锁住，则该进程要等到该临界区开锁之后才有可能获得临界区。 第三章 进程管理 第*页 * 二. 用锁实现互斥 1.锁和上锁、开锁操作 解决进程互斥的最简单的办法是加锁。 在系统中为每个临界资源设置一个锁位， 0 表示资源可用， 1 表示资源已被占用（不可用）。 同时,系统要提供上锁原语和开锁原语，供进程在使用临界资源之前和使用完临界资源之后使用。 第三章 进程管理 第*页 * 2.用上锁原语和开锁原语实现进程互斥 上锁原语 进入临界区csb 开锁原语 进程B 上锁原语 进入临界区csa 开锁原语 进程A 第三章 进程管理 第*页 * main ( ) ppa ( ) ppb ( ) { { { int w=0; : : cobegin lock(w); lock(w); ppa(); CSa;