读者写者问题说明书

1、操作系统原理课程设计任务书题目：读者-写者问题的实现学生姓名： 李志旭 学号： 13740113 班级：_13级软件工程_ 题目类型：软件工程（R） 指导教师： 陈文娟、马生菊 一、设计目的学生通过该题目的设计过程，掌握读者、写者问题的原理、软件开发方法并提高解决实际问题的能力。二、设计任务编写程序实现读者优先和写者优先问题:读者-写者问题的读写操作限制（包括读者优先和写者优先）写-写互斥：不能有两个写者同时进行写操作读-写互斥：不能同时有一个线程在读，而另一个线程在写。读-读允许：可以有一个或多个读者在读。三、设计要求1. 分析设计要求，给出解决方案（要说明设计实现所用的原理、采用的数据结构

2、）。2. 设计合适的测试用例，对得到的运行结果要有分析。3. 设计中遇到的问题，设计的心得体会。4. 文档：课程设计打印文档每个学生一份，并装在统一的资料袋中，资料袋前面要贴有学校统一的资料袋封面。 四、 提交的成果1. 课程设计说明书内容包括(1) 封面（学院统一印制）；(2) 课程设计任务书；(3) 中文摘要150字；关键词3-5个；(4) 目录；(5) 正文；（设计思想；各模块的伪码算法；函数的调用关系图；测试结果等）(6) 设计总结；(7) 参考文献；(8) 致谢等。注：每一部分是单独的一章，要另起一页写。2. 排版要求(1) 所有一级标题为宋体三号加粗（即上面写的28部分，单独一行，

3、居中）(2) 所有二级标题为宋体四号加粗（左对齐）(3) 所有三级标题为宋体小四加粗（左对齐）(4) 除标题外所有正文为宋体小四，行间距为固定值22磅，每个段落首行缩进2字符(5) 目录只显示3级标题，目录的最后一项是无序号的“参考文献资料”。3. 其他要求（班长负责，务必按照以下方式建文件夹 ）(1) 以班级为单位刻录光盘一张，光盘以班级命名，例如：“10级计算机科学与技术1班”；(2) 光盘内每人一个文件夹，以学号姓名命名如“10730101 陈映霞”，内容包括任务书、设计文档。五、 各阶段时间安排（共2周）根据教学计划安排，于2014年12月8日 2014年12月19日安排为期二周的操作

4、系统课程设计。周次日期内容地点完成情况教师签字第1周星期一二教师讲解设计要求查找参考资料教室图书馆星期三五算法设计，编程实现教室第2周星期一三算法设计，编程实现教室星期四五检查程序，答辩教室六、考勤、纪律及注意事项1每日准时教室设计，不得无故缺席、早退。2独立、按时完成课程设计任务，准时上交资料。七、主要参考文献1. 汤子瀛，哲凤屏.计算机操作系统M.西安：西安电子科技大学学出版社.1996年2. 王万森.计算机操作系统原理M.北京：高等教育出版社.2001年3. 周长林，左万历. 计算机操作系统教程M.北京：高等教育出版社.1994年4. 黄廷辉，王宇英.计算机操作系统实践教程M.北京：清华

5、大学出版社. 2007年5月5. 殷兆麟.计算机操作系统M.北京：清华大学出版社.2007年3月6. 张尧学，史美林，张高.计算机操作系统教程M.北京：清华大学出版社.1993年摘 要读者写者问题，是指保证一个writer进程必须与其他进程互斥地访问共享对象的同步问题。读者写者问题可以这样的描述，有一群写者和一群读者，写者在写同一本书，读者也在读这本书，多个读者可以同时读这本书，但是，只能有一个写者在写书，并且，读者必写者优先，也就是说，读者和写者同时提出请求时，读者优先。当读者提出请求时需要有一个互斥操作，另外，需要有一个信号量S来当前是否可操作。信号量机制是支持多道程序的并发操作系统设计中

