实验3--读者-写者问题与进程同步

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、错误的解法图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)；有同学认为，可以将文件视为临界资源，使用临界资源的代码就构成临界区，为了对临界区进行管理，只需设置一个互斥信号量r_w_

4、w，读或者写之前执行P(r_w_w)，之后执行V(r_w_w)即可，从而得到图3-1所示的算法描述。该方法虽然能满足读写互斥和写写互斥，但是不满足读读允许，只要有一个读者在读文件，其他的读者都被阻塞了。可见，单纯使用互斥信号量不能解决读者/写者问题，还需要引入计数器对读者进行记数。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)操作，以便让写者写文件。又因为readercount是一个可被多个

6、读者访问的临界资源，所以应该为它设置一个互斥信号量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_mutex);06 if(readercount=0) P(r_w_w);0

7、7 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 1516 writer()17 P(r_w_w);18 写文件;19 V(r_w_w);20 下面对该算法的调度效果进行分析。假设最初没有进程在访问文件。过了一会，就会有很多读者和写者到达。对它们可能有两种调度情形。情形1 最先调度写者写者执行P(r_w_w)操作成功，将r_w_w的值变为0，获得文件的访问权；其

8、它的写者执行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上。例如，对于请求序列w1,w2,r1,w3,r2,r3，我们用图表形象地刻画进程的活动，图表中包括读者计数器的值、信

9、号量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请求readercount=0readercount_mutex1NULLr_w_w0NULL访问文件者：w1图3-4初始状态readercount=0readercount_mutex1NULLr_w_w1NULL访问文件者：无

10、图3-3在w1尚未写完时，w2提出写请求，所以执行语句17，将信号量r_w_w的值减1后变成负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；r1请求readercount=0readercount_mutex0NULLr_w_w-2 w2,r1访问文件者：w1图3-6w2请求readercount=0readercount_mutex1

11、NULLr_w_w-1 w2访问文件者：w1图3-5同时w3提出写请求，所以执行语句17，将信号量r_w_w的值减1后变成-3，w3被阻塞在信号量r_w_w上，参见图3-7；同时r2提出读请求，所以执行语句5，将信号量readercount_mutex的值减1后变成-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接着执行

12、语句18，开始写文件，参见图3-10；r2请求readercount=0readercount_mutex-1 r2r_w_w-3 w2,r1,w3访问文件者：w1图3-8w3请求readercount=0readercount_mutex0NULLr_w_w-3 w2,r1,w3访问文件者：w1图3-7w2写完文件，执行语句19，将信号量r_w_w的值加1后变成-1，并唤醒r1，r1接着执行语句7，将readercount的值加1后变成1，执行语句8，将信号量readercount_mutex的值加1后变成-1，并唤醒r2，r1执行语句9，开始读文件；被唤醒的r2执行语句6，判断reader

13、count的值不是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，开始读文件。这样三个读者同时读文件，参见图3-11；w1结束，唤醒w2readercount=0readercount_mutex-2 r2,r3r_w_w-2 r1,w3访问文件者：w2图3-10r

14、3请求readercount=0readercount_mutex-2 r2,r3r_w_w-3 w2,r1,w3访问文件者：w1图3-9w2结束,唤醒r1,r1唤醒r2,r2唤醒r3readercount=3readercount_mutex1NULL r_w_w-1 w3访问文件者：r1,r2,r3图3-11r1,r2,r3结束,唤醒w3readercount=0readercount_mutex1NULL r_w_w0NULL 访问文件者： w3图3-12当r1、r2和r3读完文件时，都执行语句1014，并由最后一个执行语句1014的读者执行V(r_w_w)，将信号量r_w_w的值加1后

15、变成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)成功，将信号量readercount_mutex的值变为0，接着该读者判断readerc

16、ount是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)，之后开始读文件。可见多个读者可以同时读文件，并在读文件时阻塞写者。3、写者优先通过增加信号量并修改上述程序可以得到写者优先算法。为了实现写者优

17、先算法，需要将写者和读者分开排队，并且第一个读者和其它读者也要分开排队。这样就需要三个队列，一个是写者排队的地方，另一个是第一个读者排队的地方，第三个是其它读者排队的地方。相应地需要设置三个信号量，r_w_w、first_reader_wait和reader_wait。当一个写者声明想写文件时，可以让新的读者中的第一个到first_reader_wait上排队等待；当有读者阻塞在first_reader_wait上时，让其它读者阻塞在reader_wait上；当有一个写者在写文件时，其它写者到r_w_w上排队。只要有活跃的写者或者写者队列不为空，则阻塞新到达的读者。为了记录已经发出声明的写者数

