1、学号：0120710680427课 程 设 计学院(Reader-Writer Problem) 问题计算机科学与技术专业软件工程班级软件 0704姓名万力题目实现读者写者 指导教师刘军2010 年6月27日23目录1. 概述41.1 设计题目41.2 设计目的41.3 设计时间41.4 开发环境41.5 设计要求42. 数据结构与模块说明52.1 设计概述52.2 设计流程图63. 具体编程实现74. 运行结果与测试85. 课程设计总结与体会116. 参考文献11课程设计任务书学生姓名：万力专业班级：软 件 0704 指导教师：刘军工作单位： 计算机科学与技术学院题目: 实现读者写者(Rea
2、der-Writer Problem) 问题初始条件：1. 操作系统：Linux 2. 程序设计语言：C 语言3. 设有 20 个连续的存储单元，写入/读出的数据项按增序设定为120 这 20 个字符。要求完成的主要任务: （包括课程设计工作量及其技术要求，以及说明书撰写等具体要求） 1技术要求：1） 为每个读者写者产生一个线程，设计正确的同步算法2） 每个读者/写者对该存储区进行操作后，即时显示该存储区的全部内容、当前指针位置和读者/写者线程的自定义标识符。3） 读者应有 3 个以上，写者应有有两个以上。4） 多个读者/写者之间须共享对存储区进行操作的函数代码。2. 设计说明书内容要求：1）
3、 设计题目与要求2） 总的设计思想及系统平台、语言、工具等。3） 数据结构与模块说明（功能与流程图）4） 运行结果与运行情况（提示:(1)连续存储区可用数组实现。(2) 编译命令可用：cc -lpthread-o目标文件名源文件名(3) 多线程编程方法参见附件。）3. 调试报告：1) 调试记录2) 自我评析和总结上机时间安排：18 周一 五 08：0 12：00指导教师签名： 年 月 日系主任（或责任教师）签名： 年 月 日实现读者写者 (Reader-Writer Problem)问题1 概述1.1 设计题目实现读者写者(Reader-Writer Problem) 问题1.2 设计目的通过
4、对操作系统内核实现代码的阅读、修改、设计，理解和掌握复杂的操作系统的工作原理。通过研究Linux 的线程机制和信号量实现读者写者(Reader-Writer)问题并发控制。1.3 设计时间消化资料、系统调查1 天系统分析1 天总体设计、实施计划2 天撰写课程设计报告书1 天第 18 周周一至周五1.4 开发环境本次课程设计在操作系统：Linux 下，使用的编程语言为 C 语言。1.5 设计要求1） 为每个读者写者产生一个线程，设计正确的同步算法2） 每个读者/写者对该存储区进行操作后，即时显示该存储区的全部内容、当前指针位置和读者/写者线程的自定义标识符。3） 读者应有 3 个以上，写者应有有
5、两个以上。4） 多个读者/写者之间须共享对存储区进行操作的函数代码。2 数据结构与模块说明2.1 设计概述所谓读者写着问题，是指保证一个 writer 进程必须与其他进程互斥地访问共享对象的同步问题。读者写者问题可以这样的描述，有一群写者和一群读者，写者在写同一本书，读者也在读这本书，多个读者可以同时读这本书，但是，只能有一个写者在写书，并且，读者必写者优先，也就是说，读者和写者同时提出请求时，读者优先。当读者提出请求时需要有一个互斥操作，另外，需要有一个信号量S 来当前是否可操作。信号量机制是支持多道程序的并发操作系统设计中解决资源共享时进程间的同步与互斥的重要机制，而读者写者则是这一机制的
6、一个经典范例。与记录型信号量解决读者写者问题不同，信号量机制它增加了一个限制，即最多允许 RN 个读者同时读。为此，又引入了一个信号量 L,并赋予初值为 RN，通过执行 wait（L,1,1）操作，来控制读者的数目，每当有一个读者进入时，就要执行 wait（L,1,1） 操作，使L 的值减 1。当有 RN 个读者进入读后，L 便减为 0，第 RN+1 个读者要进入读时，必然会因 wait（L,1,1）操作失败而堵塞。对利用信号量来解决读者写者问题的描述如下：Var RN integer;L,mx:semaphore: =RN,1； Begin Parbegin Reader :begin Re
7、peat Swait（L,1,1）; Swait（mx,1,0）; . Perform reader operation; Ssignal(L,1); Until false; End Writer ：begin Repeat Swait(mx ,1,1,l,RN,0); Perform writer operation; Ssignal(mx,1); Until false; End Parend End 其中，Swait（mx,1,0）语句起着开关作用，只要无 Writer 进程进入些，mx=1，reader 进程就都可以进入读。但是要一旦有 Writer 进程进入写时，其 MX=0，则任
8、何 reader 进程就都无法进入读。Swait(mx ,1,1,l,RN,0)语句表示仅当既无 Write 进程在写（mx=1），又无 reader 进程在读（L=RN）时，writer 进程才能进入临界区写。2.2 设计流程图主程序()读者()写者()主控()3 具体编程实现读者-写者的读写限制（包括读者优先和写者优先）1） 写-写互斥，即不能有两个写者同时进行写操作2） 读-写互斥，即不能同时有一个读者在读，同时却有一个写者在写3） 读读允许，即可以有 2 个以上的读者同时读将所有的读者和所有的写者分别放进两个等待队列中，当读允许时就让读者队列释放一个或多个读者，当写允许时，释放第一个写
9、者操作。读者写者问题的定义如下：有一个许多进程共享的数据区，这个数据区可以是一个文件或者主存的一块空间；有一些只读取这个数据区的进程（Reader）和一些只往数据区写数据的进程(Writer)，此外还需要满足以下条件：1) 任意多个读进程可以同时读这个文件；2) 一次只有一个写进程可以往文件中写；3）如果一个写进程正在进行操作，禁止任何读进程度文件。我们需要分两种情况实现该问题：读优先：要求指一个读者试图进行读操作时，如果这时正有其他读者在进行操作，他可直接开始读操作，而不需要等待。写优先：一个读者试图进行读操作时，如果有其他写者在等待进行写操作或正在进行写操作，他要等待该写者完成写操作后才开
10、始读操作。程序由三部分组成：1. 读者模块：包括系统调用接口，读者活动描述主程序。系统接口主要功能是通过管道向父进程发送系统调用命令，并读取父进程送来的返回值。2. 写者模块：包括系统调用接口，写者活动描述主程序。 读者-写者活动程序根据临界资源的共享，互斥原则编制。3. 主控模块：主控模块实现系统初始化系统调用命令接收与解释执行，系统调用功能的实现（包括信号量机制），及读者-写者活动过程记录与显示。4 运行结果与测试测试数据文件包括n 行测试数据，分别描述创建的n 个线程是读者还是写者，以及读写操作的开始时间和持续时间。每行测试数据包括四个字段，各字段间用空格分隔。第一字段为一个正整数，表示
11、线程序号。第二字段表示相应线程角色，R 表示读者是， W 表示写者。第三字段为一个正数，表示读写操作的开始时间。线程创建后，延时相应时间（单位为秒）后发出对共享资源的读写申请。第四字段为一个正数，表示读写操作的持续时间。当线程读写申请成功后，开始对共享资源的读写操作，该操作持续相应时间后结束，并释放共享资源。下面是一个测试数据文件的例子：1, W ，4, 5,2, W, 16, 4,3, R, 5, 2,4, W, 6, 5,5, R, 4, 3,在读者写者同时在队列中等待申请资时，读者优先调用资源。而且如果一个读者申请进行读操作时已有另一读者正在进行读操作，则该读者可直接开始读操作，即读读允
12、许。进程 1 是W 操作，在时间 4 时进入队列,运行时间是 5,在它进入时没有进程占用资源， 它既占用资源；直到它释放资源，等候的进程有 3，4，5；其他进程如截图所示。5 课程设计总结与心得体会这一次课程设计，我完成了题目“读者-写者问题的实现”，更加系统地理解和掌握C 语言的基本概念、语言特点和编程技巧，在应用C 语言在程序设计方面得到系统锻炼，为将来用C 进行软件开发打下良好基础。对程序设计思想也有了比较清晰的印象， 为今后的程序设计奠定了一定的心理和技术上的准备。总的感觉，学到了很多知识，特别对于 linux 有了全面的接触和了解，也开始对linux 产生了兴趣，它所开放的源码的确为
13、学计算机的同志们提供了很好的平台。读者-写者问题经典的线程同步问题的一个模型。经过读者写者问题的编写，我对同步机构应用有了深入的了解。懂得了运用信号量实现进程间的互斥。实现了不让共享资源同时修改。用信号量上的原语操作使临界段问题的解决比较简单明了了。读者写者问题的编写，花的时间很多，也学到很多东西。了解支持多道程序的并发操作系统设计中解决资源共享时进程间的同步与互斥的信号量机制。几天的试验，虽然难度有点大，但只要自己花时间去学习，还是会攻克困难的。 课程设计提高了我对所学知识的综合应用能力，全面检查并掌握所学的内容，培养独立思考、刻苦钻研的精神，在分析问题、解决问题的过程中，更是获得一种成功的
14、喜悦，进而增加学习和应用的兴趣。同时也要督促自己在学习的过程中不断的完善自我， 加强自己的动手操作能力，培养我的独立思考的那种思维方式。总之，每一次课程设计不仅是我们学习的好机会，而且是我们锻炼实际动手能力的平台，虽然有难度的东西总会让人很抵触，比如在课设过程中有很多郁闷的时候，一个小小的错误一不小心就花去了自己一上午的时间，所以在这个过程中能够磨练人的意志与耐心，最后感谢老师的指导与监督。6 参考文1 Operating System Concepts(Sixth Edition) （操作系统概念）影印版， 主 编 ：Abraham Silberschatz 出版社：高等教育出版社2 操作系
15、统原理(第三版)主 编： 张尧学出版社：清华大学出版社3 操作系统实验教程主 编：张丽芬，刘利雄. 出版社：清华大学出版社. 本科生课程设计成绩评定表班级：软件工程 0704姓名：万力学号：0120710680427序号评分项目满分实得分1学习态度认真、遵守纪律102设计分析合理性103设计方案正确性、可行性、创造性204设计结果正确性405设计报告的规范性106设计验收10总得分/等级评语：注：最终成绩以五级分制记。优（90-100 分）、良（80-89 分）、中（70-79 分）、及格（60-69 分）、60 分以下为不及格指导教师签名：2010年6 月28 日源代码#include #i
16、nclude #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; /进程类型（读写） int m_nStartTime; /开始时间int m_nWorkTime; /运行时间int m_nID; /进程号Person; Pe
17、rson g_PersonsMAX_PERSON; int g_NumPerson = 0; long g_CurrentTime= 0; /基本时间片数int g_PersonLists = /进程队列1, W, 4, 5, 2, W, 16, 4, 3, R, 5, 2, 4, W, 6, 5, 5, R, 4, 3, END, ; int g_NumOfReading = 0; int g_NumOfWriteRequest = 0; /申请写进程的个数HANDLE g_hReadSemaphore;/读者信号HANDLE g_hWriteSemaphore;/写者信号boolfinis
18、hed = false; /所有的读完成/bool wfinished = false; /所有的写完成 void CreatePersonList( int*pPersonList); bool CreateReader( intStartTime, intWorkTime, intID); bool CreateWriter( intStartTime, intWorkTime, intID); DWORD WINAPI ReaderProc(LPVOID lpParam); DWORD WINAPI WriterProc(LPVOID lpParam); intmain() g_hRea
19、dSemaphore = CreateSemaphore(NULL,1,100,NULL);/ /创建信号灯，当前可用的资源数为，最大为 g_hWriteSemaphore = CreateSemaphore(NULL,1,100,NULL);/ /创建信号灯，当前可用的资源数为，最大为 CreatePersonList(g_PersonLists);/ / Create All the reader and writers printf(Created all the reader and writern.n); g_CurrentTime = 0; while(true) g_Curren
20、tTime+; Sleep(300); / 300 ms printf(CurrentTime = %dn,g_CurrentTime); if(finished) return0; system (pause); / return 0; voidCreatePersonList( int*pPersonLists) int i=0; int *pList = pPersonLists; boolRet; while(pList0 != END) switch(pList1) caseR: Ret = CreateReader(pList2,pList3,pList0)/;/351,w452,
21、523,654 break; caseW: Ret = CreateWriter(pList2,pList3,pList0); break; if(!Ret) printf(Create Person %d is wrongn,pList0); pList += 4; / move to next person list DWORD WINAPI ReaderProc(LPVOID lpParam/)/读过程 Person *pPerson = (Person*)lpParam; / wait for the start time while(g_CurrentTime != pPerson-
22、m_nStartTime) printf(Reader %d is Requesting n,pPerson-m_nID); printf(nn*n); / wait for the write request WaitForSingleObject(g_hReadSemaphore,INFINITE);i f(g_NumOfReading =0) WaitForSingleObject(g_hWriteSemaphore,INFINITE); g_NumOfReading+; ReleaseSemaphore(g_hReadSemaphore,1,NULL); pPerson-m_nStar
23、tTime = g_CurrentTime; printf(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_NumOfReading-; if(g_NumOfReading = 0
24、) ReleaseSemaphore(g_hWriteSemaphore,1,NULL)/;/此时没有读者，可以写 ReleaseSemaphore(g_hReadSemaphore,1,NULL); if(pPerson-m_nID = 4) finished =t rue; /所有的读写完成ExitThread(0); return0; DWORD WINAPI WriterProc(LPVOID lpParam) Person *pPerson = (Person*)lpParam; / wait for the start time while(g_CurrentTime != pPe
25、rson-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_nStart
26、Time + 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 =t rue;/所有的读写完成ExitThread(0); return0; boolCreateReader( intStartTime, intWorkTime, intID) DWORD dwThreadID; if(g_Nu
27、mPerson = MAX_PERSON) return false; Person *pPerson = &g_Personsg_NumPerson; pPerson-m_nID = ID; pPerson-m_nStartTime = StartTime; pPerson-m_nWorkTime = WorkTime; pPerson-m_nType = READER; g_NumPerson+; / Create an New Thread pPerson-m_hThread= CreateThread(NULL,0,ReaderProc,(LPVOID)pPerson,0,&dwThreadID); if(pPerson-m_hThread = NULL) return false; return true; boolCreateWriter( intStartTime, intWorkTime, intID) DWORD dwThreadID; if(g_NumPerson = MAX_PERSON) return false; Person *pPerson = &g_Personsg_Num
