1、Linux程序設計課程設計Linux程序設計課程組長春工業大學2017-12-24課程設計任務書課程設計題目：讀者寫者問題的設計、實現及性能分析起止日期：2017.12.25-2017.12.29設計地點：電腦科學與工程學院機房任務：1. Linux環境下分別設計并實現讀者寫者問題的讀者優先算法、寫者優先算法和無優先算法，針對測試數據得出每種算法下讀者線程和寫者線程的開始操作時刻和結束操作時刻；2. 計算每個線程的等待時間、周轉時間、總的等待時間、總的周轉時間、讀者總的等待時間、讀者總的周轉時間、寫者總的等待時間、寫者總的周轉時間、平均等待時間、平均周轉時間；3. 使用適當的可視化方法例如甘特

2、圖對計算結果進行可視化；4. 比較三種算法的性能。日程：本次設計共一周時間，參考日程安排如下：第1天：讀者優先算法設計、實現與測試；第2天：寫者優先算法設計、實現與測試；第3天：無優先算法設計、實現與測試；第4天：測試結果可視化及算法性能比較；第5天：答辯。報告：僅寫自己完成的設計成果，包括：5. 1.充分注釋的源代碼未寫代碼者略去測試結果結果可視化4.性能比較參考文獻心得指導教師：150408焦素云150409王俊華目錄第1章設計要求0設計目的0設計要求0第2章測試數據設計1第3章算法實現2第4章算法結果18第5章結果可視化20第6章性能分析20參考文獻21心得21第1章設計要求理解臨界區和

3、進程互斥的概念，掌握用信號量和PV操作實現進程互斥的方法。在linux環境下編寫應用程序，該程序運行時能創建N個線程，其中既有讀者線程又有寫者線程，它們按照事先設計好的測試數據進行讀寫操作。讀者/寫者問題描述如下：有一個被許多進程共享的數據區，這個數據區可以是一個文件，或者主存的一塊空間，甚至可以是一組處理器寄存器。有一些只讀取這個數據區的線程reader和一些只往數據區中寫數據的線程writer。以下假設共享數據區是文件。這些讀者和寫者對數據區的操作必須滿足以下條件：讀一讀允許；讀寫互斥；寫一寫互斥。這些條件具體來說就是：1任意多的讀線程可以同時讀這個文件；2一次只允許一個寫線程往文件中寫；

4、3如果一個寫線程正在往文件中寫，禁止任何讀線程或寫線程訪問文件；4寫線程執行寫操作前，應讓已有的寫者或讀者全部退出。這說明當有讀者在讀文件時不允許寫者寫文件。對于讀者-寫者問題，有三種解決方法：1、讀者優先除了上述四個規則外，還增加讀者優先的規定，當有讀者在讀文件時，對隨后到達的讀者和寫者，要首先滿足讀者，阻塞寫者。這說明只要有一個讀者活躍，那么隨后而來的讀者都將被允許訪問文件，從而導致寫者長時間等待，甚至有可能出現寫者被餓死的情況。2、寫者優先除了上述四個規則外，還增加寫者優先的規定，即當有讀者和寫者同時等待時，首先滿足寫者。當一個寫者聲明想寫文件時，不允許新的讀者再訪問文件。3、無優先除了

5、上述四個規則外，不再規定讀寫的優先權，誰先等待誰就先使用文件。第2章測試數據設計no測試數據線程名稱申請時刻持續使用時間r1015r2115w133r3”42w256w3610r478r592w41018w5122為了驗證算法的正確性，需要設計測試數據，并對測試數據進行分析，總結出在該組測試數據下，程序應該得到什么結果，然后運行程序，將程序運行結果與分析結果相比較，如果二者一致，則可認為程序是正確的。作者設計的測試數據如表1所示，包括10個線程，其中有5個讀者線程r1r5,另外5個是寫者線程w1w5。讀者線程r1在時刻0提出讀請求，如果請求得到允許，r1將用15秒的時間讀文件；寫者線程w3將用

