读者写着问题系统设计书.doc

读者写着问题系统设计书1 引 言1.1 问题的提出 在Windows2000环境下，创建一个控制台进程，此进程包含n个线程。用这n个线程来表示n个读者或写者。每个线程按相应测试数据文件的要求进行读写操作。用信号量机制分别实现读者优先和写者优先问题。1.2任务与分析 具体要求:读者-写者问题的读写操作限制（包括读者优先和写者优先）1） 写-写互斥：不能有两个写者同时进行写操作2） 读-写互斥：不能同时有一个线程在读，而另一个线程在写。3） 读-读允许：可以有一个或多个读者在读。读者优先的附加限制：如果读者申请进行读操作时已有另一个读者正在进行读操作，则该读者可直接开始读操作。 写者优先的附加限制：如果一个读者申请进行读操作时已有另一个写者在等待访问共享资源，则该读者必须等到没有写者处于等待状态后才能开始读操作。运行结果显示要求：要求在每个线程创建、发出读写申请、开始读写操作和结束读写操作时分别显示一行提示信息，以确定所有处理都遵守相应的读写操作限制。测试数据文件格式：测试数据文件包括n行测试数据，分别描述创建的n个线程是读者还是写者，以及读写操作的开始时间和持续时间。每行测试数据包括四个字段，每个字段间用空格分隔。第1个字段为正整数，表示线程的序号。第2个字段表示线程的角色，R表示读者，W表示写者。第3个字段为一个正数，表示读写开始时间：线程创建后，延迟相应时间（单位为秒）后发出对共享资源的读写申请。第4个字段为一个正数，表示读写操作的延迟时间。当线程读写申请成功后，开始对共享资源进行读写操作，该操作持续相应时间后结束，释放该资源。课程设计目的： 通过实现经典的读者写者问题，巩固对线程及其同步机制的学习效果，加深对相关基本概念的理解，并学习如何将基本原理和实际设计有机的结合。课程设计内容： 根据本设计书所提供的基础知识，分析相关代码得到相关的框图写出设计报告。2 设计思路可以将所有读者和所有写者分别存于一个读者等待队列和一个写者等待队列中，每当读允许时，就从读者队列中释放一个或多个读者线程进行读操作；每当写允许时，就从写者队列中释放一个写者线程进行写操作。2.1 读者优先读者优先指的是除非有写者在写文件，否则读者不需要等待。所以可以用一个整数变量Read_count记录当前的读者数目，用于确定是否需要释放正在等待的写者进程（当Read_count=0时，表明所有的读者读完，需要释放写者等待队列中的一个写者）。每当一个读者开始读文件时，必须修改Read_count变量。因此需要一个互斥对象mutex来实现对全局变量Read_count修改时的互斥。另外，为了实现写-写互斥，需要增加一个临界区对象Write。当写者发出写请求时，必须申请临界区对象的所有权。通过这种方法，可以实现读-写互斥，当Read_count=1时（即第一个读者到来时），读者线程也必须申请临界区对象的所有权。当读者拥有临界区的所有权时，写者阻塞在临界区对象Write上。当写者拥有临界区的所有权时，第一个读者判断完”Read_count=1”后阻塞在Write上，其余的读者由于等待对Read_count的判断，阻塞在mutex上。读者优先2.2 写者优先写者优先与读者优先相类似。不同之处在于一旦一个写者到来，它应该尽快对文件进行写操作，如果有一个写者在等待，则新到来的读者不允许进行读操作。为此应当填加一个整形变量Write_count，用于记录正在等待的写者的数目，当Write_count=0时，才可以释放等待的读者线程队列。为了对全局变量Write_count实现互斥，必须增加一个互斥对象mutex3。为了实现写者优先，应当填加一个临界区对象read，当有写者在写文件或等待时，读者必须阻塞在read上。读者线程除了要对全局变量Read_count实现操作上的互斥外，还必须有一个互斥对象对阻塞read这一过程实现互斥。这两个互斥对象分别命名为mutex1,mutex2。3 程序调试运行和使用平台3.1运行平台操作系统原理课程的实验环境如下：硬件环境：微型计算机（Intel x86系列CPU）一台软件环境：Windows98/2000/XP操作系统，以VC+ 6.0集成开发环境为主要开发工具。3.2具体操作如下：3.2.1.启动Visual C+ 6.0开发环境从“开始”菜单中选择“程序”| Microsoft Visual Studio 6.0 | Microsoft Visual C+6.0，显示Visual C+ 6.0开发环境主窗口。3.2.2.创建一个项目单击File菜单中的New选项显示New（新建）对话框（如图3.1所示）。图3.1 New对话框单击Projects标签，在Projects（项目）选项卡中，选择MFC AppWizard(.exe)。在Location（位置）文本框中指定一个路径，如E:TPOOP，在Preject Name（项目名称）文本框中为项目输入一个名字，最好是见名知意，如“ScoreInput”，单击OK（确定）按钮，便可勇MFC 向导创建应用程序，其步骤如下：第一步 选择【Single document】应用类型，即单文档应用程序，其他使用默认值，单击【Next】按钮。第二步 让用户选择程序中是否加入数据库支持，在此使用默认值【None】，单击【Next】按钮。第三步 让用户选择在程序中加入复合文档，自动化或ActiveX控件的支持，在此使用默认值，单击【Next】按钮。第四步 让用户选择应用程序的一些特性，在此使用默认值，单击【Next】按钮。第五步 让用户选择应用程序主窗口的风格、在源文件中是否加入注释、使用怎样的MFC类库，在此使用默认值，单击【Next】按钮。第六步 用户可以对MFC AppWizard提供的缺省类名、基类名、头文件名、源文件名进行修改，使用默认值，单击【Finish】按钮。则会显示出用户在前面几个步骤中作出的选择内容，单击【OK】按钮，系统开始创建应用程序，并回到Visual C+ 6.0的主界面。运行过的应用程序ScoreInput可以脱离Visual C+ 6.0单独运行，运行该文档可以双击“E: E:TPOOP ScoreInput Debug”下的ScoreInput.exe文件。和所有的Windows应用程序一样，ScoreInput也包含标题栏、菜单栏、工具栏、状态栏等窗口元素。 3.2.3.关闭工作空间选择菜单命令File | Close Workspace关闭工作空间。4课程设计理论基础4.1临界区：CRITICAL_SECTION RP_Write; /临界区CRITICAL_SECTION cs_Write;CRITICAL_SECTION cs_Read;临界区（Critical Section）是一段独占对某些共享资源访问的代码，在任意时刻只允许一个线程对共享资源进行访问。如果有多个线程试图同时访问临界区，那么在有一个线程进入后其他所有试图访问此临界区的线程将被挂起，并一直持续到进入临界区的线程离开。临界区在被释放后，其他线程可以继续抢占，并以此达到用原子方式操作共享资源的目的。临界区在使用时以CRITICAL_SECTION结构对象保护共享资源，并分别用EnterCriticalSection（）和LeaveCriticalSection（）函数去标识和释放一个临界区。所用到的CRITICAL_SECTION结构对象必须经过InitializeCriticalSection（）的初始化后才能使用，而且必须确保所有线程中的任何试图访问此共享资源的代码都处在此临界区的保护之下。否则临界区将不会起到应有的作用，共享资源依然有被破坏的可能。4.2 定义线程结构:struct ThreadInfo int Threadhao; char ThreadClass; double ThreadStartTime; double ThreadRunTime; ;此结构用来存放线程的信息,四个成员变量依次表示线程序号、线程类别、线程开始时间、线程读写持续时间。4.3 互斥对象创建互斥对象CreateMutex(NULL,FALSE,mutex_for_readcount);参数含义如下： NULL表示创建带有默认安全性的内核对象FALSE表示该互斥对象没有被任何线程所拥有mutex_for_readcount是为内核对象赋予名字。 释放互斥信号ReleaseMutex(h_Mutex); 对资源具有访问权的线程不再需要访问此资源而要离开时，必须通过ReleaseMutex（）函数来释放其拥有的互斥对象4.4 创建读者线程CreateThread(NULL,0,(LPTHREAD_START_ROUTINE)(R_ReaderThread),&thread_infoi,0,&thread_ID);参数含义如下：NULL表示创建带有默认安全性的内核对象0表示新读者线程拥有自己的堆栈，使用缺省大小：1MB。 (LPTHREAD_START_ROUTINE)(R_ReaderThread)表示新读者线程执行的线程函数的地址 &thread_infoi表示在线程启动执行时将该参数传递给读者线程函数。0表示读者线程创建后可以立即进行调度 &thread_ID表示CreateThread使用这个地址来存放系统分配 给新读者线程的I D4.5 等待函数WaitForMultipleObjects(n_thread,h_Thread,TRUE,-1);等待函数可使线程自愿进入等待状态，直到一个特定的内核对象变为已通知状态为止参数含义如下：n_thread表示线程数量。h_Thread是指向线程对象句柄的数组的指针。ture表示:在所有线程对象变为已通知状态之前，该函数将不允许调用线程运行参数 -1 告诉系统，调用线程愿意永远等待下去（无限时间量），直到该进程终止运行。Linux 采用消息队列的方式来实现消息传递。消息的发送方式是发送方不必等待，接收方检查它所收到的消息就可以继续工作下去。而接收方如果没有收到消息，也不需等待。这种通信机制相对简单，但是应用程序需要使用较复杂的方式来处理。新的消息总是放在队列的末尾，接收时并不总是从头来接收，也可以从中间来接收。 4.6 程序结构5运行结果5.1 读者优先结果图5.15.2 写者优先结果5.3数据结构以及核心算法以下是实现方法：void ReaderFun(char* file);/读者优先函数void R_ReaderThread(void *p);/处理读者优先读者线程 void R_WriterThread(void *p);/处理读者优先写者线程void WriterFun(char* file); void W_ReaderThread(void *p);void W_WriterThread(void *p);6 结论 本次操作系统课程设计完成的是读者-写者问题，通过学习对线程及其同步机制有了很的学习和掌握. 并认识到同步可以保证在一个时间内只有一个线程对某个资源有控制权。共享资源包括全局变量、公共数据成员或者句柄等。同步还可以使得有关联交互作用的代码按一定的顺序执行。同时也掌握了实现线程同步的对象有Critical_section（关键段），Event（事件），Mutex（互斥对象），Semaphores（信号量）并对这些对象理解如下： 对于关键段对象：首先，定义一个关键段对象;然后，初始化该对象。初始化时把对象设置为NOT_SINGALED，表示允许线程使用资源：如果一段程序代码需要对某个资源进行同步保护，则这是一段关键段代码。在进入该关键段代码前调用EnterCriticalSection函数，这样，其他线程都不能执行该段代码，若它们试图执行就会被阻塞。完成关键段的执行之后，调用LeaveCriticalSection函数，其他的线程就可以继续执行该段代码。如果该函数不被调用，则其他线程将无限期的等待。对于互斥对象 首先，调用CreateMutex创建互斥对象；然后，调用等待函数，可以的话利用关键资源；最后，调用RealseMutex释放互斥对象。互斥对象可以在进程间使用，但关键段对象只能用于同一进程的线程之间。对于等待函数：等待函数有：1.等待单个对象的(FOR SINGLE OBJECT): WaitForSingleObject,函数参数包括同步对象的句柄和等待时间等。如果等待时间不限制(Infinite)，则只有同步对象获得信号才返回；如果等待时间为0，则在测试了同步对象的状态之后马上返回。2.等待多个对象的(FOR MULTIPLE OBJECTS) WaitForMultipleObjects,函数参数包括同步对象的句柄，等待时间，是等待一个还是多个同步对象等等,如果等待时间不限制(Infinite)，则只有同步对象获得信号才返回；如果等待时间为0，则在测试了同步对象的状态之后马上返回。操作系统设计使我对C+有了一个很好的复习和学习，对线程的创建及同步问题及其同步对象都有了很好的理解。并能初步进行简单的程序编程。并对程序的调式过程，也使我更好了解到线程同步的具体运行过程，使我更好的理解程序。学习语言是一个漫长的过程，我想只有在不断的实践练习中，才能更好的掌握编程的技巧，提高自己的编程能力，通过此次课设也让我深深体会到自己还有很多东西需要学习，还有很多课程需要复习。总之，此次课程设计使我收益匪浅。致 谢感谢谭老师本学期对我们的教导，给予了我们莫大的支柱。感谢我的室友为我排忧解难。如果没有你们的帮助，这次课程设计很难一个人完成，在此我致以衷心的谢意。参考文献1 孙钟秀 操作系统教程M. 北京-高等教育出版社 1989.3 2 陈建峰，张荣奇等 Visual C+.NET实用编程百例M. 北京-清华大学出版社 2004.83 黄维通，鲁明羽 Visual C+程序设计教程M.北京-清华大学出版社 2005.10 4 计算机职业教育联盟主编 Visual C+ .NET基础教程与上机指导M.北京-清华大学出版社 2005.35 陈天华 面向对象程序设计与Visual C+ 6.0教程M.北京-清华大学出版社 2006.1附 录#include windows.h#include #include #include #include #include #include #define READER R /读者#define WRITER W /写者#define INTE_PER_SEC 1000 /每秒时钟中断的数目#define MAX_THREAD_NUM 64 /最大线程数#define MAX_FILE_NUM 32 /最大文件数目数#define MAX_STR_LEN 32 /字符串的长度int readcount=0; /读者数目int writecount=0; /写者数目CRITICAL_SECTION RP_Write; /临界资源CRITICAL_SECTION cs_Write;CRITICAL_SECTION cs_Read;struct ThreadInfo int serial; /线程序号 char entity; /线程类别(判断是读者还是写者线程) double delay; /线程延迟时间 double persist; /线程读写操作时间;/ 读者优先-读者线程/P:读者线程信息void RP_ReaderThread(void *p) /互斥变量 HANDLE h_Mutex; h_Mutex=OpenMutex(MUTEX_ALL_ACCESS,FALSE,mutex_for_readcount); /*HANDLE OpenMutex( DWORD dwDesiredAccess, / access flag BOOL bInheritHandle, / inherit flag LPCTSTR lpName / pointer to mutex-object name );*/ DWORD wait_for_mutex; /等待互斥变量所有权 DWORD m_delay; /延迟时间 DWORD m_persist; /读文件持续时间 int m_serial; /线程序号 / 从参数中获得信息 m_serial=(ThreadInfo*)(p)-serial ; m_delay=(DWORD)(ThreadInfo*)(p)-delay *INTE_PER_SEC); m_persist=(DWORD)(ThreadInfo*)(p)-persist *INTE_PER_SEC); Sleep(m_delay); /延迟等待 printf(读者线程 %d 发来读请求.n,m_serial); /等待互斥信号,保证对ReadCount 的访问,修改互斥 wait_for_mutex=WaitForSingleObject(h_Mutex,-1); /读者数目增加 readcount+; if(readcount=1) /第一个读者,等待资源 EnterCriticalSection(&RP_Write); ReleaseMutex(h_Mutex); /释放互斥信号 /读文件 printf(读者线程 %d 开始读文件.n,m_serial); Sleep(m_persist);/线程挂起 /退出线程 printf(读者线程 %d 完成读文件.n,m_serial); /等待互斥信号,保证对ReadCount的访问,修改互斥 wait_for_mutex=WaitForSingleObject(h_Mutex,-1); /读者数目减少 readcount-; if(readcount=0) /如果所有的读者读完,唤醒写者 LeaveCriticalSection(&RP_Write); ReleaseMutex(h_Mutex); /释放互斥信号/P:写者线程信息void RP_WriterThread(void *p) DWORD m_delay; /延迟时间 DWORD m_persist; /写文件持续时间 int m_serial; /线程序号 / 从参数中获得信息 m_serial=(ThreadInfo*)(p)-serial ; m_delay=(DWORD)(ThreadInfo*)(p)-delay *INTE_PER_SEC); m_persist=(DWORD)(ThreadInfo*)(p)-persist *INTE_PER_SEC); Sleep(m_delay); printf(写者线程 %d 发来写请求.n,m_serial); /等待资源 EnterCriticalSection(&RP_Write); /写文件 printf(写者线程 %d 开始写文件.n,m_serial); Sleep(m_persist); /退出线程 printf(写者线程 %d 完成写文件.n,m_serial); /释放资源 LeaveCriticalSection(&RP_Write);/读者优先处理函数/file:文件名void ReaderPriority(char *file) DWORD n_thread=0; /线程数目 DWORD thread_ID; /线程ID DWORD wait_for_all; /等待所有线程结束 /互斥对象 HANDLE h_Mutex; h_Mutex=CreateMutex(NULL,FALSE,mutex_for_readcount); /*HANDLE CreateMutex( LPSECURITY_ATTRIBUTES lpMutexAttributes, / pointer to security attributes BOOL bInitialOwner, / flag for initial ownership LPCTSTR lpName / pointer to mutex-object name );*/ /线程对象的数组 HANDLE h_ThreadMAX_THREAD_NUM; ThreadInfo thread_infoMAX_THREAD_NUM; readcount=0; /初始化readcount InitializeCriticalSection(&RP_Write); /初始化临界区 ifstream inFile; inFile.open (file); printf(读者优先:nn); while(inFile) /读入每一个读者,写者的信息 inFilethread_infon_thread.serial; inFilethread_infon_thread.entity; inFilethread_infon_thread.delay; inFilethread_infon_thread+.persist; inFile.get(); for(int i=0;iserial ; m_delay=(DWORD)(ThreadInfo*)(p)-delay *INTE_PER_SEC); m_persist=(DWORD)(ThreadInfo*)(p)-persist *INTE_PER_SEC); Sleep(m_delay); /延迟等待 printf(读者线程 %d 发来读请求.n,m_serial); wait_for_mutex1=WaitForSingleObject(h_Mutex1,-1); /读者进去临界区 EnterCriticalSection(&cs_Read); /阻塞互斥对象Mutex2,保证对readCount的访问和修改互斥 wait_for_mutex2=WaitForSingleObject(h_Mutex2,-1); /修改读者的数目 readcount+; if(readcount=1) / 如果是第1个读者,等待写者写完 EnterCriticalSection(&cs_Write); ReleaseMutex(h_Mutex2);/ 释放互斥信号 Mutex2 /让其他读者进去临界区 LeaveCriticalSection(&cs_Read); ReleaseMutex(h_Mutex1); /读文件 printf(读者线程 %d 开始读文件.n,m_serial); Sleep(m_persist); /退出线程 printf(读者线程 %d 完成读操作.n,m_serial); /阻塞互斥对象Mutex2,保证对readcount的访问,修改互斥 wait_for_mutex2=WaitForSingleObject(h_Mutex2,-1); readcount-; if(readcount=0) /最后一个读者,唤醒写者 LeaveCriticalSection(&cs_Write); ReleaseMutex(h_Mutex2); /释放互斥信号/写者优先-写者线程/P:写者线程信息void WP_WriterThread(void *p) DWORD wait_for_mutex3; /互斥变量 DWORD m_delay; /延迟时间 DWORD m_persist; /读文件持续时间 int m_serial; /线程序号 HANDLE h_Mutex3; h_Mutex3=OpenMutex(MUTEX_ALL_ACCESS,FALSE,mutex3); /从参数中获得信息 m_serial=(ThreadInfo*)(p)-serial ; m_delay=(DWORD)(ThreadInfo*)(p)-delay *INTE_PER_SEC); m_persist=(DWORD)(ThreadInfo*)(p)-persist *INTE_PER_SEC); Sleep(m_delay); /延迟等待 printf(写者线程 %d 发来写请求.n,m_serial); wait_for_mutex3=WaitForSingleObject(h_Mutex3,-1); writecount+; /修改写者数目 if(writecount=1) EnterCriticalSection(&cs_Read); ReleaseMutex(h_Mutex3); EnterCriticalSection(&cs_Write); printf(写者线程 %d 开始写文件.n,m_serial); Sleep(m_persist); printf(写者线程 %d 完成写文件.n,m_serial); LeaveCriticalSection(&cs_Write); wait_for_mutex3=WaitForSingleObject(h_Mutex3,-1); writecount-; if(writecount=0) LeaveCriticalSection(&cs_Read); ReleaseMutex(h_Mutex3);/写者优先处理函数/ file:文件名void WriterPriority(char * file) DWORD n_thread=0; DWORD thread_ID; DWORD wait_for_all; HANDLE h_Mutex1; h_Mutex1=CreateMutex(NULL,FALSE,mutex1); HANDLE h_Mutex2; h_Mutex2=CreateMutex(NULL,FALSE,mutex2); HANDLE h_Mutex3; h_Mutex3=CreateMutex(NULL,FALSE,