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

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

2、区的进程 （ reader ）和一些只往数据区中写数据的进程 （ writer ）。以下假设共享数据区是文件。 这些读 者和写者对数据区的操作必须满足以下条件： 读 读允许；读写互斥；写 写互斥。这些条件 具体来说就是：（1）任意多的读进程可以同时读这个文件；（2）一次只允许一个写进程往文件中写；（3）如果一个写进程正在往文件中写，禁 止任何读进程或写进程访问文件；（4）写进程执行写操作前，应让已有的写 者或读者全部退出。 这说明当有读者在读文件时 不允许写者写文件。对于读者 -写者问题，有三种解决方法：1、读者优先 除了上述四个规则外， 还增加读者优先的规 定，当有读者在读文件时， 对随后到

3、达的读者和 写者，要首先满足读者，阻塞写者。这说明只要 有一个读者活跃， 那么随后而来的读者都将被允 许访问文件， 从而导致写者长时间等待， 甚至有 可能出现写者被饿死的情况。2、写者优先 除了上述四个规则外， 还增加写者优先的规 定，即当有读者和写者同时等待时， 首先满足写 者。当一个写者声明想写文件时， 不允许新的读 者再访问文件。3、无优先 除了上述四个规则外， 不再规定读写的优先 权，谁先等待谁就先使用文件。3.3 实验步骤3.3.1 算法分析1、错图误3-的1 解错法误的解法sema r_w rer_w_w) ；V读(r文_w件_；w) ；)w；riPte(rr_()w _w )；V

4、写(r文_w件_；w )；有同学认为， 可以将文件视为临 界资源，使用临界 资源的代码就构成临界区， 为了对临界区进行管理， 只需设置一个 互 斥 信 号 量 r_w_w ， 读 或 者 写 之 前 执 行P(r_w_w) ，之后执行 V(r_w_w) 即可，从而得到 图 3-1 所示的算法描述。该方法虽然能满足读 写互斥和写 写互 斥，但是不满足读 读允许， 只要有一个读者在 读文件，其他的读者都被阻塞了。可见，单纯使用互斥信号量不能解决读者 / 写者问题，还需要引入计数器对读者进行记数。2、读者优先如何纠正上述解法中存在的错误呢？ 其实，对于相继到达的一批读者， 并不是每 个读者都需要执行

5、 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 时，即尚 无读者在

6、读文件时，读者才需要执行 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) 。通过上述分析得到图

7、3-2 所示的算法描述， 其中的数字表示语句对应的行号。图 3-2 读者优 semaphore semaphore t_mutex=1; dercount=0;01 r0_2w _w=1; readercoun 03 int rea 00P54( reader()r eadercount_mutex); r e_awd_ewrc);o unt=0) r _w_wre);a dercount+; r eade读rc文ou件nt_; mutex); readercount_mutex); readercount-; eadercount=0) r _w_w);r ead ercount mutex

8、);先算法161w7ri ter() )P; (r_w_w 1文)8;件 ; 写 12V09(r _w _w);3、写者优先 通过增加信号量并修改上述程序可以得到 写者优先算法。 为了实现写者优先算法， 需要将 写者和读者分开排队， 并且第一个读者和其它读 者也要分开排队。 这样就需要三个队列， 一个是 写者排队的地方， 另一个是第一个读者排队的地 方，第三个是其它读者排队的地方。 相应地需要 设置三个信号量， r_w_w 、first_reader_wait 和 reader_wait 。当一个写者声明想写文件时， 可以 让新的读者中的第一个到 first_reader_wait 上排 队等

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

10、读者声明，可以直接执行 P(r_w_w) 去竞争写文件权利。同理仅当写者在执 行 writercount 减 1 操作后其值为 0 时，才需要 执行 V(first_reader_wait) 操作，以便唤醒第一个 被阻塞的读者去读文件。又因为 writercount 是 一个可被多个写者访问的临界资源， 所以，应该 为它设置一个互斥信号量 writer_mutex 。4、无优先除了在读者优先时需要的信号量 r_w_w 和 readercount_mutex 之外，还需要设置一个信号 量 wait 供读者和写者排队。读者和写者都排在 wait 队列上。 若有读者在读文件， 则第一个写者阻塞在 r