6、10秒的時間寫文件。從r1,r2,w1,r3,w2,w3,r4,r5,w4,w5。w3在時刻6提出寫請求，如果請求得到允許,表中可以看出，10個線程提出請求的次序是:1讀者優先算法線程實際讀寫文件順序為：r1,r2,r3,r4,r5,w1,w2,w3,w4,w5。執行情況見表2。表2線程的運行狀況線程申鬲持續開始操結束操名稱時刻時間作時刻作時刻r1015015r2115116r3”4246r478715r5”92911w1331619w2561925w3”6102535w410183553w5”12253552寫者優先算法線程實際讀寫文件順序為：r1,r2,w1,w2,w3,w4,w5,r3,

7、r4,r5。執行情況見表3。表3線程的運行狀況線程申請持續開始操結束操名稱時刻時間作時刻作時刻r1015015r2115116w1331619w2561925w36102535w410183553w51225355r3425557r4785563r59255573無優先算法線程實際讀寫文件順序為：r1,r2,w1,r3,w2,w3,r4,r5,w4,w5。執行情況見表4。表4線程的運行狀況線程申鬲持續開始操結束操名稱時刻時間作時刻作時刻r1015015r2115116w1331619r3421921w2562127w36102737r4783745r5923739w410184563w5122

8、6365第3章算法實現讀者優先算法:#include#include#include#include#include#include#defineMAX_THREAD10#defineSNL8typedefstructchartn3;/nameofthreadunsignedintrm;/themomentwhenthisthreadrequesttoaccessdata.unsignedintpt;/durationofoperationunsignedinti;/sametormunsignedintb;/instanceatwhichthisthreadbegintooperatedat

9、aunsignedinte;/endinginstanceTEST_INFO;/TEST_INFOtest_dataMAX_THREAD;typedefstructcharsnSNL+1;/studentnumberTEST_INFOtiMAX_THREAD;/testitemTI;/test_item_for_student/TItest_itemsSTUDENTS;TItest_item=20152566,w1”,4,7,r1”,11,14,r2”,1,5,w2”,8,11,w3”,15,2,r3”,5,8,r4”,12,15,w4”,5,2,r5”,9,12,r6”,15,3;charr

10、_seqMAX_THREAD3;charo_seqMAX_THREAD3;intsr=0;intso=0;intrc=0;/counthowmanyreadersarereadingpthread_mutex_tcs_d;/guarenteemutuallyaccessdatapthread_mutex_tcs_rc;/guarenteemutuallyaccessrcpthread_mutex_tcs_sr;/guarenteemutuallyaccesssrpthread_mutex_tcs_so;/guarenteemutuallyaccesssrtime_tbase;/themomen

11、twhenfunctionmainbegin/*voidprint_answer()(inti;printf(%sn”,test_item.sn);printf(namer_mp_ti_tb_te_tn);for(i=0;iMAX_THREAD;i+)printf(%4s%4d%4d%8d%8d%8dn”,(test_item.ti)i.tn,(test_item.ti)i.rm,(test_item).tii.pt,(test_item.ti)i.i,(test_item.ti)i.b,(test_item.ti)i.e);printf(r_seq:);for(i=0;iMAX_THREAD

12、;i+)printf(%4s”,r_seqi);printf(n);printf(o_seq:);for(i=0;iMAX_THREAD;i+)printf(%4s,o_seqi);printf(n);*/voidsave_answer(FILE*f)inti;fprintf(f,t%s_answer.txtntr/wproblem:readfirstnn,test_item.sn);fprintf(f,namer_mp_ti_tb_te_tn);for(i=0;iMAX_THREAD;i+)fprintf(f,%4s%4d%4d%8d%8d%8dn,(test_item.ti)i.tn,(t

13、est_item.ti)i.rm,(test_item).tii.pt,(test_item.ti)i.i,(test_item.ti)i.b,(test_item.ti)i.e);fprintf(f,n);fprintf(f,r_seq:);for(i=0;iMAX_THREAD;i+)fprintf(f,%4s”,r_seqi);fprintf(f,n);fprintf(f,o_seq:);for(i=0;irm);gettimeofday(&t,NULL);(TEST_INFO*)td)-i=difftime(t.tv_sec,rl);pthread_mutex_lock(&cs_sr)

