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

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

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

3、有可能出现写者被饿死的情况。2、写者优先除了上述四个规那么外， 还增加写者优先的规定，即当有读者和写者同时等待时，首先满足写者。当一个写者声明想写文件时，不允许新的读者再访问文件。3、无优先除了上述四个规那么外，不再规定读写的优先权，谁先等待谁就先使用文件。实验步骤算法分析1、错误的解法semaphore r_w_w=1;reader()writer()P(r_w_w)；P(r_w_w)；读文件；写文件；V(r_w_w)；V(r_w_w)；J-J图3-1错误的解法有同学认为，可以将文件视为临界资源，使用临界资源的代码就构成临界区，为了对临界区进行管理，只需设置一个互斥信号量r_w_w，读或者写

4、之前执行 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,每一个读者到达时都要将 readerco unt加1，退出时都要将 readercou nt减1。由于只要有一个读者在读文件，便不允许写者写文件，所以，仅当readercount=O时，即尚无读者在读文件时，读者才需要执行P(r_w_w)操作。假设P(r_w_w)操作成功，读者便可去读文件，相应地，readercou nt+1。同理，仅当在执行了readercou nt减1操作后其值为 0时，才需要执行 V(r_w_w)操作，以便让写者写文件。又因为reade

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

7、r w w);06if(readerco un t=0) P(r_w_w);18写文件;07readerco un t+;19V(r w w);08V(readerco un t_mutex);2009读文件；10P(readerco un t_mutex);11readerc oun t-;12if(readerco un t=0) V(r_w_w);13V(readerco un t_mutex);14153、写者优先通过增加信号量并修改上述程序可以得到写者优先算法。为了实现写者优先算法，需要将写者和读者分开排队，并且第一个读者和其它读者也要分开排队。这样就需要三个队列， 一个是写者排队的

8、地方，另一个是第一个读者排队的地方，第三个是其它读者排队的地方。相应地需要设置三个信号量，r_w_w、first_reader_wait和reader_wait。当一个写者声明想写文件时，可以让新的读者中的第一个到first_reader_wait上排队等待；当有读者阻塞在first_reader_wait上时，让其它读者阻塞在reader_wait上；当有一个写者在写文件时，其它写者到r_w_w上排队。只要有活泼的写者或者写者队列不为空，那么阻塞新到达的读者。为了记录已经发出声明的写者数量，需要设置一个整数writercount，以表示声明要写文件的写者数目。由于只要有一个写者到达，就不允许

9、读者去读，因此仅当writercount=0，表示无写者声明写时，写者才需要执行P(first_reader_wait)操作，假设操作成功，写者便可以执行P(r_w_w)去竞争写文件权利。其它写者不需要再向读者声明，可以直接执行P(r_w_w)去竞争写文件权利。同理仅当写者在执行 writercount减1操作后其值为 便唤醒第一个被阻塞的读者去读文件。又因为 资源，所以，应该为它设置一个互斥信号量4、无优先除了在读者优先时需要的信号量r w0时，才需要执行 V(first_reader_wait)操作，以 writercount是一个可被多个写者访问的临界 writer mutex。和rea

10、dercount_mutex之外，还需要设置一个信号量wait供读者和写者排队。读者和写者都排在 wait队列上。假设有读者在读文件，那么第 一个写者阻塞在r_w_w上，其它的写者和读者阻塞在 wait上；假设有一个写者在写文件， 那么其它写者和读者都阻塞在 wait上。无优先的算法描述如图3-3所示。图3-3 尢优先算法01semaphore r_w_w=1;02semaphore wait=1;03semaphorereaderc oun t_mutex=1;04int readerco un t=0;05reader()18writer()06P(wait);19P(wait);07P(

11、readerco un t_mutex);20P(r w w);08if(readerc oun t=0) P(r_w_w);21写文件;09readerco un t+;22V(r_w_w);10V(readerco un t_mutex);23V(wait);11V(wait);2412读文件；13P(readerco un t_mutex);14readerco un t-;15if(readerc oun t=0) V(r_w_w);16V(readercount mutex);17332程序功能及界面设计该程序采用简单的控制台应用程序界面，在主界面上显示程序的功能。该程序的功能如下：

12、1. 演示读者优先算法；2. 演示写者优先算法；3. 演示无优先算法；4. 退出。3.3.3 函数设计实现读者/写者问题的源程序名称是reader_and_writer.cpp。该程序共包括10个函数。这些函数可以分成 4组。各组包含的函数及其功能如图3-4。组别包括函数函数功能-一-main()显示主菜单，接收用户的选择并执行相应的功能。-二二RF_reader_thread() RF_writer_thread() reader first()读者优先算法的读者线程函数读者优先算法的写者线程函数读者优先算法的初始化函数：创立10个线程并等待它们结束二WF_reader_thread()写者

13、优先算法的读者线程函数WF_writer_thread() writer_first()写者优先算法的写者线程函数 写者优先算法的初始化函数：创立10个线程并等待它们结束四FIFO_reader_thread()FIFO_writer_thread() first_come_first_serverd()无优先算法的读者线程函数无者优先算法的写者线程函数无者优先算法的初始化函数：创立10个线程并等待它们结束图3-4 函数功能简述程序开始局部定义了宏MAX_THREAD ，表示程序中创立的线程数。还定义了测试数据的结构体TEST_INFO，该结构体包含三个数据项：线程名称；提出请求的时刻；操作持

