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

1、*實踐教學(xué)實踐教學(xué)* 蘭州理工大學(xué)蘭州理工大學(xué)計算機(jī)與通信學(xué)院2012 年秋季學(xué)期操作系統(tǒng)原理操作系統(tǒng)原理課程設(shè)計課程設(shè)計題 目： 讀者-寫者問題的實現(xiàn) 專業(yè)班級： 姓 名： 學(xué) 號： 指導(dǎo)教師： 成 績： 1目錄目錄摘 要.21 設(shè)計思想.32 各模塊的偽碼算法.43. 函數(shù)關(guān)系調(diào)用圖.64 程序測試結(jié)果.7設(shè)計總結(jié).10參考文獻(xiàn).11致 謝.122摘摘 要要 本設(shè)計的讀者寫者問題，是指一些進(jìn)程共享一個數(shù)據(jù)區(qū)。數(shù)據(jù)區(qū)可以使一個文件、一塊內(nèi)存空間或者一組寄存器。Reader 進(jìn)程只能讀數(shù)據(jù)區(qū)中的數(shù)據(jù)，而 writer 進(jìn)程必須與其他進(jìn)程互斥地訪問共享對象的同步問題。 讀者寫者問題可以這樣的描述

2、, 有一群寫者和一群讀者, 寫者在寫同一本書, 讀者也在讀這本書, 多個讀者可以同時讀這本書。但是,只能有一個寫者在寫書, 并且,讀者必寫者優(yōu)先,也就是說，讀者和寫者同時提出請求時,讀者優(yōu)先。當(dāng)讀者提出請求時需要有一個互斥操作, 另外, 需要有一個信號量 S 來確定當(dāng)前是否可操作。 本設(shè)計方案就是通過利用記錄型信號量對讀者寫者問題的解決過程進(jìn)行模 擬演示，形象地闡述記錄型信號量機(jī)制的工作原理。關(guān)鍵詞關(guān)鍵詞：共享對象，互斥，同步，信號量31 1 設(shè)計設(shè)計思想思想本設(shè)計借助 C 語言實現(xiàn)進(jìn)程同步和互斥的經(jīng)典問題-讀者寫者問題，用高級語言編寫和調(diào)試一個進(jìn)程同步程序，以加深對進(jìn)程同步機(jī)制的理解。通過用

3、C 語言模擬進(jìn)程同步實現(xiàn)，加深理解有關(guān)進(jìn)程同步和互斥機(jī)制的概念及 P、V 操作的應(yīng)用。學(xué)生通過該題目的設(shè)計過程，掌握讀者、寫者問題的原理、軟件開發(fā)方法并提高解決實際問題的能力。在 Windows 環(huán)境下,創(chuàng)建一個包含 n 個線程的控制臺進(jìn)程。用這 n 個線每個線程按相應(yīng)測試數(shù)據(jù)文件的要求，進(jìn)行讀寫操作。程來表示 n 個讀者或?qū)懻摺Ｕ堄眯盘柫繖C(jī)制分別實現(xiàn)讀者優(yōu)先和寫者優(yōu)先的讀者-寫者問題。將所有的讀者和所有的寫者分別放進(jìn)兩個等待隊列中，當(dāng)讀允許時就讓讀者隊列釋放一個或多個讀者,當(dāng)寫允許時，釋放第一個寫者操作。讀者-寫者的讀寫限制(包括讀者優(yōu)先和寫者優(yōu)先) 1)寫-寫互斥,即不能有兩個寫者同時進(jìn)行

4、寫操作； 2)讀-寫互斥,即不能同時有一個讀者在讀,同時卻有一個寫者在寫； 3)讀讀允許,即可以有 2 個以上的讀者同時讀；4)讀者優(yōu)先附加條件：如果一個讀者申請進(jìn)行讀操作，同時又有一個讀操作正在進(jìn)行讀操作，則該讀者可以直接開始讀操作； 5)寫者優(yōu)先附加條件：如果一個讀者申請進(jìn)行讀操作時已經(jīng)有一個寫者在等待訪問共享資源，則該讀者必須等到?jīng)]有寫者處于等待狀態(tài)后才能開始讀操作。42 2 各模塊的偽碼算法各模塊的偽碼算法讀者優(yōu)先算法：讀者優(yōu)先算法：設(shè)置兩個互斥信號量：rwmutex 用于寫者與其他讀者/寫者互斥的訪問共享數(shù)據(jù)rmutex 用于讀者互斥的訪問讀者計數(shù)器 readcountsemapho

