读者-写者问题解答计算机操作系统实验报告指导资料

读者—写者问题（Readers-Writers problem）也是一个经典的并发程序设计问题，是经常出现的一种同步问题。计算机系统中的数据（文件、记录）常被多个进程共享，但其中某些进程可能只要求读数据（称为读者Reader）；另一些进程则要求修改数据（称为写者Writer）。就共享数据而言，Reader和Writer是两组并发进程共享一组数据区，要求：

（1）允许多个读者同时执行读操作；

（2）不允许读者、写者同时操作；

（3）不允许多个写者同时操作。

Reader和Writer的同步问题分为读者优先、弱写者优先（公平竞争）和强写者优先三种情况，它们的处理方式不同。

（1）读者优先。对于读者优先，应满足下列条件：

如果新读者到：

①无读者、写者，新读者可以读；

②有写者等待，但有其它读者正在读，则新读者也可以读；

③有写者写，新读者等待。

如果新写者到：

①无读者，新写者可以写；

②有读者，新写者等待；

③有其它写者，新写者等待。

单纯使用信号量不能解决读者与写者问题，必须引入计数器rc 对读进程计数；rc_mutex 是用于对计数器rc 操作的互斥信号量；write表示是否允许写的信号量；于是读者优先的程序设计如下：

int rc=0;      //用于记录当前的读者数量

semaphore rc_mutex=1;          //用于对共享变量rc 操作的互斥信号量

semaphore write=1;             //用于保证读者和写者互斥地访问的信号量

void reader()       /*读者进程*/

do{

      P(rc_mutex);                //开始对rc共享变量进行互斥访问

        rc ++;                    //来了一个读进程，读进程数加1

if (rc==1)  P(write)；                //如是第一个读进程，判断是否有写进程在临界区，

//若有，读进程等待，若无，阻塞写进程

      V(rc_mutex);               //结束对rc共享变量的互斥访问

         读文件；

      P(rc_mutex);                //开始对rc共享变量的互斥访问

        rc--;                    //一个读进程读完，读进程数减1

if (rc == 0)  V(write)；     //最后一个离开临界区的读进程需要判断是否有写进程//需要进入临界区，若有，唤醒一个写进程进临界区

      V(rc_mutex);                //结束对rc共享变量的互斥访问

} while(1)

void writer()      /*写者进程*/

do{

         P(write);                       //无读进程，进入写进程；若有读进程，写进程等待

         写文件;

V(write);                       //写进程完成；判断是否有读进程需要进入临界区， 

        //若有，唤醒一个读进程进临界区

       } while(1)

读者优先的设计思想是读进程只要看到有其它读进程正在读，就可以继续进行读；写进程必须等待所有读进程都不读时才能写，即使写进程可能比一些读进程更早提出申请。该算法只要还有一个读者在活动，就允许后续的读者进来，该策略的结果是，如果有一个稳定的读者流存在，那么这些读者将在到达后被允许进入。而写者就始终被挂起，直到没有读者为止。

（2）写者优先1。为了解决以上问题，写者优先1的设计思想是在一个写者到达时如果有正在工作的读者，那么该写者只要等待正在工作的读者完成，而不必等候其后面到来的读者就可以进行写操作。注意，该算法当一个写者在等待时，后到达的读者是在写者之后被挂起，而不是立即允许进入。

在读者优先的算法的基础上增加了一个排队信号量read，读、写进程在每次操作前都要等待read信号量。写者优先1的程序设计如下：

int rc=0;     //用于记录当前的读者数量

semaphore rc_mutex=1;      //用于对共享变量rc 操作的互斥信号量

semaphore wc_mutex=1;      //用于保证读者和写者互斥地访问的信号量

semaphore write=1;         //用于保证读者和写者互斥地访问的信号量

semaphore read=1;          //用于保证在写进程封锁其后续的读进程的信号量

void reader()      /*读者进程*/

do{

P(read);                       //若有写进程，后续读进程等待，在read队列上排队

P(rc_mutex);                   //开始对rc共享变量进行互斥访问

rc++;                       //来了一个读进程，读进程数加1 

if rc=1 then  P(write);          //第一个读进程需要判断是否有写进程在临界区，若有，

//读进程需要等待，若没有，阻塞写进程

V(rc_mutex);                    //结束对rc共享变量的互斥访问

V(read);                        //从 read队列中唤醒一个进程

Reading the file;

P(rc_mutex);                    //开始对rc共享变量的互斥访问

rc--;                          //一个读进程读完，读进程数减1

if rc=0 then  V(write);     //最后一个离开临界区的读进程需要判断是否有写进程

/        //需要进入临界区，若有，唤醒一个写进程进临界区

V(rc_mutex);                //结束对rc共享变量的互斥访问

}

