操作系統(tǒng)讀者與寫者問題課程設(shè)計報告[1]

1、課程設(shè)計任務(wù)書學(xué) 院信息學(xué)院專 業(yè)計算機科學(xué)與技術(shù)學(xué) 生 姓 名學(xué) 號題 目讀者與寫者問題（進程同步問題）內(nèi)容及要求：內(nèi)容：讀者與寫者問題（進程同步問題）實驗?zāi)康模毫私膺M程同步的概念，理解信號量機制的原理，掌握信號量解決同步問題的方法，進而學(xué)會進程的同步與互斥。設(shè)計要求：編程模擬教材中討論讀者與寫者的問題，要求能顯示結(jié)果。任務(wù)交付：1.程序源代碼；2課程設(shè)計論文及電子文檔。進度安排：16周確定題目，查找資料，上機編程；20周上機編程調(diào)試，驗收答辯,提交課程序設(shè)計報告書。指導(dǎo)教師（簽字）：年 月 日學(xué)院院長（簽字）：年 月 日目 錄一、課程設(shè)計目的及要求1二、相關(guān)知識1三、題目分析2四、概要設(shè)計

2、4五、代碼及流程5六、運行結(jié)果11七、設(shè)計心得12八、參考文獻12一、課程設(shè)計目的及要求讀者與寫者問題（進程同步問題）用n 個線程來表示n個讀者或?qū)懻摺Ｃ總€線程按相應(yīng)測試數(shù)據(jù)文件的要求，進行讀寫操作。請用信號量機制分別實現(xiàn)讀者優(yōu)先和寫者優(yōu)先的讀者-寫者問題。讀者-寫者問題的讀寫操作限制：1）寫-寫互斥；2）讀-寫互斥；3）讀-讀允許；寫者優(yōu)先的附加限制：如果一個讀者申請進行讀操作時已有另一寫者在等待訪問共享資源，則該讀者必須等到?jīng)]有寫者處于等待狀態(tài)后才能開始讀操作。二、相關(guān)知識Windows API：在本實驗中涉及的API 有：1線程控制：CreateThread 完成線程創(chuàng)建，在調(diào)用進程的地

3、址空間上創(chuàng)建一個線程，以執(zhí)行指定的函數(shù)；它的返回值為所創(chuàng)建線程的句柄。HANDLE CreateThread(LPSECURITY_ATTRIBUTES lpThreadAttributes, / SDDWORD dwStackSize, / initial stack sizeLPTHREAD_START_ROUTINE lpStartAddress, / threadfunctionLPVOID lpParameter,/ thread argumentDWORD dwCreationFlags, / creation optionLPDWORD lpThreadId / thread i

4、dentifier);2 ExitThread 用于結(jié)束當(dāng)前線程。VOID ExitThread(DWORD dwExitCode / exit code for this thread);3 Sleep 可在指定的時間內(nèi)掛起當(dāng)前線程。VOID Sleep(DWORD dwMilliseconds / sleep time);4信號量控制：WaitForSingleObject 可在指定的時間內(nèi)等待指定對象為可用狀態(tài)；DWORD WaitForSingleObject(HANDLE hHandle, / handle to objectDWORD dwMilliseconds / time-o

5、ut interval);hHandle為等待的對象，也就是實現(xiàn)同步或者互斥的對象。該函數(shù)一執(zhí)行，相應(yīng)的信號量就減去1，如果信號量小于等于0，那么他一直在循環(huán)。5 實現(xiàn)信號量互斥和同步CreateSemaphore用于創(chuàng)建信號量，根據(jù)參數(shù)的不同可以利用它實現(xiàn)互斥和同步。ReleaseSemaphore用于釋放信號量，使用后相應(yīng)的信號量加1HANDLE CreateSemaphore(LPSECURITY_ATTRIBUTES lpSemaphoreAttributes,/SDLONG,lInitialCount,/initial countLONG,lMaximumCount,/maximum

6、 countLPCTSTR lpName/object name);ReleaseSemaphore(HANDLE hSemaphore, /handle to semaphoreLONG lRelseaseCount,/cont increment amountLPLONG lpPreviousCount/previous count);三、題目分析將所有的讀者和所有的寫者分別放進兩個等待隊列中，當(dāng)讀允許時就讓讀者隊列釋放一個或多個讀者，當(dāng)寫允許時，釋放第一個寫者操作。（1）構(gòu)筑讀者進程和寫者進程間的臨界區(qū)題目中說的一批數(shù)據(jù)被多個讀者、寫者共享使用，允許多個讀者同時訪問這些數(shù)據(jù)，但是如果有一

