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

2、nux系統(tǒng)提供的IPC進(jìn)程通信機(jī)制實(shí)驗并實(shí)現(xiàn)理發(fā)店問題的一個解法。實(shí)驗?zāi)康模?進(jìn)一步研究和實(shí)踐操作系統(tǒng)中關(guān)于并發(fā)進(jìn)程同步與互斥操作的一些經(jīng)典問題的解法，加深對于非對稱性互斥問題有關(guān)概念的理解。觀察和體驗非對稱性互斥問題的并發(fā)控制方法。進(jìn)一步了解Linux系統(tǒng)中IPC進(jìn)程同步工具的用法，訓(xùn)練解決對該類問題的實(shí)際編程、調(diào)試和分析問題的能力。硬件環(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í)驗步驟： 1、問題分析: 為了解決本實(shí)驗的同步問題，采用共享內(nèi)存，信號量，消 息隊列三種IPC 同步對象處理。 客戶程序思想： 每一個客戶把自己的請求當(dāng)做一條消息發(fā)送到相應(yīng)的消息 隊列中去，并通過阻塞等待接收消息的方式來等待理發(fā)師 最終幫自己理發(fā)。每一個客戶先判斷sofa 是不是坐滿了，如 果沒有就坐在沙發(fā)上等，否者就判斷waitroom 是不是坐滿 了，如果沒有，就坐在waitroom 等，只要有一個坐在sofa 的客戶離開sofa 理發(fā)，理發(fā)師就會到waitroom 找最先來的 客戶，讓他進(jìn)入sofa

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

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

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

7、。3、 開發(fā)調(diào)試過程：在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號理發(fā)師睡眠2728號理發(fā)師睡眠2727號理發(fā)師睡眠運(yùn)行$./customer1號新顧客坐入沙發(fā)2號新顧客坐入沙發(fā)3號新顧客坐入沙發(fā)4號新顧客坐入沙發(fā)5號新顧客坐入沙發(fā)6號新顧客坐入沙發(fā)7號新顧客坐入沙發(fā)8號新顧客坐入沙發(fā)9號新顧客坐入沙

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

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

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

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

12、號量的使用，明白了消息隊列的使用方法，進(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;/測試由 sem_key 標(biāo)識的信號燈數(shù)組是否已經(jīng)建立if(sem_id = get_ipc_id(/proc/sysvipc/sem,sem_key) 0 )/semget 新建一個信號燈,其標(biāo)號返回到 sem_idif(sem_id = semget(sem_key,1,sem_flg) 0)perror(semaphore create error);exit(EXIT_FAILURE);/設(shè)置信號燈的初值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;/測試由 shm_key 標(biāo)識的共享內(nèi)存區(qū)是否已經(jīng)建立if(shm_id = get_ipc_id(/proc/sysvipc/shm,shm_key) 0 )/shmget 新建 一個長度為 shm_num 字節(jié)的共享內(nèi)存,其標(biā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)識的共享內(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)識的共享內(nèi)存區(qū)已經(jīng)建立,將由 shm_id 標(biāo)識的

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;/測試由 msq_key 標(biāo)識的消息隊列是否已經(jīng)建立if(msq_id = get_ipc_id(/proc/sysvipc/msg,msq_key) 0 )/msgget 新建一個消息隊列,其標(biā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 /寫請求標(biāo)識 /讀請求標(biāo)識/讀寫完成標(biāo)識 typedef

20、 union semuns int val; Sem_uns; typedef struct msgbuf long mtype;int mid; Msg_buf; /信號量key_t costomer_key;int costomer_sem;key_t account_key;int account_sem; int sem_val;int sem_flg; /消息隊列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ù)指定一個進(jìn)程睡眠秒數(shù),以調(diào)解進(jìn)程執(zhí)行速度 if(argv1 != NULL) rate = atoi(argv1); else rate = 3; /聯(lián)系一個請求消息隊列 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)系一個響應(yīng)消息隊列 wait_respond_flg = IPC_CREAT| 0644; wait_respond_key = 102; wait_respond_id = set_msq(wait_respond_key,wait_respond_flg); /聯(lián)系一個請求消息隊列 sofa_quest_flg = IPC_CREAT| 0644; sofa_quest_key = 201; sofa_quest_id = set_msq(sofa_quest_key

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

25、r_sem costomer_sem = set_sem(costomer_key,sem_val,sem_flg); /賬簿互斥信號燈初值設(shè)為 1 sem_val = 1; /獲取消費(fèi)者同步信號燈,引用標(biāo)識存 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號理發(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號理發(fā)師為%d號顧客理發(fā)n, getpid(), msg_arg.mid); sleep(rate); down(account_sem); printf(%d號理發(fā)師收取%d號顧客交費(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號理發(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號理發(fā)師為%d號顧客理發(fā)n, getpid(), msg_arg.mid); sleep(rate); down(account_sem); printf(%d號理發(fā)師收

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