進程同步通信經典問題—讀者寫者問題的算法分析與設計

曾思源，徐艷

（四川大學錦城學院計算機與軟件學院，四川成都，611731）

關鍵字：讀者和寫者；同步通信；PV操作算法

0 引言

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

無論是多少個讀進程存在，都不會對數據進行修改，因此讀進程是被允許同時訪問的。但是寫進程是不會被允許與其他讀/寫進程同時訪問數據集，因為這將違反Bernstein條件,破壞數據的完整性、正確性。

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

1.1 信號量控制

要實現讀寫進程之間的互斥，我們首先想到的就是添加信號量。

在操作系統中，信號量在解決多種多樣的進程同步問題起到了至關重要的作用，比如，信號量能夠保證兩個或者多個臨界區不被并發調用。同時，信號量本質上代表的，是某種資源的可利用數量。

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

在該問題當中，我們首先嘗試使用信號量rw來達到我們的需求。因為讀寫算法相同，所以以寫算法為例。信號量rw初始值賦為1。算法如下：

寫進程：

1.2 存在的問題

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

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

1.3 改進算法——讀者程序加入計數器實現讀者優先

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

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

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

1.4 讀者優先存在的問題

這種算法，基本實現了引言中的需求。但是弊端也很明顯，當讀者進程源源不斷的進入，寫者進程會一直處于等待資源的狀態，也就是說，寫進程會被“餓死”。因此這種算法不算是完美的，是一種優先服務讀進程的算法。

1.5 進一步改進算法——寫者程序加入計數器實現寫者優先

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

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

在這里，讀寫進程的count變量起到了類似的作用，下面以實例驗證之。

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

1.6 寫者優先存在的問題

顯然，這種算法是一種寫者優先的算法。只要存在寫進程，就會阻塞后來的讀進程。同時假如存在多個讀寫程序，系統也會優先喚醒寫進程。

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

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

下面是該算法的分析。

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

3 讀者寫者問題的實際應用

各類聯網售票系統會難以避免的遇到頻繁的數據查詢和更新請求。此時的查詢請求，比如多個消費者試圖查看剩余售票情況是允許的。但系統允許一條更新請求執行的過程中，此時則其他所有請求都不能被允許。否則就會出現一張票被賣出多次的情況。