操作系統(tǒng)課程設(shè)計-用多線程同步方法解決睡眠理發(fā)師問題(Sleeping-Barber-Problem)

1、題目：用多線程同步方法解決睡眠理發(fā)師問題（Sleeping-BarberProblem）初始條件：1操作系統(tǒng)：Linux2程序設(shè)計語言：C語言3.設(shè)有一個理發(fā)師，5把椅子（另外還有一把理發(fā)椅），幾把椅子可用連續(xù)存儲單元。要求完成的主要任務(wù)：（包括課程設(shè)計工作量及其技術(shù)要求，以及說明書撰寫等具體要求）1技術(shù)要求：1）為每個理發(fā)師顧客產(chǎn)生一個線程，設(shè)計正確的同步算法2）每個顧客進入理發(fā)室后，即時顯示“Entered及其線程自定義標識，還同時顯示理發(fā)室共有幾名顧客及其所坐的位置。3）至少有10個顧客，每人理發(fā)至少3秒鐘。4）多個顧客須共享操作函數(shù)代碼。2.設(shè)計說明書內(nèi)容要求：1）設(shè)計題目與要求2）總

2、的設(shè)計思想及系統(tǒng)平臺、語言、工具等。3）數(shù)據(jù)結(jié)構(gòu)與模塊說明（功能與流程圖）4）給出用戶名、源程序名、目標程序名和源程序及其運行結(jié)果。（要注明存儲各個程序及其運行結(jié)果的主機IP地址和目錄。）5）運行結(jié)果與運行情況（提示:（1）連續(xù)存儲區(qū)可用數(shù)組實現(xiàn)。（2）編譯命令可用：cc-lpthread-o目標文件名源文件名（3）多線程編程方法參見附件。）1設(shè)計題目與要求設(shè)計題目用多線程同步方法解決睡眠理發(fā)師問題(Sleeping-BarberProblem)設(shè)計要求初始條件操作系統(tǒng)：Linux程序設(shè)計語言：C語言設(shè)有一個理發(fā)師，5把椅子(另外還有一把理發(fā)椅)，幾把椅子可用連續(xù)存儲單元。技術(shù)要求為每個理發(fā)師

3、顧客產(chǎn)生一個線程，設(shè)計正確的同步算法每個顧客進入理發(fā)室后，即時顯示“Entered及其線程自定義標識，還同時顯示理發(fā)室共有幾名顧客及其所坐的位置。至少有10個顧客，每人理發(fā)至少3秒鐘。多個顧客須共享操作函數(shù)代碼。2總體設(shè)計思想及開發(fā)環(huán)境與工具總體設(shè)計思想題目中要求描述理發(fā)師和顧客的行為，因此需要兩類線程barber()和customer()分別描述理發(fā)師和顧客的行為。其中，理發(fā)師有活動有理發(fā)和睡覺兩個事件；等待和理發(fā)二個事件。店里有固定的椅子數(shù)，上面坐著等待的顧客，顧客在到來這個事件時，需判斷有沒有空閑的椅子，理發(fā)師決定要理發(fā)或睡覺時，也要判斷椅子上有沒有顧客。所以，顧客和理發(fā)師之間的關(guān)系表現(xiàn)

4、為：理發(fā)師和顧客之間同步關(guān)系：當理發(fā)師睡覺時顧客近來需要喚醒理發(fā)師為其理發(fā)，當有顧客時理發(fā)師為其理發(fā)，沒有的時候理發(fā)師睡覺。理發(fā)師和顧客之間互斥關(guān)系：由于每次理發(fā)師只能為一個人理發(fā)，且可供等侯的椅子有限只有n把，即理發(fā)師和椅子是臨界資源，所以顧客之間是互斥的關(guān)系。故引入3個信號量和一個控制變量：i控制變量waiting用來記錄等候理發(fā)的顧客數(shù)，初值為0;ii信號量customers用來記錄等候理發(fā)的顧客數(shù)，并用作阻塞理發(fā)師進程，初值為0；iii信號量barbers用來記錄正在等候顧客的理發(fā)師數(shù)，并用作阻塞顧客進程，初值為1；iv信號量mutex用于互斥，初值為1多線程編程原理此次在Linux下

