实验3读者写者问题与进程同步中学教育试题中学教育试题.pdf

《实验3读者写者问题与进程同步中学教育试题中学教育试题.pdf》由会员分享，可在线阅读，更多相关《实验3读者写者问题与进程同步中学教育试题中学教育试题.pdf（40页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、实验 3 读者/写者问题与进程同步 3.1 实验目的 理解临界区和进程互斥的概念，掌握用信号量和 PV操作实现进程互斥的方法。3.2 实验要求 在windows 或者linux 环境下编写一个控制台应用程序，该程序运行时能创建N个线程，其中既有读者线程又有写者线程，它们按照事先设计好的测试数据进行读写操作。请用信号量和 PV操作实现读者/写者问题。读者/写者问题的描述如下：有一个被许多进程共享的数据区，这个数据区可以是一个文件，或者主存的一块空间，甚至可以是一组处理器寄存器。有一些只读取这个数据区的进程（reader）和一些只往数据区中写数据的进程（writer）。以下假设共享数据区是文件。这

2、些读者和写者对数据区的操作必须满足以下条件：读读允许；读写互斥；写写互斥。这些条件具体来说就是：（1）任意多的读进程可以同时读这个文件；（2）一次只允许一个写进程往文件中写；（3）如果一个写进程正在往文件中写，禁止任何读进程或写进程访问文件；（4）写进程执行写操作前，应让已有的写者或读者全部退出。这说明当有读者在读文件时不允许写者写文件。对于读者-写者问题，有三种解决方法：1、读者优先 除了上述四个规则外，还增加读者优先的规定，当有读者在读文件时，对随后到达的读者和写者，要首先满足读者，阻塞写者。这说明只要有一个读者活跃，那么随后而来的读者都将被允许访问文件，从而导致写者长时间等待，甚至有可能

3、出现写者被饿死的情况。2、写者优先 除了上述四个规则外，还增加写者优先的规定，即当有读者和写者同时等待时，首先满足写者。当一个写者声明想写文件时，不允许新的读者再访问文件。3、无优先 除了上述四个规则外，不再规定读写的优先权，谁先等待谁就先使用文件。3.3 实验步骤 3.3.1 算法分析 1、错误的解法 有同学认为，可以将文件视为临界资源，使用临界资源的代码就构成临界区，为了对临界区进行管理，只需设置一个互斥信号量r_w_w，读或者写之前执行 P(r_w_w)，之后执行 V(r_w_w)即可，从而得到图 3-1 所示的算法描述。该方法虽然能满足读写互斥和写写互斥，但是不满足读读允许，只要有一个

4、读者在读文件，其他的读者都被阻塞了。图 3-1 错误的解法 semaphore r_w_w=1;reader()P(r_w_w)；读文件；V(r_w_w)；writer()P(r_w_w)；写文件；V(r_w_w)；可见，单纯使用互斥信号量不能解决读者/写者问题，还需要引入计数器对读者进行记数。2、读者优先 如何纠正上述解法中存在的错误呢？其实，对于相继到达的一批读者，并不是每个读者都需要执行 P(r_w_w)和 V(r_w_w)。在这批读者中，只有最先到达的读者才需要执行 P(r_w_w)，与写者竞争对文件的访问权，若执行 P(r_w_w)成功则获得了文件的访问权，其他的读者可直接访问文件；

5、同理，只有最后退出临界区的读者需要执行 V(r_w_w)来归还文件访问权。为了记录正在读文件的一批读者的数量，需要设置一个整型变量 readercount，每一个读者到达时都要将 readercount加 1，退出时都要将 readercount减 1。由于只要有一个读者在读文件，便不允许写者写文件，所以，仅当 readercount=0时，即尚无读者在读文件时，读者才需要执行 P(r_w_w)操作。若 P(r_w_w)操作成功，读者便可去读文件，相应地，readercount+1。同理，仅当在执行了 readercount减 1 操作后其值为0 时，才需要执行 V(r_w_w)操作，以便让写

