山東大學(xué)操作系統(tǒng)實(shí)驗(yàn)五理發(fā)師問(wèn)題報(bào)告

1、精選優(yōu)質(zhì)文檔-傾情為你奉上計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院操作系統(tǒng)實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)題目：理發(fā)店問(wèn)題 理發(fā)店問(wèn)題：假設(shè)理發(fā)店的理發(fā)室中有3個(gè)理發(fā)椅子和3個(gè)理發(fā)師，有一個(gè)可容納4個(gè)顧客坐等理發(fā)的沙發(fā)。此外還有一間等候室，可容納13位顧客等候進(jìn)入理發(fā)室。顧客如果發(fā)現(xiàn)理發(fā)店中顧客已滿（超過(guò)20人），就不進(jìn)入理發(fā)店。在理發(fā)店內(nèi)，理發(fā)師一旦有空就為坐在沙發(fā)上等待時(shí)間最長(zhǎng)的顧客理發(fā)，同時(shí)空出的沙發(fā)讓在等候室中等待時(shí)間最長(zhǎng)的的顧客就坐。顧客理完發(fā)后，可向任何一位理發(fā)師付款。但理發(fā)店只有一本現(xiàn)金登記冊(cè)，在任一時(shí)刻只能記錄一個(gè)顧客的付款。理發(fā)師在沒(méi)有顧客的時(shí)候就坐在理發(fā)椅子上睡眠。理發(fā)師的時(shí)間就用在理發(fā)、收款、睡眠上。請(qǐng)利用li

2、nux系統(tǒng)提供的IPC進(jìn)程通信機(jī)制實(shí)驗(yàn)并實(shí)現(xiàn)理發(fā)店問(wèn)題的一個(gè)解法。實(shí)驗(yàn)?zāi)康模?進(jìn)一步研究和實(shí)踐操作系統(tǒng)中關(guān)于并發(fā)進(jìn)程同步與互斥操作的一些經(jīng)典問(wèn)題的解法，加深對(duì)于非對(duì)稱性互斥問(wèn)題有關(guān)概念的理解。觀察和體驗(yàn)非對(duì)稱性互斥問(wèn)題的并發(fā)控制方法。進(jìn)一步了解Linux系統(tǒng)中IPC進(jìn)程同步工具的用法，訓(xùn)練解決對(duì)該類問(wèn)題的實(shí)際編程、調(diào)試和分析問(wèn)題的能力。硬件環(huán)境： Inter(R)Core(TM)i5-3210M CPU 2.50GHz 內(nèi)存：4GB 硬盤：500G軟件環(huán)境： XUbuntuLinux 操作系統(tǒng) Gnome 桌面 2.18.3 BASH_VERSION=3.2.33(1)-release gcc

3、 version 4.1.2 gedit 2.18.2 OpenOffice 2.3 實(shí)驗(yàn)步驟： 1、問(wèn)題分析: 為了解決本實(shí)驗(yàn)的同步問(wèn)題，采用共享內(nèi)存，信號(hào)量，消 息隊(duì)列三種IPC 同步對(duì)象處理。 客戶程序思想： 每一個(gè)客戶把自己的請(qǐng)求當(dāng)做一條消息發(fā)送到相應(yīng)的消息 隊(duì)列中去，并通過(guò)阻塞等待接收消息的方式來(lái)等待理發(fā)師 最終幫自己理發(fā)。每一個(gè)客戶先判斷sofa 是不是坐滿了，如 果沒(méi)有就坐在沙發(fā)上等，否者就判斷waitroom 是不是坐滿 了，如果沒(méi)有，就坐在waitroom 等，只要有一個(gè)坐在sofa 的客戶離開sofa 理發(fā)，理發(fā)師就會(huì)到waitroom 找最先來(lái)的 客戶，讓他進(jìn)入sofa

