讀者與寫者問題課程設(shè)計報告

1、操作系統(tǒng)課程設(shè)計說明書 學(xué)院名稱： 計算機(jī)與信息工程學(xué)院 班級名稱： 網(wǎng)工114班 組長姓名： 何銘川 學(xué) 號： 2011211371 題 目： 讀者寫者問題 指導(dǎo)教師： 張巧云 組員姓名： 曹海波、李保磊、賈發(fā)展、王禮輝 起止日期： 2013.06.242013.06.28 第一部分：正文部分一、選題背景所謂讀者寫者問題，是指保證一個writer進(jìn)程必須與其他進(jìn)程互斥地訪問共享對象的同步問題。讀者寫者問題可以這樣的描述，有一群寫者和一群讀者，寫者在寫同一本書，讀者也在讀這本書，多個讀者可以同時讀這本書，但是，只能有一個寫者在寫書，并且，讀者必寫者優(yōu)先，也就是說，讀者和寫者同時提出請求時，讀者

2、優(yōu)先。當(dāng)讀者提出請求時需要有一個互斥操作，另外，需要有一個信號量S來當(dāng)前是否可操作。信號量機(jī)制是支持多道程序的并發(fā)操作系統(tǒng)設(shè)計中解決資源共享時進(jìn)程間的同步與互斥的重要機(jī)制，而讀者寫者問題則是這一機(jī)制的一個經(jīng)典范例。與記錄型信號量解決讀者寫者問題不同，信號量機(jī)制它增加了一個限制，即最多允許RN個讀者同時讀。為此，又引入了一個信號量L,并賦予初值為RN，通過執(zhí)行wait（L,1,1）操作，來控制讀者的數(shù)目，每當(dāng)有一個讀者進(jìn)入時，就要執(zhí)行wait（L,1,1）操作，使L的值減1。當(dāng)有RN個讀者進(jìn)入讀后，L便減為0，第RN+1 個讀者要進(jìn)入讀時，必然會因wait（L,1,1）操作失敗而堵塞。對利用信號

3、量來解決讀者寫者問題的描述如下：Var RN integer;L,mx:semaphore: =RN,1；BeginParbeginReader :begin Repeat Swait（L,1,1）; Swait（mx,1,0）; Perform reader operation;Ssignal(L,1);Until false;EndWriter：begin RepeatSwait(mx ,1,1,l,RN,0);Perform writer operation;Ssignal(mx,1);Until false;EndParendEnd其中，Swait（mx,1,0）語句起著開關(guān)作用，只要

4、無Writer進(jìn)程進(jìn)入些，mx=1，reader進(jìn)程就都可以進(jìn)入讀。但是要一旦有Writer進(jìn)程進(jìn)入寫時，其MX=0，則任何reader進(jìn)程就都無法進(jìn)入讀。Swait(mx ,1,1,l,RN,0)語句表示僅當(dāng)既無Write進(jìn)程在寫（mx=1），又無reader進(jìn)程在讀（L=RN）時，writer進(jìn)程才能進(jìn)入臨界區(qū)寫。本設(shè)計方案就是通過利用記錄型信號量對讀者寫者問題的解決過程進(jìn)行模擬演示，形象地闡述記錄型信號量機(jī)制的工作原理。二、設(shè)計思路在Windows 7 環(huán)境下，創(chuàng)建一個包含n 個線程的控制臺進(jìn)程。用這n 個線程來表示n個讀者或?qū)懻?。每個線程按相應(yīng)測試數(shù)據(jù)文件的要求，進(jìn)行讀寫操作。請用信號

5、量機(jī)制分別實現(xiàn)讀者優(yōu)先和寫者優(yōu)先的讀者-寫者問題。讀者-寫者問題的讀寫操作限制：讀者-寫者的讀寫限制（包括讀者優(yōu)先和寫者優(yōu)先）寫-寫互斥，即不能有兩個寫者同時進(jìn)行寫操作讀-寫互斥，即不能同時有一個讀者在讀，同時卻有一個寫者在寫讀讀允許，即可以有2個以上的讀者同時讀將所有的讀者和所有的寫者分別放進(jìn)兩個等待隊列中，當(dāng)讀允許時就讓讀者隊列釋放一個或多個讀者，當(dāng)寫允許時，釋放第一個寫者操作。讀者寫者問題的定義如下：有一個許多進(jìn)程共享的數(shù)據(jù)區(qū)，這個數(shù)據(jù)區(qū)可以是一個文件或者主存的一塊空間；有一些只讀取這個數(shù)據(jù)區(qū)的進(jìn)程（Reader）和一些只往數(shù)據(jù)區(qū)寫數(shù)據(jù)的進(jìn)程(Writer)，此外還需要滿足以下條件：任意

