2024年5月18日发(作者：摩托罗拉w156)

读者写者算法的改进及其应用

摘 要：分析了操作系统中同步互斥机制中的经典算法之一——读者

写者算法，并对其进行了一些改进，给出了基于PV原语与信号量机

制的解决方案。最后，得出信号量个数和位置的应用是同步互斥精髓

的结论。

关键词：读者写者；同步；互斥；信号量

1 读进程优先改进算法

读进程优先算法是让读者在任何时刻优先于写者，即当有进程在

写文件时，如果有进程请求读，那么新的写进程被拒绝，待现有读进

程完成读操作后，立即让写进程开始运行，当无读进程工作时才让写

进程工作。

为允许多个读进程同时访问数据域，增设变量count表示当前在

读读者的数量，并把互斥变量一分为二，变成写者互斥信号量Wmutex

与读者互斥信号量Rmutex，其中写者互斥信号量用来协调读者与写

者对数据的访问，读者信号量用来使不同读者互斥的访问count变量。

该算法较好满足了上述3个限制，引入的全局变量count控制了

读者操作，阻塞写者的任务交给第一个读的进程，唤醒写者的任务交

给最后一个读的进程。因此，当count变量由0变为1时，执行

P(Wmutex)操作阻止写进程访问，当count变量由1变为0时，执行

V(Wmutex)操作唤醒等待写进程。当count由非0值增加或为非1值

减少时，由于第一个读进程已对写进程进行了阻塞操作，故不需再次

对信号量进行P操作。

通过改变信号量的位置，可以得到一种更好的读进程优先算法。

把P(Rmutex)操作改在P(Wmutex)后面对写操作无影响，对读操

作而言，当有若干读进程同时访问数据域时，第二种写法可以减少单

个读进程对变量count的控制时间，更高效地执行读操作。

该算法的缺点是：读进程会彻底阻塞写进程，当有若干读进程时，

写进程将长期挂起，直至读进程全部执行完毕后，写进程才得以执行。

2 写进程优先改进算法

由于读者优先会造成写者“饥饿”现象，即写者会因为等待读者

而长期得不到资源，而在有些情况下写者需要优于读者占用资源。写

者优先是指新来的写者进程会阻塞后来的读者进程，但是仍然不剥夺

当前在读取数据的读者所占用的数据资源。当没有写者时，读者仍然

可以同时访问的数据域。为实现这一目标，可以分别设置两个计数器

Rcount与Wcount分别表示当前的读者数与写者数，Wcount包括在

写写者与等待写者。Rmutex与Wmutex分别令读者与写者互斥地使

用各自的计数器。如果当第一个写者阻塞信号量为S1时，则后续读

者均会在S1上挂起，这将导致一旦写者进程完成操作后，读者进程

将立即开始操作，因此阻塞信号量应该设在S1前面，同理，读者阻

塞信号量应在S2前。因为此时唤醒策略为先来先服务，为保证写者

优先（即写者被优先唤醒），加一个互斥信号量S_Reader，使得读者

在此被阻塞，而写者可以跨越此信号直接访问。改进如下：

可能出现的两种情况：

（1）当前系统中有若干读进程在读，后来读进程可以继续加入

读者队列，而后来第一个写进程则阻塞其后读进程，但本身被P(S1)

阻塞，且所有非第一个后来写进程将在P(Wmutex)队列上排队。当前

读进程全部执行完毕后写进程开始依次执行。在此后来第一个读进程

将在P(S1)上排队，其他读进程在P(S_Reader)上排队。

（2）当前系统中有若干写进程，其中有一个在写，其他进程在

等待。这时后来的第一个读进程将在P(S1)被阻塞，且其他读进程将

在P(S_Reader)上排队，而其他写进程将在P(S2)上排队。整个执行过

程遵循写优先原则，直到最后一个写进程执行完毕后读队列才开始执

行。

3 兼顾公平改进算法

有些时候，读者写者的优先级是并重的，这要求我们兼顾二者的

优先级，在这种前提下，我们需要一个二者公用的信号量来区分到达

先后顺序。代码如下：

兼顾公平原则较前一种相对简单，公用信号量可以区分到达的先

后顺序，后来进程会因为访问公用信号失败而挂起。从而实现了公平

竞争的原则。

4 读者写者改进算法应用

读者写者问题的变形有很多，但万变不离其中，基本上就是靠信

号量的灵活运用解决问题。下述变形描述：假设公司里有三个部门：

财务部，经理部，员工部。财务部可以登记公司员工（包括领导）的

薪金，经理部和员工部可以访问财务部。但需分开访问（经理部与员

工部访问权限相同），财务部登记时不允许其他部门访问。试用读者

写者模型写出各进程原语。

由问题分析可知，本题中读者分两个，经理部(R_Manage）和员

工部(R_Employee)，写者只有一个，即财务部(W_Finace)，整个问题

的解决采用兼顾公平模式，代码如下：

分析：由于有3个不同对象，故在抢占资源时设置了两个信号量

RS和WS。3个部门访问数据进程数分别用RMcount

（Reader_Manage_count

（Reader_Employee_count

经理部读者数）、REcount

员工部读者数）、WFcount

（Writer_Finace_count财务部写者数）表示，且各部门对其访问方式

仍为互斥。与兼顾公平算法类似，但是读者公用一个信号量RS即可，

各部门对数据进行操作时会阻塞其他部门操作，整个过程严格按照访

问先后顺序执行。

5 结束语

对于临界资源需要灵活掌握其控制方法，但所有的方法离不开对

信号量的控制。只要深入分析问题本质，针对不同情况适当增减信号

量个数或改变所在位置，问题就会迎刃而解。

参考文献：

［1］ WILLIAN ing Systems:Internals and

Design Principles (Sixth Edition)［M］.New York:Prentice Hall，2010.

［2］ 汤子瀛.计算机操作系统［M］.西安:西安电子科技大学出

版社,2006.

［3］ 藤艳平.操作系统中读者写者算法的改进与实现［J］.齐齐

哈尔大学学报,2006(5).