操作系統(tǒng)原理課程設(shè)計讀者-寫者問題的實現(xiàn)

1、<p>　　*******************</p><p><b>　　實踐教學(xué)</b></p><p>　　*******************</p><p><b>　　計算機與通信學(xué)院</b></p><p><b>　　2012年秋季學(xué)期</b>&

2、lt;/p><p>　　操作系統(tǒng)原理課程設(shè)計</p><p>　　題 目： 讀者-寫者問題的實現(xiàn) </p><p>　　專業(yè)班級： </p><p>　　姓 名： </p><p>　　學(xué) 號： </p><

3、;p>　　指導(dǎo)教師： </p><p>　　成 績： </p><p><b>　　目錄</b></p><p><b>　　摘 要2</b></p><p><b>　　1． 設(shè)計思想3</b>

4、</p><p>　　2． 各模塊的偽碼算法4</p><p>　　3. 函數(shù)關(guān)系調(diào)用圖6</p><p>　　4． 程序測試結(jié)果7</p><p><b>　　設(shè)計總結(jié)10</b></p><p><b>　　參考文獻11</b></p><

5、p><b>　　致 謝12</b></p><p><b>　　摘 要</b></p><p>　　本設(shè)計的讀者寫者問題，是指一些進程共享一個數(shù)據(jù)區(qū)。數(shù)據(jù)區(qū)可以使一個文件、一塊內(nèi)存空間或者一組寄存器。Reader進程只能讀數(shù)據(jù)區(qū)中的數(shù)據(jù)，而writer進程必須與其他進程互斥地訪問共享對象的同步問題。</p><p&

6、gt;　　讀者寫者問題可以這樣的描述, 有一群寫者和一群讀者, 寫者在寫同一本書, 讀者也在讀這本書, 多個讀者可以同時讀這本書。但是,只能有一個寫者在寫書, 并且,讀者必寫者優(yōu)先,也就是說，讀者和寫者同時提出請求時,讀者優(yōu)先。當(dāng)讀者提出請求時需要有一個互斥操作, 另外, 需要有一個信號量S來確定當(dāng)前是否可操作。</p><p>　　本設(shè)計方案就是通過利用記錄型信號量對讀者寫者問題的解決過程進行模 擬演示，形象地

7、闡述記錄型信號量機制的工作原理。</p><p>　　關(guān)鍵詞：共享對象，互斥，同步，信號量</p><p><b>　　1． 設(shè)計思想</b></p><p>　　本設(shè)計借助C語言實現(xiàn)進程同步和互斥的經(jīng)典問題--讀者寫者問題，用高級語言編寫和調(diào)試一個進程同步程序，以加深對進程同步機制的理解。通過用C語言模擬進程同步實現(xiàn)，加深理解有關(guān)進程同步和互

8、斥機制的概念及P、V操作的應(yīng)用。學(xué)生通過該題目的設(shè)計過程，掌握讀者、寫者問題的原理、軟件開發(fā)方法并提高解決實際問題的能力。</p><p>　　在 Windows環(huán)境下,創(chuàng)建一個包含n個線程的控制臺進程。用這n個線每個線程按相應(yīng)測試數(shù)據(jù)文件的要求，進行讀寫操作。程來表示 n 個讀者或?qū)懻?。請用信號量機制分別實現(xiàn)讀者優(yōu)先和寫者優(yōu)先的讀者-寫者問題。</p><p>　　將所有的讀者和所有的寫

9、者分別放進兩個等待隊列中，當(dāng)讀允許時就讓讀者隊列釋放一個或多個讀者,當(dāng)寫允許時，釋放第一個寫者操作。</p><p>　　讀者-寫者的讀寫限制(包括讀者優(yōu)先和寫者優(yōu)先) </p><p>　　1)寫-寫互斥,即不能有兩個寫者同時進行寫操作； </p><p>　　2)讀-寫互斥,即不能同時有一個讀者在讀,同時卻有一個寫者在寫； </p><p&g

