實(shí)驗(yàn)3-讀者-寫者問(wèn)題與進(jìn)程同步

實(shí)驗(yàn)3讀者/寫者問(wèn)題與進(jìn)程同步3.1實(shí)驗(yàn)?zāi)康睦斫馀R界區(qū)和進(jìn)程互斥的概念，掌握用信號(hào)量和PV操作實(shí)現(xiàn)進(jìn)程互斥的方法。3.2實(shí)驗(yàn)要求在linux環(huán)境下編寫一個(gè)控制臺(tái)應(yīng)用程序，該程序運(yùn)行時(shí)能創(chuàng)立N個(gè)線程〔或者進(jìn)程〕，其中既有讀者線程又有寫者線程，它們按照事先設(shè)計(jì)好的測(cè)試數(shù)據(jù)進(jìn)行讀寫操作。請(qǐng)用信號(hào)量和PV操作實(shí)現(xiàn)讀者/寫者問(wèn)題。讀者/寫者問(wèn)題的描述如下：有一個(gè)被許多進(jìn)程共享的數(shù)據(jù)區(qū)，這個(gè)數(shù)據(jù)區(qū)可以是一個(gè)文件，或者主存的一塊空間〔比方一個(gè)數(shù)組或一個(gè)變量〕，甚至可以是一組處理器存放器。有一些只讀取這個(gè)數(shù)據(jù)區(qū)的進(jìn)程〔reader〕和一些只往數(shù)據(jù)區(qū)中寫數(shù)據(jù)的進(jìn)程〔writer〕。以下假設(shè)共享數(shù)據(jù)區(qū)是文件。這些讀者和寫者對(duì)數(shù)據(jù)區(qū)的操作必須滿足以下條件：讀—讀允許；讀—寫互斥；寫—寫互斥。這些條件具體來(lái)說(shuō)就是：〔1〕任意多的讀進(jìn)程可以同時(shí)讀這個(gè)文件；〔2〕一次只允許一個(gè)寫進(jìn)程往文件中寫；〔3〕如果一個(gè)寫進(jìn)程正在往文件中寫，禁止任何讀進(jìn)程或?qū)戇M(jìn)程訪問(wèn)文件；〔4〕寫進(jìn)程執(zhí)行寫操作前，應(yīng)讓已有的寫者或讀者全部退出。這說(shuō)明當(dāng)有讀者在讀文件時(shí)不允許寫者寫文件。對(duì)于讀者-寫者問(wèn)題，有三種解決方法：1、讀者優(yōu)先除了上述四個(gè)規(guī)那么外，還增加讀者優(yōu)先的規(guī)定，當(dāng)有讀者在讀文件時(shí)，對(duì)隨后到達(dá)的讀者和寫者，要首先滿足讀者，阻塞寫者。這說(shuō)明只要有一個(gè)讀者活潑，那么隨后而來(lái)的讀者都將被允許訪問(wèn)文件，從而導(dǎo)致寫者長(zhǎng)時(shí)間等待，甚至有可能出現(xiàn)寫者被餓死的情況。2、寫者優(yōu)先除了上述四個(gè)規(guī)那么外，還增加寫者優(yōu)先的規(guī)定，即當(dāng)有讀者和寫者同時(shí)等待時(shí)，首先滿足寫者。當(dāng)一個(gè)寫者聲明想寫文件時(shí)，不允許新的讀者再訪問(wèn)文件。3、無(wú)優(yōu)先除了上述四個(gè)規(guī)那么外，不再規(guī)定讀寫的優(yōu)先權(quán)，誰(shuí)先等待誰(shuí)就先使用文件。3.3實(shí)驗(yàn)步驟算法分析1、錯(cuò)誤的解法圖3-1錯(cuò)誤的解法semaphorer_w_w=1;reader(){P(r_w_w)；讀文件；V(r_w_w)；}writer(){P(r_w_w)；寫文件；V(r_w_w)；}有同學(xué)認(rèn)為，可以將文件視為臨界資源，使用臨界資源的代碼就構(gòu)成臨界區(qū)，為了對(duì)臨界區(qū)進(jìn)行管理，只需設(shè)置一個(gè)互斥信號(hào)量r_w_w，讀或者寫之前執(zhí)行P(r_w_w)，之后執(zhí)行V(r_w_w)即可，從而得到圖3-1所示的算法描述。該方法雖然能滿足讀—寫互斥和寫—寫互斥，但是不滿足讀—讀允許，只要有一個(gè)讀者在讀文件，其他的讀者都被阻塞了。可見，單純使用互斥信號(hào)量不能解決讀者/寫者問(wèn)題，還需要引入計(jì)數(shù)器對(duì)讀者進(jìn)行記數(shù)。2、讀者優(yōu)先如何糾正上述解法中存在的錯(cuò)誤呢？其實(shí)，對(duì)于相繼到達(dá)的一批讀者，并不是每個(gè)讀者都需要執(zhí)行P(r_w_w)和V(r_w_w)。在這批讀者中，只有最先到達(dá)的讀者才需要執(zhí)行P(r_w_w)，與寫者競(jìng)爭(zhēng)對(duì)文件的訪問(wèn)權(quán)，假設(shè)執(zhí)行P(r_w_w)成功那么獲得了文件的訪問(wèn)權(quán)，其他的讀者可直接訪問(wèn)文件；同理，只有最后退出臨界區(qū)的讀者需要執(zhí)行V(r_w_w)來(lái)歸還文件訪問(wèn)權(quán)。為了記錄正在讀文件的一批讀者的數(shù)量，需要設(shè)置一個(gè)整型變量readercount，每一個(gè)讀者到達(dá)時(shí)都要將readercount加1，退出時(shí)都要將readercount減1。由于只要有一個(gè)讀者在讀文件，便不允許寫者寫文件，所以，僅當(dāng)readercount=0時(shí)，即尚無(wú)讀者在讀文件時(shí)，讀者才需要執(zhí)行P(r_w_w)操作。假設(shè)P(r_w_w)操作成功，讀者便可去讀文件，相應(yīng)地，readercount+1。同理，僅當(dāng)在執(zhí)行了readercount減1操作后其值為0時(shí)，才需要執(zhí)行V(r_w_w)操作，以便讓寫者寫文件。又因?yàn)閞eadercount是一個(gè)可被多個(gè)讀者訪問(wèn)的臨界資源，所以應(yīng)該為它設(shè)置一個(gè)互斥信號(hào)量readercount_mutex.。每個(gè)讀者在訪問(wèn)readercount之前執(zhí)行P(readercount_mutex)，之后執(zhí)行V(readercount_mutex)。通過(guò)上述分析得到圖3-2所示的算法描述，其中的數(shù)字表示語(yǔ)句對(duì)應(yīng)的行號(hào)。圖3-2讀者優(yōu)先算法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、寫者優(yōu)先通過(guò)增加信號(hào)量并修改上述程序可以得到寫者優(yōu)先算法。為了實(shí)現(xiàn)寫者優(yōu)先算法，需要將寫者和讀者分開排隊(duì)，并且第一個(gè)讀者和其它讀者也要分開排隊(duì)。這樣就需要三個(gè)隊(duì)列，一個(gè)是寫者排隊(duì)的地方，另一個(gè)是第一個(gè)讀者排隊(duì)的地方，第三個(gè)是其它讀者排隊(duì)的地方。相應(yīng)地需要設(shè)置三個(gè)信號(hào)量，r_w_w、first_reader_wait和reader_wait。當(dāng)一個(gè)寫者聲明想寫文件時(shí)，可以讓新的讀者中的第一個(gè)到first_reader_wait上排隊(duì)等待；當(dāng)有讀者阻塞在first_reader_wait上時(shí)，讓其它讀者阻塞在reader_wait上；當(dāng)有一個(gè)寫者在寫文件時(shí)，其它寫者到r_w_w上排隊(duì)。只要有活潑的寫者或者寫者隊(duì)列不為空，那么阻塞新到達(dá)的讀者。為了記錄已經(jīng)發(fā)出聲明的寫者數(shù)量，需要設(shè)置一個(gè)整數(shù)writercount，以表示聲明要寫文件的寫者數(shù)目。由于只要有一個(gè)寫者到達(dá)，就不允許讀者去讀，因此僅當(dāng)writercount=0，表示無(wú)寫者聲明寫時(shí)，寫者才需要執(zhí)行P(first_reader_wait)操作，假設(shè)操作成功，寫者便可以執(zhí)行P(r_w_w)去競(jìng)爭(zhēng)寫文件權(quán)利。其它寫者不需要再向讀者聲明，可以直接執(zhí)行P(r_w_w)去競(jìng)爭(zhēng)寫文件權(quán)利。同理僅當(dāng)寫者在執(zhí)行writercount減1操作后其值為0時(shí)，才需要執(zhí)行V(first_reader_wait)操作，以便喚醒第一個(gè)被阻塞的讀者去讀文件。又因?yàn)閣ritercount是一個(gè)可被多個(gè)寫者訪問(wèn)的臨界資源，所以，應(yīng)該為它設(shè)置一個(gè)互斥信號(hào)量writer_mutex。4、無(wú)優(yōu)先除了在讀者優(yōu)先時(shí)需要的信號(hào)量r_w_w和readercount_mutex之外，還需要設(shè)置一個(gè)信號(hào)量wait供讀者和寫者排隊(duì)。讀者和寫者都排在wait隊(duì)列上。假設(shè)有讀者在讀文件，那么第一個(gè)寫者阻塞在r_w_w上，其它的寫者和讀者阻塞在wait上；假設(shè)有一個(gè)寫者在寫文件，那么其它寫者和讀者都阻塞在wait上。無(wú)優(yōu)先的算法描述如圖3-3所示。圖3-3無(wú)優(yōu)先算法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該程序采用簡(jiǎn)單的控制臺(tái)應(yīng)用程序界面，在主界面上顯示程序的功能。該程序的功能如下：演示讀者優(yōu)先算法；演示寫者優(yōu)先算法；演示無(wú)優(yōu)先算法；退出。3.3.3實(shí)現(xiàn)讀者/寫者問(wèn)題的源程序名稱是reader_and_writer.cpp。該程序共包括10個(gè)函數(shù)。這些函數(shù)可以分成4組。各組包含的函數(shù)及其功能如圖3-4。組別包括函數(shù)函數(shù)功能一main()顯示主菜單，接收用戶的選擇并執(zhí)行相應(yīng)的功能。二RF_reader_thread()RF_writer_thread()reader_first()讀者優(yōu)先算法的讀者線程函數(shù)讀者優(yōu)先算法的寫者線程函數(shù)讀者優(yōu)先算法的初始化函數(shù)：創(chuàng)立10個(gè)線程并等待它們結(jié)束三WF_reader_thread()WF_writer_thread()writer_first()寫者優(yōu)先算法的讀者線程函數(shù)寫者優(yōu)先算法的寫者線程函數(shù)寫者優(yōu)先算法的初始化函數(shù)：創(chuàng)立10個(gè)線程并等待它們結(jié)束四FIFO_reader_thread()FIFO_writer_thread()first_come_first_serverd()無(wú)優(yōu)先算法的讀者線程函數(shù)無(wú)者優(yōu)先算法的寫者線程函數(shù)無(wú)者優(yōu)先算法的初始化函數(shù)：創(chuàng)立10個(gè)線程并等待它們結(jié)束圖3-4函數(shù)功能簡(jiǎn)述程序開始局部定義了宏MAX_THREAD，表示程序中創(chuàng)立的線程數(shù)。還定義了測(cè)試數(shù)據(jù)的結(jié)構(gòu)體TEST_INFO，該結(jié)構(gòu)體包含三個(gè)數(shù)據(jù)項(xiàng)：線程名稱；提出請(qǐng)求的時(shí)刻；操作持續(xù)時(shí)間。接著定義了全局變量，這些全局變量的作用如下：數(shù)組test_data保存了10個(gè)線程的測(cè)試數(shù)據(jù)；整數(shù)read_count記錄一段時(shí)間內(nèi)同時(shí)對(duì)文件進(jìn)行讀操作的線程數(shù)；整數(shù)write_count記錄一段時(shí)間內(nèi)提出寫操作請(qǐng)求的線程數(shù)，該整數(shù)只在寫者優(yōu)先算法中使用；CS_DATA是臨界區(qū)變量，用來(lái)保護(hù)文件，實(shí)現(xiàn)對(duì)文件的讀—寫互斥和寫—寫互斥〔相當(dāng)于算法描述中的r_w_w〕；互斥體h_mutex_read_count用來(lái)保護(hù)整數(shù)read_count，以保證多個(gè)讀者對(duì)read_count的互斥訪問(wèn)；互斥體h_mutex_write_count用來(lái)保護(hù)整數(shù)write_count，以保證多個(gè)寫者對(duì)write_count的互斥訪問(wèn)，該互斥體只在寫者優(yōu)先算法中使用；互斥體h_mutex_first_reader_wait和h_mutex_reader_wait只在寫者優(yōu)先算法中使用，當(dāng)有寫者在寫文件時(shí)，提出讀請(qǐng)求的第一個(gè)讀者阻塞在h_mutex_first_reader_wait上，其余的讀者阻塞在h_mutex_reader_wait上；互斥體h_mutex_wait只在無(wú)優(yōu)先算法中使用，當(dāng)文件被使用時(shí)，后繼的讀請(qǐng)求和寫請(qǐng)求依次阻塞在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