6、多個讀進(jìn)程可以同時讀這個文件；一次只有一個寫進(jìn)程可以往文件中寫；如果一個寫進(jìn)程正在進(jìn)行操作，禁止任何讀進(jìn)程度文件。我們需要分兩種情況實現(xiàn)該問題：讀優(yōu)先：要求指一個讀者試圖進(jìn)行讀操作時，如果這時正有其他讀者在進(jìn)行操作，他可直接開始讀操作，而不需要等待。寫優(yōu)先：一個讀者試圖進(jìn)行讀操作時，如果有其他寫者在等待進(jìn)行寫操作或正在進(jìn)行寫操作，他要等待該寫者完成寫操作后才開始讀操作，具體流程如下圖2.1所示。圖2.1讀者寫者總體流程框圖三、過程論述概要設(shè)計程序由兩部分組成：讀者-寫者模塊：包括系統(tǒng)調(diào)用接口，讀者-寫者活動描述主程序。系統(tǒng)接口主要功能是通過管道向父進(jìn)程發(fā)送系統(tǒng)調(diào)用命令，并讀取父進(jìn)程送來的返回值

7、。讀者-寫者活動程序根據(jù)臨界資源的共享，互斥原則編制，具體見源程序。主控模塊：主控模塊實現(xiàn)系統(tǒng)初始化系統(tǒng)調(diào)用命令接收與解釋執(zhí)行，系統(tǒng)調(diào)用功能的實現(xiàn)（包括信號量機(jī)制），及讀者-寫者活動過程記錄與顯示。初始化系統(tǒng)環(huán)境建立通信管道啟動讀者-寫者進(jìn)程接收系統(tǒng)調(diào)用命令解釋執(zhí)行詳細(xì)設(shè)計為了實現(xiàn)讀者和寫者的讀寫過程,將每個讀者和每個寫者作為了一個單獨的線程,所以設(shè)置了兩個類,一個是讀者類Reader,一個是寫者類Writer.以讀者類為例:一個讀者的動作過程為由睡眠-等待-開始讀-結(jié)束讀-睡眠的一個循環(huán)過程,而一個寫者的動作過程也為此.讀者調(diào)用方法Sleep()進(jìn)行等待,調(diào)用Weakup()方法喚醒,最后在

8、調(diào)用endReading()方法結(jié)束讀入,釋放運行空間.寫者同讀者.首先要實現(xiàn)睡眠的方法Sleep(),讀者和寫者在睡眠過程都應(yīng)該是一樣的,只是他們睡眠的時間不同,所以只需寫出一個方法；在方法中,控制線程休眠隨機(jī)的時間,由于每個讀者或?qū)懻叨际且粋€線程,而每個讀者或?qū)懻咚麄児ぷ餍菝叩臅r間都不一定相同,他們請求工作的時間也不一定相同,所以取了隨機(jī)時間。其次設(shè)置了讀者的兩個方法,開始讀和結(jié)束讀,由于這只是個模擬讀寫問題,所以只需要知道結(jié)果就行,就不用顯示出他是怎么讀的。在開始讀中,當(dāng)有寫者在寫時,讀者需要等待wait(),在沒有人在工作時,如果有寫者和讀者同時請求,那么就讓寫者先進(jìn),這是寫者優(yōu)先。所

9、以這就歸納于一種情況, 當(dāng)讀者布爾變量為FALSE時,如果有需要工作的寫者,那么讀者就等待。當(dāng)讀者請求讀入后,計數(shù)有多少讀者需要工作的變量readerCount +1,如果這是第一個進(jìn)入工作的讀者就需要將顯示是否有讀者在工作的讀者布爾變量變?yōu)門RU E。具體流程如下圖3.1、3.2所示。圖3.1創(chuàng)建寫者進(jìn)程 圖3.2創(chuàng)建讀者進(jìn)程四、結(jié)果分析測試數(shù)據(jù)文件格式:測試數(shù)據(jù)文件包括n 行測試數(shù)據(jù)，分別描述創(chuàng)建的n 個線程是讀者還是寫者，以及讀寫操作的開始時間和持續(xù)時間。每行測試數(shù)據(jù)包括四個字段，各字段間用空格分隔。第一字段為一個正整數(shù)，表示線程序號。第二字段表示相應(yīng)線程角色，R 表示讀者是，W 表示寫