6、解决资源共享时进程间的同步与互斥的重要机制，而读者写者则是这一机制的一个经典范例。 关键字：信号量 ；读者优先；写者优先；线程；互斥。目 录1概述11.1设计内容11.2实验目的21.3设计思想21.4设计方案32.总体设计42.1系统总体框架42.2函数调用关系图52.3数据结构定义53详细设计73.1读者进程优先算法73.2写者进程优先算法84调试分析104.1程序分析104.2调试结果104.3调试出现的问题12总 结13参考文献14致 谢15附 录161概述1.1 设计内容读者-写者问题可以这样的描述，有一群写者和一群读者，写者在写同一本书，读者也在读这本书，多个读者可以同时读这本书，

7、但是，只能有一个写者在写书，并且，读者必写者优先，也就是说，读者和写者同时提出请求时，读者优先。当读者提出请求时需要有一个互斥操作，另外，需要有一个信号量S来当前是否可操作。读者-写者问题（Readers-Writers problem）也是一个经典的并发程序设计问题，是经常出现的一种同步问题。计算机系统中的数据（文件、记录）常被多个进程共享，但其中某些进程可能只要求读数据（称为读者Reader）；另一些进程则要求修改数据（称为写者Writer）。就共享数据而言，Reader和Writer是两组并发进程共享一组数据区，要求：（1）允许多个读者同时执行读操作；（2）不允许读者、写者同时操作；（3

8、）不允许多个写者同时操作。Reader和Writer的同步问题分为读者优先、弱写者优先（公平竞争）和强写者优先三种情况，它们的处理方式不同。（1）读者优先。对于读者优先，应满足下列条件：如果新读者到：无读者、写者，新读者可以读；有写者等待，但有其它读者正在读，则新读者也可以读；有写者写，新读者等待。如果新写者到：无读者，新写者可以写；有读者，新写者等待；有其它写者，新写者等待。信号量机制是支持多道程序的并发操作系统设计中解决资源共享时进程间的同步与互斥的重要机制，而读者写者问题则是这一机制的一个经典范例。与记录型信号量解决读者写者问题不同，信号量机制它增加了一个限制，即最多允许RN个读者同时读

9、。为此，又引入了一个信号量L,并赋予初值为RN，通过执行wait（L,1,1）操作，来控制读者的数目，每当有一个读者进入时，就要执行wait（L,1,1）操作，使L的值减1。当有RN个读者进入读后，L便减为0，第RN+1 个读者要进入读时，必然会因wait（L,1,1）操作失败而堵塞。1.2 设计目的理解临界区和进程互斥的概念，掌握用信号量和PV操作实现进程互斥的方法。1.3设计思想读者-写者的读写限制（包括读者优先和写者优先）1）写-写互斥，即不能有两个写者同时进行写操作；2）读-写互斥，即不能同时有一个读者在读，同时却有一个写者在写；3）读读允许，即可以有2个以上的读者同时读。将所有的读者

10、和所有的写者分别放进两个等待队列中，当读允许时就让读者队列释放一个或多个读者，当写允许时，释放第一个写者操作。读者写者问题的定义如下：有一个许多进程共享的数据区，这个数据区可以是一个文件或者主存的一块空间；有一些只读取这个数据区的进程（Reader）和一些只往数据区写数据的进程(Writer)，此外还需要满足以下条件：1)任意多个读进程可以同时读这个文件；2) 一次只有一个写进程可以往文件中写；3）如果一个写进程正在进行操作，禁止任何读进程读文件。我们需要分两种情况实现该问题：读优先：要求指一个读者试图进行读操作时，如果这时正有其他读者在进行操作，他可直接开始读操作，而不需要等待。写优先：一个

11、读者试图进行读操作时，如果有其他写者在等待进行写操作或正在进行写操作，他要等待该写者完成写操作后才开始读操作。程序由三部分组成：1)读者模块：包括系统调用接口，读者活动描述主程序。系统接口主要功能是通过管道向父进程发送系统调用命令，并读取父进程送来的返回值。2)写者模块：包括系统调用接口，写者活动描述主程序。读者-写者活动程序根据临界资源的共享，互斥原则编制。3）主控模块：主控模块实现系统初始化系统调用命令接收与解释执行，系统调用功能的实现（包括信号量机制），及读者-写者活动过程记录与显示。1.4设计方案团队合作方案：主要成员 ：李荣，李龙，李志旭。成员分工：李荣：实施设计计划，统筹安排任务。