18、量，需要设置一个整数writercount，以表示声明要写文件的写者数目。由于只要有一个写者到达，就不允许读者去读，因此仅当writercount=0，表示无写者声明写时，写者才需要执行P(first_reader_wait)操作，若操作成功，写者便可以执行P(r_w_w)去竞争写文件权利。其它写者不需要再向读者声明，可以直接执行P(r_w_w)去竞争写文件权利。同理仅当写者在执行writercount减1操作后其值为0时，才需要执行V(first_reader_wait)操作，以便唤醒第一个被阻塞的读者去读文件。又因为writercount是一个可被多个写者访问的临界资源，所以，应该为它设置

19、一个互斥信号量writer_mutex。通过上述分析得到图3-13的算法描述。下面对该算法的调度效果进行分析。假设最初没有进程在访问文件。过了一会，就会有很多读者和写者到达。对它们可能有两种调度情形。情形1 最先调度写者写者执行P(writercount_mutex)，将writercount_mutex的值变为0，并判断writercount是0，从而执行P(first_reader_wait)，将first_reader_wait的值变为0，成功地向读者声明了写访问意图，接着将writercount变为1，执行V(writercount_mutex)，将writercount_mutex的

20、值变为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的值变为负数，写者依次被阻塞在信号量r_w_w上；第一个读者执行P(reader_wait)，将reader_wait的值变为0，接着执行P(first_reader_wait)，将first_reader_wait的值变为负1，阻塞在信号量first_reade

21、r_wait上；其它读者执行P(reader_wait)，将reader_wait的值变为负数，依次阻塞在reader_wait上。当第一个写者写完文件后，执行V(r_w_w)，唤醒一个写者并将写者计数器writercount减1，被唤醒的写者可以写文件，写完后执行V(r_w_w)，唤醒下一个写者并将写者计数器writercount减1，直到最后一个写者将writercount减为0，才执行V(first_reader_wait)唤醒第一个阻塞的读者。被唤醒的读者执行P(readercount_mutex)，然后判断readercount是0，从而执行 P(r_w_w)，由于最后一个写者写完文

22、件后，r_w_w的值已经还原为1，所以被唤醒的读者执行P(r_w_w)成功，将r_w_w的值变为0，获得文件的读访问权。接着将readercount的值加到1，执行V(readercount_mutex)，再执行V(reader_wait)，唤醒第二个等待的读者，第一个读者执行V(first_reader_wait)，将first_reader_wait的值还原到1。第一个读者可以读文件了。若没有新的写者到达，则第二个读者执行P(first_reader_wait)成功，执行P(readercount_mutex)并判断readercount不是0，将readercount加到2，执行V(re

23、adercount_mutex)，再执行V(reader_wait)唤醒第三个读者，再执行V(first_reader_wait)，第二个读者也可以读文件了。图3-13 写者优先算法01 semaphore r_w_w=1;02 semaphore reader_wait=1;03 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(rea

24、der_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_wait);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(writercoun

25、t_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);32 writercount-;33 if(writercount=0) V(first_reader_wait);34 V(writercount_mutex);35 情形2 最先调度读者第一个读者执行P(reader_wait)，将reader_wait的值变为0，执行P(first_reader_wa

26、it)，将first_reader_wait的值变为0，向写者声明有读者要读文件，接着执行P(readercount_mutex)，并判断readercount是0所以执行P(r_w_w)，将r_w_w的值变为0，成功地获得了文件的读访问权，将读者计数器readercount加到1，执行V(readercount_mutex)，V(reader_wait)，V(first_reader_wait)，将reader_wait和first_reader_wait的值依次还原为1。之后，第一个读者开始读文件。若在第一个读者读文件的过程中没有写者到达，则其它读者可以同时读文件；若在读者读文件时，有写者

27、到达，则第一个到达的写者执行P(writercount_mutex)，将writercount_mutex的值变为0，并判断writercount是0，从而执行P(first_reader_wait)，将first_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_

