操作系统原理课程设计读者-写者问题的实现.doc

实践教学实践教学 兰州理工大学兰州理工大学 计算机与通信学院 2012 年秋季学期 操作系统原理操作系统原理课程设计课程设计 题 目 读者 写者问题的实现 专业班级 姓 名 学 号 指导教师 成 绩 1 目录目录 摘 要 2 1 设计思想 3 2 各模块的伪码算法 4 3 函数关系调用图 6 4 程序测试结果 7 设计总结 10 参考文献 11 致 谢 12 2 摘摘 要要 本设计的读者写者问题 是指一些进程共享一个数据区 数据区可以使一 个文件 一块内存空间或者一组寄存器 Reader 进程只能读数据区中的数据 而 writer 进程必须与其他进程互斥地访问共享对象的同步问题 读者写者问题可以这样的描述 有一群写者和一群读者 写者在写同一本 书 读者也在读这本书 多个读者可以同时读这本书 但是 只能有一个写者在 写书 并且 读者必写者优先 也就是说 读者和写者同时提出请求时 读者优先 当读者提出请求时需要有一个互斥操作 另外 需要有一个信号量 S 来确定当 前是否可操作 本设计方案就是通过利用记录型信号量对读者写者问题的解决过程进行模 拟演示 形象地阐述记录型信号量机制的工作原理 关键词关键词 共享对象 互斥 同步 信号量 3 1 1 设计设计思想思想 本设计借助 C 语言实现进程同步和互斥的经典问题 读者写者问题 用高 级语言编写和调试一个进程同步程序 以加深对进程同步机制的理解 通过用 C 语言模拟进程同步实现 加深理解有关进程同步和互斥机制的概念及 P V 操 作的应用 学生通过该题目的设计过程 掌握读者 写者问题的原理 软件开 发方法并提高解决实际问题的能力 在 Windows 环境下 创建一个包含 n 个线程的控制台进程 用这 n 个线每 个线程按相应测试数据文件的要求 进行读写操作 程来表示 n 个读者或写者 请用信号量机制分别实现读者优先和写者优先的读者 写者问题 将所有的读者和所有的写者分别放进两个等待队列中 当读允许时就让读 者队列释放一个或多个读者 当写允许时 释放第一个写者操作 读者 写者的读写限制 包括读者优先和写者优先 1 写 写互斥 即不能有两个写者同时进行写操作 2 读 写互斥 即不能同时有一个读者在读 同时却有一个写者在写 3 读读允许 即可以有 2 个以上的读者同时读 4 读者优先附加条件 如果一个读者申请进行读操作 同时又有一个读操 作正在进行读操作 则该读者可以直接开始读操作 5 写者优先附加条件 如果一个读者申请进行读操作时已经有一个写者在 等待访问共享资源 则该读者必须等到没有写者处于等待状态后才能开始读操 作 4 2 2 各模块的伪码算法各模块的伪码算法 读者优先算法 读者优先算法 设置两个互斥信号量 rwmutex 用于写者与其他读者 写者互斥的访问共享数据 rmutex 用于读者互斥的访问 读者计数器 readcount semaphore rwmutex 1 rmutex 1 int readcount 0 reader i 读者进程 i 1 2 do P rmutex 读者互斥 readcount 读者数加 1 if readcount 1 P rwmutex 读者写者互斥 V rmutex 读者读数据 P rmutex Readcount if readcount 0 V rwmutex V rmutex while 1 writer j 写者进程 j 1 2 do P rwmutex 写文件 V rwmutex while 1 写者优先算法 写者优先算法 设置三个互斥信号量 rwmutex 用于写者与其他读者 写者互斥的访问共享数据 rmutex 用于读者互斥的访问 读者计数器 readcount nrmutex 用于写者等待已进入读者退出 所有读者退出前互斥写操作 semaphore rwmutex 1 rmutex 1 nrmutex 1 5 int readcount 0 reader i 读者进程 i 1 2 do P rwmutex P rmutex readcount if readcount 1 P nrmutex 有读者进入 互斥写操作 V rmutex V rwmutex 及时释放读写互斥信号量 允许其它读 写进程申请资源 读数据 P rmutex readcount if readcount 0 V nrmutex 所有读者退出 允许写更新 V rmutex while 1 writer j 写者进程 j 1 2 do P rwmutex 互斥后续其它读者 写者 P nrmutex 如有读者正在读 等待所有读者读完 写更新 V nrmutex 允许后续新的第一个读者进入后互斥写操作 V rwmutex 允许后续新读者及其它写者 while 1 6 3 3 函数关系调用图函数关系调用图 Main g CurrentTime CreatePersonList ReaderProc WriterProc CreateReader CreateWriter 图 1 函数关系图 7 4 4 程序程序测试结果测试结果 测试数据文件包括 n 行测试数据 分别描述创建的 n 个线程是读者还 是写者 以及读写操作的开始时间和持续时间 每行测试数据包括四个字段 各 字段 间用空格分隔 第一字段为一个正整数 表示线程序号 第二字段表示相 应线程 角色 R 表示读者是 W 表示写者 第三字段为一个正数 表示读写操 作的开 始时间 线程创建后 延时相应时间 单位为秒 后发出对共享资源 的读写申请 第四字段为一个正数 表示读写操作的持续时间 当线程读写申 请成功后 开始 对共享资源的读写操作 该操作持续相应时间后结束 并释放 共享资源 在读者写者同时在队列中等待申请资时 读者优先调用资源 而且如果一 个 读者申请进行读操作时已有另一读者正在进行读操作 则该读者可直接开 始读操 作 即读读允许 图 2 进程 1 2 的测试结果 如图 2 所示 进程 1 是 W 操作 在时间 3 时进入队列 运行时间是 5 即在 时间 8 时 进程 1 退出 在它进入时没有进程 占用资源 它既占用资源 知道 它释放资源 等候的进程有 3 4 5 8 图 3 进程 3 5 的测试结果 如图 3 所示 进程 5 是 R 操作 在时间 4 时进入队列 运行时间是 3 进 程 3 是 R 操作 在时间 5 时进入队列 运行时间是 2 在它们进入时 进程 1 占用资源 它等待资源 当进程 1 释放资源后 由于读者优先 进程 3 5 同时调 运资源 因此在时间 11 时 进程 3 退出 在时间 12 时 进程 5 退出 图 4 进程 2 4 6 的测试结果 如图 4 所示 进程 4 是 W 操作 在时间 5 时进入队列 运行时间是 5 在它 9 进入时进程 1 占用资源 它等待资源 当进程 1 释放资源后 由于读者优先 进 程 3 5 占用资源 它依然等待 直到进程 3 5 都结束 即进程 4 在时间 12 时 开始调用资源 进程 2 是 R 操作 在时间 16 时进入队列 运行时间是 5 在它 进入时进程 4 占用资源 它等待资源 当 4 释放时占用资源后 进程 2 开始运 行 进程 6 是 R 操作 在时间 17 时进入队列 运行时间是 7 在它进入时进程 2 占用资源 它等待进程 2 释放后最后调用资源 10 设计总结设计总结 课程设计是培养学生综合运用所学知识 发现 提出 分析和解决实际问 题 锻炼实践能力的重要环节 是对学生实际工作能力的具体训练和考察过程 此次操作系统课程设计 我的感慨颇多 的确 从选题到定稿 从理论 到实践 在整整两星期的日子里 我学到很多的东西 同时不仅巩固了以前所 学过的知识 而且学到了很多在书本上所没有学到过的知识 通过这次课程设计我懂得了理论与实际相结合的重要性 只有理论知识 是远远不够的 所以只有把所学的理论知识与实践相结合起来 从理论中得 出结论 才能真正的服务于社会 从而提高自己的实际动手能力和独立思考 的能力 在设计的过程中遇到问题 可以说是困难重重 难免会遇到过各种 各样的问题 同时在设计的过程中发现了自己的不足之处 对以前所学过的 知识理解得不够深刻 掌握得不够牢固 因此 在以后的学习中要多下苦功 加强基础知识的学习 并且培养自己的动手实践能力 11 参考文献参考文献 1 汤子瀛 哲凤屏 计算机操作系统 西安 电子科技大学学出版社 2002 年 2 王清 李光明 计算机操作系统 北京 冶金工业出版社 2003 年 3 月 3 孙钟秀等 操作系统教程 北京 高等教育出版社 2008 年 4 月 4 曾明 Linux 操作系统应用教程 西安 陕西科学技术出版社 2005 年 5 张丽芬 刘利雄 操作系统实验教程 北京 清华大学出版社 2006 年 6 孟静 操作系统教程 原理和实例分析 北京 高等教育出版社 2001 年 7 周长林 计算机操作系统教程 北京 高等教育出版社 2011 年 12 月 8 张尧学 计算机操作系统教程 北京 清华大学出版社 2006 年 10 月 9 任满杰 操作系统原理实用教程 北京 电子工业出版社 2006 年 1 月 12 致致 谢谢 这次课程设计培养了我耐心 缜密 全面地思考问题的能力 从而加快 了问题解决的速度 提高了个人的工作效率 以及锻炼了使问题在短时间内 得以解决的品质 我从 纸上谈兵 到可以自己动脑动手分析调试程序 收 获不少 首先要感谢学校给我这次实践的机会 给了自己一个舞台 这不仅是对 自身的检验 而且增加了我编写代码的功力 还有多亏了老师们从理论到上 机亲自指导的辛苦教授 给予了我们最大帮助和全面指导 在这里 尤其感 谢我的指导老师朱红蕾老师 你不辞辛苦的给我们耐心指导 在这里 我衷 心向你们致谢 最后还要感谢热心的同学们 在我陷入误区的时候 是他们 热心的帮助使我摆脱困境 最后衷心感谢所有给予我帮助和指导的老师和同学 没有他们的帮助我的 程序也不会完成得这么顺利 13 源代码 include include 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 开始时间 14 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 3 5 2 W 16 5 3 R 5 2 4 W 6 5 5 R 4 3 6 R 17 7 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 15 ID DWORD WINAPI ReaderProc LPVOID lpParam DWORD WINAPI WriterProc LPVOID lpParam int main g hReadSemaphore CreateSemaphore NULL 1 100 NULL 创建信号灯 当 前可用的资源数为 1 最大为 100 g hWriteSemaphore CreateSemaphore NULL 1 100 NULL 创建信号灯 当 前 可用的资源数为 1 最大为 100 CreatePersonList g PersonLists 创建所 有的读者和写者 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 16 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 17 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 18 printf Reader d is Reading the Shared Buffer n pPerson m nID printf n n n while g CurrentTime 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 19 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 m nStartTime pPerson m nWorkTime printf Writer d is Exit n pPerson m nID printf n n n 20 g NumOfWriteRequest ReleaseSemaphore g hWriteSemaphore 1 NULL if