14、;strcpy(r_seqsr+,(TEST_INFO*)td)-tn);pthread_mutex_unlock(&cs_sr);pthread_mutex_lock(&cs_rc);rc+;if(rc=1)pthread_mutex_lock(&cs_d);pthread_mutex_unlock(&cs_rc);gettimeofday(&t,NULL);(TEST_INFO*)td)-b=difftime(t.tv_sec,rl);pthread_mutex_lock(&cs_so);strcpy(o_seqso+,(TEST_INFO*)td)-tn);pthread_mutex_u

15、nlock(&cs_so);sleep(TEST_INFO*)td)-pt);gettimeofday(&t,NULL);(TEST_INFO*)td)-e=difftime(t.tv_sec,rl);pthread_mutex_lock(&cs_rc);rc-;if(rc=0)pthread_mutex_unlock(&cs_d);pthread_mutex_unlock(&cs_rc);return0;void*w(void*td)structtimevalt;time_twl=base;sleep(TEST_INFO*)td)-rm);gettimeofday(&t,NULL);(TES

16、T_INFO*)td)-i=difftime(t.tv_sec,wl);pthread_mutex_lock(&cs_sr);strcpy(r_seqsr+,(TEST_INFO*)td)-tn);pthread_mutex_unlock(&cs_sr);pthread_mutex_lock(&cs_d);gettimeofday(&t,NULL);(TEST_INFO*)td)-b=difftime(t.tv_sec,wl);pthread_mutex_lock(&cs_so);strcpy(o_seqso+,(TEST_INFO*)td)-tn);pthread_mutex_unlock(

17、&cs_so);sleep(TEST_INFO*)td)-pt);gettimeofday(&t,NULL);(TEST_INFO*)td)-e=difftime(t.tv_sec,wl);pthread_mutex_unlock(&cs_d);return0;voidcreate_exam()inti=0;pthread_thtMAX_THREAD;pthread_mutex_init(&cs_d,NULL);pthread_mutex_init(&cs_rc,NULL);pthread_mutex_init(&cs_sr,NULL);學習文檔僅供參考pthread_mutex_init(&

18、cs_so,NULL);structtimevalt;gettimeofday(&t,NULL);base=t.tv_sec;for(i=0;iMAX_THREAD;i+)if(test_item.ti)i.tn0=r)pthread_create(&hti,NULL,r,&(test_item.ti)i);elseif(test_item.ti)i.tn0=w)pthread_create(&hti,NULL,w,&(test_item.ti)i);for(i=0;iMAX_THREAD;i+)pthread_join(hti,NULL);pthread_mutex_destroy(&cs_

19、d);pthread_mutex_destroy(&cs_rc);pthread_mutex_destroy(&cs_sr);pthread_mutex_destroy(&cs_so);intmain(intargc,char*argv)inti=0;intsi,pos;intfd;FILE*fa;charfile_name100;create_exam();sprintf(file_name,%s_answer.txt,test_item.sn);if(fa=fopen(file_name,w)=NULL)printf(Erroropenninganswerfile:%sn”,file_na

20、me);exit(3);save_answer(fa);exit(0);1.寫優先算法#include#include#include#include#include#include#include#defineMAX_THREAD10#defineSNL8typedefstructchartn3;/nameofthreadunsignedintrm;/themomentwhenthisthreadrequesttoaccessdata.unsignedintpt;/durationofoperationunsignedinti;/sametormunsignedintb;/instancea

21、twhichthisthreadbegintooperatedataunsignedinte;/endinginstanceTEST_INFO;/TEST_INFOtest_dataMAX_THREAD;typedefstructcharsn100;/studentnumberTEST_INFOtiMAX_THREAD;/testitemTI;/test_item_for_student/TItest_itemsSTUDENTS;TItest_item=20152566,w1”,4,7,r1”,11,14,r2”,1,5,w2”,8,11,w3”,15,2,r3”,5,8,r4”,12,15,