6、者写文件。又因为 readercount是一个可被多个读者访问的临界资源，所以应该为它设置一个互斥信号量 readercount_mutex.。每个读者在访问 readercount之前执行 P(readercount_mutex)，之后执行 V(readercount_mutex)。通过上述分析得到图 3-2 所示的算法描述，其中的数字表示语句对应的行号。图 3-2 读者优先算法 01 semaphore r_w_w=1;02 semaphore readercount_mutex=1;03 int readercount=0;04 reader()05 P(readercount_mute

7、x);06 if(readercount=0)P(r_w_w);07 readercount+;08 V(readercount_mutex);09 读文件;10 P(readercount_mutex);11 readercount-;12 if(readercount=0)V(r_w_w);13 V(readercount_mutex);14 15 16 writer()17 P(r_w_w);18 写文件;19 V(r_w_w);20 下面对该算法的调度效果进行分析。假设最初没有进程在访问文件。过了一会，就会有很多读者和写者到达。对它们可能有两种调度情形。情形 1 最先调度写者 写者执行

8、 P(r_w_w)操作成功，将 r_w_w的值变为 0，获得文件的访问权；其它的写者执行 P(r_w_w)将 r_w_w 的值变为负数，从而阻塞在信号量 r_w_w 上；第一个读者执行P(readercount_mutex)成功，将信号量 readercount_mutex的值变为 0，然后判断readercount是 0，所以执行 P(r_w_w)，将 r_w_w 的值减 1 后仍然为负数从而阻塞在信号量r_w_w 上，其它的读者执行 P(readercount_mutex)将信号量 readercount_mutex的值变为负数，从而阻塞在信号量 readercount_mutex上。验要

9、求在或者环境下编写一个控制台应用程序该程序运行时能创建个线程其中既有读者线程又有写者线程它们按照事先设计好的测试数据进行读写操作请用信号量和操作实现读者写者问题读者写者问题的描述如下有一个被许多进程据区的进程和一些只往数据区中写数据的进程以下假设共享数据区是文件这些读者和写者对数据区的操作必须满足以下条件读读允许读写互斥写写互斥这些条件具体来说就是任意多的读进程可以同时读这个文件一次只允许一个写进者或读者全部退出这说明当有读者在读文件时不允许写者写文件对于读者写者问题有三种解决方法读者优先除了上述四个规则外还增加读者优先的规定当有读者在读文件时对随后到达的读者和写者要首先满足读者阻塞写者这说明

10、只例如，对于请求序列 w1,w2,r1,w3,r2,r3，我们用图表形象地刻画进程的活动，图表中包括读者计数器的值、信号量readercount_mutex和r_w_w的值和队列以及访问文件的进程。初始状态。没有进程使用文件，计数器 readercount的值是 0，信号量readercount_mutex和 r_w_w 的值都是 1，队列都是空，参见图 3-3；w1请求写文件，所以执行语句 17，将信号量 r_w_w 的值减 1 后变成 0，w1获得文件使用权，执行语句 18，开始写文件，参见图 3-4；在 w1尚未写完时，w2提出写请求，所以执行语句 17，将信号量 r_w_w的值减 1

11、后变成负 1，w2被阻塞在信号量 r_w_w 上，参见图 3-5；同时 r1 提出读请求，所以执行语句 5，将信号量 readercount_mutex的值减 1 后变成 0，接着执行语句 6，判断 readercount的值是 0，所以执行 P(r_w_w)，将信号量 r_w_w的值减 1 后变成-2，r1 被阻塞在信号量 r_w_w上，参见图 3-6；同时 w3提出写请求，所以执行语句 17，将信号量 r_w_w 的值减 1 后变成-3，w3被阻塞在信号量 r_w_w 上，参见图 3-7；同时 r2 提出读请求，所以执行语句 5，将信号量 readercount_mutex的值减 1 后变

12、成-1，r2 被阻塞在信号量 readercount_mutex上，参见图 3-8；同时 r3 提出读请求，所以执行语句 5，将信号量 readercount_mutex的值减 1 后变成-2，r3 被阻塞在信号量 readercount_mutex上，参见图 3-9；w1写完文件，执行语句 19，将信号量 r_w_w的值加 1 后变成-2，并唤醒 w2，w2接着执行语句 18，开始写文件，参见图 3-10；w1请求 readercount=0 readercount_mutex 1 NULL r_w_w 0 NULL 访问文件者：w1 图 3-4 初始状态 readercount=0 rea