14、 续时间。接着定义了全局变量，这些全局变量的作用如下：数组test_data保存了 10个线程的测试数据；整数read_count记录一段时间内同时对文件进行读操作的线程数；整数write_count记录一段时间内提出写操作请求的线程数，该整数只在写者优先算法 中使用；CS_DATA是临界区变量，用来保护文件，实现对文件的读一写互斥和写一写互斥相当于算法描述中的r_w_w；互斥体h_mutex_read_count用来保护整数 read_count，以保证多个读者对 read_count的 互斥访问；互斥体h_mutex_write_count用来保护整数 write_count，以保证多个写

15、者对 write_count 的互斥访问，该互斥体只在写者优先算法中使用；互斥体h_mutex_first_reader_wait和h_mutex_reader_wait只在写者优先算法中使用，当 有写者在写文件时，提出读请求的第一个读者阻塞在h_mutex_first_reader_wait上，其余的读者阻塞在 h_mutex_reader_wait 上;互斥体h_mutex_wait只在无优先算法中使用，当文件被使用时，后继的读请求和写请 求依次阻塞在 h_mutex_wait上。3.3.4 参考源程序3.3.4.1 Linux下的参考源程序CD编译命令gcc reader_and_wri

16、ter .cpp reader_and_writer.o -curses -pthreadC程序清单#in clude <uni std.h>#in clude <pthread.h>#in clude <curses.h> #i nclude <stdlib.h> #in clude <stri ng.h> #defi ne MAX_THREAD 10typedef structchar thread_ name3;un sig ned int require_mome nt; un sig ned int persist_time

17、;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 read_count=0;int write_count=0;pthread_mutex_t CS_DATA;pt

18、hread_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_name,(TEST_INFO *)data)->thread_name);sleep(TEST_INFO *

19、)data)->require_moment);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);printw("%s ",thread_name);refresh();sleep(TEST_INFO *)data)->persist_time);pthread_mutex_lock(&h_mutex_r

20、ead_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_nam

21、e); refresh();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;i<MAX_THREAD;i+)printw("%s ",test_datai.thread_name);printw("n&quo

22、t;);printw("reader first operation sequence:");refresh();pthread_mutex_init(&CS_DATA,NULL);for(i=0;i<MAX_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,&

23、amp;test_datai);for(i=0;i<MAX_THREAD;i+) pthread_join(h_threadi,NULL);printw("n");refresh();void* FIFO_reader_thread(void *data)char thread_name3;strcpy(thread_name,(TEST_INFO *)data)->thread_name);sleep(TEST_INFO *)data)->require_moment);pthread_mutex_lock(&h_mutex_wait);pthr

24、ead_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(&

25、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* FIFO_writer_thread(void *data) sleep(TEST_INFO *)data)->require_moment); pthread_mutex_lock(&h_mutex_wait); pthread_mutex_lock(&CS_DATA);printw(&

26、quot;%s ",(TEST_INFO *)data)->thread_name);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:");

27、 for(i=0;i<MAX_THREAD;i+) printw("%s ",test_datai.thread_name);printw("n");printw("FCFS:operation sequence:");refresh();pthread_mutex_init(&CS_DATA,NULL);for(i=0;i<MAX_THREAD;i+) if(test_datai.thread_name0='r') pthread_create(&h_threadi,NULL,FIFO_r

28、eader_thread,&test_datai); elsepthread_create(&h_threadi,NULL,FIFO_writer_thread,&test_datai); for(i=0;i<MAX_THREAD;i+) pthread_join(h_threadi,NULL);printw("n");refresh();void* WF_reader_thread(void *data)char thread_name3;strcpy(thread_name,(TEST_INFO *)data)->thread_nam

29、e);sleep(TEST_INFO *)data)->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);

30、pthread_mutex_unlock(&h_mutex_first_reader_wait); pthread_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); pt

31、hread_mutex_unlock(&h_mutex_read_count); return 0;void* WF_writer_thread(void *data) sleep(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_writ

32、e_count);pthread_mutex_lock(&CS_DATA);printw("%s ",(TEST_INFO *)data)->thread_name); refresh();sleep(TEST_INFO *)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_

33、first_reader_wait); pthread_mutex_unlock(&h_mutex_write_count); return 0;void writer_first()int i=0;pthread_t h_threadMAX_THREAD; printw("writer first require sequence:"); for(i=0;i<MAX_THREAD;i+)printw("%s ",test_datai.thread_name);printw("n"); printw("writ

34、er first operation sequence:"); refresh();pthread_mutex_init(&CS_DATA,NULL);for(i=0;i<MAX_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;i<MAX_THREAD;i+)pthread_join(h_threadi,NULL);printw("n"); refresh();int main(int argc,char *argv)char select;bool end=false;initscr();while(!e nd)clear();refresh。；printw("|n");prin tw("| 1:reader first|n");prin tw("| 2:first come firs