5、re rwmutex=1, rmutex=1;int readcount = 0; reader i /讀者進(jìn)程 i=1,2,. doP(rmutex); /讀者互斥readcount+; /讀者數(shù)加 1if (readcount = 1) P(rwmutex); /讀者寫者互斥 V(rmutex); 讀者讀數(shù)據(jù);P(rmutex); Readcount-; if (readcount = 0) V(rwmutex); V(rmutex);while(1); writer j /寫者進(jìn)程 j = 1,2,. doP(rwmutex); 寫文件； V(rwmutex); while(1); 寫者

6、優(yōu)先算法：寫者優(yōu)先算法：設(shè)置三個互斥信號量：rwmutex 用于寫者與其他讀者/寫者互斥的訪問共享數(shù)據(jù) rmutex 用于讀者互斥的訪問讀者計數(shù)器 readcount nrmutex 用于寫者等待已進(jìn)入讀者退出，所有讀者退出前互斥寫操作semaphore rwmutex= 1，rmutex= 1，nrmutex= 1; 5int readcount = 0;reader i /讀者進(jìn)程 i=1,2,.doP(rwmutex); P(rmutex); readcount+;if (readcount = 1) P(nrmutex); /有讀者進(jìn)入，互斥寫操作V(rmutex);V(rwmutex

7、);/及時釋放讀寫互斥信號量，允許其它讀、寫進(jìn)程申請資源讀數(shù)據(jù);P(rmutex);readcount-;if (readcount = 0) V(nrmutex); /所有讀者退出，允許寫更新V(rmutex); while(1);writer j /寫者進(jìn)程 j = 1,2,.doP(rwmutex); / 互斥后續(xù)其它讀者、寫者P(nrmutex); /如有讀者正在讀，等待所有讀者讀完寫更新；V(nrmutex); /允許后續(xù)新的第一個讀者進(jìn)入后互斥寫操作V(rwmutex); /允許后續(xù)新讀者及其它寫者 while(1);63.3. 函數(shù)關(guān)系調(diào)用圖函數(shù)關(guān)系調(diào)用圖Main()g_Curr

8、entTime()CreatePersonList()ReaderProc()WriterProc()CreateReader()CreateWriter()圖 1 函數(shù)關(guān)系圖74 4 程序程序測試結(jié)果測試結(jié)果測試數(shù)據(jù)文件包括 n 行測試數(shù)據(jù),分別描述創(chuàng)建的 n 個線程是讀者還是寫者,以及讀寫操作的開始時間和持續(xù)時間.每行測試數(shù)據(jù)包括四個字段,各字段 間用空格分隔。第一字段為一個正整數(shù),表示線程序號.第二字段表示相應(yīng)線程 角色,R 表示讀者是，W 表示寫者。第三字段為一個正數(shù),表示讀寫操作的開 始時間。線程創(chuàng)建后,延時相應(yīng)時間 (單位為秒) 后發(fā)出對共享資源的讀寫申請. 第四字段為一個正數(shù),表

9、示讀寫操作的持續(xù)時間。當(dāng)線程讀寫申請成功后,開始 對共享資源的讀寫操作,該操作持續(xù)相應(yīng)時間后結(jié)束,并釋放共享資源。在讀者寫者同時在隊列中等待申請資時,讀者優(yōu)先調(diào)用資源.而且如果一個 讀者申請進(jìn)行讀操作時已有另一讀者正在進(jìn)行讀操作, 則該讀者可直接開始讀操 作,即讀讀允許。圖 2 進(jìn)程 1、2 的測試結(jié)果 如圖 2 所示，進(jìn)程 1 是 W 操作,在時間 3 時進(jìn)入隊列,運(yùn)行時間是 5,即在時間 8 時，進(jìn)程 1 退出。在它進(jìn)入時沒有進(jìn)程 占用資源,它既占用資源;知道它釋放資源,等候的進(jìn)程有 3,4,5； 8圖 3 進(jìn)程 3、5 的測試結(jié)果如圖 3 所示，進(jìn)程 5 是 R 操作,在時間 4 時進(jìn)入

10、隊列,運(yùn)行時間是 3, 進(jìn)程 3 是 R 操作,在時間 5 時進(jìn)入隊列,運(yùn)行時間是 2, 在它們進(jìn)入時，進(jìn)程 1占用資源,它等待資源,當(dāng)進(jìn)程 1 釋放資源后,由于讀者優(yōu)先,進(jìn)程 3,5 同時調(diào)運(yùn)資源，因此在時間 11 時，進(jìn)程 3 退出，在時間 12 時，進(jìn)程 5 退出；圖 4 進(jìn)程 2、4、6 的測試結(jié)果如圖 4 所示，進(jìn)程 4 是 W 操作,在時間 5 時進(jìn)入隊列,運(yùn)行時間是 5,在它9進(jìn)入時進(jìn)程 1 占用資源,它等待資源,當(dāng)進(jìn)程 1 釋放資源后,由于讀者優(yōu)先,進(jìn)程 3,5 占用資源,它依然等待,直到進(jìn)程 3,5 都結(jié)束，即進(jìn)程 4 在時間 12 時開始調(diào)用資源；進(jìn)程 2 是 R 操作,