12、李荣、李志旭、李龙：查阅资料，设计流程图,调试程序，。李志旭、李龙、李荣：设计分析程序，撰写报告册。程序设计方案：主要函数：WINAPI ReaderProc(LPVOID lpParam); /创建读进程函数WINAPI WriterProc(LPVOID lpParam); /创建写进程函数CreatePersonList(g_PersonLists); /创建进程队列函数主要变量：m_nType;/进程类型（读写）int m_nStartTime;/开始时间int m_nWorkTime;/运行时间int m_nID;/进程号2总体分析2.1系统总体框架：读者-写者问题与进程同步。理解临

13、界区和进程互斥的概念，掌握用信号量和PV操作实现进程互斥的方法。要求学生用信号量和PV操作实现读者/写者问题的读者优先算法、写者优先算法和无优先算法WWRR开始显示界面读者优先写者优先创建读者线程读者线程完成读入数据创建写者线程写者线程完成创建读者线程读者线程完成读入数据完成操作图2-1 程序主框架图2.2函数调用关系图：主函数（main）读者进程函数ReaderProc(LPVOID lpParam)写者进程函数WriterProc(LPVOID lpParam)处理写者优先的函数 W_writeThread处理读者优先的函数 R_readThread图2-2 函数调用关系图2.3数据结构定

14、义：创建Person结构体typedef struct _PersonHANDLE m_hThread;/定义处理线程的句柄int m_nType;/进程类型（读写）int m_nStartTime;/开始时间int m_nWorkTime;/运行时间int m_nID;/进程号Person;int g_PersonLists = /进程队列1, W, 4, 5, 2, W, 16, 4, 3, R, 5, 2,4, W, 6, 5, 5, R, 4, 3, END,;Var RN integer;L,mx:semaphore: =RN,1；BeginParbegin  Reader

15、 :begin          Repeat           Swait（L,1,1）;           Swait（mx,1,0）;              

16、;    .           Perform reader operation;           Ssignal(L,1); Until false;  EndWriter ：beginRepeatSwait(mx ,1,1,l,RN,0);Perform writer operation;Ssignal(mx,1);Until false

17、;EndParendEnd  其中，Swait（mx,1,0）语句起着开关作用，只要无Writer进程进入些，mx=1，reader进程就都可以进入读。但是要一旦有Writer进程进入写时，其MX=0，则任何reader进程就都无法进入读。Swait(mx ,1,1,l,RN,0)语句表示仅当既无Writer进程在写（mx=1），又无Reader进程在读（L=RN）时，Writer进程才能进入临界区写。3详细设计Reader和Writer的同步问题分为读者优先、写者优先（公平竞争）两种情况，它们的处理方式不同。3.1读者优先1. 读者优先流程图读优先：要求指一个读者试图进行读操作时，

18、如果这时正有其他读者在进行操作，他可直接开始读操作，而不需要等待。让读者进程优先执行，其他进程滞后。开始创建临界区创建读者进程(Reader)准备读操作， Read+；读进程执行读操作，Read-；Read=0 ？否创建写者进程(Writer)释放系统内存和cpu资源准备写操作， Write+；读进程执行写操作，Write-；Write=0 ？是释放系统内存和cpu资源执行其他进程返回否是图3-1 读者优先算法程序流程图2程序实现DWORD WINAPI ReaderProc(LPVOID lpParam)/读过程Person *pPerson = (Person*)lpParam;/ wai

19、t for the start timewhile(g_CurrentTime != pPerson->m_nStartTime) 3.2写者优先 1. 写者优先流程图写优先：写者在等待进行写操作或正在进行写操作，读者要等待该写者完成写操作后才开始读操作。让写者进程优先执行，其他进程滞后。准备读操作， Read+；开始创建临界区创建写者进程(Writer)准备写操作， Write+；写进程执行写操作，Write-；Write=0 ？否创建读者进程(Reader)释放系统内存和cpu资源读进程执行写操作，Read-；Read=0 ？是释放系统内存和cpu资源执行其他进程返回否是图3-2 写

