心灵梦境

读者写者问题

                                      

 

实验二   读者写者问题

实   验   报   告

 

一、实验目的

l        用信号量来实现读者写者问题。

l        学习NachOS的使用方法

l        理解和运用信号量、PV原语、进程间的同步互斥关系等基本知识。

 

二、实验内容

读者写者问题的定义如下：有一个许多进程共享的数据区，这个数据区可以是一个文件或者主存的一块空间；有一些只读取这个数据区的进程（Reader）和一些只往数据区写数据的进程(Writer)，此外还需要满足以下条件：

（1）    任意多个读进程可以同时读这个文件；

（2）    一次只有一个写进程可以往文件中写；

（3）    如果一个写进程正在进行操作，禁止任何读进程度文件。

实验要求用信号量来实现读者写者问题的调度算法。实验提供了Semaphore类，该类通过P( )、V( )两个方法实现了P、V原语的功能。实验的任务是修改Reader类的Read(int)方法以及Writer类的Write(int)方法。

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

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

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

 

三、问题分析

在Windows 2000 环境下，创建一个包含n 个线程的控制台进程。用这n 个线程来表示n个读者或写者。每个线程按相应测试数据文件的要求，进行读写操作。请用信号量机制分别实现读者优先和写者优先的读者-写者问题。

读者-写者问题的读写操作限制：

1）写-写互斥；

2）读-写互斥；

3）读-读允许；

读者优先的附加限制：如果一个读者申请进行读操作时已有另一读者正在进行读操作，则该读者可直接开始读操作。

写者优先的附加限制：如果一个读者申请进行读操作时已有另一写者在等待访问共享资源，则该读者必须等到没有写者处于等待状态后才能开始读操作。

运行结果显示要求：要求在每个线程创建、发出读写操作申请、开始读写操作和结束读写操作时分别显示一行提示信息，以确信所有处理都遵守相应的读写操作限制。

四、实现程序及说明

#include <windows.h>

#include <ctype.h>

#include <stdio.h>

#include <string.h>

#include <stdlib.h>

#include <malloc.h>

 

#define  MAX_PERSON   100  //最多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, 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 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); // 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;

 }

// 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

/* while(g_NumOfWriteRequest != 0)

 {

         //g_NumOfWriteRequest != 0 表示现在正在写，不能读

 }*/

//该语句在写者优先的时候是认为写者优先级高于读者，在有写者的时候读者需//要等候，而在读者优先的时候，不用判断是否存在写者，有读者时即开始读操//作。

 WaitForSingleObject(g_hReadSemaphore,INFINITE);//等待g_hReadSemaphore读信号,即当g_hReadSemaphore有信号时等待结束 相当于p操作

 if(g_NumOfReading ==0)

 {

  WaitForSingleObject(g_hWriteSemaphore,INFINITE); //当第一个读者到了，如果g_hWriteSemaphore信号灯灭了，说明有写者再写，读者必须等待。即互斥写操作

 }

 

 g_NumOfReading++;

 ReleaseSemaphore(g_hReadSemaphore,1,NULL); //还有读者，但是允许下一个读进程读取，相当于V操作// modify the reader's real start time

 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)

 {

  // ..  perform read operations

 }

 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");

 //g_NumOfWriteRequest++;

 

//在写者优先的时候需要用自加来初始信号值，而在读者优先的时是通过读者操作来控制信号值

 

 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)

 {

  // ..  perform write operations

}

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;

}

五、实验结果

测试数据文件格式

测试数据文件包括n 行测试数据，分别描述创建的n 个线程是读者还是写者，以及读写

操作的开始时间和持续时间。每行测试数据包括四个字段，各字段间用空格分隔。第一字段

为一个正整数，表示线程序号。第二字段表示相应线程角色，R 表示读者是，W 表示写者。

第三字段为一个正数，表示读写操作的开始时间。线程创建后，延时相应时间（单位为秒）

后发出对共享资源的读写申请。第四字段为一个正数，表示读写操作的持续时间。当线程读

写申请成功后，开始对共享资源的读写操作，该操作持续相应时间后结束，并释放共享资源。

下面是一个测试数据文件的例子：

1, W, 3, 5,

  2, W, 16, 5,

  3, R, 5, 2,

  4, W, 6, 5,

  5, R, 4, 3,

  6, R, 17,7,

试验结果如下图：

 

六、结果分析和讨论

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

进程1是W操作，在时间3时进入队列,运行时间是5,在它进入时没有进程占用资源，它既占用资源；知道它释放资源，等候的进程有3，4，5；

进程2是R操作，在时间16时进入队列,运行时间是5,在它进入时进程4占用资源，它等待资源，当4释放时占用资源；

进程3是R操作，在时间5时进入队列,运行时间是2,在它进入时进程1占用资源，它等待资源，当进程1释放资源后，由于读者优先，进程3，5同时调运资源；

进程4是W操作，在时间6时进入队列,运行时间是5,在它进入时进程1占用资源，它等待资源，当进程1释放资源后，由于读者优先，进程3，5占用资源，它依然等待，直到进程3，5都结束；

进程5是R操作，在时间4时进入队列,运行时间是3, 在它进入时进程1占用资源，它等待资源，当进程1释放资源后，由于读者优先，进程3，5同时调运资源；

进程6是R操作，在时间17时进入队列,运行时间是7,在它进入时进程2占用资源，它等待进程2释放后最后调用资源。

 

七、收获感想和体会

经过读者写者问题的编写，我对同步机构应用有了深入的了解。懂得了运用信号量实现进程间的互斥。实现了不让共享资源同时修改。用信号量上的原语操作使临界段问题的解决比较简单明了了。

【作者: nine9909】【访问统计:】【2005年07月27日 星期三 01:23】【注册】【打印】