28、w)唤醒写者。第一个写者开始写文件。4、无优先除了在读者优先时需要的信号量r_w_w和readercount_mutex之外，还需要设置一个信号量wait供读者和写者排队。读者和写者都排在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

29、reader()06 P(wait);07 P(readercount_mutex);08 if(readercount=0) P(r_w_w);09 readercount+;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 下面对该算

30、法的调度效果进行分析。最初没有进程在访问文件。过了一会，就会有很多读者和写者到达。对它们可能有两种调度情形。情形1 最先调度写者写者执行P(wait)操作成功，将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 最先调度读者第一个读者执行P(wait)操作成功，将wait的值变

31、为0，再执行P(readercount_mutex)成功，将信号量readercount_mutex的值变为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_

32、w_w的值变为负数，从而阻塞在r_w_w上。这使得在它之后到达的读者和写者相继阻塞在wait上。当第一批读者读完文件后，由最后一个退出的读者执行执行V(r_w_w)，从而唤醒第一个被阻塞的写者。3.3.2 设计并分析测试数据图3-15 测试数据线程名称申请时刻持续使用时间"r1"015"r2"115"w1"33"r3"42"w2"56"w3"610"r4"78"r5"92"w4"1018"w5"1

33、22为了验证算法的正确性，需要设计测试数据，并对测试数据进行分析，总结出在该组测试数据下，程序应该得到什么结果，然后运行程序，将程序运行结果与分析结果相比较，如果二者一致，则可认为程序是正确的。作者设计的测试数据如图3-15所示，包括10个线程，其中有5个读者线程r1r5，另外5个是写者线程w1w5。读者线程r1在时刻0提出读请求，如果请求得到允许，r1将用15秒的时间读文件；写者线程w3在时刻6提出写请求，如果请求得到允许，w3将用10秒的时间写文件。从表中可以看出，10个线程提出请求的次序是：r1,r2,w1,r3,w2,w3,r4,r5,w4,w5。下面分析一下测试数据在不同调度算法下的

34、调度次序。1、读者优先算法请对照图3-2的读者优先算法和图3-15的测试数据来理解下面的分析。作者将使用图形来帮助理解，图形中包括所分析的时刻，读者计数器变量readercount的值，信号量r_w_w的值和队列。为了简化分析，不考虑读者在语句6、7之间和语句11、12之间被中断的情况，所以图形中省略了信号量readercount_mutex。初始状态没有线程使用文件，读者计数器的值为0，信号量r_w_w的值为1，没有线程阻塞在r_w_w上。如图3-16所示。时刻0线程r1在0时刻执行语句5，将readercount_mutex的值减1后变成0，执行语句6，判断readercount的值是0，

35、从而执行P(r_w_w)申请使用文件，将r_w_w的值减1后变成0，说明此时没有任何线程使用文件，所以r1顺利获得文件的使用权，r1执行语句7，将readercount的值加到1，执行语句8，将readercount_mutex的值加1后还原成1，r1执行语句9，开始读文件，直到时刻15才会释放文件的使用权。如图3-17所示。时刻0：r1申请使用文件者：r1readercount=1r_w_w0NULL图3-17初始状态使用文件者：无readercount=0r_w_w1NULL图3-16时刻1线程r2在1时刻执行语句5，将readercount_mutex的值减1后变成0，执行语句6，判断r

36、eadercount的值是1，而不是0，说明此时有一个读者线程在使用文件，所以r2不执行P(r_w_w)，而是直接执行语句7，将readercount的值加到2，执行语句8，将readercount_mutex的值加1后还原成1，r2执行语句9，开始读文件，直到时刻16才会释放文件的使用权。如图3-18所示。时刻3线程w1在3时刻执行语句17申请使用文件，将r_w_w的值减到-1，表示已经有读者或者其它写者线程在使用文件，所以w1被阻塞在r_w_w上。如图3-19所示。时刻3：w1申请使用文件者：r1,r2readercount=2r_w_w-1w1图3-19时刻1：r2申请使用文件者：r1,

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

38、阻塞在r_w_w上。如图3-21所示。时刻6在时刻6，w3请求写文件，并且r3执行完读操作。我们首先处理w3的写请求，然后再考虑r3的退出。线程w3在6时刻执行语句17申请使用文件，将r_w_w的值减到-3，表示已经有读者或者其它写者线程在使用文件，所以w3被阻塞在r_w_w上。如图3-22所示。同时，r3执行语句10，将readercount_mutex的值减1后变成0，执行语句11，将readercount的值减1后变成到2，判断readercount的值不是0，这说明还有两个读者在读文件，所以r3不执行V(r_w_w)，而是接着执行语句13，将readercount_mutex的值加1后

