操作系统读者写者问题.docx
《操作系统读者写者问题.docx》由会员分享，可在线阅读，更多相关《操作系统读者写者问题.docx（33页珍藏版）》请在冰点文库上搜索。
操作系统读者写者问题
操作系统
课程设计报告
第1章实验目的和实验要求
1.1实验目的
理解临界区和进程互斥的概念，掌握用信号量和PV操作实现进程互斥的方法。
1.2实验要求
在windows或者linux环境下编写一个控制台应用程序，该程序运行时能创建N个线程，其中既有读者线程又有写者线程，它们按照事先设计好的测试数据进行读写操作。
请用信号量和PV操作实现读者/写者问题。
1.3课程设计题目
本课程设计共包括3个题目，内容覆盖了操作系统原理的关键知识点，包括进程调度、内存管理、进程同步、死锁、进程通讯、文件系统及嵌入式操作系统。
题目1：
进程调度算法。
模拟在单处理器情况下的进程调度，目的是加深对进程调度工作的理解，掌握不同调度算法的优缺点
题目2：
动态异长分区的存储分配与回收算法。
编写一个程序，模拟操作系统对动态异长分区的存储分配与回收算法。
题目3：
读者/写者问题与进程同步。
理解临界区和进程互斥的概念，掌握用信号量和PV操作实现进程互斥的方法。
要求学生用信号量和PV操作实现读者/写者问题的读者优先算法、写者优先算法和无优先算法。
我们小组选择题目3，即读者/写者问题与进程同步。
以下是该题目的实验报告。
第2章实验内容
2.1题目分析
2.1.1问题的描述
有一个被许多进程共享的数据区，这个数据区可以是一个文件，或者主存的一块空间，甚至可以是一组处理器寄存器。
有一些只读取这个数据区的进程（reader）和一些只往数据区中写数据的进程（writer）。
以下假设共享数据区是文件。
这些读者和写者对数据区的操作必须满足以下条件：
读—读允许；读—写互斥；写—写互斥。
这些条件具体来说就是：
（1）任意多的读进程可以同时读这个文件；
（2）一次只允许一个写进程往文件中写；
（3）如果一个写进程正在往文件中写，禁止任何读进程或写进程访问文件；
（4）写进程执行写操作前，应让已有的写者或读者全部退出。
这说明当有读者在读文件时不允许写者写文件。
2.1.2问题的解决方法
（1）读者优先
除了上述四个规则外，还增加读者优先的规定，当有读者在读文件时，对随后到达的读者和写者，要首先满足读者，阻塞写者。
这说明只要有一个读者活跃，那么随后而来的读者都将被允许访问文件，从而导致写者长时间等待，甚至有可能出现写者被饿死的情况。
（2）写者优先
除了上述四个规则外，还增加写者优先的规定，即当有读者和写者同时等待时，首先满足写者。
当一个写者声明想写文件时，不允许新的读者再访问文件。
（3）无优先
除了上述四个规则外，不再规定读写的优先权，谁先等待谁就先使用文件。
2.2算法分析
2.2.1读者优先算法分析
对于相继到达的一批读者，并不是每个读者都需要执行P（r_w_w）和V（r_w_w）。
在这批读者中，只有最先到达的读者才需要执行P（r_w_w），与写者竞争对文件的访问权，若执行P（r_w_w）成功则获得了文件的访问权，其他的读者可直接访问文件；同理，只有最后退出临界区的读者需要执行V（r_w_w）来归还文件访问权。
为了记录正在读文件的一批读者的数量，需要设置一个整型变量read_count，每一个读者到达时都要将read_count加1，退出时都要将read_count减1。
由于只要有一个读者在读文件，便不允许写者写文件，所以，仅当read_count=0时，即尚无读者在读文件时，读者才需要执行P（r_w_w）操作。
若P（r_w_w）操作成功，读者便可去读文件，相应地，read_count+1。
同理，仅当在执行了read_count减1操作后其值为0时，才需要执行V（r_w_w）操作，以便让写者写文件。
又因为read_count是一个可被多个读者访问的临界资源，所以应该为它设置一个互斥信号量h_mutex_read_count。
每个读者在访问read_count之前执行P（h_mutex_read_count），之后执行V（h_mutex_read_count）。
通过上述分析得到图2-1所示的算法描述，其中的数字表示语句对应的行号。
01semaphorer_w_w=1;
02semaphoreh_mutex_read_count=1;
03intread_count=0;
04reader（）{
05P（h_mutex_read_count）;
06if（read_count==0）P（r_w_w）;
07read_count++;
08V（h_mutex_read_count）;
09读文件;
10P（h_mutex_read_count）;
11read_count--;
12if（read_count==0）V（r_w_w）;
13V（h_mutex_read_count）;
14}
15
16writer（）{
17P（r_w_w）;
18写文件;
19V（r_w_w）;
20}
图2-1读者优先算法
下面对该算法的调度效果进行分析。
假设最初没有进程在访问文件。
过了一会，就会有很多读者和写者到达。
对它们可能有两种调度情形。
●情形1最先调度写者
写者执行P（r_w_w）操作成功，将r_w_w的值变为0，获得文件的访问权；其它的写者执行P（r_w_w）将r_w_w的值变为负数，从而阻塞在信号量r_w_w上；第一个读者执行P（h_mutex_read_count）成功，将信号量h_mutex_read_count的值变为0，然后判断read_count是0，所以执行P（r_w_w），将r_w_w的值减1后仍然为负数从而阻塞在信号量r_w_w上，其它的读者执行P（h_mutex_read_count）将信号量h_mutex_read_count的值变为负数，从而阻塞在信号量h_mutex_read_count上。
例如，对于请求序列w1,w2,r1,w3,r2,r3，我们用图表形象地刻画进程的活动，图表中包括读者计数器的值、信号量h_mutex_read_count和r_w_w的值和队列以及访问文件的进程。
①初始状态。
没有进程使用文件，计数器read_count的值是0，信号量h_mutex_read_count和r_w_w的值都是1，队列都是空，参见图2-2；
②w1请求写文件，所以执行语句17，将信号量r_w_w的值减1后变成0，w1获得文件使用权，执行语句18，开始写文件，参见图2-3；
③在w1尚未写完时，w2提出写请求，所以执行语句17，将信号量r_w_w的值减1后变成负1，w2被阻塞在信号量r_w_w上，参见图2-4；
②w1请求
read_count=0
h_mutex_read_count
1
NULL
r_w_w
0
NULL
访问文件者：
w1
图2-3
①初始状态
read_count=0
h_mutex_read_count
1
NULL
r_w_w
1
NULL
访问文件者：
无
图2-2
④同时r1提出读请求，所以执行语句5，将信号量h_mutex_read_count的值减1后变成0，接着执行语句6，判断read_count的值是0，所以执行P（r_w_w），将信号量r_w_w的值减1后变成-2，r1被阻塞在信号量r_w_w上，参见图2-5；
⑤同时w3提出写请求，所以执行语句17，将信号量r_w_w的值减1后变成-3，w3被阻塞在信号量r_w_w上，参见图2-6；
⑥同时r2提出读请求，所以执行语句5，将信号量h_mutex_read_count的值减1后变成-1，r2被阻塞在信号量h_mutex_read_count上，参见图2-7；
③w2请求
read_count=0
h_mutex_read_count
1
NULL
r_w_w
-1
w2
访问文件者：
w1
图2-4
④r1请求
read_count=0
h_mutex_read_count
0
NULL
r_w_w
-2
w2,r1
访问文件者：
w1
图2-5
⑦同时r3提出读请求，所以执行语句5，将信号量h_mutex_read_count的值减1后变成-2，r3被阻塞在信号量h_mutex_read_count上，参见图2-8；
⑧w1写完文件，执行语句19，将信号量r_w_w的值加1后变成-2，并唤醒w2，w2接着执行语句18，开始写文件，参见图2-9；
⑨w2写完文件，执行语句19，将信号量r_w_w的值加1后变成-1，并唤醒r1，r1接着执行语句7，将read_count的值加1后变成1，执行语句8，将信号量h_mutex_read_count的值加1后变成-1，并唤醒r2，r1执行语句9，开始读
文件；被唤醒的r2执行语句6，判断read_count的值不是0，所以执行语句7，将read_count的值加1后变成2，执行语句8，将信号量h_mutex_read_count的值加1后变成0，并唤醒r3，r2执行语句9，开始读文件；被唤醒的r3执行语句6，判断read_count的值不是0，所以执行语句7，将read_count的值加1后变成3，执行语句8，将信号量h_mutex_read_count的值加1后变成1，r3执行语句9，开始读文件。
这样三个读者同时读文件，参见图2-10；
⑩当r1、r2和r3读完文件时，都执行语句10~14，并由最后一个执行语句10~14的读者执行V（r_w_w），将信号量r_w_w的值加1后变成0，并唤醒w3，w3接着执行语句18，开始写文件，参见图2-11；
当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将一直被阻塞，直至被饿死。
⑧w1结束，唤醒w2
read_count=0
h_mutex_read_count
-2
r2,r3
r_w_w
-2
r1,w3
访问文件者：
w2
图2-9
⑦r3请求
read_count=0
h_mutex_read_count
-2
r2,r3
r_w_w
-3
w2,r1,w3
访问文件者：
w1
图2-8
⑩r1,r2,r3结束,唤醒w3
read_count=0
h_mutex_read_count
1
NULL
r_w_w
0
NULL
访问文件者：
w3
图2-11
⑨w2结束,唤醒r1,
r1唤醒r2,r2唤醒r3
read_count=3
h_mutex_read_count
1
NULL
r_w_w
-1
w3
访问文件者：
r1,r2,r3
图2-10
●情形2最先调度读者
第一个读者执行P（h_mutex_read_count）成功，将信号量h_mutex_read_count的值变为0，接着该读者判断read_count是0，所以执行P（r_w_w）操作成功，获得文件的访问权，将r_w_w的值变为0，然后将read_count变成1，执行V（h_mutex_read_count），之后开始读文件；随后的写者执行P（r_w_w）将r_w_w的值变为负数，从而阻塞在信号量r_w_w上；其它的读者执行P（h_mutex_read_count）成功，判断read_count不是0，所以直接将read_count的值再加1，执行V（h_mutex_read_count），之后开始读文件。
可见多个读者可以同时读文件，并在读文件时阻塞写者。
2.2.2写者优先算法分析
通过增加信号量并修改上述程序可以得到写者优先算法。
为了实现写者优先算法，需要将写者和读者分开排队，并且第一个读者和其它读者也要分开排队。
这样就需要三个队列，一个是写者排队的地方，另一个是第一个读者排队的地方，第三个是其它读者排队的地方。
相应地需要设置三个信号量，r_w_w、first_reader_wait和reader_wait。
当一个写者声明想写文件时，可以让新的读者中的第一个到first_reader_wait上排队等待；当有读者阻塞在first_reader_wait上时，让其它读者阻塞在reader_wait上；当有一个写者在写文件时，其它写者到r_w_w上排队。
只要有活跃的写者或者写者队列不为空，则阻塞新到达的读者。
为了记录已经发出声明的写者数量，需要设置一个整数writ_count，以表示声明要写文件的写者数目。
由于只要有一个写者到达，就不允许读者去读，因此仅当writ_count=0，表示无写者声明写时，写者才需要执行P（first_reader_wait）操作，若操作成功，写者便可以执行P（r_w_w）去竞争写文件权利。
其它写者不需要再向读者声明，可以直接执行P（r_w_w）去竞争写文件权利。
同理仅当写者在执行writ_count减1操作后其值为0时，才需要执行V（first_reader_wait）操作，以便唤醒第一个被阻塞的读者去读文件。
又因为writ_count是一个可被多个写者访问的临界资源，所以，应该为它设置一个互斥信号量writer_mutex。
通过上述分析得到图2-13的算法描述。
下面对该算法的调度效果进行分析。
假设最初没有进程在访问文件。
过了一会，就会有很多读者和写者到达。
对它们可能有两种调度情形。
●情形1最先调度写者
写者执行P（writ_count_mutex），将writ_count_mutex的值变为0，并判断writ_count是0，从而执行P（first_reader_wait），将first_reader_wait的值变为0，成功地向读者声明了写访问意图，接着将writ_count变为1，执行V（writ_count_mutex），将writ_count_mutex的值变为1。
然后写者执行P（r_w_w）操作，将r_w_w的值变为0，成功地获得了文件的写访问权利。
第一个写者开始写文件；
其它的写者执行P（writ_count_mutex），判断writ_count不是0，所以直接将writ_count加1，执行V（writ_count_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_reader_wait上；其它读者执行P（reader_wait），将reader_wait的值变为负数，依次阻塞在reader_wait上。
当第一个写者写完文件后，执行V（r_w_w），唤醒一个写者并将写者计数器writ_count减1，被唤醒的写者可以写文件，写完后执行V（r_w_w），唤醒下一个写者并将写者计数器writ_count减1，直到最后一个写者将writ_count减为0，才执行V（first_reader_wait）唤醒第一个阻塞的读者。
被唤醒的读者执行P（h_mutex_read_count），然后判断read_count是0，从而执行P（r_w_w），由于最后一个写者写完文件后，r_w_w的值已经还原为1，所以被唤醒的读者执行P（r_w_w）成功，将r_w_w的值变为0，获得文件的读访问权。
接着将read_count的值加到1，执行V（h_mutex_read_count），再执行V（reader_wait），唤醒第二个等待的读者，第一个读者执行V（first_reader_wait），将first_reader_wait的值还原到1。
第一个读者可以读文件了。
若没有新的写者到达，则第二个读者执行P（first_reader_wait）成功，执行P（h_mutex_read_count）并判断read_count不是0，将read_count加到2，执行V（h_mutex_read_count），再执行V（reader_wait）唤醒第三个读者，再执行V（first_reader_wait），第二个读者也可以读文件了。
01semaphorer_w_w=1;
02semaphorereader_wait=1;
03semaphorefirst_reader_wait=1;
04semaphoreh_mutex_read_count=1;
05semaphorewrit_count_mutex=1;
06intwrit_count=0;
07intread_count=0;
08reader（）{
09P（reader_wait）;
10P（first_reader_wait）;
11P（h_mutex_read_count）;
12if（read_count==0）P（r_w_w）;
13read_count++;
14V（h_mutex_read_count）;
15V（reader_wait）;
16V（first_reader_wait）;
17读文件;
18P（h_mutex_read_count）;
19read_count--;
20if（read_count==0）V（r_w_w）;
21V（h_mutex_read_count）;
22}
23writer（）{
24P（writ_count_mutex）;
25if（writ_count==0）P（first_reader_wait）;
26writ_count++;
27V（writ_count_mutex）;
28P（r_w_w）;
29写文件;
30V（r_w_w）;
31P（writ_count_mutex）;
32writ_count--;
33if（writ_count==0）V（first_reader_wait）;
34V（writ_count_mutex）;
35}
图2-12写者优先算法
●情形2最先调度读者
第一个读者执行P（reader_wait），将reader_wait的值变为0，执行P（first_reader_wait），将first_reader_wait的值变为0，向写者声明有读者要读文件，接着执行P（h_mutex_read_count），并判断read_count是0所以执行P（r_w_w），将r_w_w的值变为0，成功地获得了文件的读访问权，将读者计数器read_count加到1，执行V（h_mutex_read_count），V（reader_wait），V（first_reader_wait），将reader_wait和first_reader_wait的值依次还原为1。
之后，第一个读者开始读文件。
若在第一个读者读文件的过程中没有写者到达，则其它读者可以同时读文件；
若在读者读文件时，有写者到达，则第一个到达的写者执行P（writ_count_mutex），将writ_count_mutex的值变为0，并判断writ_count是0，从而执行P（first_reader_wait），将first_reader_wait的值变为0，成功地向读者声明了写访问意图，接着将writ_count变为1，执行V（writ_count_mutex），将writ_count_mutex的值变为1。
然后写者执行P（r_w_w）操作，（由于有读者在读文件，所以）将r_w_w的值变为负1，写者被阻塞在信号量r_w_w上；当在读文件的所有读者都读完文件后，由最后一个退出的读者执行V（r_w_w）唤醒写者。
第一个写者开始写文件。
2.2.3无优先算法分析
除了在读者优先时需要的信号量r_w_w和h_mutex_read_count之外，还需要设置一个信号量wait供读者和写者排队。
读者和写者都排在wait队列上。
若有读者在读文件，则第一个写者阻塞在r_w_w上，其它的写者和读者阻塞在wait上；若有一个写者在写文件，则其它写者和读者都阻塞在wait上。
无优先的算法描述如图2-13所示。
01semaphorer_w_w=1;
02semaphorewait=1;
03semaphoreh_mutex_read_count=1;
04intread_count=0;
05reader（）{
06P（wait）;
07P（h_mutex_read_count）;
08if（read_count==0）P（r_w_w）;
09read_count++;
10V（h_mutex_read_count）;
11V（wait）;
12读文件;
13P（h_mutex_read_count）;
14read_count--;
15if（read_count==0）V（r_w_w）;
16V（h_mutex_read_count）;
17}
18writer（）{
19P（wait）;
20P（r_w_w）;
21写文件;
22V（r_w_w）;
23V（wait）;
24}
图2-13无优先算法
下面对该算法的调度效果进行分析。
最初没有进程在访问文件。
过了一会，就会有很多读者和写者到达。
对它们可能有两种调度情形。
●情形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的值变为0，再执行P（h_mutex_read_count）成功，将信号量h_mutex_read_count的值变为0，接着该读者判断read_count是0，所以执行P（r_w_w）操作成功，获得文件的访问权，将r_w_w的值变为0，然后将read_count变成1，执行V（h_mutex_read_count），V（wait），将信号量h_mutex_read_count和wait的值还原为1，之后开始读文件；若随后到达的仍然是读者，则这些读者将read_count各加1之后也开始读文件；若随后到达的是写者，则写者执行P（wait）操作成功，将wait的值变为0，再执行P（r_w_w）操作将r_w_w的值变为负数，从而阻塞在r_w_w上。
这使得在它之后到达的读者和写者相继阻
升级会员 