22、w4”,5,2,r5”,9,12,r6”,15,3;charr_seqMAX_THREAD3;charo_seqMAX_THREAD3;intsr=0;intso=0;intrc=0;/counthowmanyreadersarereadingpthread_mutex_tcs_d;/guarenteemutuallyaccessdatapthread_mutex_tcs_rc;/guarenteemutuallyaccessrcpthread_mutex_tcs_sr;/guarenteemutuallyaccesssrpthread_mutex_tcs_so;/guarenteemutua

23、llyaccesssrtime_tbase;/themomentwhenfunctionmainbegin/*voidprint_answer()inti;printf(%sn”,test_item.sn);printf(namer_mp_ti_tb_te_tn);for(i=0;iMAX_THREAD;i+)printf(%4s%4d%4d%8d%8d%8dn”,(test_item.ti)i.tn,(test_item.ti)i.rm,(test_item).tii.pt,(test_item.ti)i.i,(test_item.ti)i.b,(test_item.ti)i.e);prin

24、tf(r_seq:);for(i=0;iMAX_THREAD;i+)printf(%4s,r_seqi);printf(n);printf(o_seq:);for(i=0;iMAX_THREAD;i+)printf(%4s,o_seqi);printf(n);*/voidsave_answer(FILE*f)/savetheresultinti;fprintf(f,t%s_answer.txtntr/wproblem:readfirstnn,test_item.sn);fprintf(f,namer_mp_ti_tb_te_tn);for(i=0;iMAX_THREAD;i+)fprintf(

25、f,%4s%4d%4d%8d%8d%8dn”,(test_item.ti)i.tn,(test_item.ti)i.rm,(test_item).tii.pt,(test_item.ti)i.i,(test_item.ti)i.b,(test_item.ti)i.e);fprintf(f,n);fprintf(f,r_seq:);for(i=0;iMAX_THREAD;i+)fprintf(f,%4s”,r_seqi);fprintf(f,n);fprintf(f,o_seq:);for(i=0;irm);/休眠讀線程進入的時間長gettimeofday(&t,NULL);/獲得當前的時間(T

26、EST_INFO*)td)-i=difftime(t.tv_sec,rl);/將系統時間與main主函數執行的時間差賦值給i變量讀線程進入的時間pthread_mutex_lock(&cs_sr);/建立互斥鎖strcpy(r_seqsr+,(TEST_INFO*)td)-tn);pthread_mutex_unlock(&cs_sr);/解除互斥鎖pthread_mutex_lock(&cs_rc);rc+;if(rc=1)pthread_mutex_lock(&cs_d);pthread_mutex_unlock(&cs_rc);gettimeofday(&t,NULL);/獲得當前的時間

27、(TEST_INFO*)td)-b=difftime(t.tv_sec,rl);/將系統時間與main主函數執行的時間差賦值給b變量讀線程開始的時間pthread_mutex_lock(&cs_so);strcpy(o_seqso+,(TEST_INFO*)td)-tn);/將讀線程名復制給0_seq隊列pthread_mutex_unlock(&cs_so);sleep(TEST_INFO*)td)-pt);/休眠寫進程持續的時間長gettimeofday(&t,NULL);/獲得當前的時間(TEST_INFO*)td)-e=difftime(t.tv_sec,rl);/pthread_mu

28、tex_lock(&cs_rc);rc-;if(rc=0)pthread_mutex_unlock(&cs_d);pthread_mutex_unlock(&cs_rc);return0;void*r(void*td)structtimevalt;time_twl=base;sleep(TEST_INFO*)td)-rm);/休眠寫進程進入的時間長gettimeofday(&t,NULL);(TEST_INFO*)td)-i=difftime(t.tv_sec,wl);/將系統時間與main主函數執行的時間差賦值給i變量寫線程進入的時間pthread_mutex_lock(&cs_sr);/建