5、進行多線程編程需要用到pthread_create和pthread_join這兩個函數(shù)。創(chuàng)建一個線程pthread_create用來創(chuàng)建一個線程，原型為：externintpthread_create(pthread_t*_thread,_constpthread_attr_t*_attr,void*(*_start_routine)(void*),void*_arg)第一個參數(shù)為指向線程標識符的指針，第二個參數(shù)用來設(shè)置線程屬性，第三個參數(shù)是線程運行函數(shù)的起始地址，最后一個參數(shù)是運行函數(shù)的參數(shù)。函數(shù)thread不需要參數(shù)時，最后一個參數(shù)設(shè)為空指針。第二個參數(shù)設(shè)為空指針時，將生成默認屬性的線程。

6、創(chuàng)建線程成功后，新創(chuàng)建的線程則運行參數(shù)三和參數(shù)四確定的函數(shù)，原來的線程則繼續(xù)運行下一行代碼。等待一個線程結(jié)束pthread_join用來等待一個線程的結(jié)束，函數(shù)原型為：externintpthread_join_P(pthread_t_th,void*_thread_return);while(true)/判斷有無顧客第一個參數(shù)為被等待的線程標識符，第二個參數(shù)為一個用戶定義的指針，它可以用來存儲被等待線程的返回值。這個函數(shù)是一個線程阻塞的函數(shù)，調(diào)用它的函數(shù)將一直等待到被等待的線程結(jié)束為止，當函數(shù)返回時，被等待線程的資源被收回。信號量函數(shù)sem_init()用來初始化一個信號量，函數(shù)原型為：ex

7、ternintsem_init_P(sem_t*_sem,int_pshared,unsignedint_value);sem為指向信號量結(jié)構(gòu)的一個指針；pshared不為0時此信號量在進程間共享，否則只能為當前進程的所有線程共享；value給出了信號量的初始值。函數(shù)sem_post(sem_t*sem)用來增加信號量的值。當有線程阻塞在這個信號量上時，調(diào)用這個函數(shù)會使其中的一個線程不在阻塞，選擇機制同樣是由線程的調(diào)度策略決定的。函數(shù)sem_wait(sem_t*sem)被用來阻塞當前線程直到信號量sem的值大于0,解除阻塞后將sem的值減一，表明公共資源經(jīng)使用后減少。函數(shù)sem_trywai

8、t(sem_t*sem)是函數(shù)sem_wait()的非阻塞版本，它直接將信號量sem的值減一。偽碼實現(xiàn)difinen5；/為顧客準備的椅子數(shù)為5semaphoremutex=l；/用于互斥semaphorecustomers=0；/等候理發(fā)的顧客數(shù)semaphorebarbers=1；/正在等候顧客的理發(fā)師數(shù)intwaiting=0；/等候理發(fā)的顧客數(shù)/理發(fā)師線程voidbarber()wait(customers);wait(mutex);waiting;signal(mutex);signal(barber);cut_hair;/顧客線程voidcustomer()wait(mutex);

9、if(waitingn)waiting+;signal(mutex);signal(customers);wait(barber);get_haircut;elsesignal(mutex);/若無顧客，理發(fā)師睡眠/互斥/等候顧客數(shù)少一個/釋放臨界資源/理發(fā)師去為一個顧客理發(fā)/正在理發(fā)/互斥/如果有空椅子，則等待/等候顧客數(shù)加1/釋放臨界資源/如果理發(fā)師睡覺，喚醒理發(fā)師/理發(fā)師在理發(fā)，顧客等候/顧客坐下等理發(fā)師/店里人滿了，顧客離開開發(fā)環(huán)境與工具系統(tǒng)平臺：LINUX環(huán)境實現(xiàn)語言：C語言開發(fā)工具：NANO編輯器3數(shù)據(jù)結(jié)構(gòu)與模塊說明數(shù)據(jù)結(jié)構(gòu)通過分析課程設(shè)計要求，定義以下的數(shù)據(jù):sem_tmutex

