学

　 号：

　 课 程 设 计

　 题

　目 实现读者写者

　 (Reader-Writer Problem) 问题 学

　院 计算机科学与技术 专

　业 软件工程 班

　级 软件 姓

　名

　指导教师

　 2010 年 X 月 X 日

　 目

　 录

　1．概述 …………………………………………4 1.1设计题目 ………………………………………………4 1.2设计目的 ………………………………………………4 1.3设计时间 ………………………………………………4 1.4开发环境 ………………………………………………4 1.5设计要求 ………………………………………………4 2．数据结构与模块说明 ………………………5 2.1设计概述

　 ……………………………………………5 2.2设计流程图 ……………………………………………6 3．具体编程实现 ………………………………7 4．运行结果与测试 ……………………………8 5. 课程设计总结与体会 ………………………11 6．参考文献 ……………………………………11

　 课程设计任务书 学生姓名：

　专业班级：

　软件

　指导教师：

　工作单位：

　计算机科学与技术学院

　题目: 实现读者写者 (Reader-Writer Problem) 问题 初始条件：

　1. 操作系统：Linux 2. 程序设计语言：C语言 3. 设有20个连续的存储单元，写入/读出的数据项按增序设定为1－20这20个字符。

　要求完成的主要任务: （包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）

　 1．技术要求：

　1）为每个读者／写者产生一个线程，设计正确的同步算法 2）每个读者/写者对该存储区进行操作后，即时显示该存储区的全部内容、当前指针位置和读者/写者线程的自定义标识符。。

　3）读者应有3个以上，写者应有有两个以上。

　4）多个读者/写者之间须共享对存储区进行操作的函数代码。

　2． 设计说明书内容要求：

　1）设计题目与要求 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 设计目的 通过对操作系统内核实现代码的阅读、修改、设计，理解和掌握复杂的操作系统的工作原理。

　通过研究Linux的线程机制和信号量实现读者写者(Reader-Writer)问题并发控制。

　1.3设计时间 消化资料、系统调查 1天 系统分析 1天 总体设计、实施计划 2天 撰写课程设计报告书 1天 第18周周一至周五 1.4开发环境 本次课程设计在操作系统：Linux下，使用的编程语言为C语言。

　1.5 设计要求 1）为每个读者／写者产生一个线程，设计正确的同步算法 2）每个读者/写者对该存储区进行操作后，即时显示该存储区的全部内容、当前指针位置和读者/写者线程的自定义标识符。。

　3）读者应有3个以上，写者应有有两个以上。

　4）多个读者/写者之间须共享对存储区进行操作的函数代码。

　2数据结构与模块说明

　2.1设计概述

　所谓读者写着问题，是指保证一个writer进程必须与其他进程互斥地访问共享对象的同步问题。

　读者写者问题可以这样的描述，有一群写者和一群读者，写者在写同一本书，读者也在读这本书，多个读者可以同时读这本书，但是，只能有一个写者在写书，并且，读者必写者优先，也就是说，读者和写者同时提出请求时，读者优先。当读者提出请求时需要有一个互斥操作，另外，需要有一个信号量S来当前是否可操作。

　信号量机制是支持多道程序的并发操作系统设计中解决资源共享时进程间的同步与互斥的重要机制，而读者写者则是这一机制的一个经典范例。

　与记录型信号量解决读者—写者问题不同，信号量机制它增加了一个限制，即最多允许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           Repeat            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，则任何reader进程就都无法进入读。Swait(mx ,1,1,l,RN,0)语句表示仅当既无Write进程在写（mx=1），又无reader进程在读（L=RN）时，writer进程才能进入临界区写。

　2.2设计流程图

　 主程序() 读者() 写者() 主控()

　3 具体编程实现 读者-写者的读写限制（包括读者优先和写者优先） 1）写-写互斥，即不能有两个写者同时进行写操作 2）读-写互斥，即不能同时有一个读者在读，同时却有一个写者在写 3）读读允许，即可以有2个以上的读者同时读 将所有的读者和所有的写者分别放进两个等待队列中，当读允许时就让读者队列释放一个或多个读者，当写允许时，释放第一个写者操作。读者写者问题的定义如下：有一个许多进程共享的数据区，这个数据区可以是一个文件或者主存的一块空间；有一些只读取这个数据区的进程（Reader）和一些只往数据区写数据的进程(Writer)，此外还需要满足以下条件：