39、还原成1，r3执行语句14结束自身。如图3-23所示。时刻5：w2申请使用文件者：r1,r2,r3readercount=3r_w_w-2w1,w2图3-21时刻4：r3申请使用文件者：r1,r2,r3readercount=3r_w_w-1w1图3-20时刻6：r3结束使用文件者：r1,r2readercount=2r_w_w-3w1,w2,w3图3-23时刻6：w3申请使用文件者：r1,r2,r3readercount=3r_w_w-3w1,w2,w3图3-22时刻7线程r4在7时刻执行语句5，将readercount_mutex的值减1后变成0，执行语句6，判断readercount的值

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

41、x的值加1后还原成1，r5执行语句9，开始读文件，直到时刻11才会释放文件的使用权。如图3-25所示。时刻10线程w4在时刻10执行语句17申请使用文件，将r_w_w的值减到-4，表示已经有读者或者其它写者线程在使用文件，所以w1被阻塞在r_w_w上。如图3-26所示。时刻11r5结束。r5执行语句10，将readercount_mutex的值减1后变成0，执行语句11，将readercount的值减1后变成3，判断readercount的值不是0，这说明还有3个读者在读文件，所以r5不执行V(r_w_w)，而是接着执行语句13，将readercount_mutex的值加1后还原成1，r5执行

42、语句14结束自身。如图3-27所示。时刻9：r5申请使用文件者：r1,r2,r4,r5readercount=4r_w_w-3w1,w2,w3图3-25时刻7：r4申请使用文件者：r1,r2,r4readercount=3r_w_w-3w1,w2,w3图3-24时刻11：r5结束使用文件者：r1,r2,r4readercount=3r_w_w-4w1,w2,w3,w4图3-27时刻10：w4申请使用文件者：r1,r2,r4,r5readercount=4r_w_w-4w1,w2,w3,w4图3-26时刻12w5提出申请。线程w5在时刻12执行语句17申请使用文件，将r_w_w的值减到-5，表示

43、已经有读者或者其它写者线程在使用文件，所以w5被阻塞在r_w_w上。如图3-28所示。时刻15在时刻15，r1和r4都读完文件。r1执行语句10，将readercount_mutex的值减1后变成0，执行语句11，将readercount的值减1后变成2，判断readercount的值不是0，这说明还有2个读者在读文件，所以r1不执行V(r_w_w)，而是接着执行语句13，将readercount_mutex的值加1后还原成1，r1执行语句14结束自身。如图3-29所示。r4执行语句10，将readercount_mutex的值减1后变成0，执行语句11，将readercount的值减1后变成

44、1，判断readercount的值不是0，这说明还有1个读者在读文件，所以r4不执行V(r_w_w)，而是接着执行语句13，将readercount_mutex的值加1后还原成1，r4执行语句14结束自身。如图3-30所示。时刻15：r1结束使用文件者：r2,r4readercount=2r_w_w-5w1,w2,w3,w4,w5图3-29时刻12：w5申请使用文件者：r1,r2,r4readercount=3r_w_w-5w1,w2,w3,w4,w5图3-28时刻16r2读完文件。r2执行语句10，将readercount_mutex的值减1后变成0，执行语句11，将readercount的

45、值减1后变成0，判断readercount的值是0，这说明已经没有读者读文件了，所以r2执行V(r_w_w)，将r_w_w的值加1后变成-4，唤醒阻塞在r_w_w上的线程w1。r2接着执行语句13，将readercount_mutex的值加1后还原成1，执行语句14结束自身。被唤醒的w1执行语句18，开始写文件，直到时刻19才能写完。如图3-31所示。时刻16：r2结束使用文件者：w1readercount=0r_w_w-4w2,w3,w4,w5图3-31时刻15：r4结束使用文件者：r2readercount=1r_w_w-5w1,w2,w3,w4,w5图3-30时刻19w1写完文件，执行语

