經典讀寫進程問題的改進算法

李廣軍

【摘要】讀者-寫者問題是操作系統中經典進程同步問題之一，本文在闡述傳統解決讀者寫者問題方案的基礎上，給出了改進解決方案和算法。

【關鍵詞】進程； 同步； 互斥； 信號量

引言

利用信號量機制來實現讀者與寫者的同步問題，一直是操作系統中討論一個的經典進程同步問題.這類題型變化多、實例多，又與實際生活中的問題有著緊密聯系，本文利用信號量機制和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