10、t;　　3)讀讀允許,即可以有 2 個以上的讀者同時讀；</p><p>　　4)讀者優(yōu)先附加條件：如果一個讀者申請進行讀操作，同時又有一個讀操作正在進行讀操作，則該讀者可以直接開始讀操作； </p><p>　　5)寫者優(yōu)先附加條件：如果一個讀者申請進行讀操作時已經(jīng)有一個寫者在等待訪問共享資源，則該讀者必須等到?jīng)]有寫者處于等待狀態(tài)后才能開始讀操作。</p><p>

11、;　　2． 各模塊的偽碼算法</p><p><b>　　讀者優(yōu)先算法：</b></p><p>　　設(shè)置兩個互斥信號量：</p><p>　　rwmutex 用于寫者與其他讀者/寫者互斥的訪問共享數(shù)據(jù)rmutex  用于讀者互斥的訪問</p><p>　　讀者計數(shù)器 readcount</p

12、><p>　　semaphore rwmutex=1, rmutex=1;</p><p>　　int readcount = 0;       </p><p>　　reader i  //讀者進程 i=1,2,….  </p><p><b>　　

13、do{</b></p><p>　　P(rmutex);   //讀者互斥</p><p>　　readcount++; //讀者數(shù)加1</p><p>　　if (readcount == 1) P(rwmutex);   //讀者寫者互斥 </p><p>　　V(rmute

14、x); </p><p><b>　　讀者讀數(shù)據(jù);</b></p><p>　　P(rmutex); </p><p>　　Readcount--;  </p><p>　　if (readcount == 0) V(rwmutex);   </p><p>　　

15、V(rmutex);</p><p>　　}while(1);       </p><p>　　writer j //寫者進程 j = 1,2,….         </p><p><b>　　do{</b>

16、;</p><p>　　P(rwmutex);   </p><p><b>　　寫文件；   </b></p><p>　　V(rwmutex);       </p><p>　　}while(1); </p&g

17、t;<p><b>　　寫者優(yōu)先算法：</b></p><p>　　設(shè)置三個互斥信號量：</p><p>　　rwmutex 用于寫者與其他讀者/寫者互斥的訪問共享數(shù)據(jù)</p><p>　　rmutex  用于讀者互斥的訪問</p><p>　　讀者計數(shù)器readcount <

18、/p><p>　　nrmutex 用于寫者等待已進入讀者退出，所有讀者退出前互斥寫操作</p><p>　　semaphore rwmutex= 1，rmutex= 1，nrmutex= 1; </p><p>　　int readcount = 0;</p><p>　　reader i  //讀者進程 i=1,2,….<