20、者优先算法程序流程图2. 程序实现WaitForSingleObject(g_hWriteSemaphore,INFINITE);/ modify the writer's real start timepPerson->m_nStartTime = g_CurrentTime;DWORD WINAPI WriterProc(LPVOID lpParam)Person *pPerson = (Person*)lpParam;/ wait for the start timewhile(g_CurrentTime != pPerson->m_nStartTime)4调试分析4

21、.1程序分析 测试数据文件包括n 行测试数据，分别描述创建的n 个线程是读者还是写者，以及读写操作的开始时间和持续时间。每行测试数据包括四个字段，各字段间用空格分隔。第一字段为一个正整数，表示线程序号。第二字段表示相应线程角色，R 表示读者是，W 表示写者。第三字段为一个正数，表示读写操作的开始时间。线程创建后，延时相应时间（单位为秒）后发出对共享资源的读写申请。第四字段为一个正数，表示读写操作的持续时间。当线程读写申请成功后，开始对共享资源的读写操作，该操作持续相应时间后结束，并释放共享资源。下面是一个测试数据文件的例子：1, W，4, 5, 2, W, 16, 4, 3, R, 5, 2,

22、 4, W, 6, 5,4.2调试结果图4.1进程进入队列5, R, 4, 3,图4.2读进程释放内存写进程1申请资源，而进程3正在使用进程图4.3读进程退出写进程进入队列进程5,3依次释放资源图4.4写进程请求资源进程1释放资源，进程4正在使用资源。在读者写者同时在队列中等待申请资时，读者优先调用资源。而且如果一个读者申请进行读操作时已有另一读者正在进行读操作，则该读者可直接开始读操作，即读读允许。进程1是W操作，在时间4时进入队列,运行时间是5,在它进入时没有进程占用资源，它既占用资源；直到它释放资源，等候的进程有3，4，5；其他进程如截图所示。4.3 调试出现的问题在程序调试过程中出现的

23、问题有因为不细心连接的时候没有找对相应的函数名；定义一个类，但类的成员函数不小心被注释掉了；读者写着优先级判断错误；申请资源这部分对资源调用的先后次序没有做出正确的判断。总结这一次课程设计，我们组完成了“读者-写者问题与进程同步”问题，更加系统地理解和掌握了临界区和进程互斥的概念掌握用信号量和PV操作实现进程互斥的方法。要求学生用信号量和PV操作实现读者/写者问题的读者优先算法、写者优先算法和无优先算法。经过读者写者问题的编写，我对同步机构应用有了深入的了解，懂得了运用信号量实现进程间的互斥，实现了不让共享资源同时修改。用信号量上的原语操作使临界段问题的解决比较简单明了了。读者写者问题的编写，

24、花的时间很多，也学到很多东西。了解在支持多道程序的并发操作系统设计中，如何解决资源共享时进程间的同步与互斥的信号量机制。课程设计提高了我们对所学知识的综合应用能力，全面检查并掌握所学的内容，培养独立思考、刻苦钻研的精神，在分析问题、解决问题的过程中，更是获得一种成功的喜悦，进而增加学习和应用的兴趣。同时也要督促自己在学习的过程中不断的完善自我，加强自己的动手操作能力，培养我的独立思考的那种思维方式。总之，这一次课程设计我们深刻的理解操作系统，而且锻炼了实际编程能力和思维方式，虽然有难度过程中遇到很多问题，经过深刻细致的理解问题、剖析问题、解决问题使我们深刻的认识理解了读者/写者问题与进程同步。

25、参考文献1 汤子瀛，哲凤屏.计算机操作系统M.西安：西安电子科技大学学出版社.1996年2 王万森.计算机操作系统原理M.北京：高等教育出版社.2001年3 周长林，左万历. 计算机操作系统教程M.北京：高等教育出版社.1994年4 黄廷辉，王宇英.计算机操作系统实践教程M.北京：清华大学出版社. 2007.5.5殷兆麟.计算机操作系统M.北京：清华大学出版社.2007年3月6张尧学，史美林，张高.计算机操作系统教程M.北京：清华大学出版社.1993年7 张丽芬等，操作系统实验教程M，北京清华大学出版社，2006.10.8&