7、個寫者在訪問數(shù)據(jù)時，就不允許其他讀者或?qū)懻呤褂茫?，對這一批數(shù)據(jù)既要保證讀者和寫者互斥使用，也要保證寫者與寫者互斥使用。也就是說，在讀者進程程序中，使用數(shù)據(jù)的程序段應(yīng)該構(gòu)成臨界區(qū)；在寫者進程程序中，使用數(shù)據(jù)的程序段應(yīng)該構(gòu)成臨界區(qū)。（2）判定是否是第一個讀者根據(jù)上面的分析，希望在讀者進程中有一個辦法能判定請求進入臨界區(qū)的是否是第一個讀者。如果是第一個讀者，就對信號量wsem做P操作，以取得和寫者的同步。為此，設(shè)置一個變量rfirst，初值為0.任何一個讀者運行時，都現(xiàn)在rfirst上加1，然后判定他是否取值為1.如果是1，則做P(wrt)，否則不做。（3）判定是否是第一個寫者原理同（2）判定是

8、否為第一個讀者。（4）寫者優(yōu)先問題的解決需要用到的如下的信號量和變量rsem: 初值為1的互斥信號量，在至少有一個寫者準(zhǔn)備訪問數(shù)據(jù)時就不允許隨后來的讀者訪問數(shù)據(jù)wserm: 初值為1的互斥信號量，之后有一個寫者訪問數(shù)據(jù)時其他寫者和讀者就被阻止對數(shù)據(jù)的訪問ReadMutex: 創(chuàng)建寫者的互斥信號量，初值為1WriteMutex: 創(chuàng)建讀者的互斥信號量，初值為1z: 初值為1的互斥信號量，在至少有一個寫著準(zhǔn)備訪問數(shù)據(jù)、且后面已經(jīng)來一個讀者時再來的讀者將在這個信號量上等待rifrrst:讀者計數(shù)變量，初值為0wfirst:寫者計數(shù)變量，初值為0寫者優(yōu)先的PV原語：reader(i):P(z);P(r

9、sem);P(ReadMutex);rfirst=rfirst+1;if(rfirst=1)P(wsem);V(ReadMutex);V(rsem);V(z);讀取所需數(shù)據(jù);P(ReadMutex);rfirst=rfirst-1;if(rfirst=0)V(wsem);V(ReadMutex);Writer():P(WriteMutex);wfirst=wfirst+1;if(wfirst=1)P(rsem);V(WritedMutex);P(wsem);改寫所需數(shù)據(jù);V(wsem);P(WriteMutex);wfirst=wfirst-1;if(wfirst=0)V(rsem);V(Wr

10、iteMutex);讀者 寫者圖3.1讀者-寫者的完整流程框圖（5）讀者優(yōu)先與寫者優(yōu)先算法相反，有一個讀者優(yōu)先的算法，即只要有讀者在讀數(shù)據(jù)，寫者被拒絕在臨界區(qū)外面，如果有源源不斷的寫者來，但是只要寫者不是第一個，那么寫者將會永遠被拒絕在臨界區(qū)外面。wrt:：初值為1的互斥信號量，只要有一個寫者訪問數(shù)據(jù)， 則其他寫者和讀者就要被阻止對數(shù)據(jù)的訪問。mutex：保證讀者互斥操作first的信號量，初值為1first ：讀者計數(shù)變量，初值為0讀者優(yōu)先的PV原語：write():P(wrt);對數(shù)據(jù)進行修改；V(wrt);read():P(mutex);first = first+1;if(first

11、= 1)P(wrt);V(mutex);讀取所需數(shù)據(jù)P(mutex);first = first+1;if(first = 0)V(wrt);V(mutex);四、概要設(shè)計（1）控制流程用CheckPersonList(PersonLists)函數(shù)檢查PersonLists中是否有為創(chuàng)建的進程（讀寫者）。如果有則創(chuàng)建相應(yīng)的讀寫線程（2）創(chuàng)建讀寫者用bool CreateReader(int StartTime,int WorkTime)函數(shù)創(chuàng)建讀者寫者相應(yīng)的線程，其中由windows提供的函數(shù)為CreateThread(NULL,0,ReaderProc,(LPVOID)pPerson,0,&

12、dwThreadID);返回的是DWORD型變量。在CreateReader(int StartTime,int WorkTime)中還會初始化相應(yīng)的讀寫者的基本信息，例如何時申請數(shù)據(jù)何時讀數(shù)據(jù)何時關(guān)閉線程等等。（3）讀寫者進程參見圖2.1讀者-寫者的完整流程圖。（4）同步與互斥WaitForSingleObject(信號量名字,infinite)和ReleaseSemaphore(信號量名字,1,null)用于實現(xiàn)同步于互斥，執(zhí)行WaitForSingleObject(信號量名字,infinite)信號量相應(yīng)的信號量減1，執(zhí)行ReleaseSemaphore(信號量名字,1,null)恢復(fù)1