19、;/p><p><b>　　do{</b></p><p>　　P(rwmutex);  </p><p>　　P(rmutex);    </p><p>　　readcount++;</p><p>　　if (readcount ==

20、1) P(nrmutex); //有讀者進入，互斥寫操作</p><p>　　V(rmutex);</p><p>　　V(rwmutex);//及時釋放讀寫互斥信號量，允許其它讀、寫進程申請資源</p><p><b>　　讀數(shù)據(jù);</b></p><p>　　P(rmutex);</p><p&g

21、t;　　readcount--;</p><p>　　if (readcount == 0) V(nrmutex); //所有讀者退出，允許寫更新</p><p>　　V(rmutex);</p><p>　　}while(1);</p><p>　　writer j //寫者進程 j = 1,2,….</p><p

22、><b>　　do{</b></p><p>　　P(rwmutex);  // 互斥后續(xù)其它讀者、寫者</p><p>　　P(nrmutex);  //如有讀者正在讀，等待所有讀者讀完</p><p><b>　　寫更新；</b></p><p>　　V(nrmutex

23、);   //允許后續(xù)新的第一個讀者進入后互斥寫操作</p><p>　　V(rwmutex);  //允許后續(xù)新讀者及其它寫者</p><p>　　}while(1);</p><p>　　3. 函數(shù)關(guān)系調(diào)用圖</p><p><b>　　圖1 函數(shù)關(guān)系圖</b></p>

24、<p><b>　　4． 程序測試結(jié)果</b></p><p>　　測試數(shù)據(jù)文件包括 n 行測試數(shù)據(jù),分別描述創(chuàng)建的 n 個線程是讀者還是寫者,以及讀寫操作的開始時間和持續(xù)時間.每行測試數(shù)據(jù)包括四個字段,各字段 間用空格分隔。第一字段為一個正整數(shù),表示線程序號.第二字段表示相應(yīng)線程 角色,R 表示讀者是，W 表示寫者。第三字段為一個正數(shù),表示讀寫操作的開 始時間。線程創(chuàng)建后,延時相

25、應(yīng)時間 (單位為秒) 后發(fā)出對共享資源的讀寫申請. 第四字段為一個正數(shù),表示讀寫操作的持續(xù)時間。當(dāng)線程讀寫申請成功后,開始 對共享資源的讀寫操作,該操作持續(xù)相應(yīng)時間后結(jié)束,并釋放共享資源。</p><p>　　在讀者寫者同時在隊列中等待申請資時,讀者優(yōu)先調(diào)用資源.而且如果一個 讀者申請進行讀操作時已有另一讀者正在進行讀操作, 則該讀者可直接開始讀操 作,即讀讀允許。</p><p>　　圖

26、2 進程1、2的測試結(jié)果</p><p>　　如圖2所示，進程1是W操作,在時間3時進入隊列,運行時間是5,即在時間8時，進程1退出。在它進入時沒有進程 占用資源,它既占用資源;知道它釋放資源,等候的進程有3,4,5； </p><p>　　圖3 進程3、5的測試結(jié)果</p><p>　　如圖3所示，進程5是R操作,在時間4時進入隊列,運行時間是3, 進程3是R

27、操作,在時間5時進入隊列,運行時間是 2, 在它們進入時，進程1占用資源,它等待資源,當(dāng)進程1釋放資源后,由于讀者優(yōu)先,進程 3,5 同時調(diào)運資源，因此在時間11時，進程3退出，在時間12時，進程5退出；</p><p>　　圖4 進程2、4、6的測試結(jié)果</p><p>　　如圖4所示，進程4是W操作,在時間5時進入隊列,運行時間是5,在它進入時進程1占用資源,它等待資源,當(dāng)進程1釋放資

28、源后,由于讀者優(yōu)先,進程 3,5占用資源,它依然等待,直到進程 3,5 都結(jié)束，即進程4在時間12時開始調(diào)用資源；進程2是R操作, 在時間16時進入隊列,運行時間是5,在它進入時進程4占用資源,它等待資源,當(dāng)4釋放時占用資源后，進程2開始運行；進程6是R操作,在時間17時進入隊列,運行時間是7,在它進入時進程2占用資源,它等待進程2釋放后最后調(diào)用資源。</p><p><b>　　設(shè)計總結(jié)</b&

29、gt;</p><p>　　課程設(shè)計是培養(yǎng)學(xué)生綜合運用所學(xué)知識,發(fā)現(xiàn),提出,分析和解決實際問題,鍛煉實踐能力的重要環(huán)節(jié),是對學(xué)生實際工作能力的具體訓(xùn)練和考察過程。</p><p>　　此次操作系統(tǒng)課程設(shè)計，我的感慨頗多，的確，從選題到定稿，從理論到實踐，在整整兩星期的日子里，我學(xué)到很多的東西;同時不僅鞏固了以前所學(xué)過的知識，而且學(xué)到了很多在書本上所沒有學(xué)到過的知識。</p>

30、<p>　　通過這次課程設(shè)計我懂得了理論與實際相結(jié)合的重要性，只有理論知識是遠遠不夠的，所以只有把所學(xué)的理論知識與實踐相結(jié)合起來，從理論中得出結(jié)論，才能真正的服務(wù)于社會，從而提高自己的實際動手能力和獨立思考的能力。在設(shè)計的過程中遇到問題，可以說是困難重重，難免會遇到過各種各樣的問題，同時在設(shè)計的過程中發(fā)現(xiàn)了自己的不足之處，對以前所學(xué)過的知識理解得不夠深刻，掌握得不夠牢固。因此，在以后的學(xué)習(xí)中要多下苦功，加強基礎(chǔ)知識的學(xué)習(xí)，并且

31、培養(yǎng)自己的動手實踐能力。</p><p><b>　　參考文獻</b></p><p>　　1. 湯子瀛，哲鳳屏. 計算機操作系統(tǒng)，西安：電子科技大學(xué)學(xué)出版社，2002年</p><p>　　2. 王清，李光明. 計算機操作系統(tǒng)，北京：冶金工業(yè)出版社，2003年3月</p><p>　　3.孫鐘秀等. 操作系統(tǒng)教程. 北

32、京：高等教育出版社，2008年4月</p><p>　　4.曾明.  Linux操作系統(tǒng)應(yīng)用教程. 西安： 陜西科學(xué)技術(shù)出版社，2005年</p><p>　　5. 張麗芬，劉利雄. 操作系統(tǒng)實驗教程. 北京： 清華大學(xué)出版社，2006年</p><p>　　6. 孟靜.操作系統(tǒng)教程——原理和實例分析. 北京：高等教育出版社，2001年</p>

33、<p>　　7. 周長林. 計算機操作系統(tǒng)教程. 北京：高等教育出版社，2011年12月</p><p>　　8. 張堯?qū)W. 計算機操作系統(tǒng)教程.北京：清華大學(xué)出版社，2006年10月</p><p>　　9. 任滿杰. 操作系統(tǒng)原理實用教程.北京：電子工業(yè)出版社，2006年1月</p><p><b>　　致 謝</b><

