山大操作系統(tǒng)實(shí)驗(yàn)五

1、山東大學(xué)軟件學(xué)院操作系統(tǒng)實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)題目：進(jìn)程互斥實(shí)驗(yàn)實(shí)驗(yàn)?zāi)康模哼M(jìn)一步研究和實(shí)踐操作系統(tǒng)中關(guān)于并發(fā)進(jìn)程同步與互斥操作的一些經(jīng)典問(wèn)題的解法，加深對(duì)于非對(duì)稱(chēng)性互斥問(wèn)題有關(guān)概念的理解。觀察和體驗(yàn)非對(duì)稱(chēng)性互斥問(wèn)題的并發(fā)控制方法。進(jìn)一步了解Linux系統(tǒng)中IPC進(jìn)程同步工具的用法，訓(xùn)練解決對(duì)該類(lèi)問(wèn)題的實(shí)際編程、調(diào)試和分析問(wèn)題的能力。實(shí)驗(yà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ā)店中顧客已滿(mǎn)（超過(guò)20人），就不進(jìn)入理發(fā)店。在理發(fā)店內(nèi)，理發(fā)師一旦有空就為坐在沙發(fā)上等待時(shí)間最長(zhǎng)的顧客

2、理發(fā)，同時(shí)空出的沙發(fā)讓在等候室中等待時(shí)間最長(zhǎng)的的顧客就坐。顧客理完發(fā)后，可向任何一位理發(fā)師付款。但理發(fā)店只有一本現(xiàn)金登記冊(cè)，在任一時(shí)刻只能記錄一個(gè)顧客的付款。理發(fā)師在沒(méi)有顧客的時(shí)候就坐在理發(fā)椅子上睡眠。理發(fā)師的時(shí)間就用在理發(fā)、收款、睡眠上。請(qǐng)利用linux系統(tǒng)提供的IPC進(jìn)程通信機(jī)制實(shí)驗(yàn)并實(shí)現(xiàn)理發(fā)店問(wèn)題的一個(gè)解法?？偨Y(jié)和分析示例實(shí)驗(yàn)和獨(dú)立實(shí)驗(yàn)中觀察到的調(diào)試和運(yùn)行信息，說(shuō)明您對(duì)與解決非對(duì)稱(chēng)性互斥操作的算法有哪些新的理解和認(rèn)識(shí)？為什么會(huì)出現(xiàn)進(jìn)程饑餓現(xiàn)象？本實(shí)驗(yàn)的饑餓現(xiàn)象是怎樣表現(xiàn)的？怎樣解決并發(fā)進(jìn)程間發(fā)生的饑餓現(xiàn)象？您對(duì)于并發(fā)進(jìn)程間使用消息傳遞解決進(jìn)程通信問(wèn)題有哪些新的理解和認(rèn)識(shí)？根據(jù)實(shí)驗(yàn)程序、調(diào)

3、試過(guò)程和結(jié)果分析寫(xiě)出實(shí)驗(yàn)報(bào)告。硬件環(huán)境： CPU： P4/1.8MHz 內(nèi)存：256MB 硬盤(pán)： 10GB 軟件環(huán)境： Ubuntu08.4Linux 操作系統(tǒng) Gnome 桌面 2.18.3BASH_VERSION='3.2.33(1)-release gcc version 4.1.2 vi 3.1.2 gedit 2.18.2 OpenOffice 2.3實(shí)驗(yàn)步驟：1. 問(wèn)題分析假設(shè)理發(fā)店的理發(fā)室中有3個(gè)理發(fā)椅子和3個(gè)理發(fā)師，有一個(gè)可容納4個(gè)顧客坐等理發(fā)的沙發(fā)。此外還有一間等候室，可容納13位顧客等候進(jìn)入理發(fā)室。顧客如果發(fā)現(xiàn)理發(fā)店中顧客已滿(mǎn)（超過(guò)20人），就不進(jìn)入理發(fā)店。在理發(fā)店