13、dercount_mutex 1 NULL r_w_w 1 NULL 访问文件者：无 图 3-3 w2请求 readercount=0 readercount_mutex 1 NULL r_w_w -1 w2 访问文件者：w1 图 3-5 r1 请求 readercount=0 readercount_mutex 0 NULL r_w_w -2 w2,r1 访问文件者：w1 图 3-6 验要求在或者环境下编写一个控制台应用程序该程序运行时能创建个线程其中既有读者线程又有写者线程它们按照事先设计好的测试数据进行读写操作请用信号量和操作实现读者写者问题读者写者问题的描述如下有一个被许多进程据区的进

14、程和一些只往数据区中写数据的进程以下假设共享数据区是文件这些读者和写者对数据区的操作必须满足以下条件读读允许读写互斥写写互斥这些条件具体来说就是任意多的读进程可以同时读这个文件一次只允许一个写进者或读者全部退出这说明当有读者在读文件时不允许写者写文件对于读者写者问题有三种解决方法读者优先除了上述四个规则外还增加读者优先的规定当有读者在读文件时对随后到达的读者和写者要首先满足读者阻塞写者这说明只 w2写完文件，执行语句 19，将信号量 r_w_w的值加 1 后变成-1，并唤醒 r1，r1 接着执行语句 7，将 readercount的值加 1 后变成 1，执行语句 8，将信号量 readerco

15、unt_mutex的值加 1 后变成-1，并唤醒 r2，r1 执行语句 9，开始读文件；被唤醒的 r2 执行语句 6，判断 readercount的值不是 0，所以执行语句 7，将 readercount的值加 1 后变成 2，执行语句 8，将信号量 readercount_mutex的值加 1 后变成 0，并唤醒 r3，r2 执行语句 9，开始读文件；被唤醒的r3 执行语句6，判断readercount的值不是0，所以执行语句7，将readercount的值加 1 后变成 3，执行语句 8，将信号量 readercount_mutex的值加 1 后变成 1，r3 执行语句 9，开始读文件。这

16、样三个读者同时读文件，参见图 3-11；w3请求 readercount=0 readercount_mutex 0 NULL r_w_w -3 w2,r1,w3 访问文件者：w1 图 3-7 r2 请求 readercount=0 readercount_mutex -1 r2 r_w_w -3 w2,r1,w3 访问文件者：w1 图 3-8 w1结束，唤醒 w2 readercount=0 readercount_mutex -2 r2,r3 r_w_w -2 r1,w3 访问文件者：w2 图 3-10 r1,r2,r3结束,唤醒 w3 readercount=0 readercount_

17、mutex 1 NULL r_w_w 0 NULL 访问文件者：w3 图 3-12 r3 请求 readercount=0 readercount_mutex -2 r2,r3 r_w_w -3 w2,r1,w3 访问文件者：w1 图 3-9 w2结束,唤醒 r1,r1 唤醒 r2,r2唤醒 r3 readercount=3 readercount_mutex 1 NULL r_w_w -1 w3 访问文件者：r1,r2,r3 图 3-11 验要求在或者环境下编写一个控制台应用程序该程序运行时能创建个线程其中既有读者线程又有写者线程它们按照事先设计好的测试数据进行读写操作请用信号量和操作实现读

18、者写者问题读者写者问题的描述如下有一个被许多进程据区的进程和一些只往数据区中写数据的进程以下假设共享数据区是文件这些读者和写者对数据区的操作必须满足以下条件读读允许读写互斥写写互斥这些条件具体来说就是任意多的读进程可以同时读这个文件一次只允许一个写进者或读者全部退出这说明当有读者在读文件时不允许写者写文件对于读者写者问题有三种解决方法读者优先除了上述四个规则外还增加读者优先的规定当有读者在读文件时对随后到达的读者和写者要首先满足读者阻塞写者这说明只当 r1、r2 和 r3 读完文件时，都执行语句 1014，并由最后一个执行语句 1014 的读者执行 V(r_w_w)，将信号量 r_w_w 的值

