实验3-读者-写者问题与进程同步_第1页
实验3-读者-写者问题与进程同步_第2页
实验3-读者-写者问题与进程同步_第3页
实验3-读者-写者问题与进程同步_第4页
实验3-读者-写者问题与进程同步_第5页
已阅读5页,还剩3页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

实验3读者/写者问题与进程同步3.1实验目的理解临界区和进程互斥的概念,掌握用信号量和PV操作实现进程互斥的方法。3.2实验要求在linux环境下编写一个控制台应用程序,该程序运行时能创立N个线程〔或者进程〕,其中既有读者线程又有写者线程,它们按照事先设计好的测试数据进行读写操作。请用信号量和PV操作实现读者/写者问题。读者/写者问题的描述如下:有一个被许多进程共享的数据区,这个数据区可以是一个文件,或者主存的一块空间〔比方一个数组或一个变量〕,甚至可以是一组处理器存放器。有一些只读取这个数据区的进程〔reader〕和一些只往数据区中写数据的进程〔writer〕。以下假设共享数据区是文件。这些读者和写者对数据区的操作必须满足以下条件:读—读允许;读—写互斥;写—写互斥。这些条件具体来说就是:〔1〕任意多的读进程可以同时读这个文件;〔2〕一次只允许一个写进程往文件中写;〔3〕如果一个写进程正在往文件中写,禁止任何读进程或写进程访问文件;〔4〕写进程执行写操作前,应让已有的写者或读者全部退出。这说明当有读者在读文件时不允许写者写文件。对于读者-写者问题,有三种解决方法:1、读者优先除了上述四个规那么外,还增加读者优先的规定,当有读者在读文件时,对随后到达的读者和写者,要首先满足读者,阻塞写者。这说明只要有一个读者活泼,那么随后而来的读者都将被允许访问文件,从而导致写者长时间等待,甚至有可能出现写者被饿死的情况。2、写者优先除了上述四个规那么外,还增加写者优先的规定,即当有读者和写者同时等待时,首先满足写者。当一个写者声明想写文件时,不允许新的读者再访问文件。3、无优先除了上述四个规那么外,不再规定读写的优先权,谁先等待谁就先使用文件。3.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);}有同学认为,可以将文件视为临界资源,使用临界资源的代码就构成临界区,为了对临界区进行管理,只需设置一个互斥信号量r_w_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)成功那么获得了文件的访问权,其他的读者可直接访问文件;同理,只有最后退出临界区的读者需要执行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}3、写者优先通过增加信号量并修改上述程序可以得到写者优先算法。为了实现写者优先算法,需要将写者和读者分开排队,并且第一个读者和其它读者也要分开排队。这样就需要三个队列,一个是写者排队的地方,另一个是第一个读者排队的地方,第三个是其它读者排队的地方。相应地需要设置三个信号量,r_w_w、first_reader_wait和reader_wait。当一个写者声明想写文件时,可以让新的读者中的第一个到first_reader_wait上排队等待;当有读者阻塞在first_reader_wait上时,让其它读者阻塞在reader_wait上;当有一个写者在写文件时,其它写者到r_w_w上排队。只要有活泼的写者或者写者队列不为空,那么阻塞新到达的读者。为了记录已经发出声明的写者数量,需要设置一个整数writercount,以表示声明要写文件的写者数目。由于只要有一个写者到达,就不允许读者去读,因此仅当writercount=0,表示无写者声明写时,写者才需要执行P(first_reader_wait)操作,假设操作成功,写者便可以执行P(r_w_w)去竞争写文件权利。其它写者不需要再向读者声明,可以直接执行P(r_w_w)去竞争写文件权利。同理仅当写者在执行writercount减1操作后其值为0时,才需要执行V(first_reader_wait)操作,以便唤醒第一个被阻塞的读者去读文件。又因为writercount是一个可被多个写者访问的临界资源,所以,应该为它设置一个互斥信号量writer_mutex。4、无优先除了在读者优先时需要的信号量r_w_w和readercount_mutex之外,还需要设置一个信号量wait供读者和写者排队。读者和写者都排在wait队列上。假设有读者在读文件,那么第一个写者阻塞在r_w_w上,其它的写者和读者阻塞在wait上;假设有一个写者在写文件,那么其它写者和读者都阻塞在wait上。无优先的算法描述如图3-3所示。图3-3无优先算法01semaphorer_w_w=1;02semaphorewait=1;