34、;/p><p>　　這次課程設(shè)計培養(yǎng)了我耐心、縝密、全面地思考問題的能力，從而加快了問題解決的速度、提高了個人的工作效率，以及鍛煉了使問題在短時間內(nèi)得以解決的品質(zhì)。我從“紙上談兵”到可以自己動腦動手分析調(diào)試程序，收獲不少。</p><p>　　首先要感謝學(xué)校給我這次實踐的機會，給了自己一個舞臺。這不僅是對自身的檢驗，而且增加了我編寫代碼的功力。還有多虧了老師們從理論到上機親自指導(dǎo)的辛苦教授，給

35、予了我們最大幫助和全面指導(dǎo)。在這里，尤其感謝我的指導(dǎo)老師朱紅蕾老師，你不辭辛苦的給我們耐心指導(dǎo)。在這里，我衷心向你們致謝！最后還要感謝熱心的同學(xué)們，在我陷入誤區(qū)的時候，是他們熱心的幫助使我擺脫困境。</p><p>　　最后衷心感謝所有給予我?guī)椭椭笇?dǎo)的老師和同學(xué),沒有他們的幫助我的程序也不會完成得這么順利。</p><p><b>　　源代碼：</b></p&

36、gt;<p>　　#include <windows.h></p><p>　　#include <ctype.h> </p><p>　　#include <stdio.h></p><p>　　#include <string.h> </p><p>　　#include &l

37、t;stdlib.h> </p><p>　　#include <malloc.h> </p><p>　　#define MAX_PERSON 100</p><p>　　#define READER 0 //讀者</p><p>　　#define WRITER 1 //寫者</p><p>

38、;　　#define END -1</p><p>　　#define R READER</p><p>　　#define W WRITER </p><p>　　typedef struct _Person { </p><p>　　HANDLE m_hThread; //定義處理線程的句柄</p><p&

39、gt;　　int m_nType; //進程類型(讀寫)</p><p>　　int m_nStartTime; //開始時間</p><p>　　int m_nWorkTime; //運行時間</p><p>　　int m_nID;//進程號 </p><p><b>　　}Person;

40、 </b></p><p>　　Person g_Persons[MAX_PERSON]; </p><p>　　int g_NumPerson = 0;</p><p>　　long g_CurrentTime= 0; //基本時間片數(shù)</p><p>　　int g_PersonLists[] = {//進程隊列

41、</p><p>　　1, W, 3, 5, 2, W, 16, 5, 3, R, 5, 2, </p><p>　　4, W, 6, 5, 5, R, 4, 3, 6, R, 17,7, </p><p><b>　　END, </b></p><p><b>　　}; </b></

42、p><p>　　int g_NumOfReading = 0;</p><p>　　int g_NumOfWriteRequest = 0; //申請寫進程的個數(shù) </p><p>　　HANDLE g_hReadSemaphore; //讀者信號 </p><p>　　HANDLE g_hWriteSemaphore;

