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

1实验3读者/写者问题与进程同步3.1实验目的理解临界区和进程互斥的概念，掌握用信号量和PV操作实现进程互斥的方法。3.2实验要求在windows或者linux环境下编写一个控制台应用程序，该程序运行时能创建N个线程，其中既有读者线程又有写者线程，它们按照事先设计好的测试数据进行读写操作。请用信号量和PV操作实现读者/写者问题。读者/写者问题的描述如下：有一个被许多进程共享的数据区，这个数据区可以是一个文件，或者主存的一块空间，甚至可以是一组处理器寄存器。有一些只读取这个数据区的进程（reader）和一些只往数据区中写数据的进程（writer）。以下假设共享数据区是文件。这些读者和写者对数据区的操作必须满足以下条件：读—读允许；读—写互斥；写—写互斥。这些条件具体来说就是：（1）任意多的读进程可以同时读这个文件；（2）一次只允许一个写进程往文件中写；（3）如果一个写进程正在往文件中写，禁止任何读进程或写进程访问文件；（4）写进程执行写操作前，应让已有的写者或读者全部退出。这说明当有读者在读文件时不允许写者写文件。对于读者-写者问题，有三种解决方法：1、读者优先除了上述四个规则外，还增加读者优先的规定，当有读者在读文件时，对随后到达的读者和写者，要首先满足读者，阻塞写者。这说明只要有一个读者活跃，那么随后而来的读者都将被允许访问文件，从而导致写者长时间等待，甚至有可能出现写者被饿死的情况。2、写者优先除了上述四个规则外，还增加写者优先的规定，即当有读者和写者同时等待时，首先满足写者。当一个写者声明想写文件时，不允许新的读者再访问文件。3、无优先除了上述四个规则外，不再规定读写的优先权，谁先等待谁就先使用文件。3.3实验步骤3.3.1算法分析1、错误的解法有同学认为，可以将文件视为临界资源，使用临界资源的代码就构成临界区，为了对临界区进行管理，只需设置一个互斥信号量r_w_w，读或者写之前执行P(r_w_w)，之后执行V(r_w_w)即可，从而得到图3-1所示的算法描述。该方法虽然能满足读—写互斥和写—写互斥，但是不满足读—读允许，只要有一个读者在读文件，其他的读者都被阻塞了。图3-1错误的解法semaphorer_w_w=1;reader(){P(r_w_w)；读文件；V(r_w_w)；}writer(){P(r_w_w)；写文件；V(r_w_w)；}2可见，单纯使用互斥信号量不能解决读者/写者问题，还需要引入计数器对读者进行记数。2、读者优先如何纠正上述解法中存在的错误呢？其实，对于相继到达的一批读者，并不是每个读者都需要执行P(r_w_w)和V(r_w_w)。在这批读者中，只有最先到达的读者才需要执行P(r_w_w)，与写者竞争对文件的访问权，若执行P(r_w_w)成功则获得了文件的访问权，其他的读者可直接访问文件；同理，只有最后退出临界区的读者需要执行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是一个可被多个读者访问的临界资源，所以应该为它设置一个互斥信号量readercount_mutex.。每个读者在访问readercount之前执行P(readercount_mutex)，之后执行V(readercount_mutex)。通过上述分析得到图3-2所示的算法描述，其中的数字表示语句对应的行号。图3-2读者优先算法01semaphorer_w_w=1;02semaphorereadercount_mutex=1;03intreadercount=0;04reader(){05P(readercount_mutex);06if(readercount==0)P(r_w_w);07readercount++;08V(readercount_mutex);09读文件;10P(readercount_mutex);11readercount--;12if(readercount==0)V(r_w_w);13V(readercount_mutex);14}1516writer(){17P(r_w_w);18写文件;19V(r_w_w);20}下面对该算法的调度效果进行分析。假设最初没有进程在访问文件。过了一会，就会有很多读者和写者到达。对它们可能有两种调度情形。情形1最先调度写者写者执行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上。3例如，对于请求序列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后变成负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后变成-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=0readercount_mutex1NULLr_w_w0NULL访问文件者：w1图3-4①初始状态readercount=0readercount_mutex1NULLr_w_w1NULL访问文件者：无图3-3③w2请求readercount=0readercount_mutex1NULLr_w_w-1w2访问文件者：w1图3-5④r1请求readercount=0readercount_mutex0NULLr_w_w-2w2,r1访问文件者：w1图3-64⑨w2写完文件，执行语句19，将信号量r_w_w的值加1后变成-1，并唤醒r1，r1接着执行语句7，将readercount的值加1后变成1，执行语句8，将信号量readercount_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，开始读文件。这样三个读者同时读文件，参见图3-11；⑤w3请求readercount=0readercount_mutex0NULLr_w_w-3w2,r1,w3访问文件者：w1图3-7⑥r2请求readercount=0readercount_mutex-1r2r_w_w-3w2,r1,w3访问文件者：w1图3-8⑧w1结束，唤醒w2readercount=0readercount_mutex-2r2,r3r_w_w-2r1,w3访问文件者：w2图3-10⑩r1,r2,r3结束,唤醒w3readercount=0readercount_mutex1NULLr_w_w0NULL访问文件者：w3图3-12⑦r3请求readercount=0readercount_mutex-2r2,r3r_w_w-3w2,r1,w3访问文件者：w1图3-9⑨w2结束,唤醒r1,r1唤醒r2,r2唤醒r3readercount=3readercount_mutex1NULLr_w_w-1w3访问文件者：r1,r2,r3图3-115⑩当r1、r2和r3读完文件时，都执行语句10~14，并由最后一个执行语句10~14的读者执行V(r_w_w)，将信号量r_w_w的值加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)成功，将信号量readercount_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)，之后开始读文件。可见多个读者可以同时读文件，并在读文件时阻塞写者。3、写者优先通过增加信号量并修改上述程序可以得到写者优先算法。为了实现写者优先算法，需要将写者和读者分开排队，并且第一个读者和其它读者也要分开排队。这样就需要三个队列，一个是写者排队的地方，另一个是第一个读者排队的地方，第三个是其它读者排队的地方。相应地需要设置三个信号量，r_w_w、first_reader_wait和reader_wait。当一个写者声明想写文件时，可以让新的读者中的第一个到first_reader_wait上排队等待；当有读者阻塞在first_reader_wait上时，让其它读者阻