山东大学操作系统实验五理发师问题报告_操作系统实验报告五
山东大学操作系统实验五理发师问题报告由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“操作系统实验报告五”。
计算机科学与技术学院操作系统实验报告
实验题目：理发店问题
理发店问题：假设理发店的理发室中有3个理发椅子和3个理发师，有一个可容纳4个顾客坐等理发的沙发。此外还有一间等候室，可容纳13位顾客等候进入理发室。顾客如果发现理发店中顾客已满（超过20人），就不进入理发店。
在理发店内，理发师一旦有空就为坐在沙发上等待时间最长的顾客理发，同时空出的沙发让在等候室中等待时间最长的的顾客就坐。顾客理完发后，可向任何一位理发师付款。但理发店只有一本现金登记册，在任一时刻只能记录一个顾客的付款。理发师在没有顾客的时候就坐在理发椅子上睡眠。理发师的时间就用在理发、收款、睡眠上。请利用linux系统提供的IPC进程通信机制实验并实现理发店问题的一个解法。
实验目的：
进一步研究和实践操作系统中关于并发进程同步与互斥操作的一些经典问题的解法，加深对于非对称性互斥问题有关概念的理解。观察和体验非对称性互斥问题的并发控制方法。进一步了解Linux系统中IPC进程同步工具的用法，训练解决对该类问题的实际编程、调试和分析问题的能力。
硬件环境：
Inter(R)Core(TM)i5-3210M CPU @ 2.50GHz 内存：4GB 硬盘：500G 软件环境：
XUbuntu－Linux 操作系统 Gnome 桌面 2.18.3 BASH_VERSION='3.2.33(1)-release gcc version 4.1.2 gedit 2.18.2 OpenOffice 2.3
实验步骤：
1、问题分析:
为了解决本实验的同步问题，采用共享内存，信号量，消
息队列三种IPC 同步对象处理。客户程序思想：
每一个客户把自己的请求当做一条消息发送到相应的消息 队列中去，并通过阻塞等待接收消息的方式来等待理发师 最终帮自己理发。每一个客户先判断sofa 是不是坐满了，如 果没有就坐在沙发上等，否者就判断waitroom 是不是坐满 了，如果没有，就坐在waitroom 等，只要有一个坐在sofa 的客户离开sofa 理发，理发师就会到waitroom 找最先来的 客户，让他进入sofa 等待。理发师程序思想：
理发师查看sofa 上有没有人，没有就睡3 秒，然后再一次 看有没有人，如果有人，就到沙发请最先来的客户来理发。
账本互斥的实现： Semaphore mutex=1 ；
Sofa 队列的长度和wait 队列的长度的实现：
在顾客进程中设置两个变量sofa_count,wait_count，分别保存沙发和等候室的顾客数。
2、算法设计说明如下：
该解法利用消息队列的每条消息代表每个顾客，将进入等候室的顾客组织到一个队列，将坐入沙发的顾客组织到另一个队列。理发师从沙发队列请出顾客，空出的沙发位置再从等候室请入顾客进入沙发队列。三个理发师进程使用相同的程序段上下文，所有顾客使用同一个程序段上下文。这样可避免产生太多进程，以便节省系统资源。理发师程序（Barber）｛
建立一个互斥帐本信号量：s_account,初值=1;建立一个同步顾客信号量：s_customer,初值=0;建立沙发消息队列：q_sofa;建立等候室消息队列：q_wait;建立3个理发师进程：b1_pid, b2_pid, b3_pid;每个理发师进程作： while(1){ 以阻塞方式从沙发队列接收一条消息，如果有消息，则消息出沙发队列(模拟一顾客理发)； 唤醒顾客进程(让下一顾客坐入沙发）。用进程休眠一个随机时间模拟理发过程。理完发,使用帐本信号量记账。互斥的获取账本 记账
唤醒用账本理发师者 否则没有消息(沙发上无顾客)则理发师进程在沙发队列上睡眠；
当沙发队列有消息时被唤醒(有顾客坐入沙发)。
｝ ｝
顾客程序(customer){ while(1){ 取沙发队列消息数(查沙发上顾客数)； 如果消息数小于4(沙发没座满）
以非阻塞方式从等候室队列接收一条消息(查等候室有顾客否)，如果有消息将接收到的消息发送到沙发队列(等候室顾客坐入沙发)； 否则发送一条消息到沙发队列(新来的顾客直接坐入沙发)； 否则(沙发坐满)取等候室队列消息数(查等候室顾客数)； 如果消息数小于13 发送一条消息到等候室队列(等候室没满,新顾客进等候室)； 否则
在顾客同步信号量上睡眠(等候室满暂不接待新顾客)； 用进程休眠一个随机时间模拟顾客到达的时间间隔。｝ ｝
3、开发调试过程：
在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
假设先运行理发师程序： $./barber 2726号理发师睡眠 2728号理发师睡眠 2727号理发师睡眠 运行$./customer 1号新顾客坐入沙发 2号新顾客坐入沙发 3号新顾客坐入沙发 4号新顾客坐入沙发 5号新顾客坐入沙发 6号新顾客坐入沙发 7号新顾客坐入沙发 8号新顾客坐入沙发 9号新顾客坐入沙发 10号新顾客坐入沙发 11号新顾客坐入沙发 12号新顾客坐入沙发
沙发坐满13号顾客在等候室等候 13号顾客从等候室坐入沙发 沙发坐满14号顾客在等候室等候 14号顾客从等候室坐入沙发 沙发坐满15号顾客在等候室等候 15号顾客从等候室坐入沙发 沙发坐满16号顾客在等候室等候 16号顾客从等候室坐入沙发 17号新顾客坐入沙发
沙发坐满18号顾客在等候室等候 18号顾客从等候室坐入沙发 沙发坐满19号顾客在等候室等候 19号顾客从等候室坐入沙发 沙发坐满20号顾客在等候室等候 20号顾客从等候室坐入沙发 沙发坐满21号顾客在等候室等候 21号顾客从等候室坐入沙发......在理发师窗体理发师进程被唤醒： 2726号理发师为1号顾客理发…… 2726号理发师收取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号顾客交费......反之，如果先运行顾客程序： $./customer 1号新顾客坐入沙发 2号新顾客坐入沙发 3号新顾客坐入沙发 4号新顾客坐入沙发
沙发坐满5号顾客在等候室等候 沙发坐满6号顾客在等候室等候 沙发坐满7号顾客在等候室等候 沙发坐满8号顾客在等候室等候 沙发坐满9号顾客在等候室等候 沙发坐满10号顾客在等候室等候 沙发坐满11号顾客在等候室等候 沙发坐满12号顾客在等候室等候 沙发坐满13号顾客在等候室等候 沙发坐满14号顾客在等候室等候 沙发坐满15号顾客在等候室等候 沙发坐满16号顾客在等候室等候 沙发坐满17号顾客在等候室等候 等候室满18号顾客没有进入理发店
当18号顾客到达时理发店20个位置已满，顾客进程阻塞(假设理发师进程没运行表示三个理发师正坐在3个理发椅上睡觉)。
再运行理发师程序： $./barber 运行截图如下： 附
件
：
4.7.分析与感悟：
首先运行顾客程序的话，顾客程序首先向沙发队列发送消息，然后向等候室队列发送消息，当两个队列都满了之后，该进程会暂停，及停止在顾客同步信号量上。而随着理发师程序的开始运行，理发师进程会唤醒顾客进程，及在顾客同步信号量上进行up操作，并且从消息队列中接受消息。反之，若理发师程序先运行，则三个理发师由于无法从沙发队列上接收到消息，而且由于是阻塞式接受，就会阻塞在这个消息队列上，只有当顾客程序运行时，向沙发队列发送消息后理发师进程才会继续。通过编写这个实验，是我更加熟练了信号量的使用，明白了消息队列的使用方法，进一步了解了Linux系统中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] = ' ';if(atoi(colum)!= key)continue;j=0;while(line[i] == ' ')i++;while(line[i]!=' ')colum[j++] = line[i++];colum[j] = ' ';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.sem_flg = SEM_UNDO;if((semop(sem_id,&buf,1))
int set_sem(key_t sem_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))
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))
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))
#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 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_respond_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 sem_val,int sem_flag);int down(int sem_id);int up(int sem_id);Barber.c： #include “ipc.h” int main(int argc,char *argv[]){
// int i;
int rate;
Msg_buf msg_arg;
//可在在命令行第一参数指定一个进程睡眠秒数,以调解进程执行速度
if(argv[1]!= NULL)rate = atoi(argv[1]);
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_respond_key,wait_respond_flg);
//联系一个请求消息队列
sofa_quest_flg = IPC_CREAT| 0644;
sofa_quest_key = 201;
sofa_quest_id = set_msq(sofa_quest_key,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;
//获取顾客同步信号灯,引用标识存 costomer_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(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(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号理发师收取%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);
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.h” int main(int argc,char *argv[]){
int rate;
Msg_buf msg_arg;
//可在在命令行第一参数指定一个进程睡眠秒数,以调解进程执行速度
if(argv[1]!= NULL)rate = atoi(argv[1]);
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_respond_key,wait_respond_flg);
//联系一个请求消息队列
sofa_quest_flg = IPC_CREAT| 0644;
sofa_quest_key = 201;
sofa_quest_id = set_msq(sofa_quest_key,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;
//获取顾客同步信号灯,引用标识存 costomer_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 sofa_count=0;
int wait_count=0;
int i=0;//
int count=0;
while(1){
sleep(rate);
//
count++;
//
printf(“count = %d ”, count);
i++;
//
printf(“i = %d ”, i);
msg_arg.mid = i;
if(sofa_count
if(wait_count!= 0){
i--;
//阻塞方式接收消息
msgrcv(wait_quest_id, &msg_arg, sizeof(msg_arg), 0, 0);
printf(“mid = %d ”, msg_arg.mid);
msgsnd(wait_respond_id, &msg_arg,sizeof(msg_arg), 0);
printf(“%d号顾客从等候室坐入沙发n”, msg_arg.mid);
//
up(costomer_sem);
} else {
printf(“%d号新顾客坐入沙发n”, i);
}
sofa_quest_flg=IPC_NOWAIT;
if(msgsnd(sofa_quest_id, &msg_arg, sizeof(msg_arg), sofa_quest_flg)>= 0){
// sofa_count++;
// return 0;
}
sofa_count++;
} else if(wait_count
printf(“沙发坐满，%d号顾客在等候室等候……n”, i);
wait_quest_flg = IPC_NOWAIT;
msgsnd(wait_quest_id, wait_quest_flg);
wait_count++;
} else {
printf(“等候室满，%d顾客没有进入理发店n”, i);
//
down(costomer_sem);
&msg_arg,sizeof(msg_arg),msgrcv(sofa_respond_id, &msg_arg, sizeof(msg_arg), 0, 0);
sofa_count--;
i--;
}
sofa_quest_flg=IPC_NOWAIT;
if(msgrcv(sofa_respond_id, &msg_arg, sofa_quest_flg)>=0){
sofa_count--;
}
wait_quest_flg = IPC_NOWAIT;
if(msgrcv(wait_respond_id, &msg_arg, wait_quest_flg)>=0){
wait_count--;
}
}
return 0;}
sizeof(msg_arg), sizeof(msg_arg), 0, 0,
