山东大学操作系统实验五理发师问题报告

计算机科学与技术学院操作系统实验报告实验题目：理发店问题理发店问题：假设理发店的理发室中有3个理发椅子和3个理发师，有一个可容纳4个顾客坐等理发的沙发。此外还有一间等候室，可容纳13位顾客等候进入理发室。顾客如果发现理发店中顾客已满（超过20人），就不进入理发店。在理发店内，理发师一旦有空就为坐在沙发上等待时间最长的顾客理发，同时空出的沙发让在等候室中等待时间最长的的顾客就坐。顾客理完发后，可向任何一位理发师付款。但理发店只有一本现金登记册，在任一时刻只能记录一个顾客的付款。理发师在没有顾客的时候就坐在理发椅子上睡眠。理发师的时间就用在理发、收款、睡眠上。请利用linux系统提供的IPC进程通信机制实验并实现理发店问题的一个解法。实验目的：进一步研究和实践操作系统中关于并发进程同步与互斥操作的一些经典问题的解法，加深对于非对称性互斥问题有关概念的理解。观察和体验非对称性互斥问题的并发控制方法。进一步了解Linux系统中IPC进程同步工具的用法，训练解决对该类问题的实际编程、调试和分析问题的能力。硬件环境：Inter(R)Core(TM)i5-3210MCPU@2.50GHz内存：4GB硬盘：500G软件环境：XUbuntu－Linux操作系统Gnome桌面2.18.3BASH_VERSION='3.2.33(1)-releasegccversion4.1.2gedit2.18.2OpenOffice2.3实验步骤：1、问题分析:为了解决本实验的同步问题，采用共享内存，信号量，消息队列三种IPC同步对象处理。客户程序思想：每一个客户把自己的请求当做一条消息发送到相应的消息队列中去，并通过阻塞等待接收消息的方式来等待理发师最终帮自己理发。每一个客户先判断sofa是不是坐满了，如果没有就坐在沙发上等，否者就判断waitroom是不是坐满了，如果没有，就坐在waitroom等，只要有一个坐在sofa的客户离开sofa理发，理发师就会到waitroom找最先来的客户，让他进入sofa等待。理发师程序思想：理发师查看sofa上有没有人，没有就睡3秒，然后再一次看有没有人，如果有人，就到沙发请最先来的客户来理发。账本互斥的实现：Semaphoremutex=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命令行下运行$makebarbercustomergcc-g-cbarber.cipc.cgccbarber.oipc.o-obarbergcc-g-ccustomer.cipc.cgcccustomer.oipc.o-ocustomer假设先运行理发师程序：$./barber2726号理发师睡眠2728号理发师睡眠2727号理发师睡眠运行$./customer1号新顾客坐入沙发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号顾客交费......反之，如果先运行顾客程序：$./customer1号新顾客坐入沙发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#includeipc.hintget_ipc_id(char*proc_file,key_tkey){FILE*pf;inti,j;charline[BUFSZ],colum[BUFSZ];if((pf=fopen(proc_file,r))==NULL){perror(Procfilenotopen);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]='\0';if(atoi(colum)!=key)continue;j=0;while(line[i]=='')i++;while(line[i]!='')colum[j++]=line[i++];colum[j]='\0';i=atoi(colum);fclose(pf);returni;}fclose(pf);return-1;}intdown(intsem_id){structsembufbuf;buf.sem_op=-1;buf.sem_num=0;buf.sem_flg=SEM_UNDO;if((semop(sem_id,&buf,1))0){perror(downerror);exit(EXIT_FAILURE);}returnEXIT_SUCCESS;}intup(intsem_id){structsembufbuf;buf.sem_op=1;buf.sem_num=0;buf.sem_flg=SEM_UNDO;if((semop(sem_id,&buf,1))0){perror(uperror);exit(EXIT_FAILURE);}returnEXIT_SUCCESS;}intset_sem(key_tsem_key,intsem_val,intsem_flg){intsem_id;Sem_unssem_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(semaphorecreateerror);exit(EXIT_FAILURE);}//设置信号灯的初值sem_arg.val=sem_val;if(semctl(sem_id,0,SETVAL,sem_arg)0){perror(semaphoreseterror);exit(EXIT_FAILURE);}}returnsem_id;}char*set_shm(key_tshm_key,intshm_num,intshm_flg){inti,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_id=shmget(shm_key,shm_num,shm_flg))0){perror(shareMemoryseterror);exit(EXIT_FAILURE);}//shmat将由shm_id标识的共享内存附加给指针shm_bufif((shm_buf=(char*)shmat(shm_id,0,0))(char*)0){perror(getshareMemoryerror);exit(EXIT_FAILURE);}for(i=0;ishm_num;i++)shm_buf[i]=0;//初始为0}//shm_key标识的共享内存区已经建立,将由shm_id