03semaphorereadercount_mutex=1;04intreadercount=0;05reader(){06P(wait);07P(readercount_mutex);08if(readercount==0)P(r_w_w);09readercount++;10V(readercount_mutex);11V(wait);12读文件;13P(readercount_mutex);14readercount--;15if(readercount==0)V(r_w_w);16V(readercount_mutex);17}18writer(){19P(wait);20P(r_w_w);21写文件;22V(r_w_w);23V(wait);24}3.3.2该程序采用简单的控制台应用程序界面,在主界面上显示程序的功能。该程序的功能如下:演示读者优先算法;演示写者优先算法;演示无优先算法;退出。3.3.3实现读者/写者问题的源程序名称是reader_and_writer.cpp。该程序共包括10个函数。这些函数可以分成4组。各组包含的函数及其功能如图3-4。组别包括函数函数功能一main()显示主菜单,接收用户的选择并执行相应的功能。二RF_reader_thread()RF_writer_thread()reader_first()读者优先算法的读者线程函数读者优先算法的写者线程函数读者优先算法的初始化函数:创立10个线程并等待它们结束三WF_reader_thread()WF_writer_thread()writer_first()写者优先算法的读者线程函数写者优先算法的写者线程函数写者优先算法的初始化函数:创立10个线程并等待它们结束四FIFO_reader_thread()FIFO_writer_thread()first_come_first_serverd()无优先算法的读者线程函数无者优先算法的写者线程函数无者优先算法的初始化函数:创立10个线程并等待它们结束图3-4函数功能简述程序开始局部定义了宏MAX_THREAD,表示程序中创立的线程数。还定义了测试数据的结构体TEST_INFO,该结构体包含三个数据项:线程名称;提出请求的时刻;操作持续时间。接着定义了全局变量,这些全局变量的作用如下:数组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,以保证多个写者对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.1eq\o\ac(○,1)编译命令gccreader_and_writer.cpp–oreader_and_writer.o–lcurses–lpthreadeq\o\ac(○,2)程序清单#include<unistd.h>#include<pthread.h>#include<curses.h>#include<stdlib.h>#include<string.h>#defineMAX_THREAD10typedefstruct{ charthread_name[3]; unsignedintrequire_moment; unsignedintpersist_time;}TEST_INFO;TEST_INFOtest_data[MAX_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}};intread_count=0;intwrite_count=0;pthread_mutex_tCS_DATA;pthread_mutex_th_mutex_read_count;pthread_mutex_th_mutex_write_count;pthread_mutex_th_mutex_reader_wait;pthread_mutex_th_mutex_first_reader_wait;pthread_mutex_th_mutex_wait;void*RF_reader_thread(void*data){ charthread_name[3]; strcpy(thread_name,((TEST_INFO*)data)->thread_name); sleep(((TEST_INFO*)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_read_count); read_count--; if(read_count==0) pthread_mutex_unlock(&CS_DATA); pthread_mutex_unlock(&h_mutex_read_count); return0;}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(); sleep(((TEST_INFO*)data)->persist_time); pthread_mutex_unlock(&CS_DATA); return0;}voidreader_first(){ inti=0; pthread_th_thread[MAX_THREAD]; printw("readerfirstrequiresequence:"); for(i=0;i<MAX_THREAD;i++){ printw("%s",test_data[i].thread_name); }; printw("\n"); printw("readerfirstoperationsequence:"); refresh(); pthread_mutex_init(&CS_DATA,NULL); for(i=0;i<MAX_THREAD;i++){ if(test_data[i].thread_name[0]=='r') pthread_create(&h_thread[i],NULL,RF_reader_thread,&test_data[i]); else pthread_create(&h_thread[i],NULL,RF_writer_thread,&test_data[i]); } for(i=0;i<MAX_THREAD;i++){ pthread_join(h_thread[i],NULL); }printw("\n"); refresh();}void*FIFO_reader_thread(void*data){ charthread_name[3]; strcpy(thread_name,((TEST_INFO*)data)->thread_name); sleep(((TEST_INFO*)data)->require_moment); pthread_mutex_lock(&h_mutex_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); read_count--; if(read_count==0) pthread_mutex_unlock(&CS_DATA); pthread_mutex_unlock(&h_mutex_read_count); return0;}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); refresh(); sleep(((TEST_INFO*)data)->persist_time); pthread_mutex_unlock(&CS_DATA); pthread_mutex_unlock(&h_mutex_wait); return0;}voidfirst_come_first_served(){ inti=0; pthread_th_thread[MAX_THREAD]; printw("FCFSrequiresequence:"); for(i=0;i<MAX_THREAD;i++){ printw("%s",test_data[i].thread_name); }; printw("\n"); printw("FCFS:operationsequence:"); refresh(); pthread_mutex_init(&CS_DATA,NULL); for(i=0;i<MAX_THREAD;i++){ if(test_data[i].thread_name[0]=='r') pthread_create(&h_thread[i],NULL,FIFO_reader_thread,&test_data[i]); else pthread_create(&h_thread[i],NULL,FIFO_writer_thread,&test_data[i]); } for(i=0;i<MAX_THREAD;i++){ pthread_join(h_thread[i],NULL); }printw("\n"); refresh();}void*WF_reader_thread(void*data){ charthread_name[3]; strcpy(thread_name,((TEST_INFO*)data)->thread_name); 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); 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); pthread_mutex_unlock(&h_mutex_read_count); return0;}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_write_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_first_reader_wait); pthread_mutex_unlock(&h_mutex_write_count); return0;}voidwriter_first(){ inti=0; pthread_th_thread[MAX_THREAD]; printw("writerfirstrequiresequence:"); for(i=0;i<MAX_THREAD;i++){ printw("%s",test_data[i].thread_name); } printw("\n"); printw("writerfirstoperationsequence:"); refresh(); pthread_mutex_init(&CS_DATA,NULL); for(i=0;i<MAX_THREAD;i++){ if(test_data[i].thread_name[0]=='r') pthread_create(&h_thread[i],NULL,WF_reader_thread,&test_data[i]); else pthread_create(&h_thread[i],NULL,WF_writer_thread,&test_data[i]); } for(i=0;i<MAX_THREAD;i++){ pthread_join(h_thread[i],NULL); }printw("\n"); refresh();}intmain(intargc,char*argv[]){ charselect; boolend=false; initscr(); while(!end){ clear(); refresh(); printw("|-----------------------------------|\n"); printw("|1:readerfirst

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论