4、等待。 理發(fā)師程序思想： 理發(fā)師查看sofa 上有沒(méi)有人，沒(méi)有就睡3 秒，然后再一次 看有沒(méi)有人，如果有人，就到沙發(fā)請(qǐng)最先來(lái)的客戶來(lái)理發(fā)。 賬本互斥的實(shí)現(xiàn)： Semaphore mutex=1 ； Sofa 隊(duì)列的長(zhǎng)度和wait 隊(duì)列的長(zhǎng)度的實(shí)現(xiàn)： 在顧客進(jìn)程中設(shè)置兩個(gè)變量sofa_count,wait_count，分別保存沙發(fā)和等候室的顧客數(shù)。2、算法設(shè)計(jì)說(shuō)明如下：該解法利用消息隊(duì)列的每條消息代表每個(gè)顧客，將進(jìn)入等候室的顧客組織到一個(gè)隊(duì)列，將坐入沙發(fā)的顧客組織到另一個(gè)隊(duì)列。理發(fā)師從沙發(fā)隊(duì)列請(qǐng)出顧客，空出的沙發(fā)位置再?gòu)牡群蚴艺?qǐng)入顧客進(jìn)入沙發(fā)隊(duì)列。三個(gè)理發(fā)師進(jìn)程使用相同的程序段上下文，所有顧客使