13、。五、代碼及流程/寫者優(yōu)先算法#include #include #include #include #include #include #define MAX_PERSON 10#define READER 0#define WRITER 1#define END -1#define R READER#define W WRITER typedef struct _PersonHANDLE Thread;int Type;int StartTime;int WorkTime;int ID;Person; Person PersonsMAX_PERSON;int NumPerson = 0;l

14、ong CurrentTime= 0; int PersonLists = 1,R,1,3,2,W,2,5,/*讀寫互斥*/3,W,5,5,/*寫寫互斥*/4,R,3,5,/*寫讀互斥*/5,R,15,2,/*讀讀不互斥*/END,; int rfirst = 0;int wfirst = 0;int NumOfReaders = 0;int NumOfWriters = 0;HANDLE rsem;/*初值為1的互斥信號量，在至少有一個寫者準(zhǔn)備訪問數(shù)據(jù)時就不允許隨后來的讀者訪問數(shù)據(jù)*/HANDLE wsem;/*初值為1的互斥信號量，之后有一個寫者訪問數(shù)據(jù)時其他寫者和讀者就被阻止對數(shù)據(jù)的訪問

15、*/HANDLE z;/*初值為1的互斥信號量，在至少有一個寫著準(zhǔn)備訪問數(shù)據(jù)、且后面已經(jīng)來一個讀者時再來的讀者將在這個信號量上等待*/HANDLE ReadMutex;/*創(chuàng)建寫者的互斥信號量，初值為1*/HANDLE WriteMutex;/*創(chuàng)建讀者的互斥信號量, 初值為1*/ void CheckPersonList(int *pPersonList);/*查看人數(shù)，為創(chuàng)建讀寫者線程*/bool CreateReader(int StartTime,int WorkTime);bool CreateWriter(int StartTime,int WorkTime);DWORD WINA

16、PI ReaderProc(LPVOID lpParam);/*讀者進程程序*/DWORD WINAPI WriterProc(LPVOID lpParam);/*寫著進程程序*/#include Writerprior.hint main()rsem= CreateSemaphore(NULL,1,1,NULL);wsem= CreateSemaphore(NULL,1,1,NULL);z= CreateSemaphore(NULL,1,1,NULL); ReadMutex= CreateSemaphore(NULL,1,1,NULL); WriteMutex= CreateSemaphor

17、e(NULL,1,1,NULL);CurrentTime = 0;while(true)/模擬20個時鐘周期CheckPersonList(PersonLists);CurrentTime+;Sleep(600);printf(當(dāng)前時間 = %d:n,CurrentTime);if(CurrentTime=20)break;system(pause);CloseHandle(rsem);CloseHandle(wsem);CloseHandle(z);CloseHandle(ReadMutex);CloseHandle(WriteMutex);return 0; void CheckPerso

18、nList(int *pPersonLists)int i=0;int *pList = pPersonLists;bool P;while(pList0 != END)if(pList2 = CurrentTime)switch(pList1)case R:P = CreateReader(pList2,pList3);/創(chuàng)建一個讀者break;case W:P = CreateWriter(pList2,pList3);/創(chuàng)建一個寫者break;if(!P)printf(Create Person %d is wrongn,pList0);pList += 4; / 數(shù)組的指針指向第二個人

