操作系统读者与写者问题课程设计报告(共15页).doc

精选优质文档-倾情为你奉上课程设计任务书学 院信息学院专 业计算机科学与技术学 生 姓 名学 号题 目读者与写者问题（进程同步问题）内容及要求：内容：读者与写者问题（进程同步问题）实验目的：了解进程同步的概念，理解信号量机制的原理，掌握信号量解决同步问题的方法，进而学会进程的同步与互斥。设计要求：编程模拟教材中讨论读者与写者的问题，要求能显示结果。任务交付：1.程序源代码；2课程设计论文及电子文档。进度安排：16周确定题目，查找资料，上机编程；20周上机编程调试，验收答辩,提交课程序设计报告书。指导教师（签字）：年 月 日学院院长（签字）：年 月 日目 录专心-专注-专业一、课程设计目的及要求读者与写者问题（进程同步问题）用n 个线程来表示n个读者或写者。每个线程按相应测试数据文件的要求，进行读写操作。请用信号量机制分别实现读者优先和写者优先的读者-写者问题。读者-写者问题的读写操作限制：1）写-写互斥；2）读-写互斥；3）读-读允许；写者优先的附加限制：如果一个读者申请进行读操作时已有另一写者在等待访问共享资源，则该读者必须等到没有写者处于等待状态后才能开始读操作。二、相关知识Windows API：在本实验中涉及的API 有：1线程控制：CreateThread 完成线程创建，在调用进程的地址空间上创建一个线程，以执行指定的函数；它的返回值为所创建线程的句柄。HANDLE CreateThread(LPSECURITY_ATTRIBUTES lpThreadAttributes, / SDDWORD dwStackSize, / initial stack sizeLPTHREAD_START_ROUTINE lpStartAddress, / threadfunctionLPVOID lpParameter,/ thread argumentDWORD dwCreationFlags, / creation optionLPDWORD lpThreadId / thread identifier);2 ExitThread 用于结束当前线程。VOID ExitThread(DWORD dwExitCode / exit code for this thread);3 Sleep 可在指定的时间内挂起当前线程。VOID Sleep(DWORD dwMilliseconds / sleep time);4信号量控制：WaitForSingleObject 可在指定的时间内等待指定对象为可用状态；DWORD WaitForSingleObject(HANDLE hHandle, / handle to objectDWORD dwMilliseconds / time-out interval);hHandle为等待的对象，也就是实现同步或者互斥的对象。该函数一执行，相应的信号量就减去1，如果信号量小于等于0，那么他一直在循环。5 实现信号量互斥和同步CreateSemaphore用于创建信号量，根据参数的不同可以利用它实现互斥和同步。ReleaseSemaphore用于释放信号量，使用后相应的信号量加1HANDLE CreateSemaphore(LPSECURITY_ATTRIBUTES lpSemaphoreAttributes,/SDLONG,lInitialCount,/initial countLONG,lMaximumCount,/maximum countLPCTSTR lpName/object name);ReleaseSemaphore(HANDLE hSemaphore, /handle to semaphoreLONG lRelseaseCount,/cont increment amountLPLONG lpPreviousCount/previous count);三、题目分析将所有的读者和所有的写者分别放进两个等待队列中，当读允许时就让读者队列释放一个或多个读者，当写允许时，释放第一个写者操作。（1）构筑读者进程和写者进程间的临界区题目中说的一批数据被多个读者、写者共享使用，允许多个读者同时访问这些数据，但是如果有一个写者在访问数据时，就不允许其他读者或写者使用，所以，对这一批数据既要保证读者和写者互斥使用，也要保证写者与写者互斥使用。也就是说，在读者进程程序中，使用数据的程序段应该构成临界区；在写者进程程序中，使用数据的程序段应该构成临界区。（2）判定是否是第一个读者根据上面的分析，希望在读者进程中有一个办法能判定请求进入临界区的是否是第一个读者。如果是第一个读者，就对信号量wsem做P操作，以取得和写者的同步。为此，设置一个变量rfirst，初值为0.任何一个读者运行时，都现在rfirst上加1，然后判定他是否取值为1.如果是1，则做P(wrt)，否则不做。（3）判定是否是第一个写者原理同（2）判定是否为第一个读者。（4）写者优先问题的解决需要用到的如下的信号量和变量rsem: 初值为1的互斥信号量，在至少有一个写者准备访问数据时就不允许随后来的读者访问数据wserm: 初值为1的互斥信号量，之后有一个写者访问数据时其他写者和读者就被阻止对数据的访问ReadMutex: 创建写者的互斥信号量，初值为1WriteMutex: 创建读者的互斥信号量，初值为1z: 初值为1的互斥信号量，在至少有一个写着准备访问数据、且后面已经来一个读者时再来的读者将在这个信号量上等待rifrrst:读者计数变量，初值为0wfirst:写者计数变量，初值为0写者优先的PV原语：reader(i):P(z);P(rsem);P(ReadMutex);rfirst=rfirst+1;if(rfirst=1)P(wsem);V(ReadMutex);V(rsem);V(z);读取所需数据;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);改写所需数据;V(wsem);P(WriteMutex);wfirst=wfirst-1;if(wfirst=0)V(rsem);V(WriteMutex);读者 写者图3.1读者-写者的完整流程框图（5）读者优先与写者优先算法相反，有一个读者优先的算法，即只要有读者在读数据，写者被拒绝在临界区外面，如果有源源不断的写者来，但是只要写者不是第一个，那么写者将会永远被拒绝在临界区外面。wrt:：初值为1的互斥信号量，只要有一个写者访问数据， 则其他写者和读者就要被阻止对数据的访问。mutex：保证读者互斥操作first的信号量，初值为1first ：读者计数变量，初值为0读者优先的PV原语：write():P(wrt);对数据进行修改；V(wrt);read():P(mutex);first = first+1;if(first = 1)P(wrt);V(mutex);读取所需数据P(mutex);first = first+1;if(first = 0)V(wrt);V(mutex);四、概要设计（1）控制流程用CheckPersonList(PersonLists)函数检查PersonLists中是否有为创建的进程（读写者）。如果有则创建相应的读写线程（2）创建读写者用bool CreateReader(int StartTime,int WorkTime)函数创建读者写者相应的线程，其中由windows提供的函数为CreateThread(NULL,0,ReaderProc,(LPVOID)pPerson,0,&dwThreadID);返回的是DWORD型变量。在CreateReader(int StartTime,int WorkTime)中还会初始化相应的读写者的基本信息，例如何时申请数据何时读数据何时关闭线程等等。（3）读写者进程参见图2.1读者-写者的完整流程图。（4）同步与互斥WaitForSingleObject(信号量名字,infinite)和ReleaseSemaphore(信号量名字,1,null)用于实现同步于互斥，执行WaitForSingleObject(信号量名字,infinite)信号量相应的信号量减1，执行ReleaseSemaphore(信号量名字,1,null)恢复1。五、代码及流程/写者优先算法#include <windows.h>#include <ctype.h>#include <stdio.h>#include <string.h>#include <stdlib.h>#include <malloc.h> #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;long 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的互斥信号量，在至少有一个写者准备访问数据时就不允许随后来的读者访问数据*/HANDLE wsem;/*初值为1的互斥信号量，之后有一个写者访问数据时其他写者和读者就被阻止对数据的访问*/HANDLE z;/*初值为1的互斥信号量，在至少有一个写着准备访问数据、且后面已经来一个读者时再来的读者将在这个信号量上等待*/HANDLE ReadMutex;/*创建写者的互斥信号量，初值为1*/HANDLE WriteMutex;/*创建读者的互斥信号量, 初值为1*/ void CheckPersonList(int *pPersonList);/*查看人数，为创建读写者线程*/bool CreateReader(int StartTime,int WorkTime);bool CreateWriter(int StartTime,int WorkTime);DWORD WINAPI ReaderProc(LPVOID lpParam);/*读者进程程序*/DWORD WINAPI WriterProc(LPVOID lpParam);/*写着进程程序*/#include "Writerprior.h"int 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= CreateSemaphore(NULL,1,1,NULL);CurrentTime = 0;while(true)/模拟20个时钟周期CheckPersonList(PersonLists);CurrentTime+;Sleep(600);printf("当前时间 = %d:n",CurrentTime);if(CurrentTime=20)break;system("pause");CloseHandle(rsem);CloseHandle(wsem);CloseHandle(z);CloseHandle(ReadMutex);CloseHandle(WriteMutex);return 0; void CheckPersonList(int *pPersonLists)int i=0;int *pList = pPersonLists;bool P;while(pList0 != END)if(pList2 = CurrentTime)switch(pList1)case R:P = CreateReader(pList2,pList3);/创建一个读者break;case W:P = CreateWriter(pList2,pList3);/创建一个写者break;if(!P)printf("Create Person %d is wrongn",pList0);pList += 4; / 数组的指针指向第二个人 DWORD WINAPI ReaderProc(LPVOID lpParam)Person *pPerson = (Person*)lpParam;pPerson->ID = +NumOfReaders;WaitForSingleObject(z,INFINITE);/P(z)，其余读者在此排队printf("tt读者 %d 申请读数据.n",pPerson->ID);WaitForSingleObject(rsem,INFINITE);/P(rsem)，一个读者与一个写着再次竞争数据的使用权/printf("Reader %d is requesting the Shared Buffer.n",pPerson->ID); WaitForSingleObject(ReadMutex,INFINITE);/P(ReadMutex)，读者请求进入rfirst临界区rfirst+; if(rfirst = 1)/是否是第一个读者 WaitForSingleObject(wsem,INFINITE);/读者在此处与写者进行同步 ReleaseSemaphore(ReadMutex,1,NULL);/退出rfirst临界区,V(ReadMutex)ReleaseSemaphore(rsem,1,NULL);ReleaseSemaphore(z,1,NULL);/V(z)/ 读取所需数据，将现在时间赋值给读者，用以计算结束时间printf("tt读者 %d 申请成功n",pPerson->ID);pPerson->StartTime = CurrentTime; printf("tt读者 %d 正在读数据.n",pPerson->ID);while(CurrentTime < pPerson->StartTime + pPerson->WorkTime)/ 模拟读数据printf("tt读者 %d 读完数据退出n",pPerson->ID);WaitForSingleObject(ReadMutex,INFINITE); rfirst-; if(rfirst = 0) /是最后一个读者？ ReleaseSemaphore(wsem,1,NULL);/没有读者了，写者放行 ReleaseSemaphore(ReadMutex,1,NULL);/退出读者临界区 ExitThread(0);/关闭读者线程return 0; DWORD WINAPI WriterProc(LPVOID lpParam)/写者进程程序Person *pPerson = (Person*)lpParam;pPerson->ID = +NumOfWriters; printf("tt写者 %d 正在申请写数据.n",pPerson->ID); WaitForSingleObject(WriteMutex,INFINITE);/请求进入写者临界区wfirst=wfirst+;if(wfirst=1)WaitForSingleObject(rsem,INFINITE);/一个写者在此与读者取得同步ReleaseSemaphore(WriteMutex,1,NULL);/退出rfirst临界区WaitForSingleObject(wsem,INFINITE);/其他写者在此等候进入写临界区 / 读取所需数据，将现在时间赋值给读者，用以计算结束时间pPerson->StartTime = CurrentTime; printf("tt写者 %d 正在写数据.n",pPerson->ID);while(CurrentTime < pPerson->StartTime + pPerson->WorkTime)/模拟写数据printf("tt写者 %d 写完数据退出n",pPerson->ID);ReleaseSemaphore(wsem,1,NULL);/退出进入写临界区WaitForSingleObject(WriteMutex,INFINITE);/请求进入wfirst临界区wfirst=wfirst-;if(wfirst=0)/是最后一个写者？ReleaseSemaphore(rsem,1,NULL);/没有写者了，向读者放行ReleaseSemaphore(WriteMutex,1,NULL);/退出wfirst临界区ExitThread(0);/关闭写者线程return 0; bool CreateReader(int StartTime,int WorkTime)DWORD dwThreadID;Person *pPerson = &PersonsNumPerson;pPerson->StartTime= StartTime;pPerson->WorkTime= WorkTime;pPerson->Type= READER; NumPerson+; / 创建一个读者的新线程pPerson->Thread = CreateThread(NULL,0,ReaderProc,(LPVOID)pPerson,0,&dwThreadID);if(pPerson->Thread = 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+; / 创建一个写者的新线程pPerson->Thread = CreateThread(NULL,0,WriterProc,(LPVOID)pPerson,0,&dwThreadID);if(pPerson->Thread = NULL) return false;return true;六、运行结果图6.1 运行结果结果分析：顺序开始时间（s）执行时间（s）Reader1132353152Writer125255表6.1如上表，第一个读者1到达时间是第1s，执行时间是3s，即在第4s的时候结束，而在第2s的时候就写者1到达。这时候，写者1被阻挡在z的临界区外面。在第3s的时候，读者2到达，由于写者1在前面，所以同样被阻挡在z外面，在第4s读者1运行结束，写者1开始写数据，这是读者2被阻挡在rsem的临界区外面，在第5s的时候到达第二个写者，由于写写互斥，所以被阻挡在写者wsem的临界区外面。第14s写者2退出，读者2才开始读数据。读者3在第15s的时候到达，由于读读不存在互斥，所以两个读线程同时进行，知道第19s时读者2结束，整个模拟结束。（过程请参考图6.2）图6.2 程序过程图七、设计心得通过这次操作系统的课程设计，我研究了读者与写者问题，进一步深入了解了同步与互斥机制。比如什么是同步，什么是互斥，什么是信号量等等。课程设计和平时的实验课比较起来有很大的差距，实验课只是将这一章的一部分内容练习操作一遍，而课程设计需要的是他们综合起来的东西，这要更难一些。总体来说我认为操作系统这门学科在计算机科学当是中非常重要的。他将我们学过的编程语言联系起来，可以说是第一次利用C语言利用windows的API与系统进行“沟通”。总而言之，这次操作系统的课程设计收获颇丰，复习了许多东西，也从新学会了许多东西。我想这也许就是课程设计的最终目的吧。八、参考文献1刘振安、刘燕君著.C+程序设计课程设计.北京: 机械工业出版社，20042美Abraham Silberschatz, Peter Baer Galvin, Greg Gagne 著. 郑扣根 译. 操作系统概念（第六版）. 北京： 高等教育出版社，20043陈向群，向勇 等. Windows操作系统原理（第二版）. 北京：机械工业出版社，2004.