10、者。第三字段為一個正數(shù)，表示讀寫操作的開始時間。線程創(chuàng)建后，延時相應(yīng)時間（單位為秒）后發(fā)出對共享資源的讀寫申請。第四字段為一個正數(shù)，表示讀寫操作的持續(xù)時間。當(dāng)線程讀寫申請成功后，開始對共享資源的讀寫操作，該操作持續(xù)相應(yīng)時間后結(jié)束，并釋放共享資源。測試結(jié)果:在讀者寫者同時在隊列中等待申請資時，讀者優(yōu)先調(diào)用資源。而且如果一個讀者申請進(jìn)行讀操作時已有另一讀者正在進(jìn)行讀操作，則該讀者可直接開始讀操作，即讀讀允許。進(jìn)程1是W操作，在時間3時進(jìn)入隊列,運行時間是5,在它進(jìn)入時沒有進(jìn)程占用資源，它既占用資源；知道它釋放資源，等候的進(jìn)程有3，4，5，具體表現(xiàn)如下圖4.1、圖4.2所示；圖4.1進(jìn)程1進(jìn)入圖圖4

11、.2進(jìn)程1完成圖進(jìn)程2是R操作，在時間16時進(jìn)入隊列,運行時間是5,在它進(jìn)入時進(jìn)程4占用資源，它等待資源，當(dāng)4釋放時占用資源，具體表現(xiàn)如下圖4.3、圖4.4所示；圖4.3進(jìn)程2進(jìn)入圖圖4.4進(jìn)程2完成圖進(jìn)程3是R操作，在時間5時進(jìn)入隊列,運行時間是2,在它進(jìn)入時進(jìn)程1占用資源，它等待資源，當(dāng)進(jìn)程1釋放資源后，由于讀者優(yōu)先，進(jìn)程3，5同時調(diào)運資源，具體表現(xiàn)如下圖4.5、圖4.6所示；圖4.5進(jìn)程3進(jìn)入圖圖4.6進(jìn)程3完成圖進(jìn)程4是W操作，在時間6時進(jìn)入隊列,運行時間是5,在它進(jìn)入時進(jìn)程1占用資源，它等待資源，當(dāng)進(jìn)程1釋放資源后，由于讀者優(yōu)先，進(jìn)程3，5占用資源，它依然等待，直到進(jìn)程3，5都結(jié)束，

12、具體表現(xiàn)如下圖4.7、圖4.8所示；圖4.7進(jìn)程4進(jìn)入圖圖4.8進(jìn)程4完成圖進(jìn)程5是R操作，在時間4時進(jìn)入隊列,運行時間是3, 在它進(jìn)入時進(jìn)程1占用資源，它等待資源，當(dāng)進(jìn)程1釋放資源后，由于讀者優(yōu)先，進(jìn)程3，5同時調(diào)運資源，具體表現(xiàn)如下圖4.9、圖4.10所示；圖4.9進(jìn)程5進(jìn)入圖圖4.10進(jìn)程5完成圖進(jìn)程6是R操作，在時間17時進(jìn)入隊列,運行時間是7,在它進(jìn)入時進(jìn)程2占用資源，它等待進(jìn)程2釋放后最后調(diào)用資源，具體表現(xiàn)如下圖4.11所示。圖4.11進(jìn)程6進(jìn)入圖五、總結(jié)本次操作系統(tǒng)課程設(shè)計我們小組完成的是讀者寫者問題，通過學(xué)習(xí)信號量機(jī)制，我們對其的同步與互斥機(jī)制有了很深掌握并認(rèn)識到同步與互斥可以

13、保證在一個時間內(nèi)只有一個線程對某個資源有控制權(quán)。共享資源包括全局變量、公共數(shù)據(jù)成員或者句柄等。同步還可以使得有關(guān)聯(lián)交互作用的代碼按一定的順序執(zhí)行?？傮w來說我認(rèn)為操作系統(tǒng)這門學(xué)科在計算機(jī)科學(xué)當(dāng)是中非常重要的。他將我們學(xué)過的編程語言聯(lián)系起來，可以說是第一次利用C語言利用windows的API與系統(tǒng)進(jìn)行“溝通”?？偠灾?，這次操作系統(tǒng)的課程設(shè)計收獲頗豐，復(fù)習(xí)了許多東西，也從新學(xué)會了許多東西。我想這也許就是課程設(shè)計的最終目的吧。第二部分：參考文獻(xiàn)1.譚浩強.C+程序設(shè)計M.清華大學(xué)出版社，20042.湯子瀛. 計算機(jī)操作系統(tǒng)M. 西安電子科技大學(xué)出版社. 2006.93.劉振安、劉燕君著.C+程序設(shè)計