46、句19，将r_w_w的值加1后变成-3，唤醒阻塞在r_w_w上的线程w2。w1执行语句20结束自身。被唤醒的w2执行语句18，开始写文件，直到时刻25才能写完。如图3-32所示。时刻25w2写完文件，执行语句19，将r_w_w的值加1后变成-2，唤醒阻塞在r_w_w上的线程w3。w2执行语句20结束自身。被唤醒的w3执行语句18，开始写文件，直到时刻35才能写完。如图3-33所示。时刻25：w2结束使用文件者：w3readercount=0r_w_w-2w4,w5图3-33时刻19：w1结束使用文件者：w2readercount=0r_w_w-3w3,w4,w5图3-32时刻35w3写完文件，

47、执行语句19，将r_w_w的值加1后变成-1，唤醒阻塞在r_w_w上的线程w4。w3执行语句20结束自身。被唤醒的w4执行语句18，开始写文件，直到时刻53才能写完。如图3-34所示。时刻53w4写完文件，执行语句19，将r_w_w的值加1后变成0，唤醒阻塞在r_w_w上的线程w5。w4执行语句20结束自身。被唤醒的w5执行语句18，开始写文件，直到时刻55才能写完。如图3-35所示。时刻55w5写完文件，执行语句19，将r_w_w的值加1后变成1，执行语句20结束自身。在时刻55，所有线程都运行完毕。如图3-36所示。时刻35：w3结束使用文件者：w4readercount=0r_w_w-1

48、w53-34时刻55：w5结束使用文件者：readercount=0r_w_w1NULL图3-36时刻53：w4结束使用文件者：W5readercount=0r_w_w0NULL图3-35综上所述，线程实际读写文件顺序为：r1,r2,r3,r4,r5,w1,w2,w3,w4,w5。执行情况见图3-37。图3-37 线程的运行状况线程名称申请时刻持续时间开始操作时刻结束操作时刻"r1"015015"r2"115116"r3"4246"r4"78715"r5"92911"w1"3

49、31619"w2"561925"w3"6102535"w4"10183553"w5"12253552、写者优先算法请对照图3-13的写者优先算法和图3-15的测试数据来理解下面的分析。作者将使用图形来帮助理解，图形中包括所分析的时刻，读者计数器变量readercount的值，写者计数器变量writercount的值，信号量r_w_w的值和队列，信号量first_reader_wait的值和队列，信号量reader_wait的值和队列。为了简化分析，不考虑读者在语句11、12之间和语句19、20之间被中断的情况，也不

50、考虑写者在语句25、26之间和语句32、33之间被中断的情况，所以图形中省略了信号量readercount_mutex和writercount_mutex。初始状态没有线程使用文件，读者计数器和写者计数器的值是0，信号量r_w_w 、first_reader_wait、reader_wait的值是1，队列为空。如图3-38所示。时刻0r1提出读请求。r1执行语句9，将信号量reader_wait的值变为0，执行语句10，将信号量first_reader_wait的值变为0，执行语句11，将信号量readercount_mutex的值变为0，执行语句12，判断readercount的值是0，所以

51、执行P(r_w_w)，将信号量r_w_w的值变为0，执行语句13，将readercount的值加到1，执行语句14，将信号量readercount_mutex的值还原为1，执行语句15，将信号量reader_wait的值还原为1，执行语句16，将信号量first_reader_wait的值还原为1，执行语句17，开始读文件，直到时刻15才能读完，见图3-39。时刻1r2提出读请求。r2执行语句9，将信号量reader_wait的值变为0，执行语句10，将信号量first_reader_wait的值变为0，执行语句11，将信号量readercount_mutex的值变为0，执行语句12，判断re

52、adercount的值是1，而不是0，所以不执行P(r_w_w)，而是执行语句13，将readercount的值加到2，执行语句14，将信号量readercount_mutex的值还原为1，执行语句15，将信号量reader_wait的值还原为1，执行语句16，将信号量first_reader_wait的值还原为1，执行语句17，r2开始读文件，直到时刻16才能读完，见图3-40。时刻1：r2申请使用文件者：r1,r2readercount=2writercount=0r_w_w0NULLfirst_reader_wait1NULLreader_wait1NULL图3-40时刻0：r1申请使用文件者：r1readercount=1writercount=0r_w_w0NULLfirst_reader_wait1NULLreader_wait1NULL图3-39初始状态：使用文件者：无readercount=0writercount=0r_