29、立互斥鎖strcpy(r_seqsr+,(TEST_INFO*)td)-tn);/將寫線程名復制給r_seq隊列pthread_mutex_unlock(&cs_sr);/解除互斥鎖pthread_mutex_lock(&cs_d);gettimeofday(&t,NULL);/獲得當前的時間(TEST_INFO*)td)-b=difftime(t.tv_sec,wl);/將系統時間與main主函數執行的時間差賦值給b變量寫線程開始的時間pthread_mutex_lock(&cs_so);strcpy(o_seqso+,(TEST_INFO*)td)-tn);/將寫線程名復制給o_seq隊列

30、pthread_mutex_unlock(&cs_so);sleep(TEST_INFO*)td)-pt);/休眠寫進程持續的時間長gettimeofday(&t,NULL);/獲取當前的時間(TEST_INFO*)td)-e=difftime(t.tv_sec,wl);/將系統時間與main主函數執行的時間差賦值給e變量寫線程結束的時間pthread_mutex_unlock(&cs_d);return0;voidcreate_exam()inti=0;pthread_thtMAX_THREAD;pthread_mutex_init(&cs_d,NULL);/初始化互斥鎖pthread_mu

31、tex_init(&cs_rc,NULL);pthread_mutex_init(&cs_sr,NULL);pthread_mutex_init(&cs_so,NULL);structtimevalt;gettimeofday(&t,NULL);base=t.tv_sec;for(i=0;iMAX_THREAD;i+)/分別創建讀寫線程的初始化if(test_item.ti)i.tn0=r)pthread_create(&hti,NULL,r,&(test_item.ti)i);elseif(test_item.ti)i.tn0=w)pthread_create(&hti,NULL,w,&(t

32、est_item.ti)i);for(i=0;iMAX_THREAD;i+)pthread_join(hti,NULL);pthread_mutex_destroy(&cs_d);/銷毀互斥鎖pthread_mutex_destroy(&cs_rc);pthread_mutex_destroy(&cs_sr);pthread_mutex_destroy(&cs_so);intmain(intargc,char*argv)(inti=0;intsi,pos;intfd;FILE*fa;charfile_name100;create_exam();sprintf(file_name,%s_answ

33、er.txt”,test_item.sn);/從文件中讀取if(fa=fopen(file_name,w)=NULL)printf(Erroropenninganswerfile:%sn”,file_name);exit(3);save_answer(fa);exit(0);2.無優先算法#include#include#include#include#include#include#include#defineMAX_THREAD10#defineSNL8typedefstructchartn3;/nameofthreadunsignedintrm;/themomentwhenthisthr

34、eadrequesttoaccessdata.unsignedintpt;/durationofoperationunsignedinti;/sametormunsignedintb;/instanceatwhichthisthreadbegintooperatedata學習文檔僅供參考unsignedinte;/endinginstanceTEST_INFO;/TEST_INFOtest_dataMAX_THREAD;typedefstructcharsn100;/studentnumberTEST_INFOtiMAX_THREAD;/testitemTI;/test_item_for_st

35、udent/TItest_itemsSTUDENTS;TItest_item=20152566,w1”,4,7,r1”,11,14,r2”,1,5,w2”,8,11,w3”,15,2,r3”,5,8,r4”,12,15,w4”,5,2,r5”,9,12,r6”,15,3;charr_seqMAX_THREAD3;charo_seqMAX_THREAD3;intsr=0;intso=0;intrc=0;/counthowmanyreadersarereadingpthread_mutex_tcs_d;/guarenteemutuallyaccessdatapthread_mutex_tcs_rc

36、;/guarenteemutuallyaccessrcpthread_mutex_tcs_sr;/guarenteemutuallyaccesssrpthread_mutex_tcs_so;/guarenteemutuallyaccesssrtime_tbase;/themomentwhenfunctionmainbegin/*voidprint_answer()inti;printf(%sn”,test_item.sn);printf(namer_mp_ti_tb_te_tn);for(i=0;iMAX_THREAD;i+)printf(%4s%4d%4d%8d%8d%8dn,(test_i

37、tem.ti)i.tn,(test_item.ti)i.rm,(test_item).tii.pt,(test_item.ti)i.i,(test_item.ti)i.b,(test_item.ti)i.e);printf(r_seq:);for(i=0;iMAX_THREAD;i+)printf(%4s”,r_seqi);printf(n);printf(o_seq:);for(i=0;iMAX_THREAD;i+)printf(%4s,o_seqi);printf(n);*/voidsave_answer(FILE*f)/savetheresultinti;fprintf(f,t%s_an

38、swer.txtntr/wproblem:readfirstnn,test_item.sn);fprintf(f,namer_mp_ti_tb_te_tn);for(i=0;iMAX_THREAD;i+)fprintf(f,%4s%4d%4d%8d%8d%8dn”,(test_item.ti)i.tn,(test_item.ti)i.rm,(test_item).tii.pt,(test_item.ti)i.i,(test_item.ti)i.b,(test_item.ti)i.e);fprintf(f,n);fprintf(f,r_seq:);for(i=0;iMAX_THREAD;i+)f

39、printf(f,%4s,r_seqi);fprintf(f,n);fprintf(f,o_seq:);for(i=0;irm);/休眠讀線程進入的時間長gettimeofday(&t,NULL);/獲得當前的時間(TEST_INFO*)td)-i=difftime(t.tv_sec,rl);/將系統時間與main主函數執行的時間差賦值給i變量讀線程進入的時間pthread_mutex_lock(&cs_sr);/建立互斥鎖strcpy(r_seqsr+,(TEST_INFO*)td)-tn);pthread_mutex_unlock(&cs_sr);/解除互斥鎖pthread_mutex_l

