经典读写进程问题的改进算法

李广军

【摘要】读者-写者问题是操作系统中经典进程同步问题之一，本文在阐述传统解决读者写者问题方案的基础上，给出了改进解决方案和算法。

【关键词】进程； 同步； 互斥； 信号量

引言

利用信号量机制来实现读者与写者的同步问题，一直是操作系统中讨论一个的经典进程同步问题.这类题型变化多、实例多，又与实际生活中的问题有着紧密联系，本文利用信号量机制和wait、signal操作，在读者-写者问题传统传统解决方案的给出了两种改进解决方案.

1.读写同步问题及传统解决方案

1.1 问题内容

某共享文件，多个读者（只读文件进程）和多个写者（只写文件进程）在某个时间段内对该文件资源异步进行读写.为避免文件数据出现丢失修改和读脏数据的情况，对读者写者要求如下：

（1）读-读共享，即允许多个读者同时对文件进行读操作.

（2）读-写互斥，即不允许读者和写者同时对文件分别进行读写操作.

（3）写-写互斥，即不允许多个写者同时对文件进行写操作.

1.2 传统解决方案

解决方案：为实现读者与写者进程间在读写和写写互斥设置一个互斥信号量Wmutex.另外，再设置一个整型变量Readercount表示正在读的进程数目.由于只要有一个读进程在读，便不允许写进程去写.因此，仅当Readercount =0，表示尚无读进程在读时，读进程才需要执行Wait（Wmutex）操作.若Wait（Wmutex）操作成功，读进程便可去读，相应地做Readercount+1操作.同理，仅当读进程在执行了Readercount-1操作后其值为0时，才须执行Signal（Wmutex）操作，以便让写进程操作.又因为Readercount是一个可被多个读进程访问的临界资源，因此，也应该为它设置一个互斥信号量Rmutex.

2.读写问题改进解决方案

2.1 读写同步公平竞争解决方案

解决方案：为实现读者与写者进程间在读写和写写互斥设置一个互斥信号量Wmutex.另外，再设置一个整型变量Readercount表示正在读的进程数目.由于只要有一个读进程在读，便不允许写进程去写.因此，仅当Readercount =0，表示尚无读进程在读时，读进程才需要执行Wait（Wmutex）操作.若Wait（Wmutex）操作成功，读进程便可去读，相应地做Readercount+1操作.同理，仅当读進程在执行了Readercount-1操作后其值为0时，才须执行Signal（Wmutex）操作，以便让写进程操作.又因为Readercount是一个可被多个读进程访问的临界资源，因此，也应该为它设置一个互斥信号量Rmutex.

算法描述：

Var Rmutex，Wmutex：semaphore：=1，1；

Readercount：integer：=0；

Reader（读者进程）

begin

repeat

wait（Rmutex）；

if Readercount=0 then wait（Wmutex）；

Readercount：= Readercount+1；

signal（Rmutex）；

……

perform read operation；

……

wait（Rmutex）；

Readercount：= Readercount-1；

if Readercount=0 then signal（Wmutex）；

signal（Rmutex）；

until false；

end

writer（写者进程）

begin

repeat

wait（Wmutex）；

……

perform write operation；

……

signal（Wmutex）；

until false；

end

结果分析：该方案已经基本满足题目要求，但读者的高优先级可能造成后续的写者由于被随后而来的读者插队而长时间等待，直到全部读者进程运行完毕后，才可以使用文件.所以说上述算法为读者优先方案.

2.2 写者优先的解决方案

在原读者-写者问题上增加两点要求（1）仅当无写者时才允许读者使用文件；（2）多个读写进程等待时首先考虑唤醒写者.

算法描述：

Var Rmutex，Wmutex， Wcmutex，Idmutex ，Enmutex：semaphore：=1，1，1，1，1；

Readercount，writercount：integer：=0，0；

Reader（读者进程）

begin

repeat

wait（Enmutex）；

wait（Idmutex）；

wait（Rmutex）；

if Readercount=0 then wait（Wmutex）；

Readercount：= Readercount+1；

signal（Rmutex）；

signal（Idmutex）；

signal（Enmutex）；

……

perform read operation；

……

wait（Rmutex）；

Readercount：= Readercount-1；

if Readercount=0 then signal（Wmutex）；

signal（Rmutex）；

until false；

end

writer（寫者进程）

begin

repeat

wait（Wcmutex）

if writercount=0 then wait（Idmutex）；

writercount：=writercount+1；

signal（Wcmutex）；

wait（Wmutex）；

……

perform write operation；

……

signal（Wmutex）；

wait（Wcmutex）

writercount：=writercount-1；

if writercount=0 then signal（Idmutex）；

signal（Wcmutex）；

until false；

end

结果分析：该方案在满足读写同步问题要求的前提下也实现写者进程优先的要求.

3.结论

读写同步问题是进程同步问题中的经典实例，若对它问题能熟练掌握的话，那么对于常见一类进程多次访问，而不同类的进程必须互斥访问资源的控制这类问题也就不难解决了.

参考文献

[1]帖军，陆际光.同步互斥机制中的读者-写者模型[J].武汉：中南民族大学学报.2013-09

[2]汤子瀛，哲凤屏.计算机操作系统[M].西安：西安电子科技大学出版社.2012-04

[3]赵素萍.浅谈信号量的设置与使用[J].福建：福建电脑 2013-10

[4]程晓锦."读者-写者"问题的Java实现[J].北京：北京印刷学院学报，2010-03

[5]房永龙，周书民.基于线程的短信实时并发算法[J].上海：计算机应用与软件 2016-04

[6]夏春梅.用记录型信号量解决读者—写者问题[J].安微：机械工业出版社，2012-06