11、_w_w 上，其它的写者和读者阻塞在 wait 上；若有一个写者在写文件， 则其它写者和读者都阻塞在 wait 上无优先的算法描述如图 3-3 所示。图 3-3 无01r0_2w _w=1;0w3a it=1;semaphorereadercount_mutenx=t=10; ;先 semaphore semaphore sema count_mute int readercount reewra()it) ; r eadercount_mutex); eadercount=0) r_w_w);readercount+; ount_mutex);V(readP(readercount_mute

12、x); 1154readercount-;if(readercount=0) 1V6(r _w_w);1V7(r ead ercount mutex);11w89ri ter() 12P90(w ait); 2P0(r _w_w); 22文12件 ;2V3(r _w_w); 22V34(w ait );3.3.2 程序功能及界面设计 该程序采用简单的控制台应用程序界面， 在 主界面上显示程序的功能。该程序的功能如下：1. 演示读者优先算法；2. 演示写者优先算法；3. 演示无优先算法；4. 退出。3.3.3 函数设计实现读者/写者问题的源程序名称是reader_and_writer.cpp 。

13、该程序共包括 10 个函 数。这些函数可以分成 4 组。各组包含的函数及 其功能如图 3-4组别包括函数函数功能一main()显示主菜单，接收用户的选择并执行相应的功能。二RF_reader_thread() RF_writer_thread() reader first()读者优先算法的读者线程函数读者优先算法的写者线程函数读者优先算法的初始化函数：创建 10 个线程并等待它们结束三WF_reader_thread() WF_writer_thread() writer first()写者优先算法的读者线程函数写者优先算法的写者线程函数写者优先算法的初始化函数：创建 10 个线程并等待它们结

14、束四FIFO_reader_thread() FIFO_writer_thread() first come first serverd()无优先算法的读者线程函数 无者优先算法的写者线程函数 无者优先算法的初始化函数：创建 10 个线程并等待它们结束图 3-4 函数功能简述程序开始部分定义了宏 MAX_THREAD ，表示程序中创建的线程数。 还定义了测试数据的 结构体 TEST_INFO ，该结构体包含三个数据项： 线程名称；提出请求的时刻；操作持续时间。接 着定义了全局变量，这些全局变量的作用如下：数组 test_data 保存了 10 个线程的测试数据；整数 read_count 记录

15、一段时间内同时对文 件进行读操作的线程数；整数 write_count 记录一段时间内提出写操 作请求的线程数， 该整数只在写者优先算法中使 用；CS_DATA 是临界区变量，用来保护文件， 实现对文件的读 写互斥和写 写互斥（相当于 算法描述中的 r_w_w ）；互斥体 h_mutex_read_count 用来保护整数 read_count ，以保证多个读者对 read_count 的互 斥访问；互斥体 h_mutex_write_count 用来保护整数 write_count ，以保证多个写者对 write_count 的 互斥访问，该互斥体只在写者优先算法中使用；互 斥 体 h_mu

16、tex_first_reader_wait 和 h_mutex_reader_wait 只在写者优先算法中使 用，当有写者在写文件时， 提出读请求的第一个 读者阻塞在 h_mutex_first_reader_wait 上，其余 的读者阻塞在 h_mutex_reader_wait 上； 互斥体 h_mutex_wait 只在无优先算法中使 用，当文件被使用时， 后继的读请求和写请求依 次阻塞在 h_mutex_wait 上。103.3.4参考源程序 3.3.4.1 Linux 下的参考源程序1 编译命令gcc reader_and_writer .cpp reader_and_writer.

17、o lcurses lpthread 2 程序清单#include #include #include #include #include #define MAX_THREAD 10typedef structchar thread_name3;unsigned int require_moment;unsigned int persist_time;TEST_INFO;TEST_INFO test_dataMAX_THREAD=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;int r

18、ead_count=0;int write_count=0;pthread_mutex_t CS_DATA;pthread_mutex_t h_mutex_read_count;pthread_mutex_t h_mutex_write_count;pthread_mutex_t h_mutex_reader_wait;pthread_mutex_t h_mutex_first_reader_wait;pthread_mutex_t h_mutex_wait;void* RF_reader_thread(void *data)char thread_name3;strcpy(thread_na

19、me,(TEST_INFO *)data)-thread_name);sleep(TEST_INFO *)data)-require_moment);11pthread_mutex_lock(&h_mutex_read_count);read_count+; if(read_count=1)pthread_mutex_lock(&CS_DATA); pthread_mutex_unlock(&h_mutex_read_count);printw(%s ,thread_name);refresh();sleep(TEST_INFO *)data)-persist_time);pthread_mu

20、tex_lock(&h_mutex_read_count);read_count-; if(read_count=0)pthread_mutex_unlock(&CS_DATA); pthread_mutex_unlock(&h_mutex_read_count); return 0;void* RF_writer_thread(void *data) sleep(TEST_INFO *)data)-require_moment); pthread_mutex_lock(&CS_DATA); printw(%s ,(TEST_INFO *)data)-thread_name); refresh