19、加 1 后变成 0，并唤醒 w3，w3接着执行语句 18，开始写文件，参见图 3-12；当 w3写完文件时，执行语句 19，将信号量 r_w_w的值加 1 后变成 1，回到初始状态。可见，对于请求序列 w1,w2,r1,w3,r2,r3，实际访问文件的顺序是 w1,w2,r1,r2,r3,w3。虽然 w3比 r2、r3 先提出请求，但是由于在此之前已经有 r1 在读文件，所以优先响应读者r2、r3，阻塞写者 w3。如果在 w3之后不断有新的读者到达，则 w3 将一直被阻塞，直至被饿死。情形 2 最先调度读者 第一个读者执行P(readercount_mutex)成功，将信号量readercou

20、nt_mutex的值变为0，接着该读者判断 readercount是 0，所以执行 P(r_w_w)操作成功，获得文件的访问权，将r_w_w 的值变为 0，然后将 readercount变成 1，执行 V(readercount_mutex)，之后开始读文件；随后的写者执行 P(r_w_w)将 r_w_w 的值变为负数，从而阻塞在信号量 r_w_w 上；其它的读者执行 P(readercount_mutex)成功，判断 readercount不是 0，所以直接将readercount的值再加 1，执行 V(readercount_mutex)，之后开始读文件。可见多个读者可以同时读文件，并在读

21、文件时阻塞写者。3、写者优先 通过增加信号量并修改上述程序可以得到写者优先算法。为了实现写者优先算法，需要将写者和读者分开排队，并且第一个读者和其它读者也要分开排队。这样就需要三个队列，一个是写者排队的地方，另一个是第一个读者排队的地方，第三个是其它读者排队的地方。相应地需要设置三个信号量，r_w_w、first_reader_wait和 reader_wait。当一个写者声明想写文件时，可以让新的读者中的第一个到 first_reader_wait上排队等待；当有读者阻塞在 first_reader_wait上时，让其它读者阻塞在 reader_wait上；当有一个写者在写文件时，其它写者到

22、 r_w_w 上排队。只要有活跃的写者或者写者队列不为空，则阻塞新到达的读者。为了记录已经发出声明的写者数量，需要设置一个整数 writercount，以表示声明要写文件的写者数目。由于只要有一个写者到达，就不允许读者去读，因此仅当 writercount=0，表示无写者声明写时，写者才需要执行 P(first_reader_wait)操作，若操作成功，写者便可以执行 P(r_w_w)去竞争写文件权利。其它写者不需要再向读者声明，可以直接执行 P(r_w_w)去竞争写文件权利。同理仅当写者在执行writercount减1操作后其值为0时，才需要执行V(first_reader_wait)操作，

23、以便唤醒第一个被阻塞的读者去读文件。又因为 writercount是一个可被多个写者访问的临界资源，所以，应该为它设置一个互斥信号量 writer_mutex。通过上述分析得到图 3-13 的算法描述。下面对该算法的调度效果进行分析。假设最初没有进程在访问文件。过了一会，就会有很多读者和写者到达。对它们可能有两种调度情形。情形 1 最先调度写者 写者执行 P(writercount_mutex)，将 writercount_mutex的值变为 0，并判断writercount是 0，从而执行 P(first_reader_wait)，将 first_reader_wait的值变为 0，成功地向

24、读者声明了写访问意图，接着将 writercount变为 1，执行 V(writercount_mutex)，将 writercount_mutex的值变为 1。然后写者执行 P(r_w_w)操作，将 r_w_w 的值变为 0，成功地获得了文件的写访问权利。第一个写者开始写文件；其它的写者执行 P(writercount_mutex)，判断 writercount不是 0，所以直接将writercount加 1，执行 V(writercount_mutex)，然后执行 P(r_w_w)操作，将 r_w_w 的值变验要求在或者环境下编写一个控制台应用程序该程序运行时能创建个线程其中既有读者线程又