43、//寫者信號</p><p>　　bool finished = false; //所有的讀完成 </p><p>　　//bool wfinished = false; //所有的寫完成 </p><p>　　void CreatePersonList(int *pPersonList); </p><

44、;p>　　bool CreateReader(int StartTime,int WorkTime,int ID); </p><p>　　bool CreateWriter(int StartTime,int WorkTime,int ID); </p><p>　　DWORD WINAPI ReaderProc(LPVOID lpParam);</p><p&

45、gt;　　DWORD WINAPI WriterProc(LPVOID lpParam);</p><p>　　int main() </p><p><b>　　{ </b></p><p>　　g_hReadSemaphore = CreateSemaphore(NULL,1,100,NULL); //創(chuàng)建信號燈,當(dāng)前可用的資源數(shù)為 1,最

46、大為100 </p><p>　　g_hWriteSemaphore = CreateSemaphore(NULL,1,100,NULL); //創(chuàng)建信號燈,當(dāng)前 可用的資源數(shù)為 1,最大為100</p><p>　　CreatePersonList(g_PersonLists); // 創(chuàng)建所有的讀者和寫者</p><p>　　printf(&quo

47、t;Created all the reader and writer\n...\n"); </p><p>　　g_CurrentTime = 0; </p><p>　　while(true) </p><p><b>　　{ </b></p><p>　　g_CurrentTime++; </p&g

48、t;<p>　　Sleep(300); // 300 ms</p><p>　　printf("CurrentTime = %d\n",g_CurrentTime); </p><p>　　if(finished) return 0; </p><p>　　} // return 0; </p><p>&l

49、t;b>　　}</b></p><p>　　void CreatePersonList(int *pPersonLists) </p><p><b>　　{</b></p><p><b>　　int i=0; </b></p><p>　　int *pList = pPerso

50、nLists; </p><p>　　bool Ret; </p><p>　　while(pList[0] != END) </p><p><b>　　{ </b></p><p>　　switch(pList[1]) </p><p><b>　　{ </b></

51、p><p><b>　　case R: </b></p><p>　　Ret = CreateReader(pList[2],pList[3],pList[0]); //351,w452,523,654</p><p><b>　　break; </b></p><p><b>　　c

52、ase W: </b></p><p>　　Ret = CreateWriter(pList[2],pList[3],pList[0]);</p><p><b>　　break; </b></p><p><b>　　} </b></p><p><b>　　if(!Ret)

53、 </b></p><p>　　printf("Create Person %d is wrong\n",pList[0]); </p><p>　　pList += 4; // move to next person list</p><p><b>　　}</b></p><p>&l

54、t;b>　　} </b></p><p>　　DWORD WINAPI ReaderProc(LPVOID lpParam) //讀過程</p><p><b>　　{ </b></p><p>　　Person *pPerson = (Person*)lpParam; </p><p>　　

55、// wait for the start time</p><p>　　while(g_CurrentTime != pPerson->m_nStartTime) </p><p><b>　　{} </b></p><p>　　printf("Reader %d is Requesting ...\n",pPers

56、on->m_nID); </p><p>　　printf("\n\n************************************************\n"); </p><p>　　// wait for the write request </p><p>　　WaitForSingleObject(g_hReadSem

57、aphore,INFINITE); </p><p>　　if(g_NumOfReading==0) </p><p><b>　　{ </b></p><p>　　WaitForSingleObject(g_hWriteSemaphore,INFINITE); </p><p><b>　　} </b&

