第一篇：山東大學操作系統(tǒng)實驗五理發(fā)師問題報告

計算機科學與技術(shù)學院操作系統(tǒng)實驗報告

實驗題目：理發(fā)店問題

理發(fā)店問題：假設(shè)理發(fā)店的理發(fā)室中有3個理發(fā)椅子和3個理發(fā)師，有一個可容納4個顧客坐等理發(fā)的沙發(fā)。此外還有一間等候室，可容納13位顧客等候進入理發(fā)室。顧客如果發(fā)現(xiàn)理發(fā)店中顧客已滿（超過20人），就不進入理發(fā)店。

在理發(fā)店內(nèi)，理發(fā)師一旦有空就為坐在沙發(fā)上等待時間最長的顧客理發(fā)，同時空出的沙發(fā)讓在等候室中等待時間最長的的顧客就坐。顧客理完發(fā)后，可向任何一位理發(fā)師付款。但理發(fā)店只有一本現(xiàn)金登記冊，在任一時刻只能記錄一個顧客的付款。理發(fā)師在沒有顧客的時候就坐在理發(fā)椅子上睡眠。理發(fā)師的時間就用在理發(fā)、收款、睡眠上。請利用linux系統(tǒng)提供的IPC進程通信機制實驗并實現(xiàn)理發(fā)店問題的一個解法。

實驗目的：

進一步研究和實踐操作系統(tǒng)中關(guān)于并發(fā)進程同步與互斥操作的一些經(jīng)典問題的解法，加深對于非對稱性互斥問題有關(guān)概念的理解。觀察和體驗非對稱性互斥問題的并發(fā)控制方法。進一步了解Linux系統(tǒng)中IPC進程同步工具的用法，訓練解決對該類問題的實際編程、調(diào)試和分析問題的能力。

硬件環(huán)境：

Inter(R)Core(TM)i5-3210M CPU @ 2.50GHz 內(nèi)存：4GB 硬盤：500G 軟件環(huán)境：

XUbuntu－Linux 操作系統(tǒng) Gnome 桌面 2.18.3 BASH_VERSION='3.2.33(1)-release gcc version 4.1.2 gedit 2.18.2 OpenOffice 2.3

實驗步驟：

1、問題分析:

為了解決本實驗的同步問題，采用共享內(nèi)存，信號量，消

息隊列三種IPC 同步對象處理?？蛻舫绦蛩枷耄?/p>

每一個客戶把自己的請求當做一條消息發(fā)送到相應的消息 隊列中去，并通過阻塞等待接收消息的方式來等待理發(fā)師 最終幫自己理發(fā)。每一個客戶先判斷sofa 是不是坐滿了，如 果沒有就坐在沙發(fā)上等，否者就判斷waitroom 是不是坐滿 了，如果沒有，就坐在waitroom 等，只要有一個坐在sofa 的客戶離開sofa 理發(fā)，理發(fā)師就會到waitroom 找最先來的 客戶，讓他進入sofa 等待。理發(fā)師程序思想：

理發(fā)師查看sofa 上有沒有人，沒有就睡3 秒，然后再一次 看有沒有人，如果有人，就到沙發(fā)請最先來的客戶來理發(fā)。

賬本互斥的實現(xiàn)： Semaphore mutex=1 ；

Sofa 隊列的長度和wait 隊列的長度的實現(xiàn)：

在顧客進程中設(shè)置兩個變量sofa_count,wait_count，分別保存沙發(fā)和等候室的顧客數(shù)。

2、算法設(shè)計說明如下：

該解法利用消息隊列的每條消息代表每個顧客，將進入等候室的顧客組織到一個隊列，將坐入沙發(fā)的顧客組織到另一個隊列。理發(fā)師從沙發(fā)隊列請出顧客，空出的沙發(fā)位置再從等候室請入顧客進入沙發(fā)隊列。三個理發(fā)師進程使用相同的程序段上下文，所有顧客使用同一個程序段上下文。這樣可避免產(chǎn)生太多進程，以便節(jié)省系統(tǒng)資源。理發(fā)師程序（Barber）｛