11、在時間 16 時進(jìn)入隊列,運(yùn)行時間是 5,在它進(jìn)入時進(jìn)程 4 占用資源,它等待資源,當(dāng) 4 釋放時占用資源后，進(jìn)程 2 開始運(yùn)行；進(jìn)程 6 是 R 操作,在時間 17 時進(jìn)入隊列,運(yùn)行時間是 7,在它進(jìn)入時進(jìn)程2 占用資源,它等待進(jìn)程 2 釋放后最后調(diào)用資源。10設(shè)計總結(jié)設(shè)計總結(jié)課程設(shè)計是培養(yǎng)學(xué)生綜合運(yùn)用所學(xué)知識,發(fā)現(xiàn),提出,分析和解決實際問題,鍛煉實踐能力的重要環(huán)節(jié),是對學(xué)生實際工作能力的具體訓(xùn)練和考察過程。此次操作系統(tǒng)課程設(shè)計，我的感慨頗多，的確，從選題到定稿，從理論到實踐，在整整兩星期的日子里，我學(xué)到很多的東西;同時不僅鞏固了以前所學(xué)過的知識，而且學(xué)到了很多在書本上所沒有學(xué)到過的知識。通

12、過這次課程設(shè)計我懂得了理論與實際相結(jié)合的重要性，只有理論知識是遠(yuǎn)遠(yuǎn)不夠的，所以只有把所學(xué)的理論知識與實踐相結(jié)合起來，從理論中得出結(jié)論，才能真正的服務(wù)于社會，從而提高自己的實際動手能力和獨立思考的能力。在設(shè)計的過程中遇到問題，可以說是困難重重，難免會遇到過各種各樣的問題，同時在設(shè)計的過程中發(fā)現(xiàn)了自己的不足之處，對以前所學(xué)過的知識理解得不夠深刻，掌握得不夠牢固。因此，在以后的學(xué)習(xí)中要多下苦功，加強(qiáng)基礎(chǔ)知識的學(xué)習(xí)，并且培養(yǎng)自己的動手實踐能力。11參考文獻(xiàn)參考文獻(xiàn)1. 湯子瀛，哲鳳屏. 計算機(jī)操作系統(tǒng)，西安：電子科技大學(xué)學(xué)出版社，2002年2. 王清，李光明. 計算機(jī)操作系統(tǒng)，北京：冶金工業(yè)出版社，2

13、003 年 3 月3.孫鐘秀等. 操作系統(tǒng)教程. 北京：高等教育出版社，2008 年 4 月4.曾明. Linux 操作系統(tǒng)應(yīng)用教程. 西安： 陜西科學(xué)技術(shù)出版社，2005 年5. 張麗芬，劉利雄. 操作系統(tǒng)實驗教程. 北京： 清華大學(xué)出版社，2006 年6. 孟靜.操作系統(tǒng)教程原理和實例分析. 北京：高等教育出版社，2001年7. 周長林. 計算機(jī)操作系統(tǒng)教程. 北京：高等教育出版社，2011 年 12 月8. 張堯?qū)W. 計算機(jī)操作系統(tǒng)教程.北京：清華大學(xué)出版社，2006 年 10 月9. 任滿杰. 操作系統(tǒng)原理實用教程.北京：電子工業(yè)出版社，2006 年 1 月12致致 謝謝這次課程設(shè)計培

14、養(yǎng)了我耐心、縝密、全面地思考問題的能力，從而加快了問題解決的速度、提高了個人的工作效率，以及鍛煉了使問題在短時間內(nèi)得以解決的品質(zhì)。我從“紙上談兵”到可以自己動腦動手分析調(diào)試程序，收獲不少。首先要感謝學(xué)校給我這次實踐的機(jī)會，給了自己一個舞臺。這不僅是對自身的檢驗，而且增加了我編寫代碼的功力。還有多虧了老師們從理論到上機(jī)親自指導(dǎo)的辛苦教授，給予了我們最大幫助和全面指導(dǎo)。在這里，尤其感謝我的指導(dǎo)老師朱紅蕾老師，你不辭辛苦的給我們耐心指導(dǎo)。在這里，我衷心向你們致謝！最后還要感謝熱心的同學(xué)們，在我陷入誤區(qū)的時候，是他們熱心的幫助使我擺脫困境。最后衷心感謝所有給予我?guī)椭椭笇?dǎo)的老師和同學(xué),沒有他們的幫助我