25、有写者线程它们按照事先设计好的测试数据进行读写操作请用信号量和操作实现读者写者问题读者写者问题的描述如下有一个被许多进程据区的进程和一些只往数据区中写数据的进程以下假设共享数据区是文件这些读者和写者对数据区的操作必须满足以下条件读读允许读写互斥写写互斥这些条件具体来说就是任意多的读进程可以同时读这个文件一次只允许一个写进者或读者全部退出这说明当有读者在读文件时不允许写者写文件对于读者写者问题有三种解决方法读者优先除了上述四个规则外还增加读者优先的规定当有读者在读文件时对随后到达的读者和写者要首先满足读者阻塞写者这说明只为负数，写者依次被阻塞在信号量 r_w_w上；第 一 个 读 者 执 行 P

26、(reader_wait)，将 reader_wait的 值 变 为 0，接 着 执 行P(first_reader_wait)，将first_reader_wait的 值 变 为 负1，阻 塞 在 信 号 量first_reader_wait上；其它读者执行 P(reader_wait)，将 reader_wait的值变为负数，依次阻塞在 reader_wait上。当第一个写者写完文件后，执行 V(r_w_w)，唤醒一个写者并将写者计数器 writercount减 1，被唤醒的写者可以写文件，写完后执行 V(r_w_w)，唤醒下一个写者并将写者计数器writercount减 1，直到最后一个

27、写者将 writercount减为 0，才执行 V(first_reader_wait)唤醒第一个阻塞的读者。被唤醒的读者执行 P(readercount_mutex)，然后判断 readercount是 0，从而执行 P(r_w_w)，由于最后一个写者写完文件后，r_w_w 的值已经还原为 1，所以被唤醒的读者执行 P(r_w_w)成功，将 r_w_w 的值变为 0，获得文件的读访问权。接着将 readercount的值加到 1，执行 V(readercount_mutex)，再执行 V(reader_wait)，唤醒第二个等待的读者，第一个读者执行 V(first_reader_wait)

28、，将 first_reader_wait的值还原到 1。第一个读者可以读文件了。若没有新的写者到达，则第二个读者执行 P(first_reader_wait)成功，执行P(readercount_mutex)并判断 readercount不是 0，将 readercount加到 2，执行V(readercount_mutex)，再 执 行V(reader_wait)唤 醒 第 三 个 读 者，再 执 行V(first_reader_wait)，第二个读者也可以读文件了。图 3-13 写者优先算法 01 semaphore r_w_w=1;02 semaphore reader_wait=1;0

29、3 semaphore first_reader_wait=1;04 semaphore readercount_mutex=1;05 semaphore writercount_mutex=1;06 int writercount=0;07 int readercount=0;08 reader()09 P(reader_wait);10 P(first_reader_wait);11 P(readercount_mutex);12 if(readercount=0)P(r_w_w);13 readercount+;14 V(readercount_mutex);15 V(reader_wa

30、it);16 V(first_reader_wait);17 读文件;18 P(readercount_mutex);19 readercount-;20 if(readercount=0)V(r_w_w);21 V(readercount_mutex);22 23 writer()24 P(writercount_mutex);25 if(writercount=0)P(first_reader_wait);26 writercount+;27 V(writercount_mutex);28 P(r_w_w);29 写文件;30 V(r_w_w);31 P(writercount_mutex

31、);32 writercount-;33 if(writercount=0)V(first_reader_wait);34 V(writercount_mutex);35 情形 2 最先调度读者 验要求在或者环境下编写一个控制台应用程序该程序运行时能创建个线程其中既有读者线程又有写者线程它们按照事先设计好的测试数据进行读写操作请用信号量和操作实现读者写者问题读者写者问题的描述如下有一个被许多进程据区的进程和一些只往数据区中写数据的进程以下假设共享数据区是文件这些读者和写者对数据区的操作必须满足以下条件读读允许读写互斥写写互斥这些条件具体来说就是任意多的读进程可以同时读这个文件一次只允许一个写进

32、者或读者全部退出这说明当有读者在读文件时不允许写者写文件对于读者写者问题有三种解决方法读者优先除了上述四个规则外还增加读者优先的规定当有读者在读文件时对随后到达的读者和写者要首先满足读者阻塞写者这说明只第 一 个 读 者 执 行P(reader_wait)，将reader_wait的 值 变 为0，执 行P(first_reader_wait)，将 first_reader_wait的值变为 0，向写者声明有读者要读文件，接着执行 P(readercount_mutex)，并判断 readercount是 0 所以执行 P(r_w_w)，将 r_w_w的值变为 0，成功地获得了文件的读访问权，