14、課程設(shè)計M.機(jī)械工業(yè)出版社，20044.美Abraham Silberschatz, Peter Baer Galvin, Greg Gagne 著. 鄭扣根 譯. 操作系統(tǒng)概念（第六版）M.高等教育出版社，20045.陳向群，向勇 等. Windows操作系統(tǒng)原理（第二版）M.機(jī)械工業(yè)出版社，2004第三部分：指導(dǎo)教師評語第四部分：成績評定第五部分：附錄（源代碼）#include #include #include #include #include #include #define MAX_PERSON 100#define READER 0 /讀者#define WRITER 1 /寫者

15、#define END -1#define R READER#define W WRITERtypedef struct _PersonHANDLE m_hThread;/定義處理線程的句柄int m_nType;/進(jìn)程類型（讀寫）int m_nStartTime;/開始時間int m_nWorkTime;/運行時間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, 1

16、6, 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;/讀者信號HANDLE g_hWriteSemaphore;/寫者信號bool finished = false; /所有的讀完成/bool wfinished = false; /所有的寫完成void CreatePersonList(int *pPersonList);bool CreateReader(int

17、StartTime,int WorkTime,int ID);bool CreateWriter(int StartTime,int WorkTime,int ID);DWORD WINAPI ReaderProc(LPVOID lpParam);DWORD WINAPI WriterProc(LPVOID lpParam);int main()g_hReadSemaphore = CreateSemaphore(NULL,1,100,NULL); /創(chuàng)建信號燈，當(dāng)前可用的資源數(shù)為1，最大為100g_hWriteSemaphore = CreateSemaphore(NULL,1,100,NU

18、LL); /創(chuàng)建信號燈，當(dāng)前可用的資源數(shù)為1，最大為100CreatePersonList(g_PersonLists); / Create All the reader and writersprintf(Created all the reader and writern.n);g_CurrentTime = 0;while(true)g_CurrentTime+;Sleep(300); / 300 msprintf(CurrentTime = %dn,g_CurrentTime);if(finished) return 0; / return 0;void CreatePersonLis

19、t(int *pPersonLists)int i=0;int *pList = pPersonLists;bool Ret;while(pList0 != END)switch(pList1)case R: Ret = CreateReader(pList2,pList3,pList0); /351,w452,523,654break;case W:Ret = CreateWriter(pList2,pList3,pList0);break;if(!Ret)printf(Create Person %d is wrongn,pList0);pList += 4; / move to next

20、 person listDWORD WINAPI ReaderProc(LPVOID lpParam)/讀過程Person *pPerson = (Person*)lpParam;/ wait for the start timewhile(g_CurrentTime != pPerson-m_nStartTime) printf(Reader %d is Requesting .n,pPerson-m_nID);printf(nn*n);/ wait for the write requestWaitForSingleObject(g_hReadSemaphore,INFINITE); if

21、(g_NumOfReading =0)WaitForSingleObject(g_hWriteSemaphore,INFINITE);g_NumOfReading+;ReleaseSemaphore(g_hReadSemaphore,1,NULL);pPerson-m_nStartTime = g_CurrentTime; printf(Reader %d is Reading the Shared Buffer. n,pPerson-m_n ID);printf(nn*n);while(g_CurrentTimem_nStartTime + pPerson-m_nWorkTime)print

22、f(Reader %d is Exit.n,pPerson-m_nID);printf(nn*n);WaitForSingleObject(g_hReadSemaphore,INFINITE);g_NumOfReading-;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

23、;DWORD WINAPI WriterProc(LPVOID lpParam)Person *pPerson = (Person*)lpParam;/ wait for the start timewhile(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 timepPerson-m_

24、nStartTime = g_CurrentTime;printf(Writer %d is Writting the Shared Buffer.n,pPerson-m_nID);while(g_CurrentTimem_nStartTime+ pPerson-m_nWorkTime)printf(Writer %d is Exit.n,pPerson-m_nID);printf(nn*n);/g_NumOfWriteRequest-;ReleaseSemaphore(g_hWriteSemaphore,1,NULL);if(pPerson-m_nID = 4) finished = true;/所有的讀寫完成ExitThread(0);return 0;bool CreateReader(int StartTime,int WorkTime,int ID)DWORD dwThreadID;if(g_N