經(jīng)典讀寫(xiě)進(jìn)程問(wèn)題的改進(jìn)算法

李廣軍

【摘要】讀者-寫(xiě)者問(wèn)題是操作系統(tǒng)中經(jīng)典進(jìn)程同步問(wèn)題之一，本文在闡述傳統(tǒng)解決讀者寫(xiě)者問(wèn)題方案的基礎(chǔ)上，給出了改進(jìn)解決方案和算法。

【關(guān)鍵詞】進(jìn)程； 同步； 互斥； 信號(hào)量

引言

利用信號(hào)量機(jī)制來(lái)實(shí)現(xiàn)讀者與寫(xiě)者的同步問(wèn)題，一直是操作系統(tǒng)中討論一個(gè)的經(jīng)典進(jìn)程同步問(wèn)題.這類(lèi)題型變化多、實(shí)例多，又與實(shí)際生活中的問(wèn)題有著緊密聯(lián)系，本文利用信號(hào)量機(jī)制和wait、signal操作，在讀者-寫(xiě)者問(wèn)題傳統(tǒng)傳統(tǒng)解決方案的給出了兩種改進(jìn)解決方案.

1.讀寫(xiě)同步問(wèn)題及傳統(tǒng)解決方案

1.1 問(wèn)題內(nèi)容

某共享文件，多個(gè)讀者（只讀文件進(jìn)程）和多個(gè)寫(xiě)者（只寫(xiě)文件進(jìn)程）在某個(gè)時(shí)間段內(nèi)對(duì)該文件資源異步進(jìn)行讀寫(xiě).為避免文件數(shù)據(jù)出現(xiàn)丟失修改和讀臟數(shù)據(jù)的情況，對(duì)讀者寫(xiě)者要求如下：

（1）讀-讀共享，即允許多個(gè)讀者同時(shí)對(duì)文件進(jìn)行讀操作.

（2）讀-寫(xiě)互斥，即不允許讀者和寫(xiě)者同時(shí)對(duì)文件分別進(jìn)行讀寫(xiě)操作.

（3）寫(xiě)-寫(xiě)互斥，即不允許多個(gè)寫(xiě)者同時(shí)對(duì)文件進(jìn)行寫(xiě)操作.

1.2 傳統(tǒng)解決方案

解決方案：為實(shí)現(xiàn)讀者與寫(xiě)者進(jìn)程間在讀寫(xiě)和寫(xiě)寫(xiě)互斥設(shè)置一個(gè)互斥信號(hào)量Wmutex.另外，再設(shè)置一個(gè)整型變量Readercount表示正在讀的進(jìn)程數(shù)目.由于只要有一個(gè)讀進(jìn)程在讀，便不允許寫(xiě)進(jìn)程去寫(xiě).因此，僅當(dāng)Readercount =0，表示尚無(wú)讀進(jìn)程在讀時(shí)，讀進(jìn)程才需要執(zhí)行Wait（Wmutex）操作.若Wait（Wmutex）操作成功，讀進(jìn)程便可去讀，相應(yīng)地做Readercount+1操作.同理，僅當(dāng)讀進(jìn)程在執(zhí)行了Readercount-1操作后其值為0時(shí)，才須執(zhí)行Signal（Wmutex）操作，以便讓寫(xiě)進(jìn)程操作.又因?yàn)镽eadercount是一個(gè)可被多個(gè)讀進(jìn)程訪問(wèn)的臨界資源，因此，也應(yīng)該為它設(shè)置一個(gè)互斥信號(hào)量Rmutex.

2.讀寫(xiě)問(wèn)題改進(jìn)解決方案

2.1 讀寫(xiě)同步公平競(jìng)爭(zhēng)解決方案