33、将读者计数器 readercount加到 1，执行V(readercount_mutex)，V(reader_wait)，V(first_reader_wait)，将 reader_wait和first_reader_wait的值依次还原为 1。之后，第一个读者开始读文件。若在第一个读者读文件的过程中没有写者到达，则其它读者可以同时读文件；若在读者读文件时，有写者到达，则第一个到达的写者执行 P(writercount_mutex)，将writercount_mutex的 值 变 为0，并 判 断writercount是0，从 而 执 行P(first_reader_wait)，将 first

34、_reader_wait的值变为 0，成功地向读者声明了写访问意图，接着将 writercount变为 1，执行 V(writercount_mutex)，将 writercount_mutex的值变为 1。然后写者执行 P(r_w_w)操作，（由于有读者在读文件，所以）将 r_w_w 的值变为负1，写者被阻塞在信号量 r_w_w 上；当在读文件的所有读者都读完文件后，由最后一个退出的读者执行 V(r_w_w)唤醒写者。第一个写者开始写文件。4、无优先 除了在读者优先时需要的信号量 r_w_w和 readercount_mutex之外，还需要设置一个信号量 wait 供读者和写者排队。读者和写

35、者都排在 wait 队列上。若有读者在读文件，则第一个写者阻塞在 r_w_w 上，其它的写者和读者阻塞在 wait 上；若有一个写者在写文件，则其它写者和读者都阻塞在 wait 上。无优先的算法描述如图 3-14 所示。图 3-14 无优先算法 01 semaphore r_w_w=1;02 semaphore wait=1;03 semaphore readercount_mutex=1;04 int readercount=0;05 reader()06 P(wait);07 P(readercount_mutex);08 if(readercount=0)P(r_w_w);09 read

36、ercount+;10 V(readercount_mutex);11 V(wait);12 读文件;13 P(readercount_mutex);14 readercount-;15 if(readercount=0)V(r_w_w);16 V(readercount_mutex);17 18 writer()19 P(wait);20 P(r_w_w);21 写文件;22 V(r_w_w);23 V(wait);24 下面对该算法的调度效果进行分析。最初没有进程在访问文件。过了一会，就会有很多读者和写者到达。对它们可能有两种调度情形。情形 1 最先调度写者 写者执行 P(wait)操作成

37、功，将 wait 的值变为 0，再执行 P(r_w_w)操作成功，将 r_w_w的值变为 0，获得文件的访问权，写者可以写文件了。其它的写者或者读者执行 P(wait)操作，将 wait 的值变为负数，从而依次阻塞在信号量 wait 上；第一个写者写完文件后，执行 V(r_w_w)，将 r_w_w的值还原为 1，再执行 V(wait)唤醒排在 wait 队列最前面的一个进程，可能是读者，也可能是写者。情形 2 最先调度读者 验要求在或者环境下编写一个控制台应用程序该程序运行时能创建个线程其中既有读者线程又有写者线程它们按照事先设计好的测试数据进行读写操作请用信号量和操作实现读者写者问题读者写者

38、问题的描述如下有一个被许多进程据区的进程和一些只往数据区中写数据的进程以下假设共享数据区是文件这些读者和写者对数据区的操作必须满足以下条件读读允许读写互斥写写互斥这些条件具体来说就是任意多的读进程可以同时读这个文件一次只允许一个写进者或读者全部退出这说明当有读者在读文件时不允许写者写文件对于读者写者问题有三种解决方法读者优先除了上述四个规则外还增加读者优先的规定当有读者在读文件时对随后到达的读者和写者要首先满足读者阻塞写者这说明只第一个读者执行 P(wait)操作成功，将 wait 的值变为 0，再执行 P(readercount_mutex)成功，将信号量 readercount_mutex