5、用同一個(gè)程序段上下文。這樣可避免產(chǎn)生太多進(jìn)程，以便節(jié)省系統(tǒng)資源。理發(fā)師程序（Barber）建立一個(gè)互斥帳本信號(hào)量：s_account,初值=1;建立一個(gè)同步顧客信號(hào)量：s_customer,初值=0;建立沙發(fā)消息隊(duì)列：q_sofa;建立等候室消息隊(duì)列：q_wait;建立3個(gè)理發(fā)師進(jìn)程：b1_pid, b2_pid, b3_pid;每個(gè)理發(fā)師進(jìn)程作：while(1)以阻塞方式從沙發(fā)隊(duì)列接收一條消息，如果有消息，則消息出沙發(fā)隊(duì)列(模擬一顧客理發(fā))；喚醒顧客進(jìn)程(讓下一顧客坐入沙發(fā)）。用進(jìn)程休眠一個(gè)隨機(jī)時(shí)間模擬理發(fā)過(guò)程。理完發(fā),使用帳本信號(hào)量記賬?；コ獾墨@取賬本記賬喚醒用賬本理發(fā)師者否則沒(méi)有消息(沙

6、發(fā)上無(wú)顧客)則理發(fā)師進(jìn)程在沙發(fā)隊(duì)列上睡眠；當(dāng)沙發(fā)隊(duì)列有消息時(shí)被喚醒(有顧客坐入沙發(fā))。顧客程序(customer)while(1)取沙發(fā)隊(duì)列消息數(shù)(查沙發(fā)上顧客數(shù)) ；如果消息數(shù)小于4(沙發(fā)沒(méi)座滿）以非阻塞方式從等候室隊(duì)列接收一條消息(查等候室有顧客否)，如果有消息將接收到的消息發(fā)送到沙發(fā)隊(duì)列(等候室顧客坐入沙發(fā))；否則發(fā)送一條消息到沙發(fā)隊(duì)列(新來(lái)的顧客直接坐入沙發(fā))；否則(沙發(fā)坐滿)取等候室隊(duì)列消息數(shù)(查等候室顧客數(shù)) ；如果消息數(shù)小于13發(fā)送一條消息到等候室隊(duì)列(等候室沒(méi)滿,新顧客進(jìn)等候室)；否則在顧客同步信號(hào)量上睡眠(等候室滿暫不接待新顧客)；用進(jìn)程休眠一個(gè)隨機(jī)時(shí)間模擬顧客到達(dá)的時(shí)間間隔

7、。3、 開發(fā)調(diào)試過(guò)程：在shell命令行下運(yùn)行$ make barber customergcc -g -c barber.c ipc.cgcc barber.o ipc.o -o barbergcc -g -c customer.c ipc.cgcc customer.o ipc.o -o customer假設(shè)先運(yùn)行理發(fā)師程序：$ ./barber 2726號(hào)理發(fā)師睡眠2728號(hào)理發(fā)師睡眠2727號(hào)理發(fā)師睡眠運(yùn)行$./customer1號(hào)新顧客坐入沙發(fā)2號(hào)新顧客坐入沙發(fā)3號(hào)新顧客坐入沙發(fā)4號(hào)新顧客坐入沙發(fā)5號(hào)新顧客坐入沙發(fā)6號(hào)新顧客坐入沙發(fā)7號(hào)新顧客坐入沙發(fā)8號(hào)新顧客坐入沙發(fā)9號(hào)新顧客坐入沙

8、發(fā)10號(hào)新顧客坐入沙發(fā)11號(hào)新顧客坐入沙發(fā)12號(hào)新顧客坐入沙發(fā)沙發(fā)坐滿13號(hào)顧客在等候室等候13號(hào)顧客從等候室坐入沙發(fā)沙發(fā)坐滿14號(hào)顧客在等候室等候14號(hào)顧客從等候室坐入沙發(fā)沙發(fā)坐滿15號(hào)顧客在等候室等候15號(hào)顧客從等候室坐入沙發(fā)沙發(fā)坐滿16號(hào)顧客在等候室等候16號(hào)顧客從等候室坐入沙發(fā)17號(hào)新顧客坐入沙發(fā)沙發(fā)坐滿18號(hào)顧客在等候室等候18號(hào)顧客從等候室坐入沙發(fā)沙發(fā)坐滿19號(hào)顧客在等候室等候19號(hào)顧客從等候室坐入沙發(fā)沙發(fā)坐滿20號(hào)顧客在等候室等候20號(hào)顧客從等候室坐入沙發(fā)沙發(fā)坐滿21號(hào)顧客在等候室等候21號(hào)顧客從等候室坐入沙發(fā).在理發(fā)師窗體理發(fā)師進(jìn)程被喚醒：2726號(hào)理發(fā)師為1號(hào)顧客理發(fā)2726

9、號(hào)理發(fā)師收取1號(hào)顧客交費(fèi)2726號(hào)理發(fā)師睡眠2728號(hào)理發(fā)師為2號(hào)顧客理發(fā)2728號(hào)理發(fā)師收取2號(hào)顧客交費(fèi)2728號(hào)理發(fā)師睡眠2727號(hào)理發(fā)師為3號(hào)顧客理發(fā)2726號(hào)理發(fā)師為4號(hào)顧客理發(fā)2727號(hào)理發(fā)師收取3號(hào)顧客交費(fèi)2727號(hào)理發(fā)師睡眠2726號(hào)理發(fā)師收取4號(hào)顧客交費(fèi)2726號(hào)理發(fā)師睡眠2728號(hào)理發(fā)師為5號(hào)顧客理發(fā)2728號(hào)理發(fā)師收取5號(hào)顧客交費(fèi)2728號(hào)理發(fā)師睡眠2727號(hào)理發(fā)師為6號(hào)顧客理發(fā)2726號(hào)理發(fā)師為7號(hào)顧客理發(fā)2727號(hào)理發(fā)師收取6號(hào)顧客交費(fèi)2727號(hào)理發(fā)師睡眠2726號(hào)理發(fā)師收取7號(hào)顧客交費(fèi)2726號(hào)理發(fā)師睡眠2728號(hào)理發(fā)師為8號(hào)顧客理發(fā)2728號(hào)理發(fā)師收取8號(hào)顧客交費(fèi).

10、反之，如果先運(yùn)行顧客程序：$ ./customer1號(hào)新顧客坐入沙發(fā)2號(hào)新顧客坐入沙發(fā)3號(hào)新顧客坐入沙發(fā)4號(hào)新顧客坐入沙發(fā)沙發(fā)坐滿5號(hào)顧客在等候室等候沙發(fā)坐滿6號(hào)顧客在等候室等候沙發(fā)坐滿7號(hào)顧客在等候室等候沙發(fā)坐滿8號(hào)顧客在等候室等候沙發(fā)坐滿9號(hào)顧客在等候室等候沙發(fā)坐滿10號(hào)顧客在等候室等候沙發(fā)坐滿11號(hào)顧客在等候室等候沙發(fā)坐滿12號(hào)顧客在等候室等候沙發(fā)坐滿13號(hào)顧客在等候室等候沙發(fā)坐滿14號(hào)顧客在等候室等候沙發(fā)坐滿15號(hào)顧客在等候室等候沙發(fā)坐滿16號(hào)顧客在等候室等候沙發(fā)坐滿17號(hào)顧客在等候室等候等候室滿18號(hào)顧客沒(méi)有進(jìn)入理發(fā)店當(dāng)18號(hào)顧客到達(dá)時(shí)理發(fā)店20個(gè)位置已滿，顧客進(jìn)程阻塞(假設(shè)理發(fā)師進(jìn)

11、程沒(méi)運(yùn)行表示三個(gè)理發(fā)師正坐在3個(gè)理發(fā)椅上睡覺(jué)) 。再運(yùn)行理發(fā)師程序：$ ./barber 運(yùn)行截圖如下：附件：4.7.分析與感悟：首先運(yùn)行顧客程序的話，顧客程序首先向沙發(fā)隊(duì)列發(fā)送消息，然后向等候室隊(duì)列發(fā)送消息，當(dāng)兩個(gè)隊(duì)列都滿了之后，該進(jìn)程會(huì)暫停，及停止在顧客同步信號(hào)量上。而隨著理發(fā)師程序的開始運(yùn)行，理發(fā)師進(jìn)程會(huì)喚醒顧客進(jìn)程，及在顧客同步信號(hào)量上進(jìn)行up操作，并且從消息隊(duì)列中接受消息。反之，若理發(fā)師程序先運(yùn)行，則三個(gè)理發(fā)師由于無(wú)法從沙發(fā)隊(duì)列上接收到消息，而且由于是阻塞式接受，就會(huì)阻塞在這個(gè)消息隊(duì)列上，只有當(dāng)顧客程序運(yùn)行時(shí)，向沙發(fā)隊(duì)列發(fā)送消息后理發(fā)師進(jìn)程才會(huì)繼續(xù)。通過(guò)編寫這個(gè)實(shí)驗(yàn)，是我更加熟練了信

12、號(hào)量的使用，明白了消息隊(duì)列的使用方法，進(jìn)一步了解了Linux系統(tǒng)中IPC進(jìn)程同步工具的用法。附件：Ipc.c#include ipc.h int get_ipc_id(char *proc_file,key_t key)FILE *pf;int i,j;char lineBUFSZ,columBUFSZ;if(pf = fopen(proc_file,r) = NULL)perror(Proc file not open);exit(EXIT_FAILURE);fgets(line, BUFSZ, pf);while(!feof(pf)i = j = 0;fgets(line, BUFSZ,p

13、f);while(linei = ) i+;while(linei != ) columj+ = linei+;columj = 0;if(atoi(colum) != key) continue;j=0;while(linei = ) i+;while(linei != ) columj+ = linei+;columj = 0;i = atoi(colum);fclose(pf);return i;fclose(pf);return -1; int down(int sem_id)struct sembuf buf;buf.sem_op = -1;buf.sem_num = 0;buf.s

14、em_flg = SEM_UNDO;if(semop(sem_id,&buf,1) 0) perror(down error );exit(EXIT_FAILURE);return EXIT_SUCCESS;int up(int sem_id)struct sembuf buf;buf.sem_op = 1;buf.sem_num = 0;buf.sem_flg = SEM_UNDO;if(semop(sem_id,&buf,1) 0) perror(up error );exit(EXIT_FAILURE);return EXIT_SUCCESS; int set_sem(key_t sem

15、_key,int sem_val,int sem_flg)int sem_id;Sem_uns sem_arg;/測(cè)試由 sem_key 標(biāo)識(shí)的信號(hào)燈數(shù)組是否已經(jīng)建立if(sem_id = get_ipc_id(/proc/sysvipc/sem,sem_key) 0 )/semget 新建一個(gè)信號(hào)燈,其標(biāo)號(hào)返回到 sem_idif(sem_id = semget(sem_key,1,sem_flg) 0)perror(semaphore create error);exit(EXIT_FAILURE);/設(shè)置信號(hào)燈的初值sem_arg.val = sem_val;if(semctl(sem_

16、id,0,SETVAL,sem_arg) 0)perror(semaphore set error);exit(EXIT_FAILURE);return sem_id; char * set_shm(key_t shm_key,int shm_num,int shm_flg)int i,shm_id;char * shm_buf;/測(cè)試由 shm_key 標(biāo)識(shí)的共享內(nèi)存區(qū)是否已經(jīng)建立if(shm_id = get_ipc_id(/proc/sysvipc/shm,shm_key) 0 )/shmget 新建 一個(gè)長(zhǎng)度為 shm_num 字節(jié)的共享內(nèi)存,其標(biāo)號(hào)返回到 shm_idif(shm_i

17、d = shmget(shm_key,shm_num,shm_flg) 0)perror(shareMemory set error);exit(EXIT_FAILURE);/shmat 將由 shm_id 標(biāo)識(shí)的共享內(nèi)存附加給指針 shm_bufif(shm_buf = (char *)shmat(shm_id,0,0) (char *)0)perror(get shareMemory error);exit(EXIT_FAILURE);for(i=0; ishm_num; i+) shm_bufi = 0; /初始為 0/shm_key 標(biāo)識(shí)的共享內(nèi)存區(qū)已經(jīng)建立,將由 shm_id 標(biāo)識(shí)的

18、共享內(nèi)存附加給指針 shm_bufif(shm_buf = (char *)shmat(shm_id,0,0) (char *)0)perror(get shareMemory error);exit(EXIT_FAILURE);return shm_buf; int set_msq(key_t msq_key,int msq_flg)int msq_id;/測(cè)試由 msq_key 標(biāo)識(shí)的消息隊(duì)列是否已經(jīng)建立if(msq_id = get_ipc_id(/proc/sysvipc/msg,msq_key) 0 )/msgget 新建一個(gè)消息隊(duì)列,其標(biāo)號(hào)返回到 msq_idif(msq_id =

19、 msgget(msq_key,msq_flg) 0)perror(messageQueue set error);exit(EXIT_FAILURE);return msq_id;Ipc.h：#include #include #include #include #include #include #include #define BUFSZ 256#define MAXVAL 100#define STRSIZ 8#define WRITERQUEST 1#define READERQUEST 2#define FINISHED 3 /寫請(qǐng)求標(biāo)識(shí) /讀請(qǐng)求標(biāo)識(shí)/讀寫完成標(biāo)識(shí) typedef

20、 union semuns int val; Sem_uns; typedef struct msgbuf long mtype;int mid; Msg_buf; /信號(hào)量key_t costomer_key;int costomer_sem;key_t account_key;int account_sem; int sem_val;int sem_flg; /消息隊(duì)列int wait_quest_flg;key_t wait_quest_key;int wait_quest_id;int wait_respond_flg;key_t wait_respond_key;int wait_r

21、espond_id; int sofa_quest_flg;key_t sofa_quest_key;int sofa_quest_id;int sofa_respond_flg;key_t sofa_respond_key;int sofa_respond_id; int get_ipc_id(char *proc_file,key_t key);char *set_shm(key_t shm_key,int shm_num,int shm_flag);int set_msq(key_t msq_key,int msq_flag);int set_sem(key_t sem_key,int

22、sem_val,int sem_flag);int down(int sem_id);int up(int sem_id);Barber.c：#include ipc.hint main(int argc,char *argv) / int i; int rate; Msg_buf msg_arg; /可在在命令行第一參數(shù)指定一個(gè)進(jìn)程睡眠秒數(shù),以調(diào)解進(jìn)程執(zhí)行速度 if(argv1 != NULL) rate = atoi(argv1); else rate = 3; /聯(lián)系一個(gè)請(qǐng)求消息隊(duì)列 wait_quest_flg = IPC_CREAT| 0644; wait_quest_key = 1

23、01; wait_quest_id = set_msq(wait_quest_key,wait_quest_flg); /聯(lián)系一個(gè)響應(yīng)消息隊(duì)列 wait_respond_flg = IPC_CREAT| 0644; wait_respond_key = 102; wait_respond_id = set_msq(wait_respond_key,wait_respond_flg); /聯(lián)系一個(gè)請(qǐng)求消息隊(duì)列 sofa_quest_flg = IPC_CREAT| 0644; sofa_quest_key = 201; sofa_quest_id = set_msq(sofa_quest_key

24、,sofa_quest_flg); /聯(lián)系一個(gè)響應(yīng)消息隊(duì)列 sofa_respond_flg = IPC_CREAT| 0644; sofa_respond_key = 202; sofa_respond_id = set_msq(sofa_respond_key,sofa_respond_flg); /信號(hào)量使用的變量 costomer_key = 301;/顧客同步信號(hào)燈鍵值 account_key = 302;/賬簿互斥信號(hào)燈鍵值 sem_flg = IPC_CREAT | 0644; /顧客同步信號(hào)燈初值設(shè)為0 sem_val = 0; /獲取顧客同步信號(hào)燈,引用標(biāo)識(shí)存 costome

25、r_sem costomer_sem = set_sem(costomer_key,sem_val,sem_flg); /賬簿互斥信號(hào)燈初值設(shè)為 1 sem_val = 1; /獲取消費(fèi)者同步信號(hào)燈,引用標(biāo)識(shí)存 cons_sem account_sem = set_sem(account_key,sem_val,sem_flg); int pid1, pid2; pid1=fork(); if(pid1=0) while(1) / wait_quest_flg=IPC_NOWAIT; printf(%d號(hào)理發(fā)師睡眠n, getpid(); wait_quest_flg=0; if(msgrcv

26、(sofa_quest_id, &msg_arg, sizeof(msg_arg), 0, wait_quest_flg)=0) msgsnd(sofa_respond_id, &msg_arg,sizeof(msg_arg), 0); printf(%d號(hào)理發(fā)師為%d號(hào)顧客理發(fā)n, getpid(), msg_arg.mid); sleep(rate); down(account_sem); printf(%d號(hào)理發(fā)師收取%d號(hào)顧客交費(fèi)n, getpid(), msg_arg.mid); up(account_sem); else pid2=fork(); if(pid2=0) while(

27、1) / wait_quest_flg=IPC_NOWAIT; printf(%d號(hào)理發(fā)師睡眠n, getpid(); wait_quest_flg=0; if(msgrcv(sofa_quest_id, &msg_arg, sizeof(msg_arg), 0, wait_quest_flg)=0) msgsnd(sofa_respond_id, &msg_arg,sizeof(msg_arg), 0); printf(%d號(hào)理發(fā)師為%d號(hào)顧客理發(fā)n, getpid(), msg_arg.mid); sleep(rate); down(account_sem); printf(%d號(hào)理發(fā)師收

28、取%d號(hào)顧客交費(fèi)n, getpid(), msg_arg.mid); up(account_sem); else printf(%d號(hào)理發(fā)師睡眠n, getpid(); else while(1) / wait_quest_flg=IPC_NOWAIT; printf(%d號(hào)理發(fā)師睡眠n, getpid(); wait_quest_flg=0; if(msgrcv(sofa_quest_id, &msg_arg, sizeof(msg_arg), 0, wait_quest_flg)=0) msgsnd(sofa_respond_id, &msg_arg,sizeof(msg_arg), 0)

29、; printf(%d號(hào)理發(fā)師為%d號(hào)顧客理發(fā)n, getpid(), msg_arg.mid); sleep(rate); down(account_sem); printf(%d號(hào)理發(fā)師收取%d號(hào)顧客交費(fèi)n, getpid(), msg_arg.mid); up(account_sem); else printf(%d號(hào)理發(fā)師睡眠n, getpid(); return 0;Customer.c：#include ipc.hint main(int argc,char *argv) int rate; Msg_buf msg_arg; /可在在命令行第一參數(shù)指定一個(gè)進(jìn)程睡眠秒數(shù),以調(diào)解進(jìn)程執(zhí)行速度 if(argv1 != NULL) rate = atoi(argv1); else rate = 3; /聯(lián)系一個(gè)請(qǐng)求消息隊(duì)列 wait_quest_flg = IPC_CREAT| 0644; wait_quest_key = 101; wait_quest_id = set_msq(wait_quest_key,wait_quest_flg); /聯(lián)系一個(gè)響應(yīng)消息隊(duì)列 wait_respond_flg = IPC_CREAT| 0644; wait_respond_key = 102; wait_respond_id = set_msq(wait_r