华东石油大学计算机考研操作系统第二章2.pptVIP

2.4 经典进程的同步问题 生产者-消费者问题 五个哲学家吃通心面问题 读者-写者问题 一、生产者—消费者问题 设有m个生产者进程和n个消费者进程(m，n大于等于1)，它们共享包含k个缓冲区的缓冲池，每一缓冲区可存放一个单位的产品信息。生产者不断地生产产品信息并放入缓冲区中，消费者不断地从缓冲区中取产品信息消费。 分析一：同步互斥关系 同步关系：生产者和消费者两类进程间存在两个同步关系 （1）生产者生产后，消费者才能消费； （2）消费者消费产品腾出缓冲区后，生产者才能生产。 互斥关系：所有进程因共享缓冲区而存在互斥关系 分析二：信号量设置 根据进程间的相互制约关系，设置三个信号量SA、SB和mutex （1）同步信号量SA 标识BUF中有无信息可取，初值为0 生产者Pi进程送信息到BUF后执行V(SA)操作；消费者Cj进程从BUF中取信息前执行P(SA)操作。 （2）同步信号量SB 标识BUF是否空闲，初值为k 生产者Pi进程送信息到BUF前执行P(SB)操作；消费者Cj进程从BUF中取信息后执行V(SB)操作。 （3）互斥信号量mutex 用于控制所有进程互斥使用缓冲区，初值为1 实现 分析：同步与互斥的的正确实现 对临界区的互斥进入 无论是生产者还是消费者对缓冲区的操作部分即临界区均处于P(mutex)和V(mutex)之间，而mutex的初值为1 生产者进程和消费者进程间先生产后消费的同步关系 对消费者来说，它要进入临界区完成取产品的操作必须先执行P(SA)操作。要成功进入临界区则要求执行P(SA)之前SA大于0，即在此之前生产者执行了V(SA)，否则就必须等到生产者将产品放入缓冲区后执行V(SA)操作来将其唤醒。 对生产者来说，它要进入临界区完成放产品信息的操作必须先执行P(SB)操作。要成功进入临界区则要求执行P(SB)之前SB大于0。即在此之前生产者执行了V(SB) 操作，否则就必须等到消费者将产品信息从缓冲区取出后执行V(SB)操作来将其唤醒。  P.V操作讨论 1) 信号量的物理含义： S0表示有S个资源可用 S=0表示无资源可用 S0则| S |表示S等待队列中的进程个数 P(S):表示申请一个资源 V(S)表示释放一个资源。信号量的初值应该大于等于0 2) P.V操作必须成对出现，有一个P操作就一定有一个V操作 当为互斥操作时，它们同处于同一进程 当为同步操作时，则不在同一进程中出现 如果P(S1)和P(S2)两个操作在一起，那么P操作的顺序至 关重要,一个同步P操作与一个互斥P操作在一起时同步P操作在互斥P操作前 而两个V操作无关紧要  P.V操作的优缺点 P.V操作优点： 简单，而且表达能力强（用P.V操作可解决任何同步互斥问题） 缺点： “不够安全；P.V操作使用不当会出现死锁；遇到复杂同步互斥问题时实现复杂 二、五个哲学家吃通心面问题 有五个哲学家围坐在一圆桌旁，桌中央有一盘通心面，每人面前有一只空盘于，每两人之间放一把叉子。每个哲学家思考、饥饿、然后吃通心面。为了吃面，每个哲学家必须获得两把叉子，且每人只能直接从自己左边或右边去取叉子。 为每把叉子设置一个互斥信号量Si，初值均为1。当一个哲学家吃通心面前必须获得自己左边和右边的两把叉子，即执行两个P操作，吃完通心面后必须放下叉子，即执行两个V操作。 三、读者写者问题 条件： 1）多个读者可以同时进行读 2）读者与写者、写者与写者不能同时操作（只允许一个写者写，也不能读者写者同时进行） ***在下面的解法中，读者是优先的，当存在读者时，写操作将被延迟，并且只要有一个读者活跃，随后而来的读者都将被允许访问文件，从而导致了写者长时间等待。 为了有效解决读者写者问题，有的操作系统专门引进了读者/写者锁。读者/写者锁允许多个读者同时以只读方式存取有锁保护的对象；或一个写者以写方式存取有锁保护的对象。当一个或多个读者已上锁后，此时形成了读锁，写者将不能访问有读锁保护的对象；当锁被请求者用于写操作时，形成了写状态，所有其它进程的读写操作必须等待。 分析 1、互斥（读者与写者、写者与写者） 读者与写者、写者与写者互斥 设互斥信号量Wmutex 设一变量readcount统计读者个数，当： Readcount0时 读者可读； Readcount=0 且无写者时可读 Readcount为一共享变量，故要互斥使用，所以设互斥信号量Rmutex 2、写者：写之前P(Wmutex)，写之后V(Wmutex) 读者： 1）读之前： 对Read