21、();sleep(TEST_INFO *)data)-persist_time); pthread_mutex_unlock(&CS_DATA); return 0;void reader_first()int i=0;pthread_t h_threadMAX_THREAD; printw(reader first require sequence:); for(i=0;iMAX_THREAD;i+)printw(%s ,test_datai.thread_name);printw(n);printw(reader first operation sequence:); refresh();

22、pthread_mutex_init(&CS_DATA,NULL);for(i=0;iMAX_THREAD;i+)if(test_datai.thread_name0=r) pthread_create(&h_threadi,NULL,RF_reader_thread,&test_datai);else pthread_create(&h_threadi,NULL,RF_writer_thread,&test_datai);for(i=0;ithread_name);sleep(TEST_INFO *)data)-require_moment); pthread_mutex_lock(&h_m

23、utex_wait); pthread_mutex_lock(&h_mutex_read_count); read_count+;if(read_count=1)pthread_mutex_lock(&CS_DATA); pthread_mutex_unlock(&h_mutex_read_count); pthread_mutex_unlock(&h_mutex_wait);printw(%s ,thread_name);refresh();sleep(TEST_INFO *)data)-persist_time);pthread_mutex_lock(&h_mutex_read_count

24、); read_count-;if(read_count=0) pthread_mutex_unlock(&CS_DATA);pthread_mutex_unlock(&h_mutex_read_count); return 0;void* FIFO_writer_thread(void *data) sleep(TEST_INFO *)data)-require_moment); pthread_mutex_lock(&h_mutex_wait); pthread_mutex_lock(&CS_DATA);printw(%s ,(TEST_INFO *)data)-thread_name);

25、 refresh();sleep(TEST_INFO *)data)-persist_time); pthread_mutex_unlock(&CS_DATA); pthread_mutex_unlock(&h_mutex_wait);return 0;void first_come_first_served()int i=0;pthread_t h_threadMAX_THREAD;printw(FCFS require sequence:);for(i=0;iMAX_THREAD;i+)printw(%s ,test_datai.thread_name);printw(n);printw(

26、FCFS:operation sequence:);refresh();pthread_mutex_init(&CS_DATA,NULL);for(i=0;iMAX_THREAD;i+) if(test_datai.thread_name0=r) pthread_create(&h_threadi,NULL,FIFO_reader_thread,&test_datai);else13 pthread_create(&h_threadi,NULL,FIFO_writer_thread,&test_datai);for(i=0;ithread_name);sleep(TEST_INFO *)dat

27、a)-require_moment);pthread_mutex_lock(&h_mutex_reader_wait);pthread_mutex_lock(&h_mutex_first_reader_wait);pthread_mutex_lock(&h_mutex_read_count);read_count+;if(read_count=1)pthread_mutex_lock(&CS_DATA); pthread_mutex_unlock(&h_mutex_read_count); pthread_mutex_unlock(&h_mutex_first_reader_wait); pt

28、hread_mutex_unlock(&h_mutex_reader_wait);printw(%s ,thread_name);refresh();sleep(TEST_INFO *)data)-persist_time);pthread_mutex_lock(&h_mutex_read_count);read_count-;if(read_count=0)pthread_mutex_unlock(&CS_DATA);pthread_mutex_unlock(&h_mutex_read_count);return 0;void* WF_writer_thread(void *data)sle

29、ep(TEST_INFO *)data)-require_moment); pthread_mutex_lock(&h_mutex_write_count); if(write_count=0)pthread_mutex_lock(&h_mutex_first_reader_wait);write_count+;pthread_mutex_unlock(&h_mutex_write_count);pthread_mutex_lock(&CS_DATA);printw(%s ,(TEST_INFO *)data)-thread_name); refresh();sleep(TEST_INFO *

30、)data)-persist_time);pthread_mutex_unlock(&CS_DATA);pthread_mutex_lock(&h_mutex_write_count);write_count-;if(write_count=0)pthread_mutex_unlock(&h_mutex_first_reader_wait);14pthread_mutex_unlock(&h_mutex_write_count);return 0;void writer_first()int i=0;pthread_t h_threadMAX_THREAD; printw(writer fir

31、st require sequence:);for(i=0;iMAX_THREAD;i+)printw(%s ,test_datai.thread_name);printw(n);printw(writer first operation sequence:);refresh();pthread_mutex_init(&CS_DATA,NULL);for(i=0;iMAX_THREAD;i+) if(test_datai.thread_name0=r) pthread_create(&h_threadi,NULL,WF_reader_thread,&test_datai);else pthread_create(&h_threadi,NULL,WF_writer_thread,&test_datai);for(i=0;iMAX_THREAD;i+) pthread_join(h_threadi,NULL);printw(n);refresh();int main(int argc,char *argv)char select;bool end=f