記錄型信號量解決讀者寫者問題的探究

摘要：在多道程序環境下，進程同步問題十分重要，操作系統引入進程后，進程的異步性在多個進程爭用臨界資源時會給系統造成混亂，進程同步的主要任務就是使并發執行的各個進程之間能有效地共享各種資源，相互合作，是程序的執行具有可再現性。其中讀者寫者問題尤其具有代表性，而記錄型信號量是一個很好的解決方法。

關鍵詞：信號量 記錄式信號量 同步

一、信號量的描述

信號量（Semaphore），有時被稱為信號燈，是在多線程環境下使用的一種設施，是可以用來保證兩個或多個關鍵代碼段不被并發調用。在進入一個關鍵代碼段之前，線程必須獲取一個信號量；一旦該關鍵代碼段完成了，那么該線程必須釋放信號量。

信號量的取值只能是整數，即把信號量的取值定義為整型量稱為整型信號量。最初由荷蘭學者Dijkstra定義的，除初始化外，僅能通過兩個標準的原子操作（Atomic Operation）wait（S）和signal（S）來訪問。這兩個操作分別稱為P、V操作。wait和signal操作可描述為：

wait（S）：while S≤0 do no-op

S∶=S-1；

signal（S）：S∶=S+1；

S≥0說明當前有資源可供分配，S≤0無資源。，該兩個操作是原子操作，不可中斷的執行，當修改某個信號量是，其他進程不可同時對該信號量修改。

在該機制中的wait操作，只要是信號量S≤0，就會不斷地測試。因此，該機制并未遵循“讓權等待”的準則，使進程處于“忙等”的狀態。

二、記錄型信號量的描述

為了解決“忙等”現象的問題，提出了記錄型信號量機制，采用“讓權等待”，但在采取了“讓權等待”的策略后，又會出現多個進程等待訪問同一臨界資源的情況。為此，在信號量機制中，除了需要一個用于代表資源數目的整型變量value外，還應增加一個進程鏈表L，用于鏈接上述的所有等待進程。記錄型信號量是由于它采用了記錄型的數據結構而得名的。它所包含的上述兩個數據項可描述為：

type semaphore=record/*定義類型為記錄型*/

value：integer；

L：list of process；/*進程隊列*/

end

相應地，wait（S）和signal（S）操作可描述為：

procedure wait（S）

var S：semaphore；

begin

S.value∶=S.value-1；

if S.value<0 then block（S，L）/*資源數目減一操作后若資源量小于0表示該進程申請不到資源，調用阻塞原語，將該進程掛接到阻塞隊列的末尾*/

end

procedure signal（S）

var S：semaphore；

begin

S.value∶=S.value+1；

if S.value≤0then wakeup（S，L）；/*系統釋放一個資源，資源數目仍然資源量小于等于0，表示存在進程在阻塞隊列上，調用激活原語，將該隊列的第一個進程激活，從而獲得資源繼續執行*/

end

三、讀者寫著問題的提出

以上對記錄型信號量的發展，原理做了簡單的說明，在一個數據文件或者記錄經常被多個進程共享 ，我們分為兩個狀態，一個是讀該文件的進程稱為讀（Reader）進程，另外一種稱為寫（Writer）進程.允許多個進程同時讀一個共享對象，不允許一個寫進程和其他的任何同時訪問共享對象。

為實現Reader與Writer進程間在讀或寫時的互斥而設置了一個互斥信號量Wmutex。另外，再設置一個整型變量Readcount表示正在讀的進程數目。由于只要有一個Reader進程在讀，便不允許Writer進程去寫。因此，僅當Readcount=0，表示尚無Reader進程在讀時，Reader進程才需要執行Wait（Wmutex）操作

四、讀者寫著問題的描述

讀者-寫者問題可描述如下：

Var rmutex， wmutex：semaphore∶=1，1；

Readcount：integer∶=0；

begin

parbegin

Reader：begin/*讀者進程*/

repeat

wait（rmutex）；

if readcount=0 then wait（wmutex）；/*第一個讀者要申請互斥信號量wmutex */

Readcount∶=Readcount+1；

signal（rmutex）；

…

perform read operation；

…

wait（rmutex）；

readcount∶=readcount-1；

if readcount=0 then signal（wmutex）；/*最后一個讀者要釋放互斥信號量wmutex */

signal（rmutex）；

until 1；

end

writer：begin/*寫進程*/

repeat

wait（wmutex）；

perform write operation；

signal（wmutex）；

until 1；

end

parend

end

五、總結

讀者寫者問題是一個有代表性的進程同步問題，作為初學者要做到透徹理解并不容易，但是如果我們將該問題進行細分，由簡單到復雜，理解難度將大大降低。并能在其他的同步問題上有一定得舉一反三的作用。

參考文獻

[1]Crow ley C P.Operating systems：a design-oriented approach[M].Beijing：World Publishing Co，1999：100-126.

[2]湯小丹，梁紅兵，哲鳳屏，等.計算機操作系統[M].3版.西安：西安電子科技大學出版社，2007：58-61.

[3]帖軍，陸際光.同步互斥機制中的讀者-寫者模型[J].中南民族大學學報：自然科學版，2005，24.

[4]《現代操作系統Modern Operating Systems》Andrew S.Tanenbaum著，陳向群等譯 機械工業出版社1999.

作者簡介

林德麗，出生于1983年09月，女，講師，研究方向：計算機應用技術。

（作者單位：青島科技大學）