40、ock(&cs_rc);rc+;if(rc=1)pthread_mutex_lock(&cs_d);pthread_mutex_unlock(&cs_rc);gettimeofday(&t,NULL);/獲得當前的時間(TEST_INFO*)td)-b=difftime(t.tv_sec,rl);/將系統時間與main主函數執行的時間差賦值給b變量讀線程開始的時間pthread_mutex_lock(&cs_so);strcpy(o_seqso+,(TEST_INFO*)td)-tn);/將讀線程名復制給0_seq隊列pthread_mutex_unlock(&cs_so);sleep(TES

41、T_INFO*)td)-pt);/休眠寫進程持續的時間長gettimeofday(&t,NULL);/獲得當前的時間(TEST_INFO*)td)-e=difftime(t.tv_sec,rl);/pthread_mutex_lock(&cs_rc);rc-;if(rc=0)pthread_mutex_unlock(&cs_d);pthread_mutex_unlock(&cs_rc);return0;void*w(void*td)(structtimevalt;time_twl=base;sleep(TEST_INFO*)td)-rm);/休眠寫進程進入的時間長gettimeofday(&t

42、,NULL);(TEST_INFO*)td)-i=difftime(t.tv_sec,wl);/將系統時間與main主函數執行的時間差賦值給i變量寫線程進入的時間pthread_mutex_lock(&cs_sr);/建立互斥鎖strcpy(r_seqsr+,(TEST_INFO*)td)-tn);/將寫線程名復制給r_seq隊列pthread_mutex_unlock(&cs_sr);/解除互斥鎖pthread_mutex_lock(&cs_d);gettimeofday(&t,NULL);/獲得當前的時間(TEST_INFO*)td)-b=difftime(t.tv_sec,wl);/將系統時間與main主函數執行的時間差賦值給b變量寫線程開始的時間pthread_mutex_lock(&cs_so);strcpy(o_seqso+,(TEST_INFO*)td)-tn);/將寫線程名復制給o_seq隊列pthread_mutex_unlock(&cs_so);sleep(TEST_INFO*)td)-pt);/休眠寫進程持續的時間長gettimeofday(&t,NULL);/獲取當前的時間(TEST_INFO*)td)-e=d