4、內(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ā)、收款、睡眠上。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)程使用相同的程序段上下文，所有顧客使用同一個(gè)程序段上下文。這樣可避免產(chǎn)生太多進(jìn)程，以便節(jié)省系統(tǒng)資源

5、。int sem_p(int semid, int index, int ipc_nowait) /P操作 struct sembuf buf = 0, -1, 0; buf.sem_num = index; buf.sem_flg = ipc_nowait ? IPC_NOWAIT : 0; if(semop(semid, &buf, 1) = -1) if(ipc_nowait && errno = EAGAIN) return -2; else perror("a wrong operation to semaphore occured!");

6、 return -1; return 0;int sem_v(int semid, int index, int ipc_nowait) /V操作 struct sembuf buf = 0, 1, 0; buf.sem_num = index; buf.sem_flg = ipc_nowait ? IPC_NOWAIT : 0; if(semop(semid, &buf, 1) = -1) if(ipc_nowait && errno = EAGAIN) return -2; else perror("a wrong operation to semapho

7、re occured!"); return -1; return 0;Costumo:if(pid = fork() < 0) perror("fork error!"); exit(EXIT_FAILURE); else if(pid = 0) /child process while(1) sem_p(wait_lock_semid, 1, 0); /等待沙發(fā)上有人 sem_p(wait_semid, 0, 0); /等待理發(fā)師有空 if(msg_get(wait_msg, &msg, WAIT_ID_SOFA, 0) < 0) perro

8、r("message get error!"); exit(-1); msg_send(wait_msg, WAIT_ID_CHAIR, msg.id, 0); printf("the consumer %d => chair, wait %d secondsn", msg.id, (time(NULL) - msg.timestamp); /sofa => chair sem_v(wait_semid, 1, 0); /沙發(fā)上有空位了 sem_v(wait_lock_semid, 0, 0); /通知有人來(lái)理發(fā)了 return 0; if(

9、pid = fork() < 0) perror("fork error!"); exit(EXIT_FAILURE); else if(pid = 0) /child process while(1) sem_p(wait_lock_semid, 2, 0); /等待室內(nèi)有人 sem_p(wait_semid, 1, 0); /沙發(fā)上有空位 if(msg_get(wait_msg, &msg, WAIT_ID_ROOM, 0) < 0) perror("message get error!"); exit(-1); msg_send

10、(wait_msg, WAIT_ID_SOFA, msg.id, 0); printf("the consumer %d => sofa, wait %d secondsn", msg.id, (time(NULL) - msg.timestamp); /room => sofa sem_v(wait_semid, 2, 0); /等待室空出1個(gè)位子 sem_v(wait_lock_semid, 1, 0); /通知沙發(fā)上有人了 return 0; while(1) if(pid = fork()< 0) perror("fork error!&

11、quot;); exit(EXIT_FAILURE); else if(pid = 0) / if(consumer_status = sem_p(wait_semid, 2, 1) = -2) /檢查理發(fā)店（等待室）是否已滿(mǎn) printf("我是顧客%d，理發(fā)店滿(mǎn)了，我走人了。n", getpid(); /full else if(consumer_status = 0) /仍然有空間 printf("我是顧客%d,進(jìn)入理發(fā)店n", getpid(); printf("我是顧客%d,正在等待室等待n", getpid(); msg_

12、send(wait_msg, WAIT_ID_ROOM, getpid(), 0); /進(jìn)入等待室 sem_v(wait_lock_semid, 2, 0); /通知等待室有人了 exit(0); sleep(3); / Baker :if(pid2 = 0) while(1) if(barber_status = 0) if(sem_p(wait_lock_semid, 0, 1) = -2) /等待有人來(lái)理發(fā)或需要收銀 printf("我是%d號(hào)理發(fā)師，正在睡覺(jué)。zzzZZZn", barber_id); sem_p(wait_lock_semid, 0, 0); if

13、(sem_p(wait_lock_semid, 3, 1) = 0) /如果是需要收銀 barber_status = 2; if(msg_get(wait_msg, &msg, WAIT_ID_CASH, 1) < 0) perror("message1 get error!"); exit(-1); barber_consumer = msg.id; else barber_status = 1; if(msg_get(wait_msg, &msg, WAIT_ID_CHAIR, 1) < 0) perror("message2 g

14、et error!"); exit(-1); barber_consumer = msg.id; else if(barber_status = 1) printf("我是%d號(hào)理發(fā)師，正在為%d進(jìn)行理發(fā)。n", barber_id, barber_consumer); sleep(15); barber_status = 0; sem_v(wait_lock_semid, 3, 0); /需要收銀 msg_send(wait_msg, WAIT_ID_CASH, barber_consumer, 0); sem_v(wait_lock_semid, 0, 0);

15、 else sem_p(cash_semid, 0, 0); /收銀本的互斥鎖 printf("我是%d號(hào)理發(fā)師, 正在為%d進(jìn)行收銀。n", barber_id, barber_consumer); sem_v(cash_semid, 0, 0); barber_status = 0; sem_v(wait_semid, 0, 0); /通知理發(fā)師有空了 else signal(SIGINT, handler_exit); wait();3. 某種方法的偽代碼理發(fā)師程序（Barber）建立一個(gè)互斥帳本信號(hào)量：s_account,初值=1;建立一個(gè)同步顧客信號(hào)量：s_cus

16、tomer,初值=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)有消息(沙發(fā)上無(wú)顧客)則理發(fā)師進(jìn)程在沙發(fā)隊(duì)列上睡眠；當(dāng)沙發(fā)隊(duì)列有消息時(shí)被喚醒(有顧客坐入沙發(fā))。顧客程序(customer)while(1)取沙發(fā)隊(duì)列消息數(shù)(查沙發(fā)上顧客數(shù)) ；如果消息數(shù)

17、小于4(沙發(fā)沒(méi)座滿(mǎn)）以非阻塞方式從等候室隊(duì)列接收一條消息(查等候室有顧客否)，如果有消息將接收到的消息發(fā)送到沙發(fā)隊(duì)列(等候室顧客坐入沙發(fā))；否則發(fā)送一條消息到沙發(fā)隊(duì)列(新來(lái)的顧客直接坐入沙發(fā))；否則(沙發(fā)坐滿(mǎn))取等候室隊(duì)列消息數(shù)(查等候室顧客數(shù)) ；如果消息數(shù)小于13發(fā)送一條消息到等候室隊(duì)列(等候室沒(méi)滿(mǎn),新顧客進(jìn)等候室)；否則在顧客同步信號(hào)量上睡眠(等候室滿(mǎn)暫不接待新顧客)；用進(jìn)程休眠一個(gè)隨機(jī)時(shí)間模擬顧客到達(dá)的時(shí)間間隔。4. 實(shí)驗(yàn)收獲通過(guò)本次試驗(yàn)，使我加深了對(duì)進(jìn)程互斥概念的理解，體驗(yàn)到了共享內(nèi)存、信號(hào)燈數(shù)組以及消息隊(duì)列的功能。基本已經(jīng)掌握了如何用消息隊(duì)列控制和堵塞進(jìn)程，實(shí)現(xiàn)對(duì)共享內(nèi)存的有序訪問(wèn)

18、。另外，是我加深了對(duì)理發(fā)師算法的理解，找到了它與讀者寫(xiě)者問(wèn)題的共同之處：1.進(jìn)程間的互斥2.理發(fā)師類(lèi)似讀者進(jìn)程，顧客類(lèi)似寫(xiě)者進(jìn)程。最后，通過(guò)不斷的調(diào)試，使我熟練了在Linux環(huán)境下編程的技巧，對(duì)進(jìn)程的創(chuàng)建與控制更加熟悉。附錄 A： 本實(shí)驗(yàn)全部程序源代碼及注釋IPC.H#ifndef CZW_IPC_H_INCLUDED#define CZW_IPC_H_INCLUDED#include<errno.h>#include<sys/types.h>#include<sys/sem.h>int sem_create(const char *pathname, in

19、t proj_id, int nsems, int init_value) key_t keyid; int semid, i; if(keyid = ftok(pathname, proj_id) = -1) perror("ftok error!"); return -1; if(semid = semget(keyid, nsems, IPC_CREAT | 0666) < 0) perror("semget error!"); return -1; for(i = 0; i < nsems; i+) semctl(semid, i,

20、SETVAL, init_value); return semid;int sem_delete(const char *pathname, int proj_id) key_t keyid; int semid, i; if(keyid = ftok(pathname, proj_id) = -1) perror("ftok error!"); return -1; if(semid = semget(keyid, 0, 0666) < 0) perror("semget error!"); return -1; if(semctl(semid,

21、 0, IPC_RMID) < 0) perror("sem delete fail!"); return -1; return 1;int sem_set(int semid, int index, int value) if(index = -1) /todo setall else if(semctl(semid, index, SETVAL, value) < 0) perror("sem set error!"); return -1; return 0;int sem_p(int semid, int index, int ipc

22、_nowait) /P操作 struct sembuf buf = 0, -1, 0; buf.sem_num = index; buf.sem_flg = ipc_nowait ? IPC_NOWAIT : 0; if(semop(semid, &buf, 1) = -1) if(ipc_nowait && errno = EAGAIN) return -2; else perror("a wrong operation to semaphore occured!"); return -1; return 0;int sem_v(int semid

23、, int index, int ipc_nowait) /V操作 struct sembuf buf = 0, 1, 0; buf.sem_num = index; buf.sem_flg = ipc_nowait ? IPC_NOWAIT : 0; if(semop(semid, &buf, 1) = -1) if(ipc_nowait && errno = EAGAIN) return -2; else perror("a wrong operation to semaphore occured!"); return -1; return 0;

24、int sem_show(int semid, int index) return semctl(semid, index, GETVAL);void *smh_create(const char *pathname, int proj_id, size_t size) key_t keyid; int shmid; int flags = IPC_CREAT | 0666; if(keyid = ftok(pathname, proj_id) = -1) perror("ftok error!"); return (char *)-1; if(shmid = shmget

25、(keyid, size, flags) = -1) perror("shmget error!"); return (char *)-1; return shmat(shmid, NULL, 0);int msg_create(const char *pathname, int proj_id) key_t keyid; int msgid; int flags = IPC_CREAT | 0666; if(keyid = ftok(pathname, proj_id) = -1) perror("ftok error!"); return -1; i

26、f(msgid = msgget(keyid, flags) = -1) perror("msgget error!"); return -1; return msgid;int msg_delete(const char *pathname, int proj_id) key_t keyid; int msgid, i; if(keyid = ftok(pathname, proj_id) = -1) perror("ftok error!"); return -1; if(msgid = msgget(keyid, 0666) < 0) per

27、ror("msgget error!"); return -1; if(msgctl(msgid, IPC_RMID) < 0) perror("msg delete fail!"); return -1; return 1;#endif / CZW_IPC_H_INCLUDEDEX5_H#ifndef EX5_H_INCLUDED#define EX5_H_INCLUDED#include<signal.h>#include "ipc.h"#define WAIT_ID_SOFA 1#define WAIT_ID_

28、ROOM 2#define WAIT_ID_CHAIR 3#define WAIT_ID_CASH 4struct ex5msgbuf long mtype; int id; time_t timestamp;int msg_send(int msgid, int msgtype, int id, int ipc_nowait) struct ex5msgbuf msg; msg.mtype = msgtype; msg.id = id; msg.timestamp = time(NULL); if(msgsnd(msgid, &msg, sizeof(struct ex5msgbuf

29、) - 4, ipc_nowait ? IPC_NOWAIT : 0) < 0) if(ipc_nowait && errno = EAGAIN) return -2; else perror("msg send error!"); return -1; return 0;int msg_get(int msgid, struct ex5msgbuf *msg, long msgtype, int ipc_nowait) return msgrcv(msgid, msg, sizeof(struct ex5msgbuf) - 4, msgtype, (

30、ipc_nowait ? IPC_NOWAIT : 0);#endif / EX5_H_INCLUDEDBaker:#include<stdio.h>#include<stdlib.h>#include "ex5.h"const int debug = 0;void handler_exit(int signo) sem_delete(".", 10); sem_delete(".", 11); msg_delete(".", 31); sem_delete(".", 1

31、10); exit(0);int main() int wait_semid = sem_create(".", 10, 3, 0); int wait_lock_semid = sem_create(".", 11, 4, 0); int wait_msg = msg_create(".", 31); int cash_semid = sem_create(".", 110, 1, 1); debug && printf("twait_semid is %dn", wait_s

32、emid); debug && printf("twait_lock_semid is %dn", wait_lock_semid); debug && printf("twait_msg is %dn", wait_msg); debug && printf("tcash_semid is %dn", cash_semid); sem_set(wait_semid, 0, 3); sem_set(wait_semid, 1, 4); sem_set(wait_semid, 2, 13)

33、; pid_t pid3 = 0; int i; int barber_id, barber_status, barber_consumer; struct ex5msgbuf msg; for(i = 0; i < 3; i+) if(pidi = fork() < 0) perror("fork error!"); exit(EXIT_FAILURE); else if(pidi = 0) barber_id = i + 1; barber_status = 0; debug && printf("tI'm barber%d

34、, my pid is %dn",barber_id,getpid(); break; if(pid2 = 0) while(1) if(barber_status = 0) if(sem_p(wait_lock_semid, 0, 1) = -2) /等待有人來(lái)理發(fā)或需要收銀 printf("我是%d號(hào)理發(fā)師，正在睡覺(jué)。zzzZZZn", barber_id); sem_p(wait_lock_semid, 0, 0); if(sem_p(wait_lock_semid, 3, 1) = 0) /如果是需要收銀 barber_status = 2; if(msg

35、_get(wait_msg, &msg, WAIT_ID_CASH, 1) < 0) perror("message1 get error!"); exit(-1); barber_consumer = msg.id; else barber_status = 1; if(msg_get(wait_msg, &msg, WAIT_ID_CHAIR, 1) < 0) perror("message2 get error!"); exit(-1); barber_consumer = msg.id; else if(barber_

36、status = 1) printf("我是%d號(hào)理發(fā)師，正在為%d進(jìn)行理發(fā)。n", barber_id, barber_consumer); sleep(15); barber_status = 0; sem_v(wait_lock_semid, 3, 0); /需要收銀 msg_send(wait_msg, WAIT_ID_CASH, barber_consumer, 0); sem_v(wait_lock_semid, 0, 0); else sem_p(cash_semid, 0, 0); /收銀本的互斥鎖 printf("我是%d號(hào)理發(fā)師, 正在為%d進(jìn)

37、行收銀。n", barber_id, barber_consumer); sem_v(cash_semid, 0, 0); barber_status = 0; sem_v(wait_semid, 0, 0); /通知理發(fā)師有空了 else signal(SIGINT, handler_exit); wait(); return 0;Costomer：#include<stdio.h>#include<stdlib.h>#include "ex5.h"const int debug = 0;int main() int wait_semid

38、 = sem_create(".", 10, 0, 0); int wait_lock_semid = sem_create(".", 11, 0, 0); int wait_msg = msg_create(".", 31); debug && printf("twait_semid is %dn", wait_semid); debug && printf("twait_lock_semid is %dn", wait_lock_semid); debug &

39、amp;& printf("twait_msg is %dn", wait_msg); debug && printf("twait_semid_0 is %dn", sem_show(wait_semid, 0); pid_t pid = 0; struct ex5msgbuf msg; int i; int consumer_status; if(pid = fork() < 0) perror("fork error!"); exit(EXIT_FAILURE); else if(pid = 0) /child process while(1) sem_p(wait_lock_semid, 1, 0); /等待沙發(fā)上有人 sem_p(wait_semid, 0, 0); /等待理發(fā)師有空 if(msg_get(wait_msg, &msg, WAIT_ID_SOFA, 0) < 0) perror(&