進(jìn)程同步通信經(jīng)典問題—讀者寫者問題的算法分析與設(shè)計(jì)

曾思源，徐艷

（四川大學(xué)錦城學(xué)院計(jì)算機(jī)與軟件學(xué)院，四川成都，611731）

關(guān)鍵字：讀者和寫者；同步通信；PV操作算法

0 引言

一個(gè)共享的數(shù)據(jù)集合，會面臨同時(shí)被多個(gè)進(jìn)程訪問的情況。一個(gè)存儲器，一個(gè)數(shù)據(jù)庫，亦或是內(nèi)存中的一個(gè)寄存器，都可以成為這個(gè)數(shù)據(jù)集合。其中一類進(jìn)程只有讀取數(shù)據(jù)的需求，且不會對數(shù)據(jù)進(jìn)行修改，我們稱此類進(jìn)程為讀進(jìn)程。而另外一類進(jìn)程會對數(shù)據(jù)集中的數(shù)據(jù)進(jìn)行修改，我們稱之為寫進(jìn)程。

無論是多少個(gè)讀進(jìn)程存在，都不會對數(shù)據(jù)進(jìn)行修改，因此讀進(jìn)程是被允許同時(shí)訪問的。但是寫進(jìn)程是不會被允許與其他讀/寫進(jìn)程同時(shí)訪問數(shù)據(jù)集，因?yàn)檫@將違反Bernstein條件,破壞數(shù)據(jù)的完整性、正確性。

1 讀者寫者問題的算法分析

1.1 信號量控制

要實(shí)現(xiàn)讀寫進(jìn)程之間的互斥，我們首先想到的就是添加信號量。

在操作系統(tǒng)中，信號量在解決多種多樣的進(jìn)程同步問題起到了至關(guān)重要的作用，比如，信號量能夠保證兩個(gè)或者多個(gè)臨界區(qū)不被并發(fā)調(diào)用。同時(shí)，信號量本質(zhì)上代表的，是某種資源的可利用數(shù)量。

信號量只能通過初始化和兩個(gè)標(biāo)準(zhǔn)的原語來訪問--作為OS核心代碼執(zhí)行，不受進(jìn)程調(diào)度的打斷[1]。P操作減少一個(gè)信號量的值，如果它的值大于零，進(jìn)程繼續(xù)執(zhí)行，否則就睡眠，等待喚醒；而V操作增加它的值，若有進(jìn)程在此信號量上睡眠，則喚醒之[2]。

在該問題當(dāng)中，我們首先嘗試使用信號量rw來達(dá)到我們的需求。因?yàn)樽x寫算法相同，所以以寫算法為例。信號量rw初始值賦為1。算法如下：

寫進(jìn)程：

1.2 存在的問題

假如此時(shí)有個(gè)讀進(jìn)程A進(jìn)入程序，首先會通過P(rw)拿走資源，然后進(jìn)入臨界區(qū)進(jìn)行讀文件操作。在此同時(shí)，寫進(jìn)程B也試圖進(jìn)入程序，由于讀進(jìn)程A還沒有進(jìn)行V(rw)，所以寫進(jìn)程B會被阻塞，只有當(dāng)讀進(jìn)程A通過V(rw)釋放掉資源，寫進(jìn)程B才能進(jìn)入臨界區(qū)。

此算法的確解決了讀寫進(jìn)程之間的互斥問題，但在此同時(shí)，多個(gè)讀進(jìn)程之間也變成互斥訪問了，并不滿足引言中所提出的需求，因此這種算法不能達(dá)到要求。

1.3 改進(jìn)算法——讀者程序加入計(jì)數(shù)器實(shí)現(xiàn)讀者優(yōu)先

我們通過1.1發(fā)現(xiàn)，只加入一組信號量不能解決問題。因此，在這里引入一個(gè)變量count，用來記錄當(dāng)前正在訪問數(shù)據(jù)集的進(jìn)程的數(shù)量，進(jìn)而能更方便的解決后面的問題。所有信號量初值均賦為1，count初值賦為0，寫進(jìn)程算法與1.1相同，因此不再贅述。實(shí)現(xiàn)如下：

可以很明顯的看出，該算法與1.1最大的區(qū)別是在P(rw)和V(rw)操作的兩側(cè)，加入了帶if檢測的count計(jì)數(shù)器。Count代表的是訪問該進(jìn)程的讀進(jìn)程數(shù)量，進(jìn)入程序/退出程序時(shí)會進(jìn)行自動的加減。If語句中的條件，目的是判斷當(dāng)前還有多少個(gè)讀進(jìn)程在訪問臨界資源，如果是第一個(gè)進(jìn)程，便會通過P(rw)操作將寫進(jìn)程給阻塞掉。同時(shí)，因?yàn)橛衖f的存在，不滿足條件的后來的讀進(jìn)程不會因?yàn)榍耙粋€(gè)讀進(jìn)程而阻塞在P(rw)，從而實(shí)現(xiàn)了讀進(jìn)程之間的同步訪問。

需要特別注意的是，在控制count加減和加/解鎖操作的兩側(cè)，都加入了新信號量mutex，保證count的增減和加/解鎖操作的連貫性。試想，假如沒有該信號量，此時(shí)進(jìn)來讀進(jìn)程A，剛進(jìn)行了P(rw)的操作，還沒來得及進(jìn)行count++的操作，又進(jìn)來另一個(gè)讀進(jìn)程B，此時(shí)的count還是為零，滿足if判斷的結(jié)果，試圖用P操作上鎖，但由于前一個(gè)進(jìn)程A沒有執(zhí)行V操作釋放信號量，所以進(jìn)程B就被阻塞了，這是不能被允許的。