39、的值变为 0，接着该读者判断 readercount是 0，所以执行 P(r_w_w)操作成功，获得文件的访问权，将 r_w_w 的值变为 0，然后将 readercount变成 1，执行 V(readercount_mutex)，V(wait)，将信号量 readercount_mutex和 wait 的值还原为 1，之后开始读文件；若随后到达的仍然是读者，则这些读者将 readercount各加 1 之后也开始读文件；若随后到达的是写者，则写者执行 P(wait)操作成功，将 wait的值变为 0，再执行P(r_w_w)操作将 r_w_w 的值变为负数，从而阻塞在 r_w_w上。这使得在它

40、之后到达的读者和写者相继阻塞在 wait 上。当第一批读者读完文件后，由最后一个退出的读者执行执行 V(r_w_w)，从而唤醒第一个被阻塞的写者。3.3.2 设计并分析测试数据 为了验证算法的正确性，需要设计测试数据，并对测试数据进行分析，总结出在该组测试数据下，程序应该得到什么结果，然后运行程序，将程序运行结果与分析结果相比较，如果二者一致，则可认为程序是正确的。作者设计的测试数据如图 3-15 所示，包括10 个线程，其中有 5 个读者线程 r1r5，另外 5个是写者线程 w1w5。读者线程 r1 在时刻 0 提出读请求，如果请求得到允许，r1 将用 15 秒的时间读文件；写者线程 w3在

41、时刻 6 提出写请求，如果请求得到允许，w3 将用 10 秒的时间写文件。从表中可以看出，10 个线程提出请求的次序是：r1,r2,w1,r3,w2,w3,r4,r5,w4,w5。下面分析一下测试数据在不同调度算法下的调度次序。1、读者优先算法 请对照图 3-2 的读者优先算法和图 3-15 的测试数据来理解下面的分析。作者将使用图形来帮助理解，图形中包括所分析的时刻，读者计数器变量 readercount的值，信号量 r_w_w的值和队列。为了简化分析，不考虑读者在语句 6、7 之间和语句 11、12 之间被中断的情况，所以图形中省略了信号量 readercount_mutex。1 初始状态

42、 没有线程使用文件，读者计数器的值为 0，信号量 r_w_w的值为 1，没有线程阻塞在 r_w_w上。如图 3-16 所示。2 时刻 0 线程 r1 在 0 时刻执行语句 5，将 readercount_mutex的值减 1 后变成 0，执行语句 6，判断 readercount的值是 0，从而执行 P(r_w_w)申请使用文件，将 r_w_w 的值减 1 后变成 0，说明此时没有任何线程使用文件，所以 r1 顺利获得文件的使用权，r1 执行语句 7，将readercount的值加到 1，执行语句 8，将 readercount_mutex的值加 1 后还原成 1，r1 执图 3-15 测试数

43、据 线程名称 申请时刻 持续使用时间 r1 0 15 r2 1 15 w1 3 3 r3 4 2 w2 5 6 w3 6 10 r4 7 8 r5 9 2 w4 10 18 w5 12 2 验要求在或者环境下编写一个控制台应用程序该程序运行时能创建个线程其中既有读者线程又有写者线程它们按照事先设计好的测试数据进行读写操作请用信号量和操作实现读者写者问题读者写者问题的描述如下有一个被许多进程据区的进程和一些只往数据区中写数据的进程以下假设共享数据区是文件这些读者和写者对数据区的操作必须满足以下条件读读允许读写互斥写写互斥这些条件具体来说就是任意多的读进程可以同时读这个文件一次只允许一个写进者或读

44、者全部退出这说明当有读者在读文件时不允许写者写文件对于读者写者问题有三种解决方法读者优先除了上述四个规则外还增加读者优先的规定当有读者在读文件时对随后到达的读者和写者要首先满足读者阻塞写者这说明只行语句 9，开始读文件，直到时刻 15 才会释放文件的使用权。如图 3-17 所示。3 时刻 1 线程 r2 在 1 时刻执行语句 5，将 readercount_mutex的值减 1 后变成 0，执行语句 6，判断 readercount的值是 1，而不是 0，说明此时有一个读者线程在使用文件，所以 r2 不执行 P(r_w_w)，而是直接执行语句 7，将 readercount的值加到 2，执行语