19、 DWORD WINAPI ReaderProc(LPVOID lpParam)Person *pPerson = (Person*)lpParam;pPerson-ID = +NumOfReaders;WaitForSingleObject(z,INFINITE);/P(z)，其余讀者在此排隊printf(tt讀者 %d 申請讀數(shù)據(jù).n,pPerson-ID);WaitForSingleObject(rsem,INFINITE);/P(rsem)，一個讀者與一個寫著再次競爭數(shù)據(jù)的使用權(quán)/printf(Reader %d is requesting the Shared Buffer.n,pP

20、erson-ID); WaitForSingleObject(ReadMutex,INFINITE);/P(ReadMutex)，讀者請求進入rfirst臨界區(qū)rfirst+; if(rfirst = 1)/是否是第一個讀者 WaitForSingleObject(wsem,INFINITE);/讀者在此處與寫者進行同步 ReleaseSemaphore(ReadMutex,1,NULL);/退出rfirst臨界區(qū),V(ReadMutex)ReleaseSemaphore(rsem,1,NULL);ReleaseSemaphore(z,1,NULL);/V(z)/ 讀取所需數(shù)據(jù)，將現(xiàn)在時間賦值

21、給讀者，用以計算結(jié)束時間printf(tt讀者 %d 申請成功n,pPerson-ID);pPerson-StartTime = CurrentTime; printf(tt讀者 %d 正在讀數(shù)據(jù).n,pPerson-ID);while(CurrentTime StartTime + pPerson-WorkTime)/ 模擬讀數(shù)據(jù)printf(tt讀者 %d 讀完數(shù)據(jù)退出n,pPerson-ID);WaitForSingleObject(ReadMutex,INFINITE); rfirst-; if(rfirst = 0) /是最后一個讀者？ ReleaseSemaphore(wsem,1

22、,NULL);/沒有讀者了，寫者放行 ReleaseSemaphore(ReadMutex,1,NULL);/退出讀者臨界區(qū) ExitThread(0);/關(guān)閉讀者線程return 0; DWORD WINAPI WriterProc(LPVOID lpParam)/寫者進程程序Person *pPerson = (Person*)lpParam;pPerson-ID = +NumOfWriters; printf(tt寫者 %d 正在申請寫數(shù)據(jù).n,pPerson-ID); WaitForSingleObject(WriteMutex,INFINITE);/請求進入寫者臨界區(qū)wfirst=w

23、first+;if(wfirst=1)WaitForSingleObject(rsem,INFINITE);/一個寫者在此與讀者取得同步ReleaseSemaphore(WriteMutex,1,NULL);/退出rfirst臨界區(qū)WaitForSingleObject(wsem,INFINITE);/其他寫者在此等候進入寫臨界區(qū) / 讀取所需數(shù)據(jù)，將現(xiàn)在時間賦值給讀者，用以計算結(jié)束時間pPerson-StartTime = CurrentTime; printf(tt寫者 %d 正在寫數(shù)據(jù).n,pPerson-ID);while(CurrentTime StartTime + pPerson

24、-WorkTime)/模擬寫數(shù)據(jù)printf(tt寫者 %d 寫完數(shù)據(jù)退出n,pPerson-ID);ReleaseSemaphore(wsem,1,NULL);/退出進入寫臨界區(qū)WaitForSingleObject(WriteMutex,INFINITE);/請求進入wfirst臨界區(qū)wfirst=wfirst-;if(wfirst=0)/是最后一個寫者？ReleaseSemaphore(rsem,1,NULL);/沒有寫者了，向讀者放行ReleaseSemaphore(WriteMutex,1,NULL);/退出wfirst臨界區(qū)ExitThread(0);/關(guān)閉寫者線程return 0

25、; bool CreateReader(int StartTime,int WorkTime)DWORD dwThreadID;Person *pPerson = &PersonsNumPerson;pPerson-StartTime= StartTime;pPerson-WorkTime= WorkTime;pPerson-Type= READER; NumPerson+; / 創(chuàng)建一個讀者的新線程pPerson-Thread = CreateThread(NULL,0,ReaderProc,(LPVOID)pPerson,0,&dwThreadID);if(pPerson-Thread =

26、 NULL) return false; return true; bool CreateWriter(int StartTime,int WorkTime)DWORD dwThreadID;if(NumPerson = MAX_PERSON)return false;Person *pPerson = &PersonsNumPerson;pPerson-StartTime = StartTime;pPerson-WorkTime = WorkTime;pPerson-Type = WRITER; NumPerson+; / 創(chuàng)建一個寫者的新線程pPerson-Thread = CreateThread(NULL,0,WriterProc,(LPVOID)pPerson,0,&dwThread