　1)任意多个读进程可以同时读这个文件； 2) 一次只有一个写进程可以往文件中写； 3）如果一个写进程正在进行操作，禁止任何读进程度文件。

　我们需要分两种情况实现该问题：

　读优先：要求指一个读者试图进行读操作时，如果这时正有其他读者在进行操作，他可直接开始读操作，而不需要等待。

　写优先：一个读者试图进行读操作时，如果有其他写者在等待进行写操作或正在进行写操作，他要等待该写者完成写操作后才开始读操作。

　程序由三部分组成：

　1． 读者模块：包括系统调用接口，读者活动描述主程序。系统接口主要功能是通过管道向父进程发送系统调用命令，并读取父进程送来的返回值。

　2． 写者模块：包括系统调用接口，写者活动描述主程序。

　读者-写者活动程序根据临界资源的共享，互斥原则编制。

　3. 主控模块：主控模块实现系统初始化系统调用命令接收与解释执行，系统调用功能的实现（包括信号量机制），及读者-写者活动过程记录与显示。

　 4运行结果与测试

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

　 1, W，4, 5,

　 2, W, 16, 4,

　 3, R, 5, 2,

　 4, W, 6, 5,

　 5, R, 4, 3,

　在读者写者同时在队列中等待申请资时，读者优先调用资源。而且如果一个读者申请进行读操作时已有另一读者正在进行读操作，则该读者可直接开始读操作，即读读允许。

　进程1是W操作，在时间4时进入队列,运行时间是5,在它进入时没有进程占用资源，它既占用资源；直到它释放资源，等候的进程有3，4，5； 其他进程如截图所示。

　5课程设计总结与心得体会 这一次课程设计，我完成了题目“读者-写者问题的实现”，更加系统地理解和掌握C语言的基本概念、语言特点和编程技巧，在应用C语言在程序设计方面得到系统锻炼，为将来用C进行软件开发打下良好基础。对程序设计思想也有了比较清晰的印象，为今后的程序设计奠定了一定的心理和技术上的准备。总的感觉，学到了很多知识，特别对于linux有了全面的接触和了解，也开始对linux产生了兴趣，它所开放的源码的确为学计算机的同志们提供了很好的平台。读者-写者问题经典的线程同步问题的一个模型。经过读者写者问题的编写，我对同步机构应用有了深入的了解。懂得了运用信号量实现进程间的互斥。实现了不让共享资源同时修改。用信号量上的原语操作使临界段问题的解决比较简单明了了。读者写者问题的编写，花的时间很多，也学到很多东西。了解支持多道程序的并发操作系统设计中解决资源共享时进程间的同步与互斥的信号量机制。几天的试验，虽然难度有点大，但只要自己花时间去学习，还是会攻克困难的。

　课程设计提高了我对所学知识的综合应用能力，全面检查并掌握所学的内容，培养独立思考、刻苦钻研的精神，在分析问题、解决问题的过程中，更是获得一种成功的喜悦，进而增加学习和应用的兴趣。同时也要督促自己在学习的过程中不断的完善自我，加强自己的动手操作能力，培养我的独立思考的那种思维方式。

　总之，每一次课程设计不仅是我们学习的好机会，而且是我们锻炼实际动手能力的平台，虽然有难度的东西总会让人很抵触，比如在课设过程中有很多郁闷的时候，一个小小的错误一不小心就花去了自己一上午的时间，所以在这个过程中能够磨练人的意志与耐心，最后感谢老师的指导与监督。

　6参考文

　[1] 《Operating System Concepts(Sixth Edition)（操作系统概念）影印版》，

　主

　编：Abraham Silberschatz

　出版社：高等教育出版社

　[2] 《操作系统原理(第三版)》

　 主

　编：

　张尧学 出版社：清华大学出版社 [3]《操作系统实验教程》

　主

　编：张丽芬，刘利雄. 出版社：清华大学出版社.

　 本科生课程设计成绩评定表 班级：软件工程　　　姓名：　　学号：

　序号 评分项目 满分 实得分 1 学习态度认真、遵守纪律 10

　2 设计分析合理性 10

　3 设计方案正确性、可行性、创造性 20

　4 设计结果正确性 40