45、句 8，将readercount_mutex的值加 1 后还原成 1，r2 执行语句 9，开始读文件，直到时刻 16 才会释放文件的使用权。如图 3-18 所示。4 时刻 3 线程 w1在 3 时刻执行语句 17 申请使用文件，将 r_w_w 的值减到-1，表示已经有读者或者其它写者线程在使用文件，所以 w1被阻塞在 r_w_w 上。如图 3-19 所示。5 时刻 4 线程 r3 在 4 时刻执行语句 5，将 readercount_mutex的值减 1 后变成 0，执行语句 6，判断 readercount的值是 2，而不是 0，说明此时有二个读者线程在使用文件，所以 r3 不执行 P(r_

46、w_w)，而是直接执行语句 7，将 readercount的值加到 3，执行语句 8，将readercount_mutex的值加 1 后还原成 1，r3 执行语句 9，开始读文件，直到时刻 6 才会释放文件的使用权。如图 3-20 所示。6 时刻 5 线程 w2在 5 时刻执行语句 17 申请使用文件，将 r_w_w 的值减到-2，表示已经有读者或者其它写者线程在使用文件，所以 w2被阻塞在 r_w_w 上。如图 3-21 所示。7 时刻 6 在时刻 6，w3请求写文件，并且 r3 执行完读操作。我们首先处理 w3的写请求，然后再初始状态 使用文件者：无 readercount=0 r_w_w

47、 1 NULL 图 3-16 时刻 0：r1 申请 使用文件者：r1 readercount=1 r_w_w 时刻 1：r2 申请 使 用 文 件 者：r1,r2 readercount=2 r_w_w 时刻 3：w1申请 使用文件者：r1,r2 readercount=2 r_w_w -1 w1 图 3-19 验要求在或者环境下编写一个控制台应用程序该程序运行时能创建个线程其中既有读者线程又有写者线程它们按照事先设计好的测试数据进行读写操作请用信号量和操作实现读者写者问题读者写者问题的描述如下有一个被许多进程据区的进程和一些只往数据区中写数据的进程以下假设共享数据区是文件这些读者和写者对数据

48、区的操作必须满足以下条件读读允许读写互斥写写互斥这些条件具体来说就是任意多的读进程可以同时读这个文件一次只允许一个写进者或读者全部退出这说明当有读者在读文件时不允许写者写文件对于读者写者问题有三种解决方法读者优先除了上述四个规则外还增加读者优先的规定当有读者在读文件时对随后到达的读者和写者要首先满足读者阻塞写者这说明只考虑 r3 的退出。线程 w3在 6 时刻执行语句 17 申请使用文件，将 r_w_w 的值减到-3，表示已经有读者或者其它写者线程在使用文件，所以 w3被阻塞在 r_w_w 上。如图 3-22 所示。同时，r3 执行语句 10，将 readercount_mutex的值减 1

49、后变成 0，执行语句 11，将readercount的值减 1 后变成到 2，判断 readercount的值不是 0，这说明还有两个读者在读文件，所以 r3 不执行 V(r_w_w)，而是接着执行语句 13，将 readercount_mutex的值加 1后还原成 1，r3 执行语句 14 结束自身。如图 3-23 所示。8 时刻 7 线程 r4 在 7 时刻执行语句 5，将 readercount_mutex的值减 1 后变成 0，执行语句 6，判断 readercount的值是 2，而不是 0，说明此时有二个读者线程在使用文件，所以 r4 不执行 P(r_w_w)，而是直接执行语句 7，

50、将 readercount的值加到 3，执行语句 8，将readercount_mutex的值加 1 后还原成 1，r4 执行语句 9，开始读文件，直到时刻 15 才会释放文件的使用权。如图 3-24 所示。9 时刻 9 线程 r5 在 9 时刻执行语句 5，将 readercount_mutex的值减 1 后变成 0，执行语句 6，判断 readercount的值是 3，而不是 0，说明此时有 3 个读者线程在使用文件，所以 r5 不执行 P(r_w_w)，而是直接执行语句 7，将 readercount的值加到 4，执行语句 8，将readercount_mutex的值加 1 后还原成 1