操作系统原理 周苏 教学课件 第5章 互斥与同步新.ppt

5.6 读者/写者问题 在读者/写者问题中，读进程不会往数据区中写数据，写进程不会从数据区中读数据。更一般的情况是，允许任何进程读写数据区，此时，我们可以把该进程中访问数据区的部分声明成一个临界区，并强行实施一般互斥问题的解决方法。避免写进程间的相互干涉是非常重要的，此外还要求在写的过程中禁止读，以避免访问到不正确的信息。 5.6 读者/写者问题 在生产者/消费者问题中，生产者不仅是一个写进程，它必须读取队列指针，以确定往哪里写下一项，并且它还必须确定缓冲区是否已满。类似地，消费者也不仅仅是一个读进程，它必须调整队列指针以显示它已经从缓冲区中移走了一个单元。 下面我们来分析读者/写者问题的两种解决方案。 5.6.1 读者优先 图5-21是使用信号量的一种解决方案，它给出了读进程和一个写进程的实例，该方案无须修改就可用于多个读进程和写进程的情况。 图5-21 使用信号量解决读者/写者问题的一种方法：读者优先 5.6.1 读者优先 写进程非常简单，信号量wsem用于实施互斥，只要一个写进程正在访问共享数据区，其他的写进程和读进程就都不能访问它。读进程也使用wsem实施互斥，但为了允许多个读进程，当没有读进程正在读时，第一个试图读的读进程需要在wsem上等待。当至少已经有一个读进程在读时，随后的读进程无须等待，可以直接进入。全局变量readcount用于记录读进程的数目，信号量x用于确保readcount被正确地更新。 5.6.2 写者优先 在前面的解决方案中，读进程具有优先权。当一个读进程开始访问数据区时，只要至少有一个读进程正在读，就为读进程保留对这个数据区的控制权，因此，写进程有可能处于饥饿状态。 5.6.2 写者优先 在前面的解决方案中，读进程具有优先权。当一个读进程开始访问数据区时，只要至少有一个读进程正在读，就为读进程保留对这个数据区的控制权，因此，写进程有可能处于饥饿状态。 图5-22给出了另一种解决方案，它保证当一个写进程声明想写时，不允许新的读进程访问该数据区。 图5-22 使用信号量解决读者/写者 问题的一种方法：写者优先 5.6.2 写者优先 对于写进程，在已有定义的基础上还必须增加下列信号量和变量： 信号量rsem：当至少有一个写进程准备访问数据区时，用于禁止所有的读进程。 变量writecount：控制rsem的设置。 信号量y：控制writecount的更新。 对于读进程，还需要一个额外的信号量。在rsem上不允许建造长队列，否则写进程将不能跳过这个队列，因此，只允许一个读进程在rsem上排队，而所有其他读进程在等待rsem之前，在信号量z上排队。表5-5概括了这些可能性。 表5-5 图5-22所示程序中的进程队列状态 5.6.2 写者优先 图5-23给出了另一种可选的解决方案，它赋予写进程优先权，并通过消息传递来实现。在这种情况下，有一个访问共享数据区的控制进程，其他想访问这个数据区的进程给控制进程发送请求消息，如果同意访问，则会收到一个应答消息“OK”，并且通过一个“finished”消息表示访问完成。控制进程备有三个信箱，每个信箱存放一种它可能接收到的消息。 图5-23 使用消息传递解决读者/写者问题的一种方法 5.6.2 写者优先 为了赋予写进程优先权，控制进程先服务于写请求消息，后服务于读请求消息。此外，必须实施互斥，为实现这一点，需要使用变量count，它被初始化为一个大于可能的读进程数的最大值。在这个例子中，我们取值为100。控制器的动作可总结如下： 如果count 0，则无读进程正在等待，可能有也可能没有活跃的读进程。为清除活跃读进程，首先服务于所有“finished”消息，然后服务于写请求，再服务于读请求。 如果count = 0，则唯一未解决的请求是写请求。允许这个写进程继续执行并等待一个“finished”消息。 5.6.2 写者优先 如果count 0，则一个写进程已经发出了一条请求，并且正在等待消除所有活跃的读进程。因此，只有“finished”消息将得到服务。 Thanks！ 5.4.2 使用通知和广播的管程 由于进程是接到通知而不是强制激活，因此就可以给指令表中增加一条cbroadcast原语。广播可以使所有在该条件上等待的进程都被置于就绪状态，当一个进程不知道有多少进程将被激活时，这种方式是非常方便的。例如，在生产者/消费者问题中，假设append和take函数都使用于可变长度的字符块，此时，如果一个生产者往缓冲区中添加了一批字符，它不需要知道每个正在等待的消费者准备消耗多少字符，而仅仅产生一个cbroadcast，所有正在等待的进程都接到通知并再次尝试运行。 5.4.2 使用通知和广播的管程 此外，当一个进程难以准确地判定将激活哪个进程