讀者-寫者問題解答

1、2. 讀者寫者問題讀者 寫者問題 （ Readers-Writers problem ） 也是一個經(jīng)典的并發(fā)程序設(shè)計問題， 是經(jīng)常出現(xiàn)的一種同步問題。計算機系統(tǒng)中的數(shù)據(jù)（文件、記錄）常被多個進程共享， 但其中某些進程可能只要求讀數(shù)據(jù)（稱為讀者 Reader）；另一些進程則要求修改數(shù)據(jù)（稱為寫者 Writer ）。就共享數(shù)據(jù)而言， Reader 和 Writer 是兩組并發(fā)進程共享一組數(shù)據(jù)區(qū)， 要求：（ 1）允許多個讀者同時執(zhí)行讀操作；（ 2）不允許讀者、寫者同時操作；（ 3）不允許多個寫者同時操作。Reader 和 Writer 的同步問題分為讀者優(yōu)先、弱寫者優(yōu)先（公平競爭）和強寫者優(yōu)先 三種

2、情況，它們的處理方式不同。（ 1）讀者優(yōu)先 。對于讀者優(yōu)先，應(yīng)滿足下列條件：如果新讀者到： 無讀者、寫者，新讀者可以讀； 有寫者等待，但有其它讀者正在讀，則新讀者也可以讀； 有寫者寫，新讀者等待。如果新寫者到： 無讀者，新寫者可以寫； 有讀者，新寫者等待； 有其它寫者，新寫者等待。單純使用信號量不能解決讀者與寫者問題，必須引入計數(shù)器rc 對讀進程計數(shù)；rc_mutex 是用于對計數(shù)器 rc 操作的互斥信號量； write 表示是否允許寫的信號量；于是 讀者優(yōu)先的程序設(shè)計如下：int rc=0;semaphore rc_mutex=1;semaphore write=1;/用于記錄當前的讀者數(shù)量

3、/ 用于對共享變量 rc 操作的互斥信號量 /用于保證讀者和寫者互斥地訪問的信號量void reader() /* 讀者進程 */ do/ 開始對 rc 共享變量進行互斥訪問/ 來了一個讀進程，讀進程數(shù)加 1/如是第一個讀進程，判斷是否有寫進程在臨界區(qū)P(rc_mutex);rc + ;if (rc=1) P(write) ；V(rc_mutex);讀文件；P(rc_mutex); rc- ; if (rc = 0)V(write)/若有，讀進程等待，若無，阻塞寫進程/ 結(jié)束對 rc 共享變量的互斥訪問/ 開始對 rc 共享變量的互斥訪問/ 一個讀進程讀完，讀進程數(shù)減 1 /最后一個離開臨界區(qū)

4、的讀進程需要判斷是否有寫進程 進入臨界區(qū)，若有，喚醒一個寫進程進臨界區(qū)/需要V(rc_mutex);/ 結(jié)束對 rc 共享變量的互斥訪問 while(1)void writer() do/* 寫者進程 */都要等待 read 信號量。寫者優(yōu)先1 的程序設(shè)計如下：P(write);/ 無讀進程，進入寫進程；若有讀進程，寫進程等待寫文件 ;V(write);/ 寫進程完成；判斷是否有讀進程需要進入臨界區(qū)，/若有，喚醒一個讀進程進臨界區(qū) while(1) 讀者優(yōu)先的設(shè)計思想是讀進程只要看到有其它讀進程正在讀，就可以繼續(xù)進行讀；寫 進程必須等待所有讀進程都不讀時才能寫， 即使寫進程可能比一些讀進程更早

5、提出申請。 該 算法只要還有一個讀者在活動， 就允許后續(xù)的讀者進來， 該策略的結(jié)果是， 如果有一個穩(wěn)定 的讀者流存在， 那么這些讀者將在到達后被允許進入。 而寫者就始終被掛起， 直到?jīng)]有讀者 為止。(2)寫者優(yōu)先 1。為了解決以上問題，寫者優(yōu)先1 的設(shè)計思想是在一個寫者到達時如果有正在工作的讀者， 那么該寫者只要等待正在工作的讀者完成， 而不必等候其后面到來的 讀者就可以進行寫操作。注意，該算法當一個寫者在等待時，后到達的讀者是在寫者之后 被掛起，而不是立即允許進入。read，讀、寫進程在每次操作前在讀者優(yōu)先的算法的基礎(chǔ)上增加了一個排隊信號量int rc=0;semaphore rc_mute

6、x=1;semaphore wc_mutex=1;semaphore write=1;semaphore read=1;void reader() /* 讀者進程 */ doP(read);P(rc_mutex);rc+;if rc=1 then P(write);V(rc_mutex);V(read);Reading the file;P(rc_mutex);rc-;if rc=0 then V(write);/V(rc_mutex);/用于記錄當前的讀者數(shù)量/ 用于對共享變量 rc 操作的互斥信號量/用于保證讀者和寫者互斥地訪問的信號量/用于保證讀者和寫者互斥地訪問的信號量 /用于保證在寫