建立一個互斥帳本信號量：s_account,初值=1;建立一個同步顧客信號量：s_customer,初值=0;建立沙發(fā)消息隊列：q_sofa;建立等候室消息隊列：q_wait;建立3個理發(fā)師進程：b1_pid, b2_pid, b3_pid;每個理發(fā)師進程作： while(1){ 以阻塞方式從沙發(fā)隊列接收一條消息，如果有消息，則消息出沙發(fā)隊列(模擬一顧客理發(fā))； 喚醒顧客進程(讓下一顧客坐入沙發(fā)）。用進程休眠一個隨機時間模擬理發(fā)過程。理完發(fā),使用帳本信號量記賬。互斥的獲取賬本 記賬

喚醒用賬本理發(fā)師者 否則沒有消息(沙發(fā)上無顧客)則理發(fā)師進程在沙發(fā)隊列上睡眠；

當沙發(fā)隊列有消息時被喚醒(有顧客坐入沙發(fā))。

｝ ｝

顧客程序(customer){ while(1){ 取沙發(fā)隊列消息數(shù)(查沙發(fā)上顧客數(shù))； 如果消息數(shù)小于4(沙發(fā)沒座滿）

以非阻塞方式從等候室隊列接收一條消息(查等候室有顧客否)，如果有消息將接收到的消息發(fā)送到沙發(fā)隊列(等候室顧客坐入沙發(fā))； 否則發(fā)送一條消息到沙發(fā)隊列(新來的顧客直接坐入沙發(fā))； 否則(沙發(fā)坐滿)取等候室隊列消息數(shù)(查等候室顧客數(shù))； 如果消息數(shù)小于13 發(fā)送一條消息到等候室隊列(等候室沒滿,新顧客進等候室)； 否則

在顧客同步信號量上睡眠(等候室滿暫不接待新顧客)； 用進程休眠一個隨機時間模擬顧客到達的時間間隔。｝ ｝

3、開發(fā)調(diào)試過程：

在shell命令行下運行$ make barber customer gcc-g-c barber.c ipc.c gcc barber.o ipc.o-o barber gcc-g-c customer.c ipc.c gcc customer.o ipc.o-o customer

假設(shè)先運行理發(fā)師程序： $./barber 2726號理發(fā)師睡眠 2728號理發(fā)師睡眠 2727號理發(fā)師睡眠 運行$./customer 1號新顧客坐入沙發(fā) 2號新顧客坐入沙發(fā) 3號新顧客坐入沙發(fā) 4號新顧客坐入沙發(fā) 5號新顧客坐入沙發(fā) 6號新顧客坐入沙發(fā) 7號新顧客坐入沙發(fā) 8號新顧客坐入沙發(fā) 9號新顧客坐入沙發(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ā)師進程被喚醒： 2726號理發(fā)師為1號顧客理發(fā)…… 2726號理發(fā)師收取1號顧客交費 2726號理發(fā)師睡眠

2728號理發(fā)師為2號顧客理發(fā)…… 2728號理發(fā)師收取2號顧客交費 2728號理發(fā)師睡眠

2727號理發(fā)師為3號顧客理發(fā)…… 2726號理發(fā)師為4號顧客理發(fā)…… 2727號理發(fā)師收取3號顧客交費 2727號理發(fā)師睡眠

2726號理發(fā)師收取4號顧客交費 2726號理發(fā)師睡眠

2728號理發(fā)師為5號顧客理發(fā)…… 2728號理發(fā)師收取5號顧客交費 2728號理發(fā)師睡眠

2727號理發(fā)師為6號顧客理發(fā)…… 2726號理發(fā)師為7號顧客理發(fā)…… 2727號理發(fā)師收取6號顧客交費 2727號理發(fā)師睡眠

2726號理發(fā)師收取7號顧客交費 2726號理發(fā)師睡眠

2728號理發(fā)師為8號顧客理發(fā)…… 2728號理發(fā)師收取8號顧客交費......反之，如果先運行顧客程序： $./customer 1號新顧客坐入沙發(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號顧客沒有進入理發(fā)店

當18號顧客到達時理發(fā)店20個位置已滿，顧客進程阻塞(假設(shè)理發(fā)師進程沒運行表示三個理發(fā)師正坐在3個理發(fā)椅上睡覺)。

再運行理發(fā)師程序： $./barber 運行截圖如下： 附

件

：

4.7.分析與感悟：

首先運行顧客程序的話，顧客程序首先向沙發(fā)隊列發(fā)送消息，然后向等候室隊列發(fā)送消息，當兩個隊列都滿了之后，該進程會暫停，及停止在顧客同步信號量上。而隨著理發(fā)師程序的開始運行，理發(fā)師進程會喚醒顧客進程，及在顧客同步信號量上進行up操作，并且從消息隊列中接受消息。反之，若理發(fā)師程序先運行，則三個理發(fā)師由于無法從沙發(fā)隊列上接收到消息，而且由于是阻塞式接受，就會阻塞在這個消息隊列上，只有當顧客程序運行時，向沙發(fā)隊列發(fā)送消息后理發(fā)師進程才會繼續(xù)。通過編寫這個實驗，是我更加熟練了信號量的使用，明白了消息隊列的使用方法，進一步了解了Linux系統(tǒng)中IPC進程同步工具的用法。附件：

Ipc.c #include “ipc.h”

int get_ipc_id(char *proc_file,key_t key){ FILE *pf;int i,j;char line[BUFSZ],colum[BUFSZ];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,pf);while(line[i] == ' ')i++;while(line[i]!=' ')colum[j++] = line[i++];colum[j] = '