天天看點

經典程序的同步問題之——讀者寫者

問題描述:

一個資料檔案或記錄,可被多個程序共享,我們把隻要求讀該檔案的程序稱為“Reader 程序”,其他程序則稱為“Writer 程序” 。允許多個程序同時讀一個共享對象,因為讀操作不會使資料檔案混亂。但不允許一個 Writer 程序和其他 Reader 程序或 Writer 程序同時通路共享對象,因為這種通路将會引起混亂。所謂“讀者—寫者問題(Reader-Writer Problem)”是 指保證一個 Writer 程序必須與其他程序互斥地通路共享對象的同步問題。讀者—寫者問題 常被用來測試新同步原語。

1. 利用記錄型信号量解決讀者—寫者問題

為實作 Reader 與 Writer 程序間在讀或寫時的互斥而設定了一個互斥信号量 Wmutex。 另外,再設定一個整型變量 Readcount 表示正在讀的程序數目。由于隻要有一個 Reader 程序在讀,便不允許 Writer 程序去寫。是以,僅當 Readcount=0,表示尚無 Reader 程序在讀時,Reader 程序才需要執行 Wait(Wmutex)操作。若 Wait(Wmutex)操作成功,Reader 程序便可去讀,相應地,做 Readcount+1 操作。同理,僅當 Reader 程序在執行了 Readcount 減 1 操作後其值為 0 時,才須執行 signal(Wmutex)操作,以便讓 Writer 程序寫。又因為 Readcount 是一個可被多個 Reader 程序通路的臨界資源,是以,也應該為它設定一個互斥信号量 rmutex。

解釋:

互斥信号量wmutex: 實作Reader與Writer程序間在讀或寫時的互斥,整型變量Readcount: 表示正在讀的程序數目;由于隻要有一個Reader程序在讀,便不允許Writer程序寫。是以,僅當Readcount=0,即無Reader程序在讀時,Reader才需要執行Wait(wmutex)操作。若Wait(wmutex)操作成功,Reader程序便可去讀,相應地,做Readcount+1操作。同理,僅當Reader程序在執行了Readcount減1操作後其值為0時,才需執行signal(wmutex)操作,以便讓Write程序寫

互斥信号量rmutex: Reader程序間互斥通路Readcount

讀者—寫者問題可描述如下:

1  Var rmutex,wmutex:  semaphore:=1,1;
 2     Readcount:  integer:=0;
 3        begin
 4        parbegin
 5        Reader:  begin
 6             repeat
 7             wait(rmutex);
 8             if readcount=0 then wait(wmutex);
 9                 Readcount:=Readcount+1;
10             signal(rmutex);
11             ...
12             perform read operation;
13             ...
14             wait(rmutex);
15             readcount:=readcount-1;
16             if readcount=0 then signal(wmutex);
17             signal(rmutex);
18         until false;
19         end
20         writer:  begin
21             repeat
22                 wait(wmutex);
23                 perform write operation;
24                 signal(wmutex);
25             until false;
26             end
27     parend
28 end      

2.利用信号量集機制解決讀者—寫者問題

  這裡的讀者—寫者問題與前面的略有不同,它增加了一個限制,即 最 多 隻 允許 RN 個讀 者同時讀。為此,又引入了一個信号量 L,并賦予其初值為 RN,通過執行 wait(L,1,1) 操作,來控制讀者的數目。每當有一個讀者進入時,就要先執行 wait(L,1,1)操作,使 L 的值減 1。當有 RN 個讀者進入讀後,L 便減為 0,第 RN+1 個讀者要進入讀時,必然會因 wait(L,1,1)操作失敗而阻塞。

描述如下: 

1 Var RN integer;
 2     L, mx: semaphore:=RN,1;
 3   begin
 4     parbegin
 5       reader: begin
 6         repeat
 7             Swait(L,1,1);
 8             Swait(mx,1,0);
 9             ...
10             perform read operation;            
11             ...
12             Ssignal(L,1);
13         until false;
14         end
15       writer: begin
16         repeat
17         Swait(mx,1,1;L,RN,0);
18         perform write operation;
19         Ssignal(mx,1);
20         until false;
21         end
22     parend
23   end