7、進程封鎖其后續(xù)的讀進程的信號量若有寫進程，后續(xù)讀進程等待，在read隊列上排隊/開始對 rc 共享變量進行互斥訪問 /來了一個讀進程，讀進程數(shù)加 1 /第一個讀進程需要判斷是否有寫進程在臨界區(qū)，若有， /讀進程需要等待，若沒有，阻塞寫進程/結(jié)束對 rc 共享變量的互斥訪問/從 read 隊列中喚醒一個進程/開始對 rc 共享變量的互斥訪問/一個讀進程讀完，讀進程數(shù)減 1/最后一個離開臨界區(qū)的讀進程需要判斷是否有寫進程 /需要進入臨界區(qū)，若有，喚醒一個寫進程進臨界區(qū) /結(jié)束對 rc 共享變量的互斥訪問void writer()/* 寫者進程 */doP(read);/無讀進程，寫進程進入；有讀進

8、程，在 read 排隊，其后/到來的讀進程排在該隊列寫者之后P(write);/若有讀進程在讀，等待現(xiàn)有讀進程讀完才可寫Writeing the file;V(write);/寫進程完成； 判斷是否有讀進程需要進入臨界區(qū)，若有，/喚醒一個讀進程進臨界區(qū)V(read);/從 read 隊列中喚醒一個進程注意，該算法當?shù)谝粋€寫者已經(jīng)P(read)后，read變?yōu)?,來了 N個讀者，他們都停留在它的P(read)這一句。那么會出現(xiàn)什么問題呢？此時，如果原來的寫者完成了，緊接又來 了一個寫者，寫者需要P(read)。這個時候，由于N個讀者都已經(jīng)在這個寫者之前P(read)了，所以這個寫者需要排隊排在這

9、N個讀者分別都得到 P(read)后才能得到執(zhí)行，這個就不是寫者優(yōu)先了,而是讀者寫者公平競爭。(3)寫者優(yōu)先 2。為了保證寫者相對于讀者的優(yōu)先 , 需要提高寫者進程的優(yōu)先級。這里 除增加一個排隊信號量 read，讓讀者和寫者在讀寫之前都在此信號量上排隊。還需增加一個信號量 write_first ,來保證寫者優(yōu)先。寫者優(yōu)先 2 的程序設(shè)計如下：int rc, wc = 0; / 用于讀者，寫者的計數(shù)semaphore read, write = 1;/用于讀進程和寫進程的互斥信號量semaphore rc_mutex, wc_mutex, write_first = 1;/ 用于讀時、寫時和寫

10、者優(yōu)先的互斥 void reader() /* 讀者進程 */while(1)P(write_first);/用來保證寫者優(yōu)先。若有寫進程，第二個后的讀者等待在這P(read);/若有寫進程，第一個讀進程等待；若無寫進程，讀進程進入P(rc_mutex);/開始對 rc 共享變量進行互斥訪問rc+;/更新讀進程數(shù)if (rc=1) P(write);/第一個讀進程需要判斷是否有寫進程在臨界區(qū)，若有，讀進程/等待，若無，阻塞寫進程V(rc_mutex);V(read);/結(jié)束對 rc 共享變量的互斥訪問 /從 read 隊列中喚醒一個進程V(write_first);doReading();P(

11、rc_mutex);rc-;if (rc=0) V(write);V(rc_mutex); /開始對 rc 共享變量進行互斥訪問 /更新讀進程數(shù)量 /最后一個離開臨界區(qū)的讀進程需要判斷是否有寫進程 /需要進入臨界區(qū)，若有，喚醒一個寫進程進臨界區(qū) /結(jié)束對 rc 共享變量的互斥訪問void writer()/* 寫者進程 */while(1)P(wc_mutex);wct+;if (wc=1) P(read);V(wc_mutex);P(write);do writing();V(write);P(wc_mutex);wc-;if (wc=0) V(read);/開始對 wc 共享變量進行互斥訪

12、問/更新寫進程數(shù)/第一個寫進程需要判斷是否有讀進程在臨界區(qū)，若有，寫進程 /阻塞，若無，阻塞新的讀進程/結(jié)束對 wc 共享變量的互斥訪問/限制同一時刻只能有一個寫進程進行寫操作/結(jié)束對寫操作的限制/ 開始對 wc 的互斥訪問/更新寫進程數(shù)量/最后一個離開臨界區(qū)的寫進程需要 判斷是否有 讀進程需要 /進入，若有，喚醒一個讀進程進入臨界區(qū)/結(jié)束對 wc 的互斥訪問V(wc_mutex); 這里 write_first 的設(shè)立是為了保證寫者優(yōu)先。因為 write_first 的初值是 1，在讀進 程，執(zhí)行完 P(write_first) 后等在 P(read) 這一句的讀者最多只有 1 個。對于 read 信號量，每個讀進程最開始都要申請一次，之后在真正做讀操作前即讓出， 這使得寫進程可以隨時申請到read。而寫進程，只有第一個寫進程需要申請read，之后就一直