15、的程序也不會完成得這么順利。13源代碼：#include #include #include #include #include #include #define MAX_PERSON 100#define READER 0 /讀者#define WRITER 1 /寫者#define END -1#define R READER#define W WRITER typedef struct _Person HANDLE m_hThread; /定義處理線程的句柄int m_nType; /進(jìn)程類型(讀寫)int m_nStartTime; /開始時間14int m_nWorkTime; /運(yùn)

16、行時間int m_nID;/進(jìn)程號 Person; Person g_PersonsMAX_PERSON; int g_NumPerson = 0;long g_CurrentTime= 0; /基本時間片數(shù)int g_PersonLists = /進(jìn)程隊列 1, W, 3, 5, 2, W, 16, 5, 3, R, 5, 2, 4, W, 6, 5, 5, R, 4, 3, 6, R, 17,7, END, ; int g_NumOfReading = 0;int g_NumOfWriteRequest = 0; /申請寫進(jìn)程的個數(shù) HANDLE g_hReadSemaphore; /讀者

17、信號 HANDLE g_hWriteSemaphore; /寫者信號 bool finished = false; /所有的讀完成 /bool wfinished = false; /所有的寫完成 void CreatePersonList(int *pPersonList); bool CreateReader(int StartTime,int WorkTime,int ID); bool CreateWriter(int StartTime,int WorkTime,int 15ID); DWORD WINAPI ReaderProc(LPVOID lpParam);DWORD WINA

18、PI WriterProc(LPVOID lpParam);int main() g_hReadSemaphore = CreateSemaphore(NULL,1,100,NULL); /創(chuàng)建信號燈,當(dāng)前可用的資源數(shù)為 1,最大為 100 g_hWriteSemaphore = CreateSemaphore(NULL,1,100,NULL); /創(chuàng)建信號燈,當(dāng)前 可用的資源數(shù)為 1,最大為 100CreatePersonList(g_PersonLists); / 創(chuàng)建所有的讀者和寫者 printf(Created all the reader and writern.n); g_Curr

19、entTime = 0; while(true) g_CurrentTime+; Sleep(300); / 300 ms printf(CurrentTime = %dn,g_CurrentTime); if(finished) return 0; 16 / return 0; void CreatePersonList(int *pPersonLists) int i=0; int *pList = pPersonLists; bool Ret; while(pList0 != END) switch(pList1) case R: Ret = CreateReader(pList2,pL

20、ist3,pList0); /351,w452,523,654 break; case W: Ret = CreateWriter(pList2,pList3,pList0); break; if(!Ret) printf(Create Person %d is wrongn,pList0); pList += 4; / move to next person list17 DWORD WINAPI ReaderProc(LPVOID lpParam) /讀過程 Person *pPerson = (Person*)lpParam; / wait for the start time whil

21、e(g_CurrentTime != pPerson-m_nStartTime) printf(Reader %d is Requesting .n,pPerson-m_nID); printf(nn*n); / wait for the write request WaitForSingleObject(g_hReadSemaphore,INFINITE); if(g_NumOfReading=0) WaitForSingleObject(g_hWriteSemaphore,INFINITE); g_NumOfReading+; ReleaseSemaphore(g_hReadSemapho

22、re,1,NULL); pPerson-m_nStartTime = g_CurrentTime;18printf(Reader %d is Reading the Shared Buffer.n,pPerson-m_nID); printf(nn*n); while(g_CurrentTime m_nStartTime + pPerson-m_nWorkTime) printf(Reader %d is Exit.n,pPerson-m_nID); printf(nn*n); WaitForSingleObject(g_hReadSemaphore,INFINITE); g_NumOfRea

23、ding-; if(g_NumOfReading = 0) ReleaseSemaphore(g_hWriteSemaphore,1,NULL);/此時沒有讀者,可以寫 ReleaseSemaphore(g_hReadSemaphore,1,NULL); if(pPerson-m_nID = 4) finished = true; /所有的讀寫完成 ExitThread(0); return 0; 19 DWORD WINAPI WriterProc(LPVOID lpParam) Person *pPerson = (Person*)lpParam; / wait for the start

24、 time while(g_CurrentTime != pPerson-m_nStartTime) printf(Writer %d is Requesting .n,pPerson-m_nID); printf(nn*n); WaitForSingleObject(g_hWriteSemaphore,INFINITE); / modify the writers real start time pPerson-m_nStartTime = g_CurrentTime; printf(Writer %d is Writting the Shared Buffer.n,pPerson-m_nID); while(g_CurrentTime m_nStartTime + pPerson-m_nWorkTime) printf(Writer %d is Exit.n,pPerson-m_nID); printf(nn*n); 20/g_NumOfWriteRequest-; ReleaseSemaphore(g_hWriteSemaphore,1,NULL); if(pPerson-m_nID = 4) finished = true;/所有的讀寫完成 ExitThread(0); return 0;bool CreateReader(int StartTime