58、gt;</p><p>　　g_NumOfReading++; </p><p>　　ReleaseSemaphore(g_hReadSemaphore,1,NULL); </p><p>　　pPerson->m_nStartTime = g_CurrentTime;</p><p>　　printf("Reader %d

59、is Reading the Shared Buffer...\n",pPerson->m_nID); </p><p>　　printf("\n\n************************************************\n"); </p><p>　　while(g_CurrentTime <= pPerson->

60、m_nStartTime + pPerson->m_nWorkTime) </p><p><b>　　{} </b></p><p>　　printf("Reader %d is Exit...\n",pPerson->m_nID); </p><p>　　printf("\n\n**********

61、**************************************\n"); </p><p>　　WaitForSingleObject(g_hReadSemaphore,INFINITE); </p><p>　　g_NumOfReading--; </p><p>　　if(g_NumOfReading == 0) </p>

62、<p><b>　　{</b></p><p>　　ReleaseSemaphore(g_hWriteSemaphore,1,NULL);//此時沒有讀者,可以寫</p><p><b>　　} </b></p><p>　　ReleaseSemaphore(g_hReadSemaphore,1,NULL); &

63、lt;/p><p>　　if(pPerson->m_nID == 4) finished = true; //所有的讀寫完成 </p><p>　　ExitThread(0); </p><p>　　return 0; </p><p><b>　　} </b></p><p>　　DWORD

64、WINAPI WriterProc(LPVOID lpParam) </p><p><b>　　{ </b></p><p>　　Person *pPerson = (Person*)lpParam; </p><p>　　// wait for the start time</p><p>　　while(g_Cur

65、rentTime != pPerson->m_nStartTime)</p><p><b>　　{} </b></p><p>　　printf("Writer %d is Requesting ...\n",pPerson->m_nID); </p><p>　　printf("\n\n******

66、******************************************\n"); </p><p>　　WaitForSingleObject(g_hWriteSemaphore,INFINITE);</p><p>　　// modify the writer's real start time </p><p>　　pPerson

67、->m_nStartTime = g_CurrentTime; </p><p>　　printf("Writer %d is Writting the Shared Buffer...\n",pPerson->m_nID); </p><p>　　while(g_CurrentTime <= pPerson->m_nStartTime + pP

68、erson->m_nWorkTime) </p><p><b>　　{} </b></p><p>　　printf("Writer %d is Exit...\n",pPerson->m_nID); </p><p>　　printf("\n\n***************************

69、*********************\n"); </p><p>　　//g_NumOfWriteRequest--;</p><p>　　ReleaseSemaphore(g_hWriteSemaphore,1,NULL); </p><p>　　if(pPerson->m_nID == 4) finished = true;//所有的讀寫完

70、成 </p><p>　　ExitThread(0); </p><p><b>　　return 0;</b></p><p><b>　　}</b></p><p>　　bool CreateReader(int StartTime,int WorkTime,int ID) //寫過程<

71、/p><p><b>　　{ </b></p><p>　　DWORD dwThreadID; </p><p>　　if(g_NumPerson >= MAX_PERSON) </p><p>　　return false; </p><p>　　Person *pPerson = &

72、g_Persons[g_NumPerson]; </p><p>　　pPerson->m_nID = ID;</p><p>　　pPerson->m_nStartTime = StartTime; </p><p>　　pPerson->m_nWorkTime = WorkTime; </p><p>　　pPerson

73、->m_nType = READER;</p><p>　　g_NumPerson++; </p><p>　　// 創(chuàng)建一個新的線程 </p><p>　　pPerson->m_hThread=</p><p>　　CreateThread(NULL,0,ReaderProc,(LPVOID)pPerson,0,&dwT

74、hreadID); </p><p>　　if(pPerson->m_hThread == NULL) </p><p>　　return false; </p><p>　　return true; </p><p><b>　　} </b></p><p>　　bool CreateWr

75、iter(int StartTime,int WorkTime,int ID) </p><p><b>　　{ </b></p><p>　　DWORD dwThreadID; </p><p>　　if(g_NumPerson >= MAX_PERSON) </p><p>　　return false; &l

76、t;/p><p>　　Person *pPerson = &g_Persons[g_NumPerson];</p><p>　　pPerson->m_nID = ID; </p><p>　　pPerson->m_nStartTime = StartTime;</p><p>　　pPerson->m_nWorkTime

77、 = WorkTime;</p><p>　　pPerson->m_nType = WRITER;</p><p>　　g_NumPerson++; </p><p>　　// 創(chuàng)建一個新的線程 </p><p>　　pPerson->m_hThread= </p><p>　　CreateThread(N

78、ULL,0,WriterProc,(LPVOID)pPerson,0,&dwThreadID);</p><p>　　if(pPerson->m_hThread == NULL) </p><p>　　return false; </p><p>　　return true; </p><p><b>　　} <