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

2、nux系統提供的IPC進程通信機制實驗并實現理發店問題的一個解法。實驗目的： 進一步研究和實踐操作系統中關于并發進程同步與互斥操作的一些經典問題的解法，加深對于非對稱性互斥問題有關概念的理解。觀察和體驗非對稱性互斥問題的并發控制方法。進一步了解Linux系統中IPC進程同步工具的用法，訓練解決對該類問題的實際編程、調試和分析問題的能力。硬件環境： Inter(R)Core(TM)i5-3210M CPU 2.50GHz 內存：4GB 硬盤：500G軟件環境： XUbuntuLinux 操作系統 Gnome 桌面 2.18.3 BASH_VERSION=3.2.33(1)-release gcc

3、 version 4.1.2 gedit 2.18.2 OpenOffice 2.3 實驗步驟： 1、問題分析: 為了解決本實驗的同步問題，采用共享內存，信號量，消 息隊列三種IPC 同步對象處理。 客戶程序思想： 每一個客戶把自己的請求當做一條消息發送到相應的消息 隊列中去，并通過阻塞等待接收消息的方式來等待理發師 最終幫自己理發。每一個客戶先判斷sofa 是不是坐滿了，如 果沒有就坐在沙發上等，否者就判斷waitroom 是不是坐滿 了，如果沒有，就坐在waitroom 等，只要有一個坐在sofa 的客戶離開sofa 理發，理發師就會到waitroom 找最先來的 客戶，讓他進入sofa

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

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

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

7、。3、 開發調試過程：在shell命令行下運行$ 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假設先運行理發師程序：$ ./barber 2726號理發師睡眠2728號理發師睡眠2727號理發師睡眠運行$./customer1號新顧客坐入沙發2號新顧客坐入沙發3號新顧客坐入沙發4號新顧客坐入沙發5號新顧客坐入沙發6號新顧客坐入沙發7號新顧客坐入沙發8號新顧客坐入沙發9號新顧客坐入沙

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

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

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

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

12、號量的使用，明白了消息隊列的使用方法，進一步了解了Linux系統中IPC進程同步工具的用法。附件：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 標識的信號燈數組是否已經建立if(sem_id = get_ipc_id(/proc/sysvipc/sem,sem_key) 0 )/semget 新建一個信號燈,其標號返回到 sem_idif(sem_id = semget(sem_key,1,sem_flg) 0)perror(semaphore create error);exit(EXIT_FAILURE);/設置信號燈的初值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 標識的共享內存區是否已經建立if(shm_id = get_ipc_id(/proc/sysvipc/shm,shm_key) 0 )/shmget 新建 一個長度為 shm_num 字節的共享內存,其標號返回到 shm_idif(shm_i

17、d = shmget(shm_key,shm_num,shm_flg) 0)perror(shareMemory set error);exit(EXIT_FAILURE);/shmat 將由 shm_id 標識的共享內存附加給指針 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 標識的共享內存區已經建立,將由 shm_id 標識的

18、共享內存附加給指針 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 標識的消息隊列是否已經建立if(msq_id = get_ipc_id(/proc/sysvipc/msg,msq_key) 0 )/msgget 新建一個消息隊列,其標號返回到 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 /寫請求標識 /讀請求標識/讀寫完成標識 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; /可在在命令行第一參數指定一個進程睡眠秒數,以調解進程執行速度 if(argv1 != NULL) rate = atoi(argv1); else rate = 3; /聯系一個請求消息隊列 wait_quest_flg = IPC_CREAT| 0644; wait_quest_key = 1

23、01; wait_quest_id = set_msq(wait_quest_key,wait_quest_flg); /聯系一個響應消息隊列 wait_respond_flg = IPC_CREAT| 0644; wait_respond_key = 102; wait_respond_id = set_msq(wait_respond_key,wait_respond_flg); /聯系一個請求消息隊列 sofa_quest_flg = IPC_CREAT| 0644; sofa_quest_key = 201; sofa_quest_id = set_msq(sofa_quest_key

24、,sofa_quest_flg); /聯系一個響應消息隊列 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; /顧客同步信號燈初值設為0 sem_val = 0; /獲取顧客同步信號燈,引用標識存 costome

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

27、1) / wait_quest_flg=IPC_NOWAIT; printf(%d號理發師睡眠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號理發師為%d號顧客理發n, getpid(), msg_arg.mid); sleep(rate); down(account_sem); printf(%d號理發師收

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