操作系統(tǒng)讀者寫者問題.doc

操作系統(tǒng)課程設(shè)計報告 目錄目錄第1章 實(shí)驗(yàn)?zāi)康暮蛯?shí)驗(yàn)要求11.1 實(shí)驗(yàn)?zāi)康?1.2 實(shí)驗(yàn)要求11.3 課程設(shè)計題目1第2章 實(shí)驗(yàn)內(nèi)容22.1題目分析22.1.1 問題的描述22.1.2 問題的解決方法22.2 算法分析32.2.1 讀者優(yōu)先算法分析32.2.2 寫者優(yōu)先算法分析82.2.3 無優(yōu)先算法分析112.3 函數(shù)設(shè)計13第3章 程序?qū)崿F(xiàn)153.1 程序功能及界面設(shè)計153.2 實(shí)現(xiàn)程序流程153.2.1 讀者優(yōu)先算法實(shí)現(xiàn)153.2.2 寫者優(yōu)先算法實(shí)現(xiàn)163.2.3 無優(yōu)先算法實(shí)現(xiàn)173.3 程序流程圖183.3.1 讀者優(yōu)先算法流程圖183.3.2 寫者優(yōu)先算法流程圖183.3.3 無優(yōu)先算法流程圖19心得體會21參考文獻(xiàn)22附錄1 源代碼23第1章 實(shí)驗(yàn)?zāi)康暮蛯?shí)驗(yàn)要求第1章 實(shí)驗(yàn)?zāi)康暮蛯?shí)驗(yàn)要求1.1 實(shí)驗(yàn)?zāi)康睦斫馀R界區(qū)和進(jìn)程互斥的概念，掌握用信號量和PV操作實(shí)現(xiàn)進(jìn)程互斥的方法。1.2 實(shí)驗(yàn)要求在windows或者linux環(huán)境下編寫一個控制臺應(yīng)用程序，該程序運(yùn)行時能創(chuàng)建N個線程，其中既有讀者線程又有寫者線程，它們按照事先設(shè)計好的測試數(shù)據(jù)進(jìn)行讀寫操作。請用信號量和PV操作實(shí)現(xiàn)讀者/寫者問題。1.3 課程設(shè)計題目本課程設(shè)計共包括3個題目，內(nèi)容覆蓋了操作系統(tǒng)原理的關(guān)鍵知識點(diǎn)，包括進(jìn)程調(diào)度、內(nèi)存管理、進(jìn)程同步、死鎖、進(jìn)程通訊、文件系統(tǒng)及嵌入式操作系統(tǒng)。題目1：進(jìn)程調(diào)度算法。模擬在單處理器情況下的進(jìn)程調(diào)度，目的是加深對進(jìn)程調(diào)度工作的理解，掌握不同調(diào)度算法的優(yōu)缺點(diǎn)題目2：動態(tài)異長分區(qū)的存儲分配與回收算法。編寫一個程序，模擬操作系統(tǒng)對動態(tài)異長分區(qū)的存儲分配與回收算法。題目3：讀者/寫者問題與進(jìn)程同步。理解臨界區(qū)和進(jìn)程互斥的概念，掌握用信號量和PV操作實(shí)現(xiàn)進(jìn)程互斥的方法。要求學(xué)生用信號量和PV操作實(shí)現(xiàn)讀者/寫者問題的讀者優(yōu)先算法、寫者優(yōu)先算法和無優(yōu)先算法。我們小組選擇題目3，即讀者/寫者問題與進(jìn)程同步。以下是該題目的實(shí)驗(yàn)報告。28第2章 實(shí)驗(yàn)內(nèi)容第2章 實(shí)驗(yàn)內(nèi)容2.1題目分析2.1.1 問題的描述有一個被許多進(jìn)程共享的數(shù)據(jù)區(qū)，這個數(shù)據(jù)區(qū)可以是一個文件，或者主存的一塊空間，甚至可以是一組處理器寄存器。有一些只讀取這個數(shù)據(jù)區(qū)的進(jìn)程（reader）和一些只往數(shù)據(jù)區(qū)中寫數(shù)據(jù)的進(jìn)程（writer）。以下假設(shè)共享數(shù)據(jù)區(qū)是文件。這些讀者和寫者對數(shù)據(jù)區(qū)的操作必須滿足以下條件：讀讀允許；讀寫互斥；寫寫互斥。這些條件具體來說就是：（1）任意多的讀進(jìn)程可以同時讀這個文件；（2）一次只允許一個寫進(jìn)程往文件中寫；（3）如果一個寫進(jìn)程正在往文件中寫，禁止任何讀進(jìn)程或?qū)戇M(jìn)程訪問文件；（4）寫進(jìn)程執(zhí)行寫操作前，應(yīng)讓已有的寫者或讀者全部退出。這說明當(dāng)有讀者在讀文件時不允許寫者寫文件。2.1.2 問題的解決方法（1）讀者優(yōu)先除了上述四個規(guī)則外，還增加讀者優(yōu)先的規(guī)定，當(dāng)有讀者在讀文件時，對隨后到達(dá)的讀者和寫者，要首先滿足讀者，阻塞寫者。這說明只要有一個讀者活躍，那么隨后而來的讀者都將被允許訪問文件，從而導(dǎo)致寫者長時間等待，甚至有可能出現(xiàn)寫者被餓死的情況。（2）寫者優(yōu)先除了上述四個規(guī)則外，還增加寫者優(yōu)先的規(guī)定，即當(dāng)有讀者和寫者同時等待時，首先滿足寫者。當(dāng)一個寫者聲明想寫文件時，不允許新的讀者再訪問文件。（3）無優(yōu)先除了上述四個規(guī)則外，不再規(guī)定讀寫的優(yōu)先權(quán)，誰先等待誰就先使用文件。2.2 算法分析2.2.1 讀者優(yōu)先算法分析對于相繼到達(dá)的一批讀者，并不是每個讀者都需要執(zhí)行P(r_w_w)和V(r_w_w)。在這批讀者中，只有最先到達(dá)的讀者才需要執(zhí)行P(r_w_w)，與寫者競爭對文件的訪問權(quán)，若執(zhí)行P(r_w_w)成功則獲得了文件的訪問權(quán)，其他的讀者可直接訪問文件；同理，只有最后退出臨界區(qū)的讀者需要執(zhí)行V(r_w_w)來歸還文件訪問權(quán)。為了記錄正在讀文件的一批讀者的數(shù)量，需要設(shè)置一個整型變量read_count，每一個讀者到達(dá)時都要將read_count加1，退出時都要將read_count減1。由于只要有一個讀者在讀文件，便不允許寫者寫文件，所以，僅當(dāng)read_count=0時，即尚無讀者在讀文件時，讀者才需要執(zhí)行P(r_w_w)操作。若P(r_w_w)操作成功，讀者便可去讀文件，相應(yīng)地，read_count+1。同理，僅當(dāng)在執(zhí)行了read_count減1操作后其值為0時，才需要執(zhí)行V(r_w_w)操作，以便讓寫者寫文件。又因?yàn)閞ead_count是一個可被多個讀者訪問的臨界資源，所以應(yīng)該為它設(shè)置一個互斥信號量h_mutex_read_count。每個讀者在訪問read_count之前執(zhí)行P(h_mutex_read_count)，之后執(zhí)行V(h_mutex_read_count)。通過上述分析得到圖2-1所示的算法描述，其中的數(shù)字表示語句對應(yīng)的行號。01 semaphore r_w_w=1;02 semaphore h_mutex_read_count=1;03 int read_count=0; 04 reader()05 P(h_mutex_read_count);06 if(read_count=0) P(r_w_w);07 read_count+;08 V(h_mutex_read_count);09 讀文件;10 P(h_mutex_read_count);11 read_count-;12 if(read_count=0) V(r_w_w);13 V(h_mutex_read_count);14 1516 writer()17 P(r_w_w);18 寫文件;19 V(r_w_w);20 圖2-1 讀者優(yōu)先算法下面對該算法的調(diào)度效果進(jìn)行分析。假設(shè)最初沒有進(jìn)程在訪問文件。過了一會，就會有很多讀者和寫者到達(dá)。對它們可能有兩種調(diào)度情形。l 情形1 最先調(diào)度寫者寫者執(zhí)行P(r_w_w)操作成功，將r_w_w的值變?yōu)?，獲得文件的訪問權(quán)；其它的寫者執(zhí)行P(r_w_w)將r_w_w的值變?yōu)樨?fù)數(shù)，從而阻塞在信號量r_w_w上；第一個讀者執(zhí)行P(h_mutex_read_count)成功，將信號量h_mutex_read_count的值變?yōu)?，然后判斷read_count是0，所以執(zhí)行P(r_w_w)，將r_w_w的值減1后仍然為負(fù)數(shù)從而阻塞在信號量r_w_w上，其它的讀者執(zhí)行P(h_mutex_read_count)將信號量h_mutex_read_count的值變?yōu)樨?fù)數(shù)，從而阻塞在信號量h_mutex_read_count上。例如，對于請求序列w1,w2,r1,w3,r2,r3，我們用圖表形象地刻畫進(jìn)程的活動，圖表中包括讀者計數(shù)器的值、信號量h_mutex_read_count和r_w_w的值和隊列以及訪問文件的進(jìn)程。初始狀態(tài)。沒有進(jìn)程使用文件，計數(shù)器read_count的值是0，信號量h_mutex_read_count和r_w_w的值都是1，隊列都是空，參見圖2-2；w1請求寫文件，所以執(zhí)行語句17，將信號量r_w_w的值減1后變成0，w1獲得文件使用權(quán)，執(zhí)行語句18，開始寫文件，參見圖2-3；在w1尚未寫完時，w2提出寫請求，所以執(zhí)行語句17，將信號量r_w_w的值減1后變成負(fù)1，w2被阻塞在信號量r_w_w上，參見圖2-4；同時r1提出讀請求，所以執(zhí)行語句5，將信號量h_mutex_read_count的值減1后變成0，接著執(zhí)行語句6，判斷read_count的值是0，所以執(zhí)行P(r_w_w)，將信號量r_w_w的值減1后變成-2，r1被阻塞在信號量r_w_w上，參見圖2-5；初始狀態(tài)read_count=0h_mutex_read_count1NULLr_w_w1NULL訪問文件者：無圖2-2w1請求read_count=0h_mutex_read_count1NULLr_w_w0NULL訪問文件者：w1圖2-3同時w3提出寫請求，所以執(zhí)行語句17，將信號量r_w_w的值減1后變成-3，w3被阻塞在信號量r_w_w上，參見圖2-6；同時r2提出讀請求，所以執(zhí)行語句5，將信號量h_mutex_read_count的值減1后變成-1，r2被阻塞在信號量h_mutex_read_count上，參見圖2-7；w2請求read_count=0h_mutex_read_count1NULLr_w_w-1 w2訪問文件者：w1圖2-4r1請求read_count=0h_mutex_read_count0NULLr_w_w-2 w2,r1訪問文件者：w1圖2-5同時r3提出讀請求，所以執(zhí)行語句5，將信號量h_mutex_read_count的值減1后變成-2，r3被阻塞在信號量h_mutex_read_count上，參見圖2-8；w1寫完文件，執(zhí)行語句19，將信號量r_w_w的值加1后變成-2，并喚醒w2，w2接著執(zhí)行語句18，開始寫文件，參見圖2-9；w2寫完文件，執(zhí)行語句19，將信號量r_w_w的值加1后變成-1，并喚醒r1，r1接著執(zhí)行語句7，將read_count的值加1后變成1，執(zhí)行語句8，將信號量h_mutex_read_count的值加1后變成-1，并喚醒r2，r1執(zhí)行語句9，開始讀r2請求read_count=0h_mutex_read_count-1 r2r_w_w-3 w2,r1,w3訪問文件者：w1圖2-7w3請求read_count=0h_mutex_read_count0NULLr_w_w-3 w2,r1,w3訪問文件者：w1圖2-6文件；被喚醒的r2執(zhí)行語句6，判斷read_count的值不是0，所以執(zhí)行語句7，將read_count的值加1后變成2，執(zhí)行語句8，將信號量h_mutex_read_count的值加1后變成0，并喚醒r3，r2執(zhí)行語句9，開始讀文件；被喚醒的r3執(zhí)行語句6，判斷read_count的值不是0，所以執(zhí)行語句7，將read_count的值加1后變成3，執(zhí)行語句8，將信號量h_mutex_read_count的值加1后變成1，r3執(zhí)行語句9，開始讀文件。這樣三個讀者同時讀文件，參見圖2-10；當(dāng)r1、r2和r3讀完文件時，都執(zhí)行語句1014，并由最后一個執(zhí)行語句1014的讀者執(zhí)行V(r_w_w)，將信號量r_w_w的值加1后變成0，并喚醒w3，w3接著執(zhí)行語句18，開始寫文件，參見圖2-11；當(dāng)w3寫完文件時，執(zhí)行語句19，將信號量r_w_w的值加1后變成1，回到初始狀態(tài)?？梢姡瑢τ谡埱笮蛄衱1,w2,r1,w3,r2,r3，實(shí)際訪問文件的順序是w1,w2,r1,r2,r3,w3。雖然w3比r2、r3先提出請求，但是由于在此之前已經(jīng)有r1在讀文件，所以優(yōu)先響應(yīng)讀者r2、r3，阻塞寫者w3。如果在w3之后不斷有新的讀者到達(dá)，則w3將一直被阻塞，直至被餓死。r3請求read_count=0h_mutex_read_count-2 r2,r3r_w_w-3 w2,r1,w3訪問文件者：w1圖2-8w1結(jié)束，喚醒w2read_count=0h_mutex_read_count-2 r2,r3r_w_w-2 r1,w3訪問文件者：w2圖2-9r1,r2,r3結(jié)束,喚醒w3read_count=0h_mutex_read_count1NULL r_w_w0NULL 訪問文件者： w3圖2-11w2結(jié)束,喚醒r1,r1喚醒r2,r2喚醒r3read_count=3h_mutex_read_count1NULL r_w_w-1 w3訪問文件者：r1,r2,r3圖2-10l 情形2 最先調(diào)度讀者第一個讀者執(zhí)行P(h_mutex_read_count)成功，將信號量h_mutex_read_count的值變?yōu)?，接著該讀者判斷read_count是0，所以執(zhí)行P(r_w_w)操作成功，獲得文件的訪問權(quán)，將r_w_w的值變?yōu)?，然后將read_count變成1，執(zhí)行V(h_mutex_read_count)，之后開始讀文件；隨后的寫者執(zhí)行P(r_w_w)將r_w_w的值變?yōu)樨?fù)數(shù)，從而阻塞在信號量r_w_w上；其它的讀者執(zhí)行P(h_mutex_read_count)成功，判斷read_count不是0，所以直接將read_count的值再加1，執(zhí)行V(h_mutex_read_count)，之后開始讀文件?？梢姸鄠€讀者可以同時讀文件，并在讀文件時阻塞寫者。2.2.2 寫者優(yōu)先算法分析通過增加信號量并修改上述程序可以得到寫者優(yōu)先算法。為了實(shí)現(xiàn)寫者優(yōu)先算法，需要將寫者和讀者分開排隊，并且第一個讀者和其它讀者也要分開排隊。這樣就需要三個隊列，一個是寫者排隊的地方，另一個是第一個讀者排隊的地方，第三個是其它讀者排隊的地方。相應(yīng)地需要設(shè)置三個信號量，r_w_w、first_reader_wait和reader_wait。當(dāng)一個寫者聲明想寫文件時，可以讓新的讀者中的第一個到first_reader_wait上排隊等待；當(dāng)有讀者阻塞在first_reader_wait上時，讓其它讀者阻塞在reader_wait上；當(dāng)有一個寫者在寫文件時，其它寫者到r_w_w上排隊。只要有活躍的寫者或者寫者隊列不為空，則阻塞新到達(dá)的讀者。為了記錄已經(jīng)發(fā)出聲明的寫者數(shù)量，需要設(shè)置一個整數(shù)writ_count，以表示聲明要寫文件的寫者數(shù)目。由于只要有一個寫者到達(dá)，就不允許讀者去讀，因此僅當(dāng)writ_count=0，表示無寫者聲明寫時，寫者才需要執(zhí)行P(first_reader_wait)操作，若操作成功，寫者便可以執(zhí)行P(r_w_w)去競爭寫文件權(quán)利。其它寫者不需要再向讀者聲明，可以直接執(zhí)行P(r_w_w)去競爭寫文件 權(quán)利。同理僅當(dāng)寫者在執(zhí)行writ_count減1操作后其值為0時，才需要執(zhí)行V(first_reader_wait)操作，以便喚醒第一個被阻塞的讀者去讀文件。又因?yàn)閣rit_count是一個可被多個寫者訪問的臨界資源，所以，應(yīng)該為它設(shè)置一個互斥信號量writer_mutex。通過上述分析得到圖2-13的算法描述。下面對該算法的調(diào)度效果進(jìn)行分析。假設(shè)最初沒有進(jìn)程在訪問文件。過了一會，就會有很多讀者和寫者到達(dá)。對它們可能有兩種調(diào)度情形。l 情形1 最先調(diào)度寫者寫者執(zhí)行P(writ_count_mutex)，將writ_count_mutex的值變?yōu)?，并判斷writ_count是0，從而執(zhí)行P(first_reader_wait)，將first_reader_wait的值變?yōu)?，成功地向讀者聲明了寫訪問意圖，接著將writ_count變?yōu)?，執(zhí)行V(writ_count_mutex)，將writ_count_mutex的值變?yōu)?。然后寫者執(zhí)行P(r_w_w)操作，將r_w_w的值變?yōu)?，成功地獲得了文件的寫訪問權(quán)利。第一個寫者開始寫文件；其它的寫者執(zhí)行P(writ_count_mutex)，判斷writ_count不是0，所以直接將writ_count加1，執(zhí)行V(writ_count_mutex)，然后執(zhí)行P(r_w_w)操作，將r_w_w的值變?yōu)樨?fù)數(shù)，寫者依次被阻塞在信號量r_w_w上；第一個讀者執(zhí)行P(reader_wait)，將reader_wait的值變?yōu)?，接著執(zhí)行P(first_reader_wait)，將first_reader_wait的值變?yōu)樨?fù)1，阻塞在信號量first_reader_wait上；其它讀者執(zhí)行P(reader_wait)，將reader_wait的值變?yōu)樨?fù)數(shù)，依次阻塞在reader_wait上。當(dāng)?shù)谝粋€寫者寫完文件后，執(zhí)行V(r_w_w)，喚醒一個寫者并將寫者計數(shù)器writ_count減1，被喚醒的寫者可以寫文件，寫完后執(zhí)行V(r_w_w)，喚醒下一個寫者并將寫者計數(shù)器writ_count減1，直到最后一個寫者將writ_count減為0，才執(zhí)行V(first_reader_wait)喚醒第一個阻塞的讀者。被喚醒的讀者執(zhí)行P(h_mutex_read_count)，然后判斷read_count是0，從而執(zhí)行 P(r_w_w)，由于最后一個寫者寫完文件后，r_w_w的值已經(jīng)還原為1，所以被喚醒的讀者執(zhí)行P(r_w_w)成功，將r_w_w的值變?yōu)?，獲得文件的讀訪問權(quán)。接著將read_count的值加到1，執(zhí)行V(h_mutex_read_count)，再執(zhí)行V(reader_wait)，喚醒第二個等待的讀者，第一個讀者執(zhí)行V(first_reader_wait)，將first_reader_wait的值還原到1。第一個讀者可以讀文件了。若沒有新的寫者到達(dá)，則第二個讀者執(zhí)行P(first_reader_wait)成功，執(zhí)行P(h_mutex_read_count)并判斷read_count不是0，將read_count加到2，執(zhí)行V(h_mutex_read_count)，再執(zhí)行V(reader_wait)喚醒第三個讀者，再執(zhí)行V(first_reader_wait)，第二個讀者也可以讀文件了。01 semaphore r_w_w=1;02 semaphore reader_wait=1;03 semaphore first_reader_wait=1;04 semaphore h_mutex_read_count=1;05 semaphore writ_count_mutex=1;06 int writ_count=0;07 int read_count=0; 08 reader()09 P(reader_wait);10 P(first_reader_wait);11 P(h_mutex_read_count);12 if(read_count=0) P(r_w_w);13 read_count+;14 V(h_mutex_read_count);15 V(reader_wait);16 V(first_reader_wait);17 讀文件;18 P(h_mutex_read_count);19 read_count-;20 if(read_count=0) V(r_w_w);21 V(h_mutex_read_count);22 23 writer()24 P(writ_count_mutex);25 if(writ_count=0) P(first_reader_wait);26 writ_count+;27 V(writ_count_mutex);28 P(r_w_w);29 寫文件;30 V(r_w_w);31 P(writ_count_mutex);32 writ_count-;33 if(writ_count=0) V(first_reader_wait);34 V(writ_count_mutex);35 圖2-12 寫者優(yōu)先算法l 情形2 最先調(diào)度讀者第一個讀者執(zhí)行P(reader_wait)，將reader_wait的值變?yōu)?，執(zhí)行P(first_reader_wait)，將first_reader_wait的值變?yōu)?，向?qū)懻呗暶饔凶x者要讀文件，接著執(zhí)行P(h_mutex_read_count)，并判斷read_count是0所以執(zhí)行P(r_w_w)，將r_w_w的值變?yōu)?，成功地獲得了文件的讀訪問權(quán)，將讀者計數(shù)器read_count加到1，執(zhí)行V(h_mutex_read_count)，V(reader_wait)，V(first_reader_wait)，將reader_wait和first_reader_wait的值依次還原為1。之后，第一個讀者開始讀文件。若在第一個讀者讀文件的過程中沒有寫者到達(dá)，則其它讀者可以同時讀文件；若在讀者讀文件時，有寫者到達(dá)，則第一個到達(dá)的寫者執(zhí)行P(writ_count_mutex)，將writ_count_mutex的值變?yōu)?，并判斷writ_count是0，從而執(zhí)行P(first_reader_wait)，將first_reader_wait的值變?yōu)?，成功地向讀者聲明了寫訪問意圖，接著將writ_count變?yōu)?，執(zhí)行V(writ_count_mutex)，將writ_count_mutex的值變?yōu)?。然后寫者執(zhí)行P(r_w_w)操作，（由于有讀者在讀文件，所以）將r_w_w的值變?yōu)樨?fù)1，寫者被阻塞在信號量r_w_w上；當(dāng)在讀文件的所有讀者都讀完文件后，由最后一個退出的讀者執(zhí)行V(r_w_w)喚醒寫者。第一個寫者開始寫文件。2.2.3 無優(yōu)先算法分析除了在讀者優(yōu)先時需要的信號量r_w_w和h_mutex_read_count之外，還需要設(shè)置一個信號量wait供讀者和寫者排隊。讀者和寫者都排在wait隊列上。若有讀者在讀文件，則第一個寫者阻塞在r_w_w上，其它的寫者和讀者阻塞在wait上；若有一個寫者在寫文件，則其它寫者和讀者都阻塞在wait上。無優(yōu)先的算法描述如圖2-13所示。01 semaphore r_w_w=1;02 semaphore wait=1;03 semaphore h_mutex_read_count=1;04 int read_count=0; 05 reader()06 P(wait);07 P(h_mutex_read_count);08 if(read_count=0) P(r_w_w);09 read_count+;10 V(h_mutex_read_count);11 V(wait);12 讀文件;13 P(h_mutex_read_count);14 read_count-;15 if(read_count=0) V(r_w_w);16 V(h_mutex_read_count);17 18 writer()19 P(wait);20 P(r_w_w);21 寫文件;22 V(r_w_w);23 V(wait);24 圖2-13 無優(yōu)先算法下面對該算法的調(diào)度效果進(jìn)行分析。最初沒有進(jìn)程在訪問文件。過了一會，就會有很多讀者和寫者到達(dá)。對它們可能有兩種調(diào)度情形。l 情形1 最先調(diào)度寫者寫者執(zhí)行P(wait)操作成功，將wait的值變?yōu)?，再執(zhí)行P(r_w_w)操作成功，將r_w_w的值變?yōu)?，獲得文件的訪問權(quán)，寫者可以寫文件了。其它的寫者或者讀者執(zhí)行P(wait)操作，將wait的值變?yōu)樨?fù)數(shù)，從而依次阻塞在信號量wait上；第一個寫者寫完文件后，執(zhí)行V(r_w_w)，將r_w_w的值還原為1，再執(zhí)行V(wait)喚醒排在wait隊列最前面的一個進(jìn)程，可能是讀者，也可能是寫者。l 情形2 最先調(diào)度讀者第一個讀者執(zhí)行P(wait)操作成功，將wait的值變?yōu)?，再執(zhí)行P(h_mutex_read_count)成功，將信號量h_mutex_read_count的值變?yōu)?，接著該讀者判斷read_count是0，所以執(zhí)行P(r_w_w)操作成功，獲得文件的訪問權(quán)，將r_w_w的值變?yōu)?，然后將read_count變成1，執(zhí)行V(h_mutex_read_count)，V(wait)，將信號量h_mutex_read_count和wait的值還原為1，之后開始讀文件；若隨后到達(dá)的仍然是讀者，則這些讀者將read_count各加1之后也開始讀文件；若隨后到達(dá)的是寫者，則寫者執(zhí)行P(wait)操作成功，將wait的值變?yōu)?，再執(zhí)行P(r_w_w)操作將r_w_w的值變?yōu)樨?fù)數(shù)，從而阻塞在r_w_w上。這使得在它之后到達(dá)的讀者和寫者相繼阻塞在wait上。當(dāng)?shù)谝慌x者讀完文件后，由最后一個退出的讀者執(zhí)行執(zhí)行V(r_w_w)，從而喚醒第一個被阻塞的寫者。 2.3 函數(shù)設(shè)計實(shí)現(xiàn)讀者/寫者問題的源程序名稱是reader_and_writer.cpp。該程序共包括10個函數(shù)。這些函數(shù)可以分成4組。各組包含的函數(shù)及其功能如表2-1。 表2-1 函數(shù)功能簡述組別包括函數(shù)函數(shù)功能一main()顯示主菜單，接收用戶的選擇并執(zhí)行相應(yīng)的功能。二RF_reader_thread()RF_writer_thread()reader_first()讀者優(yōu)先算法的讀者線程函數(shù)讀者優(yōu)先算法的寫者線程函數(shù)讀者優(yōu)先算法的初始化函數(shù)：創(chuàng)建10個線程并等待它們結(jié)束三WF_reader_thread()WF_writer_thread()writer_first()寫者優(yōu)先算法的讀者線程函數(shù)寫者優(yōu)先算法的寫者線程函數(shù)寫者優(yōu)先算法的初始化函數(shù)：創(chuàng)建10個線程并等待它們結(jié)束四FIFO_reader_thread()FIFO_writer_thread()first_come_first_serverd()無優(yōu)先算法的讀者線程函數(shù)無者優(yōu)先算法的寫者線程函數(shù)無者優(yōu)先算法的初始化函數(shù)：創(chuàng)建10個線程并等待它們結(jié)束程序開始部分定義了宏MAX_THREAD，表示程序中創(chuàng)建的線程數(shù)。還定義了測試數(shù)據(jù)的結(jié)構(gòu)體TEST_INFO，該結(jié)構(gòu)體包含三個數(shù)據(jù)項(xiàng)：線程名稱；提出請求的時刻；操作持續(xù)時間。接著定義了全局變量，這些全局變量的作用如下：數(shù)組test_data保存了10個線程的測試數(shù)據(jù)；整數(shù)read_count記錄一段時間內(nèi)同時對文件進(jìn)行讀操作的線程數(shù)；整數(shù)write_count記錄一段時間內(nèi)提出寫操作請求的線程數(shù)，該整數(shù)只在寫者優(yōu)先算法中使用；CS_DATA是臨界區(qū)變量，用來保護(hù)文件，實(shí)現(xiàn)對文件的讀寫互斥和寫寫互斥（相當(dāng)于算法描述中的r_w_w）；互斥體h_mutex_read_count用來保護(hù)整數(shù)read_count，以保證多個讀者對read_count的互斥訪問；互斥體h_mutex_write_count用來保護(hù)整數(shù)write_count，以保證多個寫者對write_count的互斥訪問，該互斥體只在寫者優(yōu)先算法中使用；互斥體h_mutex_first_reader_wait和h_mutex_reader_wait只在寫者優(yōu)先算法中使用，當(dāng)有寫者在寫文件時，提出讀請求的第一個讀者阻塞在h_mutex_first_reader_wait上，其余的讀者阻塞在h_mutex_reader_wait上；互斥體h_mutex_wait只在無優(yōu)先算法中使用，當(dāng)文件被使用時，后繼的讀請求和寫請求依次阻塞在h_mutex_wait上。第3章 程序?qū)崿F(xiàn)第3章 程序?qū)崿F(xiàn)3.1 程序功能及界面設(shè)計該程序采用簡單的控制臺應(yīng)用程序界面，在主界面上顯示程序的功能。該程序的功能如下：1) 演示讀者優(yōu)先算法；2) 演示寫者優(yōu)先算法；3) 演示無優(yōu)先算法；4) 退出。3.2 實(shí)現(xiàn)程序流程3.2.1 讀者優(yōu)先算法實(shí)現(xiàn)對于相繼到達(dá)的一批讀者，并不是每個讀者都需要執(zhí)行P(r_w_w)和V(r_w_w)。在這批讀者中，只有最先到達(dá)的讀者才需要執(zhí)行P(r_w_w)，與寫者競爭對文件的訪問權(quán)，若執(zhí)行P(r_w_w)成功則獲得了文件的訪問權(quán)，其他的讀者可直接訪問文件；同理，只有最后退出臨界區(qū)的讀者需要執(zhí)行V(r_w_w)來歸還文件訪問權(quán)。為了記錄正在讀文件的一批讀者的數(shù)量，需要設(shè)置一個整型變量read_count，每一個讀者到達(dá)時都要將read_count加1，退出時都要將read_count減1。由于只要有一個讀者在讀文件，便不允許寫者寫文件，所以，僅當(dāng)read_count=0時，即尚無讀者在讀文件時，讀者才需要執(zhí)行P(r_w_w)操作。若P(r_w_w)操作成功，讀者便可去讀文件，相應(yīng)地，read_count+1。同理，僅當(dāng)在執(zhí)行了read_count減1操作后其值為0時，才需要執(zhí)行V(r_w_w)操作，以便讓寫者寫文件。又因?yàn)閞ead_count是一個可被多個讀者訪問的臨界資源，所以應(yīng)該為它設(shè)置一個互斥信號量h_mutex_read_count。每個讀者在訪問read_count之前執(zhí)行P(h_mutex_read_count)，之后執(zhí)行V(h_mutex_read_count)。讀優(yōu)先操作結(jié)果截圖如下圖3-1：圖3-1 讀優(yōu)先操作截圖3.2.2 寫者優(yōu)先算法實(shí)現(xiàn)為了實(shí)現(xiàn)寫者優(yōu)先算法，需要將寫者和讀者分開排隊，并且第一個讀者和其它讀者也要分開排隊。這樣就需要三個隊列，一個是寫者排隊的地方，另一個是第一個讀者排隊的地方，第三個是其它讀者排隊的地方。相應(yīng)地需要設(shè)置三個信號量，r_w_w、first_reader_wait和reader_wait。當(dāng)一個寫者聲明想寫文件時，可以讓新的讀者中的第一個到first_reader_wait上排隊等待；當(dāng)有讀者阻塞在first_reader_wait上時，讓其它讀者阻塞在reader_wait上；當(dāng)有一個寫者在寫文件時，其它寫者到r_w_w上排隊。只要有活躍的寫者或者寫者隊列不為空，則阻塞新到達(dá)的讀者。為了記錄已經(jīng)發(fā)出聲明的寫者數(shù)量，需要設(shè)置一個整數(shù)writ_count，以表示聲明要寫文件的寫者數(shù)目。由于只要有一個寫者到達(dá)，就不允許讀者去讀，因此僅當(dāng)writ_count=0，表示無寫者聲明寫時，寫者才需要執(zhí)行P(first_reader_wait)操作，若操作成功，寫者便可以執(zhí)行P(r_w_w)去競爭寫文件權(quán)利。其它寫者不需要再向讀者聲明，可以直接執(zhí)行P(r_w_w)去競爭寫文件 權(quán)利。同理僅當(dāng)寫者在執(zhí)行writ_count減1操作后其值為0時，才需要執(zhí)行V(first_reader_wait)操作，以便喚醒第一個被阻塞的讀者去讀文件。又因?yàn)閣rit_count是一個可被多個寫者訪問的臨界資源，所以，應(yīng)該為它設(shè)置一個互斥信號量writer_mutex。寫優(yōu)先操作結(jié)果截圖如下圖 3-2：圖3-2 寫優(yōu)先操作截圖3.2.3 無優(yōu)先算法實(shí)現(xiàn)不僅需要的信號量r_w_w和h_mutex_read_count之外，還需要設(shè)置一個信號量wait供讀者和寫者排隊。讀者和寫者都排在wait隊列上。若有讀者在讀文件，則第一個寫者阻塞在r_w_w上，其它的寫者和讀者阻塞在wait上；若有一個寫者在寫文件，則其它寫者和讀者都阻塞在wait上。無優(yōu)先操作結(jié)果截圖如下圖3-3：圖3-3 無優(yōu)先操作截圖3.3 程序流程圖3.3.1 讀者優(yōu)先算法流程圖根據(jù)定義的函數(shù)名稱和功能畫讀者優(yōu)先算法的函數(shù)流程圖如下圖3-4所示：圖3-4 讀者優(yōu)先算法函數(shù)流程圖3.3.2 寫者優(yōu)先算法流程圖根據(jù)定義的函數(shù)名稱和功能畫寫者優(yōu)先算法的函數(shù)流程圖如下圖3-5所示：圖3-5 寫者優(yōu)先算法函數(shù)流程圖3.3.3 無優(yōu)先算法流程圖根據(jù)定義的函數(shù)名稱和功能畫無優(yōu)先算法的函數(shù)流程圖如下圖3-6所示：圖3-6 無優(yōu)先算法函數(shù)流程圖心得體會心得體會這一次課程設(shè)計，我們組完成了題目3即“讀者-寫者問題與進(jìn)程同步”問題，更加系統(tǒng)地理解和掌握了臨界區(qū)和進(jìn)程互斥的概念掌握用信號量和PV操作實(shí)現(xiàn)進(jìn)程互斥的方法。要求學(xué)生用信號量和PV操作實(shí)現(xiàn)讀者/寫者問題的讀者優(yōu)先算法、寫者優(yōu)先算法和無優(yōu)先算法。經(jīng)過讀者寫者問題的編寫，我對同步機(jī)構(gòu)應(yīng)用有了深入的了解，懂得了運(yùn)用信號量實(shí)現(xiàn)進(jìn)程間的互斥，實(shí)現(xiàn)了不讓共享資源同時修改。用信號量上的原語操作使臨界段問題的解決比較簡單明了了。讀者寫者問題的編寫，花的時間很多，也學(xué)到很多東西。了解在支持多道程序的并發(fā)操作系統(tǒng)設(shè)計中，如何解決資源共享時進(jìn)程間的同步與互斥的信號量機(jī)制。課程設(shè)計提高了我們對所學(xué)知識的綜合應(yīng)用能力，全面檢查并掌握所學(xué)的內(nèi)容，培養(yǎng)獨(dú)立思考、刻苦鉆研的精神，在分析問題、解決問題的過程中，更是獲得一種成功的喜悅，進(jìn)而增加學(xué)習(xí)和應(yīng)用的興趣。同時也要督促自己在學(xué)習(xí)的過程中不斷的完善自我，加強(qiáng)自己的動手操作能力，培養(yǎng)我的獨(dú)立思考的那種思維方式?？傊?，這一次課程設(shè)計我們深刻的理解操作系統(tǒng)，而且鍛煉了實(shí)際編程能力和思維方式，雖然有難度過程中遇到很多問題，經(jīng)過深刻細(xì)致的理解問題、剖析問題、解決問題使我們深刻的認(rèn)識理解了讀者/寫者問題與進(jìn)程同步。參考文獻(xiàn)參考文獻(xiàn)1 劉肄卓 著.操作系統(tǒng)實(shí)驗(yàn)教程113301-1133022 百度百科 /3 左萬歷 等著.計算機(jī)操作系統(tǒng)教程（第三版）. 北京：高等教育出版社，2010.7附錄1 源代碼附錄1 源代碼 #include #include #include #include #include #include #define MAX_THREAD 10 /待測試的線程數(shù)typedef struct /表示測試數(shù)據(jù)格式char thread_name3; /線程名unsigned int require_moment; /請求操作時刻unsigned int persist_time; /操作持續(xù)時間TEST_INFO;TEST_INFO test_dataMAX_THREAD= /測試數(shù)據(jù)表r1,0,15, / r表示讀者線程r2,1, 15, /w表示寫者線程w1,3,3,r3,4, 2,w2,5,6,w3,6,10,r4,7,8,r5,9,2,w4,10,18,w5,12,2;int read_count=0; /記錄正在讀文件的讀者數(shù)int write_count=0; /在寫者優(yōu)先算法中記錄聲明要寫文件的寫者數(shù)CRITICAL_SECTION CS_DATA; /用于保護(hù)文件的臨界區(qū)變量HANDLE h_mutex_read_count=CreateMutex(NULL,FALSE,mutex_read_count);/讀者計數(shù)器互斥體HANDLE h_mutex_write_count=CreateMutex(NULL,FALSE,mutex_write_count);/寫者計數(shù)器互斥體HANDLE h_mutex_reader_wait=CreateMutex(NULL,FALSE,mutex_reader_wait);/在寫者優(yōu)先算法中用于阻塞讀者的互斥體HANDLE h_mutex_first_reader_wait=CreateMutex(NULL,FALSE,mutex_first_reader_wait);/在寫者優(yōu)先算法中用于阻塞第一個讀者的互斥體HANDLE h_mutex_wait=CreateMutex(NULL,FALSE,mutex_wait);/無優(yōu)先時用于阻塞讀者和寫者的互斥體/讀者優(yōu)先時的讀者線程void RF_reader_thread(void *data)char thread_name3; /存放線程名稱strcpy(thread_name,(TEST_INFO *)data)-thread_name);Sleep(TEST_INFO *)data)-require_moment*1000);WaitForSingleObject(h_mutex_read_count,-1);/申請進(jìn)入關(guān)于讀者計數(shù)器的臨界區(qū)相當(dāng)于P操作read_count+;if(read_count=1)EnterCriticalSection(&CS_DATA); /申請進(jìn)入關(guān)于文件的臨界區(qū)相當(dāng)于P操作ReleaseMutex(h_mutex_read_count);/離開關(guān)于讀者計數(shù)器的臨界區(qū)相當(dāng)于V操作printf(%s ,thread_name);Sleep(TEST_INFO *)data)-persist_time*1000); /用延遲相應(yīng)秒來模擬讀文件操作WaitForSingleObject(h_mutex_read_count,-1);read_count-;if(read_count=0)LeaveCriticalSection(&CS_DATA); /離開關(guān)于文件的臨界區(qū)相當(dāng)于V操作ReleaseMutex(h_mutex_read_cou