10、,customers,barbers;/designthreesemaphores:mutex,customer,barbersintwaiting=0;/thenumberofwaitingcustomersintchair5;程序模塊說明主函數(shù)模塊主函數(shù)流程圖如下：3.2.2理發(fā)師模塊理發(fā)師模塊函數(shù)流程圖如下：3.2.3顧客模塊顧客模塊函數(shù)流程圖如下：源程序代碼#include#include#include#include#include#include#include#definen5/theshophavefivechairs/designthreesemaphores:mutex,

11、customer,barberssem_tmutex,customers,barbers;intwaiting=0;/thenumberofwaitingcustomersintchair5;void*barber();void*customer(void*arg);intmain(intargc,char*argv)/create10semaphoresandoneBarbersemaphorepthread_tCustomer_id10,Barber_id;inti;sem_init(&mutex,0,1);/initmutexsemaphoreto1sem_init(&customers

12、,0,0);/initsemaphorecustomersto0sem_init(&barbers,0,1);for(i=0;i5;i+)pthread_create(&Barber_id,NULL,(void*)barber,NULL);for(i=0;i10;i+)pthread_create(&Customer_idi,NULL,(void*)customer,(void*)(i+1);for(i=0;i10;i+)pthread_join(Customer_idi,NULL);for(i=0;i5;i+)pthread_join(Barber_id,NULL);return0;/cre

13、atbarberpthreadvoid*barber()inti;intnext;/wait(customers),ifnocustomers,barbersleepingsem_wait(&customers);sem_wait(&mutex);/wait(mutex)waiting-;/thenumerofwaitingreduceonefor(i=0;i5;i+)if(chairi!=0)next=chairi;chairi=0;break;printf(Thebarberiscutting%dthcustomershairn,next);sleep(3);sem_post(&mutex

14、);sem_post(&barbers);/creatcustomerpthreadvoid*customer(void*arg)inti;sem_wait(&mutex);/wait(mutex)if(waitingn)if(waitingn)waiting+;/thenumerofwaitingplusonefor(i=0;i5;i+)if(chairi=0)chairi=(int)arg;break;chairprintf(*n);printf(Entered:Number%dcustomercomes,andsitsat%dn,(int)arg,(i+1);printf(Therear

15、e%dcustomeronthechairn,waiting);printf(Thecustomerslocationare:);for(i=0;i5;i+)printf(%d,chairi);printf(n);sleep(1);sem_post(&mutex);/signal(mutex)sem_post(&customers);/signal(customers)sem_wait(&barbers);/wait(barbers)elseprintf(Number%dcomes,therearenochairs,thecustomer%disleavingn,(int)arg,(int)a

16、rg);sem_post(&mutex);編輯，編譯和運行的過程圖J,rrj070234jsjserver:匚叵區(qū)rj070234jajserver$nanoSleepingBartoer.crjsjserver$cc-Lpthread-oSleepingBarberSleepingBarber.crj070234jsjserver$./SleepingBarberB5.2.2錯誤部分截圖rjO7O2340jsjserver回區(qū)ri0702340jsiserver-Scc-lpthread-S1eepingBarberS1eepingBarbe匸i二巧丄eep1ngBartieru:InSle

17、epinaEarb已匸i二SleepingBarb已匸u3丄匸匕匸zLngTi旦匸巴匸cnee2丄已已pingBarlj已匸i二SleepingBarber.cSleepingBarb已匸亡沽丄eepingBartie匸.cSleepingBarber.cSleepingBarb已匸i二口n)2丄已已pingBarlj已匸i二SleepingBarb已匸uleepingEarber-u:86:：37:07:unc11ncust.oiner1:rni33inaterrninatinarrcharacterand1undeclared(firstuseinthisfunction)i：E旦匚hun

18、dec1-.redidentifieris匸巴p匚i匸匚匸d口riJ.yerror:亡匸匸匸:匕匸匸口匸；error:102:已匸匸匸:inissinceteriuinatingcharacter:103:error:there1undeclared(first,usein:103:已匸匸匸:syntax已rrurh已fr已曰匸已:103:error:stray11inprugrizttTi:10-：:ertor:i：=jRingterminatingrpcharactEE1err口匸:error:error:thisfuncti87:S7:87:H7：for已achfunctionitapp

19、已;蟲匸日in.)syntax已匸匸口isbef口匸已prsitsprstray11inprograiurnlas1ngterrn1na11ng尸ciiaracterrj0702340jsiserver-5.2.3正確運行結(jié)果圖第一次運行結(jié)果如下圖：sjserver=13回因rjn7n:?4Pi：=：iservpr-Sr-ri-lpr.hread-n?：leepinaBarber?：leeriinaBarberrr-itjU7U2340i3i3ever：；./S1eepingE：=iudeu+-+*+*+*+*+*+古古古古古代孟古Entered;Nuxribeu丄customer匚口m匸ci

20、nd.sit：旦匸1chetinThereare1cusuunieruntheuhalrThecustuniers1lucatlcmare:1UUUU古古古古iv古古古古古；古古古古古古古古古古古古古古古古古古古古古卞卞卞卞卞卞卞卞卞卞卞古古古古古詵古古Entered:Nuiriljer2ci.istijnie匸uurne曰,randsitsat2chai匸Thereare2custuniercmthechairTher-i：=：r.i-iTner：=：1lnnationare:12nin古古古古iv古古古古古；古古古古古古古古古古古古古古古古古古古古古卞卞卞卞卞卞卞卞卞卞卞古古古古古詵古古E

21、ntcitccl:Nuruibcr3cii口toincr匚!oinemandsits耳七3chairTheir匚are二；c：us匕口meitcmthec：lis.irThecustomers1luca匸：Lonare:1z30uEnterecl:Wurnber4custoinercnniesfandsitsat4chairThereare4custurnercmthechairThecustoniers11neationare:1234U古古古古古古古古古古古古古古古古古古古古古古古古古古古古古古古古古古古古古書古古古古古古古古古古詵古古Thereare5custnRiercmthechai

22、rThe匸uz：toiuc：its11ocationare:12345I-lLimbe匚6comcc；,rtheri=豆匸匕nohciiL匸LliccustorncuGis1csving-Ni.unijAr/coni已s匸.h已匸已曰匸已nochairs,rEiieCl.is匸已匸/is1已avmgNwritier廿conies.rttierearenochairs,rtiieci.istonierH131eavmgNi.m-fciAEyconi已s匸.h已匸已曰匸已nochairs.rtheci.istoni已匸9is1已ErrinETEnt-pred:Numberm：=：r.rimerri

23、rme.randmFr.mat.Enhair10isleavingNi.urfcier10icunies.rthereareTh已hatrb已匸iscuttinglt.hThebarberi：=：riur.r.ina:r.hThekiarberi：=jcfiitting-：thThoJarbeuiscLi11ing4thThebarbeisis匚:i.i11ingSthrJOTOZ340曰二曰已匸y已匸-$nochairs,thecustutne匸cust.已r1shairr-!i：=：r.i-irner1：=：haireu2tortier1：=!hairuu口匸口mcu1slio.ir匚:u

24、z：匸口tncir1sHs.ir第二次運行結(jié)果如下圖：口回區(qū)I丈rjO70234jsjserver:ThetoarkieriscuttingSthcustomer1shairrj070234jajserver./SleepingBartoer古古古古古古古古古古古古古古古古古古古古古古古古古古古古古古古古古古苦古古古古古詵古古古古古專古古古古Enterecl:Muitibericustijinercoifiesanclsitsat1chairTh已匸已曰匸已1customeroilth已chairThecust.uniers1locatioiiare:10UOU古古古古古卞卞卞卞卞卞古古古古古

25、古才古古才古擊古古古古古書古古才古古書古古古古古詵古才古古才專古古古古Enterecl:Muitiber2custijinercoifiesanclsitsat2chairThereare2custoniEEoilthechairThecust-urners1locatioiiare:12U0U古古古古古卞卞卞卞卞卞古古古古古古才古古才古擊古古古古古書古古才古古書古古古古古詵古才古古才專古古古古Ent已匸亡匚1:Ni-UciJj已r8custornercLuriesandsitsat3chairTlieueare3customei;uiithechairThecust-urners1locat

26、ioiiare:1280U古古古古古古古古古古古古古古古古古古古古古古ft古古古古古書古古古古古古古古古古古n古古古古古古古古古古Enr.Eired:Ni_UijEr3custoiriErcoiries.randsitsat4chsti匸Thereare4custorneroilthechairThecustuniers1locatioiiare:12Q3U古古古古古古古古古古古古古古古古古卞卞古卞卞古卞古卞卞古古卞古卞卞古卞古卞卞古卞卞古卞卞古卞卞卞卞古卞Entered:Ni-uriljer7ci.istoiriErclueies$andsitsat5chai匸Thereare5custor

27、neroilthechairNi.m-fci已工4coin已S_rIZ.tL已匸已曰匸已nochairsrthecust.ijin已工4isleavingNi.uriljer6cijines.rt.lierearenochairs,rthecust.ijiner6isleavingNi.nrfcierScrune3.rtherearenochairs.rthecustorner5isleavinijrNi.m-fcier9cijines.rt.lierearenochairsrthecustnineryisleavingThecusturners1locatiLiiiare:12837isle

28、avingThebarljAriscuttingLthThebarberiscutting2thTheijarlzieriscuttingSthThebarberiscutting3thThebarberiscutting7thrj070234jsjserver-$1Ni.uriljer10cutne3,rtherear&nochairs,thecust.urne匸1Ucustomer1shaircusturner1shaircust.umer1shairi二ustuniEr1shair:cust.urner1shair:13回區(qū)第三次運行結(jié)果如下圖；FrjOTO2340jsjserverjr

29、i0702340jsi-$cc-Lpthread-oS1eepingBarberSleEpingBarbe匸i二rj070234I!jsiserxer-$/S1eepingBarb&r古古古古古卞卞卞卞卞卞古古古古古古才古古才古擊古古古古古書古古才古古書古古古古古詵古才古古才專古古古古Ent已匸亡匚1:Ni-UciJj已r1custornercLuriesandsitsat1chairThereare1custuinei：utithe亡hairThecust-urners1locatioiiare:10U0U古古古古古古古古古古古古古古古古古古古古古古ft古古古古古書古古古古古古古古古古古n古

30、古古古古古古古古古Enr.Eired：rJi_ULljErZcus匸匚iinercoiriesirandsits旦匸Z匚hairThereare2custorneroilthechairThecustuniers1locatioiiare:12U0U古古古古古古古古古古古古古古古古古吉卞古吉卞古卞古卞卞古古卞古吉卞古卞古卞卞古卞卞古吉卞古吉卞卞卞古卞Entered:Ni-urilj已匸3ci.istoiriErclueies$andsitsat3chai匸Thereare3custorneroilthechairTOC o 1-5 h zThecust.nniprs1locaticiiare:

31、1230U古古古古古古古古古古古古古古古古古吉卞古吉卞古卞古卞卞古古卞古吉卞古卞古卞卞古卞卞古吉卞古吉卞卞卞古卞Entered:Ni-uriljer4cu曰toiriercoiries,randsitsat4chai匸Thereare4custorneroilthechairThecust.nniprs1locaticiiare:1234U古古古古古古古古古古古古古古古古古吉卞古吉卞古卞古卞卞古古卞古吉卞古卞古卞卞古卞卞古吉卞古吉卞卞卞古卞Entered:Ni-urQjer5ci.istuine匸coirie曰andsitsat5chai匸Therearecustoniprciithechai

32、rThecust.uniErs1locatioiiare:12345Ni.urfcier8cijiie5,rt.lierearenochairs,rthecustijiner8isleavingThetoartieriscuttinglthcustunier1shair古古古古古古古古古古古古古古古古古吉卞古吉卞古卞古卞卞古古卞古吉卞古卞古卞卞古卞卞古吉卞古吉卞卞卞古卞Entered:Ni-uriljer7cu曰toiriercoiries,randsitsat1chai匸Thereare5custonierrmthechairThecust.nniprs1locaticiiare:72345Ni.uriljEr10cunies.rtherearenochairs,thecusturner10isleavin