void  writer()           /*写者进程*/

do{

P(read);                         //无读进程，写进程进入；有读进程，在read排队，其后

//到来的读进程排在该队列写者之后

P(write);                        //若有读进程在读，等待现有读进程读完才可写

Writeing the file;    

V(write);                    //写进程完成；判断是否有读进程需要进入临界区，若有， 

    //唤醒一个读进程进临界区

V(read);                         //从 read队列中唤醒一个进程

注意，该算法当第一个写者已经P(read)后，read变为0，来了N个读者，他们都停留在它的P(read)这一句。那么会出现什么问题呢？此时，如果原来的写者完成了，紧接又来了一个写者，写者需要P(read)。这个时候，由于N个读者都已经在这个写者之前P(read)了，所以这个写者需要排队排在这N个读者分别都得到P(read)后才能得到执行，这个就不是写者优先了，而是读者写者公平竞争。

（3）写者优先2。为了保证写者相对于读者的优先,需要提高写者进程的优先级。这里除增加一个排队信号量read，让读者和写者在读写之前都在此信号量上排队。还需增加一个信号量write_first，来保证写者优先。写者优先2的程序设计如下：

int rc, wc = 0; //用于读者，写者的计数

semaphore read, write = 1;              //用于读进程和写进程的互斥信号量

semaphore rc_mutex, wc_mutex, write_first = 1;//用于读时、写时和写者优先的互斥

    void reader(){    /*读者进程*/

while(1){

    P(write_first);                        //用来保证写者优先。若有写进程，第二个后的读者等待在这

      P(read);                          //若有写进程，第一个读进程等待； 若无写进程，读进程进入

P(rc_mutex);                        //开始对rc共享变量进行互斥访问

            rc++;                          //更新读进程数

            if (rc==1) P(write);               //第一个读进程需要判断是否有写进程在临界区，若有，读进程

//等待，若无，阻塞写进程

V(rc_mutex);                           //结束对rc共享变量的互斥访问

V(read);                           //从 read队列中唤醒一个进程

V(write_first); 

              doReading();

P(rc_mutex);              //开始对rc共享变量进行互斥访问

rc--;                  //更新读进程数量

if (rc==0) V(write);     //最后一个离开临界区的读进程需要判断是否有写进程

    //需要进入临界区，若有，唤醒一个写进程进临界区

V(rc_mutex);      //结束对rc共享变量的互斥访问

     } 

} 

void writer(){         /*写者进程*/

while(1){ 

   P(wc_mutex);                               //开始对wc共享变量进行互斥访问

      wct++;                                 //更新写进程数

      if (wc==1)  P(read);                 //第一个写进程需要判断是否有读进程在临界区，若有，写进程    

//阻塞，若无，阻塞新的读进程

   V(wc_mutex);                           //结束对wc共享变量的互斥访问

   P(write);                                  //同一时刻只能有一个写进程进行写操作

       do writing(); 

V(write);                                  //结束对写操作的

   P(wc_mutex);                                 //开始对wc的互斥访问

       wc--;                                  //更新写进程数量

       if (wc==0)  V(read);                  //最后一个离开临界区的写进程需要判断是否有读进程需要

//进入，若有，唤醒一个读进程进入临界区

V(wc_mutex);                             //结束对wc的互斥访问

    } 

}

    这里write_first的设立是为了保证写者优先。因为write_first的初值是1，在读进程，执行完P(write_first)后等在P(read)这一句的读者最多只有1个。

对于read信号量，每个读进程最开始都要申请一次，之后在真正做读操作前即让出，这使得写进程可以随时申请到 read。而写进程，只有第一个写进程需要申请 read，之后就一直占着不放了，直到所有写进程都完成后才让出。等于只要有写进程提出申请就禁止读进程在read信号量上排队。

假设一个写进程正在写时，接着后续有n个读者正在等待，这时又有一个新的写者要写，比较一下写者优先1和写者优先2的情况：写者优先1新来的写者需要等待n+1次V（read）操作，而写者优先2新来的写者只需等待2次V（read）操作，变相提高了写进程的优先级。

与上一篇《秒杀多线程第十篇 生产者消费者问题》的生产者消费者问题一样，读者写者也是一个非常著名的同步问题。读者写者问题描述非常简单，有一个写者很多读者，多个读者可以同时读文件，但写者在写文件时不允许有读者在读文件，同样有读者在读文件时写者也不去能写文件。

上面是读者写者问题示意图，类似于生产者消费者问题的分析过程，首先来找找哪些是属于“等待”情况。

第一．写者要等到没有读者时才能去写文件。

第二．所有读者要等待写者完成写文件后才能去读文件。

找完“等待”情况后，再看看有没有要互斥访问的资源。由于只有一个写者而读者们是可以共享的读文件，所以按题目要求并没有需要互斥访问的资源。类似于上一篇中美观的彩色输出，我们对生产者输出代码进行了颜色设置（在控制台输出颜色设置参见《VC 控制台颜色设置》）。因此在这里要加个互斥访问，不然很有可能在写者线程将控制台颜色设置还原之前，读者线程就已经有输出了。所以要对输出语句作个互斥访问处理，修改后的读者及写者的输出函数如下所示：

[cpp] view plaincopy

1.//读者线程输出函数  

2.void ReaderPrintf(char *pszFormat, ...)  

3.{  

4.    va_list   pArgList;  

5.    va_start(pArgList, pszFormat);  

6.    EnterCriticalSection(&g_cs);  

7.    vfprintf(stdout, pszFormat, pArgList);  

8.    LeaveCriticalSection(&g_cs);  

9.    va_end(pArgList);  

10.}  

11.//写者线程输出函数  

12.void WriterPrintf(char *pszStr)  

13.{  

14.    EnterCriticalSection(&g_cs);  

15.    SetConsoleColor(FOREGROUND_GREEN);  

16.    printf("     %s\\n", pszStr);  

17.    SetConsoleColor(FOREGROUND_RED | FOREGROUND_GREEN | FOREGROUND_BLUE);  

18.    LeaveCriticalSection(&g_cs);  

19.}  

读者线程输出函数所使用的可变参数详见《C,C++中使用可变参数》。

       解决了互斥输出问题，接下来再考虑如何实现同步问题。可以设置一个变量来记录正在读文件的读者个数，第一个开始读文件的读者要负责将关闭允许写者进入的标志，最后一个结束读文件的读者要负责打开允许写者进入的标志。这样第一种“等待”情况就解决了。第二种“等待”情况是有写者进入时所以读者不能进入，使用一个事件就可以完成这个任务了——所有读者都要等待这个事件而写者负责触发事件和设置事件为未触发。详细见代码中注释：

[cpp] view plaincopy

1.//读者与写者问题  

2.#include   

3.#include   

4.#include   

5.//设置控制台输出颜色  

6.BOOL SetConsoleColor(WORD wAttributes)  

7.{  

8.    HANDLE hConsole = GetStdHandle(STD_OUTPUT_HANDLE);  

9.    if (hConsole == INVALID_HANDLE_VALUE)  

10.        return FALSE;  

11.      

12.    return SetConsoleTextAttribute(hConsole, wAttributes);  

13.}  

14.const int READER_NUM = 5;  //读者个数  

15.//关键段和事件  

16.CRITICAL_SECTION g_cs, g_cs_writer_count;  

17.HANDLE g_hEventWriter, g_hEventNoReader;  

18.int g_nReaderCount;  

19.//读者线程输出函数(变参函数的实现)  

20.void ReaderPrintf(char *pszFormat, ...)  

21.{  

22.    va_list   pArgList;  

23.      

24.    va_start(pArgList, pszFormat);  

25.    EnterCriticalSection(&g_cs);  

26.    vfprintf(stdout, pszFormat, pArgList);  

27.    LeaveCriticalSection(&g_cs);  

28.    va_end(pArgList);  

29.}  

30.//读者线程函数  

31.unsigned int __stdcall ReaderThreadFun(PVOID pM)  

32.{  

33.    ReaderPrintf("     编号为%d的读者进入等待中...\\n", GetCurrentThreadId());  

34.    //等待写者完成  

35.    WaitForSingleObject(g_hEventWriter, INFINITE);  

36.  

37.    //读者个数增加  

38.    EnterCriticalSection(&g_cs_writer_count);  

39.    g_nReaderCount++;  

40.    if (g_nReaderCount == 1)  

41.        ResetEvent(g_hEventNoReader);  

42.    LeaveCriticalSection(&g_cs_writer_count);  

43.  

44.    //读取文件  

45.    ReaderPrintf("编号为%d的读者开始读取文件...\\n", GetCurrentThreadId());  

46.  

47.    Sleep(rand() % 100);  

48.  

49.    //结束阅读,读者个数减小,空位增加  

50.    ReaderPrintf(" 编号为%d的读者结束读取文件\\n", GetCurrentThreadId());  

51.  

52.    //读者个数减少  

53.    EnterCriticalSection(&g_cs_writer_count);  

54.    g_nReaderCount--;  

55.    if (g_nReaderCount == 0)  

56.        SetEvent(g_hEventNoReader);  

57.    LeaveCriticalSection(&g_cs_writer_count);  

58.  

59.    return 0;  

60.}  

61.//写者线程输出函数  

62.void WriterPrintf(char *pszStr)  

63.{  

.    EnterCriticalSection(&g_cs);  

65.    SetConsoleColor(FOREGROUND_GREEN);  

66.    printf("     %s\\n", pszStr);  

67.    SetConsoleColor(FOREGROUND_RED | FOREGROUND_GREEN | FOREGROUND_BLUE);  

68.    LeaveCriticalSection(&g_cs);  

69.}  

70.//写者线程函数  

71.unsigned int __stdcall WriterThreadFun(PVOID pM)  

72.{  

73.    WriterPrintf("写者线程进入等待中...");  

74.    //等待读文件的读者为零  

75.    WaitForSingleObject(g_hEventNoReader, INFINITE);  

76.    //标记写者正在写文件  

77.    ResetEvent(g_hEventWriter);  

78.          

79.    //写文件  

80.    WriterPrintf("  写者开始写文件.....");  

81.    Sleep(rand() % 100);  

82.    WriterPrintf("  写者结束写文件");  

83.  

84.    //标记写者结束写文件  

85.    SetEvent(g_hEventWriter);  

86.    return 0;  

87.}  

88.int main()  

.{  

90.    printf("  读者写者问题\\n");  

91.    printf(" -- by MoreWindows( http://blog.csdn.net/MoreWindows ) --\\n\\n");  

92.  

93.    //初始化事件和信号量  

94.    InitializeCriticalSection(&g_cs);  

95.    InitializeCriticalSection(&g_cs_writer_count);  

96.  

97.    //手动置位,初始已触发  

98.    g_hEventWriter = CreateEvent(NULL, TRUE, TRUE, NULL);  

99.    g_hEventNoReader  = CreateEvent(NULL, FALSE, TRUE, NULL);  

100.    g_nReaderCount = 0;  

101.  

102.    int i;  

103.    HANDLE hThread[READER_NUM + 1];  

104.    //先启动二个读者线程  

105.    for (i = 1; i <= 2; i++)  

106.        hThread[i] = (HANDLE)_beginthreadex(NULL, 0, ReaderThreadFun, NULL, 0, NULL);  

107.    //启动写者线程  

108.    hThread[0] = (HANDLE)_beginthreadex(NULL, 0, WriterThreadFun, NULL, 0, NULL);  

109.    Sleep(50);  

110.    //最后启动其它读者结程  

111.    for ( ; i <= READER_NUM; i++)  

112.        hThread[i] = (HANDLE)_beginthreadex(NULL, 0, ReaderThreadFun, NULL, 0, NULL);  

113.    WaitForMultipleObjects(READER_NUM + 1, hThread, TRUE, INFINITE);  

114.    for (i = 0; i < READER_NUM + 1; i++)  

115.        CloseHandle(hThread[i]);  

116.  

117.    //销毁事件和信号量  

118.    CloseHandle(g_hEventWriter);  

119.    CloseHandle(g_hEventNoReader);  

120.    DeleteCriticalSection(&g_cs);  

121.    DeleteCriticalSection(&g_cs_writer_count);  

122.    return 0;  

123.}  

运行结果如下所示：

根据结果可以看出当有读者在读文件时，写者线程会进入等待状态中。当写者线程在写文件时，读者线程也会排队等待，说明读者和写者已经完成了同步。