　5 设计报告的规范性 10

　6 设计验收 10

　总得分/等级

　评语：

　注：最终成绩以五级分制记。优（90-100分）、良（80-89分）、中（70-79分）、 及格（60-69分）、60分以下为不及格

　　　　　　　　　　　　　　　　　　　　　　　指导教师签名：

　　　　　　　　　　　　　　　　　　　2010

　 年　 月

　日

　 源代码 #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

　WRITER

　 typedef struct _Person

　{

　HANDLE m_hThread;//定义处理线程的句柄

　int

　m_nType;//进程类型（读写）

　int

　m_nStartTime;//开始时间

　int

　m_nWorkTime;//运行时间

　int

　m_nID;//进程号

　}Person;

　 Person g_Persons[MAX_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;//写者信号

　bool finished = false; //所有的读完成

　//bool wfinished = false; //所有的写完成

　void

　CreatePersonList(int *pPersonList);

　bool

　CreateReader(int 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); //创建信号灯，当前可用的资源数为，最大为

　g_hWriteSemaphore = CreateSemaphore(NULL,1,100,NULL); //创建信号灯，当前可用的资源数为，最大为

　CreatePersonList(g_PersonLists); // Create All the reader and writers

　printf(“Created all the reader and writer＼n...＼n“);

　g_CurrentTime = 0;

　while(true)

　{

　g_CurrentTime++;

　Sleep(300); // 300 ms

　printf(“CurrentTime = %d＼n“,g_CurrentTime);

　if(finished) return 0; system (“pause“);

　} // return 0;

　}

　void CreatePersonList(int *pPersonLists)

　{

　int

　i=0;

　int

　*pList = pPersonLists;

　bool Ret;

　while(pList[0] != END)

　{

　switch(pList[1])

　{

　case R:

　Ret = CreateReader(pList[2],pList[3],pList[0]);//351,w452,523,654

　break; case W:

　Ret = CreateWriter(pList[2],pList[3],pList[0]);

　break;

　}

　if(!Ret)

　printf(“Create Person %d is wrong＼n“,pList[0]);

　 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->m_nStartTime)

　{ }

　printf(“Reader %d is Requesting ...＼n“,pPerson->m_nID);

　printf(“＼n＼n************************************************＼n“);

　// wait for the write request

　WaitForSingleObject(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(“＼n＼n************************************************＼n“);

　while(g_CurrentTime <= pPerson->m_nStartTime + pPerson->m_nWorkTime)

　{}

　printf(“Reader %d is Exit...＼n“,pPerson->m_nID);

　printf(“＼n＼n************************************************＼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;

　}

　DWORD

　WINAPI WriterProc(LPVOID lpParam)

　{

　Person *pPerson = (Person*)lpParam;

　// wait for the start time

　while(g_CurrentTime != pPerson->m_nStartTime)

　{}

　printf(“Writer %d is Requesting ...＼n“,pPerson->m_nID);

　printf(“＼n＼n************************************************＼n“);

　WaitForSingleObject(g_hWriteSemaphore,INFINITE);

　// modify the writer＇s real start time

　pPerson->m_nStartTime = g_CurrentTime;

　printf(“Writer %d is Writting the Shared Buffer...＼n“,pPerson->m_nID);

　while(g_CurrentTime <= pPerson->m_nStartTime + pPerson->m_nWorkTime)

　{}

　printf(“Writer %d is Exit...＼n“,pPerson->m_nID);

　printf(“＼n＼n************************************************＼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_NumPerson >= MAX_PERSON)

　return false;

　Person *pPerson = &g_Persons[g_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;

　}

　bool CreateWriter(int StartTime,int WorkTime,int ID)

　{

　DWORD dwThreadID;

　if(g_NumPerson >= MAX_PERSON)

　 return false;

　Person *pPerson

　= &g_Persons[g_NumPerson];

　pPerson->m_nID

　= ID;

　pPerson->m_nStartTime = StartTime;

　pPerson->m_nWorkTime

　= WorkTime;

　pPerson->m_nType

　 = WRITER;

　g_NumPerson++;

　// Create an New Thread

　pPerson->m_hThread= CreateThread(NULL,0,WriterProc,(LPVOID)pPerson,0,&dwThreadID);

　if(pPerson->m_hThread == NULL)

　return false;

　return true;

　}