解決方案：為實(shí)現(xiàn)讀者與寫(xiě)者進(jìn)程間在讀寫(xiě)和寫(xiě)寫(xiě)互斥設(shè)置一個(gè)互斥信號(hào)量Wmutex.另外，再設(shè)置一個(gè)整型變量Readercount表示正在讀的進(jìn)程數(shù)目.由于只要有一個(gè)讀進(jìn)程在讀，便不允許寫(xiě)進(jìn)程去寫(xiě).因此，僅當(dāng)Readercount =0，表示尚無(wú)讀進(jìn)程在讀時(shí)，讀進(jìn)程才需要執(zhí)行Wait（Wmutex）操作.若Wait（Wmutex）操作成功，讀進(jìn)程便可去讀，相應(yīng)地做Readercount+1操作.同理，僅當(dāng)讀進(jìn)程在執(zhí)行了Readercount-1操作后其值為0時(shí)，才須執(zhí)行Signal（Wmutex）操作，以便讓寫(xiě)進(jìn)程操作.又因?yàn)镽eadercount是一個(gè)可被多個(gè)讀進(jìn)程訪問(wèn)的臨界資源，因此，也應(yīng)該為它設(shè)置一個(gè)互斥信號(hào)量Rmutex.

算法描述：

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

Readercount：integer：=0；

Reader（讀者進(jìn)程）

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（寫(xiě)者進(jìn)程）

begin

repeat

wait（Wmutex）；

……

perform write operation；

……

signal（Wmutex）；

until false；

end

結(jié)果分析：該方案已經(jīng)基本滿足題目要求，但讀者的高優(yōu)先級(jí)可能造成后續(xù)的寫(xiě)者由于被隨后而來(lái)的讀者插隊(duì)而長(zhǎng)時(shí)間等待，直到全部讀者進(jìn)程運(yùn)行完畢后，才可以使用文件.所以說(shuō)上述算法為讀者優(yōu)先方案.

2.2 寫(xiě)者優(yōu)先的解決方案

在原讀者-寫(xiě)者問(wèn)題上增加兩點(diǎn)要求（1）僅當(dāng)無(wú)寫(xiě)者時(shí)才允許讀者使用文件；（2）多個(gè)讀寫(xiě)進(jìn)程等待時(shí)首先考慮喚醒寫(xiě)者.

算法描述：

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

Readercount，writercount：integer：=0，0；

Reader（讀者進(jìn)程）

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（寫(xiě)者進(jìn)程）

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

結(jié)果分析：該方案在滿足讀寫(xiě)同步問(wèn)題要求的前提下也實(shí)現(xiàn)寫(xiě)者進(jìn)程優(yōu)先的要求.

3.結(jié)論

讀寫(xiě)同步問(wèn)題是進(jìn)程同步問(wèn)題中的經(jīng)典實(shí)例，若對(duì)它問(wèn)題能熟練掌握的話，那么對(duì)于常見(jiàn)一類(lèi)進(jìn)程多次訪問(wèn)，而不同類(lèi)的進(jìn)程必須互斥訪問(wèn)資源的控制這類(lèi)問(wèn)題也就不難解決了.

參考文獻(xiàn)

[1]帖軍，陸際光.同步互斥機(jī)制中的讀者-寫(xiě)者模型[J].武漢：中南民族大學(xué)學(xué)報(bào).2013-09

[2]湯子瀛，哲鳳屏.計(jì)算機(jī)操作系統(tǒng)[M].西安：西安電子科技大學(xué)出版社.2012-04

[3]趙素萍.淺談信號(hào)量的設(shè)置與使用[J].福建：福建電腦 2013-10

[4]程曉錦."讀者-寫(xiě)者"問(wèn)題的Java實(shí)現(xiàn)[J].北京：北京印刷學(xué)院學(xué)報(bào)，2010-03

[5]房永龍，周書(shū)民.基于線程的短信實(shí)時(shí)并發(fā)算法[J].上海：計(jì)算機(jī)應(yīng)用與軟件 2016-04

[6]夏春梅.用記錄型信號(hào)量解決讀者—寫(xiě)者問(wèn)題[J].安微：機(jī)械工業(yè)出版社，2012-06