1.4 讀者優(yōu)先存在的問題

這種算法，基本實(shí)現(xiàn)了引言中的需求。但是弊端也很明顯，當(dāng)讀者進(jìn)程源源不斷的進(jìn)入，寫者進(jìn)程會一直處于等待資源的狀態(tài)，也就是說，寫進(jìn)程會被“餓死”。因此這種算法不算是完美的，是一種優(yōu)先服務(wù)讀進(jìn)程的算法。

1.5 進(jìn)一步改進(jìn)算法——寫者程序加入計(jì)數(shù)器實(shí)現(xiàn)寫者優(yōu)先

在1.3中，單獨(dú)在讀進(jìn)程中加入帶檢測的count變量，雖然解決了一部分問題，但也帶來了新的問題。所以我們現(xiàn)在試著將count計(jì)數(shù)器變量加在寫者進(jìn)程。需要特別注意的是，要同時(shí)滿足引言中讀-讀同步訪問的要求的話，我們就不能像在1.3中，將count單獨(dú)加入到寫進(jìn)程中。因此，我們要在1.3的基礎(chǔ)上，在寫進(jìn)程這邊添加帶if檢測的count變量。

count在寫進(jìn)程中也是起到統(tǒng)計(jì)其進(jìn)程數(shù)量的作用，當(dāng)寫進(jìn)程的數(shù)量滿足條件的時(shí)候，我們能讓其主動的做一定的操作，而不是被動的將資源讓給一直涌入的讀進(jìn)程。以下變量初值與1.3相似，讀進(jìn)程算法與1.3相同，在此不再贅述。實(shí)現(xiàn)如下：

在這里，讀寫進(jìn)程的count變量起到了類似的作用，下面以實(shí)例驗(yàn)證之。

假如此時(shí)有三個(gè)程序：讀進(jìn)程A，寫進(jìn)程B，讀進(jìn)程C依次進(jìn)入隊(duì)列。我們假設(shè)讀進(jìn)程A此時(shí)已經(jīng)進(jìn)入臨界區(qū)，正在讀取數(shù)據(jù)，那該進(jìn)程一定經(jīng)過了P(mutex2)，P(mutex1)，P(mutex)，P(rw)，V(mutex)，V(mutex1)，V(mutex2) 這些操作。此時(shí)如果寫進(jìn)程B也想訪問臨界區(qū)資源，由于此時(shí)寫進(jìn)程B是第一個(gè)到達(dá)的該類進(jìn)程，能通過if的檢測，將會占用信號量mutex1。但是由于讀進(jìn)程還在臨界區(qū)，并沒有釋放信號量rw，所以寫進(jìn)程會被阻塞。在此同時(shí)，新加入的讀進(jìn)程C，一定會經(jīng)過P(mutex2),但是由于寫進(jìn)程沒有釋放mutex1，所以讀進(jìn)程C也會被阻塞。只有當(dāng)讀進(jìn)程A釋放掉信號量P(rw)的時(shí)候，才會將寫進(jìn)程B喚醒，進(jìn)行寫操作。寫進(jìn)程B完成操作后，會再次檢測后面是否還有寫進(jìn)程，如果沒有，才會釋放掉信號量mutex1。后面的讀進(jìn)程才有機(jī)會進(jìn)行臨界區(qū)。

1.6 寫者優(yōu)先存在的問題

顯然，這種算法是一種寫者優(yōu)先的算法。只要存在寫進(jìn)程，就會阻塞后來的讀進(jìn)程。同時(shí)假如存在多個(gè)讀寫程序，系統(tǒng)也會優(yōu)先喚醒寫進(jìn)程。

2 另一種公平的讀者寫者算法

上面的所有算法，在實(shí)現(xiàn)需求的同時(shí)，都有所偏袒，面對極端情況下會出現(xiàn)問題。所以我們決定按照進(jìn)程到達(dá)的先后順序，進(jìn)行算法的實(shí)現(xiàn)，以下算法變量初值與前篇類似。此算法部分內(nèi)容與1.3有重復(fù)之處，同時(shí)由于篇幅有限，因此在此簡單描述增加的信號量：在1.3的寫進(jìn)程基礎(chǔ)上，首尾增加信號量w；在1.3讀進(jìn)程的第一個(gè)信號量mutex前后增加信號量w。

下面是該算法的分析。

在1.3中，我們發(fā)現(xiàn)只要有讀進(jìn)程存在，信號量rw的使用權(quán)就會一直在讀進(jìn)程手中，這種情況在加入信號量w后發(fā)生了改變：我們發(fā)現(xiàn)，即使是后進(jìn)來的寫進(jìn)程，也能通過搶占信號量w來保證自己不被“餓死”，且進(jìn)程之間的執(zhí)行順序完全是按照搶占w的順序，即進(jìn)入隊(duì)列的先后順序。同時(shí)此算法也滿足引言中的其他需求，類似于是一種“先來先服務(wù)”的算法，不會造成讀/寫進(jìn)程的“饑餓”，也能提高系統(tǒng)的效率。

3 讀者寫者問題的實(shí)際應(yīng)用

各類聯(lián)網(wǎng)售票系統(tǒng)會難以避免的遇到頻繁的數(shù)據(jù)查詢和更新請求。此時(shí)的查詢請求，比如多個(gè)消費(fèi)者試圖查看剩余售票情況是允許的。但系統(tǒng)允許一條更新請求執(zhí)行的過程中，此時(shí)則其他所有請求都不能被允許。否則就會出現(xiàn)一張票被賣出多次的情況。