26、#160;屠祁等，操作系统基础（第三版）M，北京清华大学出版社，2000.7.9 冯耀霖等，操作系统M，西安电子科技大学出版社，2001.9.10 左万历，计算机操作系统教程（第二版）M，北京高等教育出版社 2007致谢 本次课设在选题及进行过程中得到老师的悉心指导。论文行文过程中，老师多次帮助我分析思路，开拓视角，在我遇到困难想放弃的时候给予我最大的支持和鼓励。老师严谨求实的治学态度，踏实坚韧的工作精神，将使我终生受益。再多华丽的言语也显苍白。在此，谨向老师致以诚挚的谢意和崇高的敬意。同时感谢学校给了我这次实践的机会让我知道了自己的不足。也非常感谢和我一个组的其

27、他两位同学，我们作为一个团队，在我遇到问题的时候他们给了我很大的帮助和支持，谢谢你们！在我陷入误区的时候，是热心的老师和同学们帮助使我摆脱困境，在此再次感谢他们。 经过两个星期的艰苦拼搏，在设计程序的过程中，让我认识到光学习书本知识是远远不够的，但在此基础上更要加强自己动脑动手分析调试程序的能力，这次课设我收获很多。 最应该感谢的就是我的父母，感谢他们不辞辛苦供我上大学，养育我成人。 在课设过程中，感谢所有给予我帮助和指导的老师和同学,没有他们的帮助我的程序也不会得到这样好的完善，也不能学到这么多的知识以及经验，真的非常感谢。 经过两个星期的艰苦拼搏，在设计程序的过程中，让我认识到光学习书本知

28、识是远远不够的，但在此基础上更要加强自己动脑动手分析调试程序的能力，这次课设我收获很多。源代码#include <windows.h>#include <ctype.h>#include <stdio.h>#include <string.h>#include <stdlib.h>#include <malloc.h>#define MAX_PERSON 100#define READER 0 /读者#define WRITER 1 /写者#define END -1#define R READER#define W WR

29、ITER typedef struct _PersonHANDLE m_hThread;/定义处理线程的句柄int m_nType;/进程类型（读写）int m_nStartTime;/开始时间int m_nWorkTime;/运行时间int m_nID;/进程号Person; Person 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

30、, END,;int g_NumOfReading = 0;int g_NumOfWriteRequest = 0;/申请写进程的个数HANDLE g_hReadSemaphore;/读者信号HANDLE g_hWriteSemaphore;/写者信号bool finished = false; /所有的读完成/bool wfinished = false; /所有的写完成void CreatePersonList(int *pPersonList);bool CreateReader(int StartTime,int WorkTime,int ID);bool CreateWriter(i

31、nt StartTime,int WorkTime,int ID);DWORD WINAPI ReaderProc(LPVOID lpParam);DWORD WINAPI WriterProc(LPVOID lpParam);int main()g_hReadSemaphore = CreateSemaphore(NULL,1,100,NULL); /创建信号灯，当前可用的资源数为，最大为g_hWriteSemaphore = CreateSemaphore(NULL,1,100,NULL); /创建信号灯，当前可用的资源数为，最大为CreatePersonList(g_PersonList

32、s); / 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;system ("pause"); / return 0;void CreatePersonList(int *

33、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

34、 next 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 requestWaitForSingle

35、Object(g_hReadSemaphore,INFINITE); if(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_nID);printf("nn*n

36、");while(g_CurrentTime <= pPerson->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)ReleaseSemaphore(g_hWriteSemaphore,1,NULL);/此时没

37、有读者，可以写ReleaseSemaphore(g_hReadSemaphore,1,NULL);if(pPerson->m_nID = 4) finished = true; /所有的读写完成ExitThread(0);return 0;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 writer's real start timepPerson->m_nStartTime = g_CurrentTime;printf("Writer %d is Writting the Shared