用信号量解决理发店问题

进程同步实验张咪软件四班一、实验目的总结和分析示例实验和独立实验中观察到的调试和运行信息，说明您对与解决非对称性互斥操作的算法有哪些新的理解和认识？为什么会出现进程饥饿现象？本实验的饥饿现象是怎样表现的？怎样解决并发进程间发生的饥饿现象？您对于并发进程间使用消息传递解决进程通信问题有哪些新的理解和认识？根据实验程序、调试过程和结果分析写出实验报告。

二、实验要求理发店问题：假设理发店的理发室中有3个理发椅子和3个理发师，有一个可容纳4个顾客坐等理发的沙发。

此外还有一间等候室，可容纳13位顾客等候进入理发室。

顾客如果发现理发店中顾客已满（超过20人），就不进入理发店。

在理发店内，理发师一旦有空就为坐在沙发上等待时间最长的顾客理发，同时空出的沙发让在等候室中等待时间最长的的顾客就坐。

顾客理完发后，可向任何一位理发师付款。

但理发店只有一本现金登记册，在任一时刻只能记录一个顾客的付款。

理发师在没有顾客的时候就坐在理发椅子上睡眠。

理发师的时间就用在理发、收款、睡眠上。

请利用linux系统提供的IPC进程通信机制实验并实现理发店问题的一个解法。

三、实验环境实验环境均为Linux操作系统，开发工具为gcc和g++。

四、实验思路约束：1．设置一个count变量来对顾客进行计数，该变量将被多个顾客进程互斥地访问并修改，通过一个互斥信号量mutext来实现。

count>20时，就不进入理发店。

7<count<20时，count++，顾客申请等候室，进入等候室等待，用一个room信号量控制。

然后等待申请沙发，用一个sofa信号量控制。

然后申请椅子。

3<count<7时，count++，顾客坐在沙发上等待，等待申请椅子。

count<3时，count++，顾客坐在椅子上等待理发。

2.只有在理发椅空闲时，顾客才能做到理发椅上等待理发师理发，否则顾客便必须等待；只有当理发椅上有顾客时，理发师才可以开始理发，否则他也必须等待。

理发师问题-信号量实现版问题描述：⼀个理发店由⼀个有⼏张椅⼦的等待室和⼀个放有⼀张理发椅的理发室组成。

1．若没有要理发的顾客，则理发师去睡觉；2．若⼀顾客进⼊理发店，理发师正在为别⼈理发，且等待室有空椅⼦，则该顾客就找张椅⼦按顺序坐下；3．若⼀顾客进⼊理发店，理发师在睡觉，则叫醒理发师为该顾客理发；4．若⼀顾客进⼊理发店且所有椅⼦都被占⽤了，则该顾客就离开。

伪码实现：引⼊3个信号量和⼀个控制变量：1)控制变量waiting⽤来记录等候理发的顾客数，初值均为0;2)信号量customers⽤来记录等候理发的顾客数，并⽤作阻塞理发师进程，初值为0;3)信号量barbers⽤来记录正在等候顾客的理发师数，并⽤作阻塞顾客进程，初值为0（刚开始时理发师在睡觉,所以理发师这个资源数⽬为0）;4)信号量mutex⽤于互斥，初值为1.关于p，v操作：P操作可以看做是申请⼀个资源，不管这个资源有没有都将这个资源的数⽬减1，如果现在资源数⽬⼩于0，就阻塞。

v操作就是释放资源，先将这个资源的数⽬加1，如果发现这个资源数⽬⼩于等于0，就会唤醒在阻塞队列上的⼀个进程看看PV原语实现：1顾客信号量 = 02理发师信号量 = 03互斥信号量mutex = 1// 椅⼦是理发师和顾客精进程都可以访问的临界区4int空椅⼦数量 = N //所有的椅⼦数量56理发师（线程/进程）7 While(true){ //持续不断地循环8 P（顾客）//试图为⼀位顾客服务，如果没有他就睡觉（进程阻塞）9 P（互斥信号量）//如果有顾客，这时他被叫醒（理发师进程被唤醒），要修改空椅⼦的数量10空椅⼦数量++ //⼀张椅⼦空了出来11 V（理发师）//现在有⼀个醒着的理发师，理发师准备理发，多个顾客可以竞争理发师互斥量，但是只有⼀个顾客进程可以被唤醒并得到服务12 V（互斥信号量）//释放椅⼦互斥量，使得进店的顾客可以访问椅⼦的数量以决定是否进店等待13/* 理发师在理发 */14｝151617顾客（线程/进程）18while(true)19｛//持续不断地循环20 P（互斥信号量）//想坐到⼀张椅⼦上21if (空椅⼦数量 > 0)22 { //如果还有空着的椅⼦的话23空椅⼦数量-- //顾客坐到⼀张椅⼦上了24 V（顾客）//通知理发师，有⼀位顾客来了25 V（互斥信号量）//顾客已经坐在椅⼦上等待了，访问椅⼦结束，释放互斥量26 P（理发师）//该这位顾客理发了，如果理发师还在忙，那么他就等着（顾客进程阻塞）27/* 竞争到了理发师则该顾客开始理发 */28 }29else30｛//没有空着的椅⼦31 V（互斥信号标）//不要忘记释放被锁定的椅⼦32/* 顾客没有理发就⾛了 */33｝34｝⾸先是信号量的实现版本：1 #include <stdio.h>2 #include <semaphore.h>3 #include <pthread.h>4#define CHAIRS 356//这个计数器才是共享资源7int waiting=0; //控制变量, ⽤来记录等候理发的顾客数89 sem_t customers; //⽤来记录等候理发的顾客数，并⽤作阻塞理发师进程10 sem_t barbers; //⽤来记录正在等候顾客的理发师数，并⽤作阻塞顾客进程11 sem_t mutex; //⽤于线程互斥1213void cut_hair()14 {15 printf("理发ing\n");16 }1718void sleeping()19 {20 printf("sleeping\n");21 }2223void *barber(void *arg)24 {25while(1){26 sem_wait(&customers); //若⽆顾客,理发师睡眠27 sem_wait(&mutex);28 waiting--;29 printf("理发师：等待顾客-1，还剩%d⼈等待 \n", waiting);30 sem_post(&barbers);31 sem_post(&mutex);32 cut_hair(); //理发ing, 这个时候顾客已经独享理发师了，所以不在临界区3334 sem_wait(&mutex);35if(waiting==0){ //没⼈就长眠去呗36 sem_post(&mutex);37break;38 }39 sem_post(&mutex);40 }41 pthread_exit(NULL);42 }4344void get_cut()45 {46 printf("顾客%u: 理发ing\n",(unsigned int)pthread_self());47 }4849void *customer(void *arg)50 {51 sem_wait(&mutex); //互斥52if(waiting < CHAIRS){ //等候的⼈⽐椅⼦少53 waiting++; //等候的⼈+154 sem_post(&customers); //多了⼀个顾客55 sem_post(&mutex);56 sem_wait(&barbers); //如果没有理发师了，那顾客就在椅⼦上等着57 get_cut();58 }59else{60 printf("顾客%u: 没椅⼦了，⾛⼈ \n", (unsigned int)pthread_self());61 sem_post(&mutex);62 }63 sem_post(&mutex); //如果前⾯没有椅⼦了，就直接⾛了64 pthread_exit(NULL);65 }66676869int main(int argc, char const *argv[])70 {71void * retval;72int res=0;73int i;74 sem_init(&customers, 0, 0); //没有顾客75 sem_init(&barbers, 0, 0); //没有理发师，都在睡觉呢76 sem_init(&mutex, 0, 1); //实现互斥7778 pthread_t bar, cus[6];79 res+=pthread_create(&bar, NULL, barber, NULL);80for(i=0; i<6; i++){81 res+=pthread_create(&cus[i], NULL, customer, NULL);82 }83if(res!=0){84 printf("线程创建失败！\n");85 pthread_exit(NULL);86 }87 printf("线程创建成功\n");88 pthread_join(bar,&retval);89for(i=0; i<6; i++){90 pthread_join(cus[i],&retval);91 }92return0;93 }。

（一）图书馆有100个座位，每位进入图书馆的读者要在登记表上登记，退出时要在登记表上注销。

要几个程序？有多少个进程？（答：一个程序；为每个读者设一个进程）（1）当图书馆中没有座位时，后到的读者在图书馆为等待（阻塞）（2）当图书馆中没有座位时，后到的读者不等待，立即回家。

解（1 )设信号量：S=100; MUTEX=1P(S)P(MUTEX)登记V(MUTEX)阅读P(MUTEX)注销V(MUTEX)V(S)解(2)设整型变量COUNT=100; 信号量：MUTEX=1;P(MUTEX);IF (COUNT==0){ V(MUTEX);RETURN;}COUNT=COUNT-1;登记V(MUTEX);阅读P(MUTEX);COUNT=COUNT+1;V(MUTEX);RETURN;（二）有一座东西方向的独木桥；用P,V操作实现：（1）每次只允许一个人过桥；（2）当独木桥上有行人时，同方向的行人可以同时过桥，相反方向的人必须等待。

（3）当独木桥上有自东向西的行人时，同方向的行人可以同时过桥，从西向东的方向，只允许一个人单独过桥。

（此问题和读者与写者问题相同,东向西的为读者，西向东的为写者）。

（1）解设信号量MUTEX=1P (MUTEX)过桥V (MUTEX)(2)解设信号量：MUTEX=1 (东西方互斥)MD=1 (东向西使用计数变量互斥)设整型变量：CD=0 (东向西的已上桥人数) CX=0 (西向东的已上桥人数)从东向西：P (MD)IF (CD=0){P (MUTEX) }CD=CD+1V (MD)过桥P (MD)CD=CD-1IF (CD=0){V (MUTEX) }V (MD)从西向东：P (MX){P (MUTEX) }CX=CX+1V (MX)过桥P (MX)CX=CX-1IF (CX=0){V (MUTEX) }V (MX)(3) 解：从东向西的，和（2）相同；从西向东的和（1）相同。

理发店问题一家理发店由一间有n张沙发的等待室和一把理发椅的理发室组成。

如果没有顾客要理发，理发室就睡觉。

当顾客走进理发店时：（1）若是第一个到达的顾客，则他坐到理发椅上唤醒理发师，开始理发；（2）若不是到达的第一个顾客，而且等待室里所有的沙发都被占用，他便离开理发店；否则，他便找一张沙发坐下等待理发。

理发结束后，顾客必须付费，指导理发师收费并将收据给顾客后，顾客方可离开。

试用信号量机制实现这一同步问题。

（1）设置整型变量count，用于统计占用沙发的顾客数量，初始值为0；（2）设置5个信号量mutex、empty、full、payment、receipt，其中mutex用来实现对count的互斥访问，初始值为1；empty表示理发椅是否空闲，初始值为1；full表示理发椅上是否坐有等待理发的顾客，初始值为0；payment表示顾客等待付费，初始值为0；receipt 表示理发师填写收据，初始值为0.算法描述如下：int count=0;semaphore mutex=1，empty=1，full=0，payment=0，receipt=0;guest(){while(true){wait(mutex);if(count>=n){signal(mutex);离开理发店;}else{count++;signal(mutex);坐在沙发上等待理发;wait(empty); //等待理发椅变空离开沙发，坐到理发椅上;wait(mutex);count--;signal(mutex);signal(full); //唤醒理发师理发;付费;signal(payment); //通知理发师付费wait(receipt); //等待理发师的收据signal(empty); //离开理发椅}}}barber(){while(true){wait(full); //等待顾客把自己唤醒为顾客理发;wait(payment); //等顾客付费收费;signal(receipt); //将收据给顾客}}。

⏹理发师问题：一个理发店由一间等候室W和一间工作室B组成。

顾客可以从外面大街上进入W等候理发。

两个房间的入口是并排的，且共享一扇日本式可滑动的推拉门(门总是挡住一个入口)。

顾客在工作室内理完发，可由B 的旁门出去。

W中有N把椅子，顾客必须坐着等候。

理发师可由门上小窗查看W中无人就睡觉，否则开门，并叫一位顾客入内理发。

顾客每进入一位，都拉铃通知理发师。

若把顾客和理发师都视为进程，请用P、V操作写出进程的同步算法。

⏹要求打印：题目中要求描述理发师和顾客的行为，因此需要两类线程barber()和customer ()分别描述理发师和顾客的行为。

其中，理发师有活动有理发和睡觉两个事件；等待和理发二个事件。

店里有固定的椅子数，上面坐着等待的顾客，顾客在到来这个事件时，需判断有没有空闲的椅子，理发师决定要理发或睡觉时，也要判断椅子上有没有顾客。

所以，顾客和理发师之间的关系表现为：（1）理发师和顾客之间同步关系：当理发师睡觉时顾客近来需要唤醒理发师为其理发，当有顾客时理发师为其理发，没有的时候理发师睡觉。

（2）理发师和顾客之间互斥关系：由于每次理发师只能为一个人理发，且可供等侯的椅子有限只有n把，即理发师和椅子是临界资源，所以顾客之间是互斥的关系。

（3）故引入3个信号量和一个控制变量：ⅰ控制变量waiting用来记录等候理发的顾客数，初值为0；ⅱ信号量customers用来记录等候理发的顾客数，并用作阻塞理发师进程，初值为0；ⅲ信号量barbers用来记录正在等候顾客的理发师数，并用作阻塞顾客进程，初值为1；ⅳ信号量mutex用于互斥，初值为1using System;using System.Collections.Generic;using System.Text;using System.Threading;namespace理发师问题2{internal class Program{// Fieldsprivate static Semaphore barbers = new Semaphore(1, 10);private static int chairs;private static int count = 0;private static Semaphore customers = new Semaphore(0, 10);private static int finish = 0;private static Semaphore mtx = new Semaphore(1, 10);private static int waiting = 0;// Methodspublic static void barber(){while (true){customers.WaitOne();mtx.WaitOne();waiting--;barbers.Release();mtx.Release();cuthair();finish++;}}public static void customer(){mtx.WaitOne();count++;Console.WriteLine("叮咚！第{0}个顾客来了", count);if (waiting < chairs){if (waiting > 0){Console.WriteLine("此时有{0}个人在等待理发", waiting);}else{Console.WriteLine("没有人在等待");}waiting++;Console.WriteLine("还有{0}个座位,顾客留下", (chairs - waiting) + 1);mtx.Release();customers.Release();barbers.WaitOne();gethaircut();}else{Console.WriteLine("座位已满，第{0}个顾客离开", count); mtx.Release();}}public static void cuthair(){Console.WriteLine("开始理发！这是理发师的第{0}个顾客.", finish + 1);Thread.Sleep(0x2328);Console.WriteLine("理发完成 !");}public static void gethaircut(){Thread.Sleep(0x238c);Console.WriteLine("第{0}个顾客理发完毕,离开.", finish);}private static void Main(string[] args){string str = string.Empty;Console.WriteLine("请输入椅子的总数目:");chairs = Convert.ToInt32(Console.ReadLine());Console.WriteLine("理发店共有{0}把椅子", chairs);Console.WriteLine("开门接待顾客吗?Y/N");for(string str2 = Console.ReadLine(); (str2 != "Y") && (str2 != "y"); str2 = Console.ReadLine()){Console.WriteLine("********对不起，尚未开门！********");Console.WriteLine("开门接待顾客吗?Y/N");}Console.WriteLine("********营业中，欢迎光临！********");new Thread(new ThreadStart(Program.barber)).Start();while ((str != "y") && (str != "Y")){Random random = new Random(lisecond);Thread.Sleep(random.Next(1, 0x2710));Console.WriteLine("*******************************");new Thread(new ThreadStart(Program.customer)).Start();if ((finish >= 10) && (waiting == 0)){Console.WriteLine("已经为{0}个顾客理发了，要关门下班吗?(Y/N)", finish);str = Console.ReadLine();}if ((str == "Y") || (str == "y")){Console.WriteLine("************暂停营业！**********");break;}}}}}题目: 用多线程同步方法解决睡眠理发师问题（Sleeping-Barber Problem)理发店有一位理发师，一把理发椅和n把用来等候理发的椅子。

课程实验报告题目计算机操作系统理发师问题姓名潘 *学号 2013 ***年级专业2013级*指导教师彭 * 华201*年1*月 30 日一题目假设有个理发店，只有一个理发师和N张可供顾客等待理发的椅子，如果没有顾客，则理发师睡觉，如果有一个顾客进入理发店发现理发师在睡觉，则把他叫醒，试用信号量设计一个协调理发师和顾客的程序。

二 PV操作伪代码C语言的伪代码实现：int waiting=0 ；//等候理发的顾客数int chairs=n；//为顾客准备的椅子数semaphore customers=0, barbers=0,mutex=1;barber() {while(TRUE); //理完一人,还有顾客吗?P(cutomers); //若无顾客,理发师睡眠P(mutex); //进程互斥waiting -= 1;//等候顾客数少一个V(barbers); //理发师去为一个顾客理发V(mutex); //开放临界区cut-hair(); //正在理发}customer() {P(mutex); //进程互斥if(waiting) {waiting += 1; // 等候顾客数加1V(customers); //必要的话唤醒理发师V(mutex); //开放临界区P(barbers); //无理发师, 顾客坐着养神get-haircut( ); //一个顾客坐下等理/}else V(mutex); //人满了,离开}三程序流程图顾客模块：理发师模块：四源程序的实现因为本人对C++的多线程库函数不了解，于是使用JAVA实现理发师问题，假设有5张可供顾客理发的椅子：package com.swxy;import java.util.concurrent.Semaphore;//导入Semaphore，用于控制进程同步互斥的量。

public class BarberShop {static int cnt = 0;// 顾客static int MAX = 5;// 假设5张可供顾客理发的椅子static int busy = 0;static Semaphore mutex= new Semaphore(1);// 临界区互斥访问信号量(二进制信号量)，相当于互斥锁。

【实战3】理发师问题理发店有一位理发师、一把理发椅及三把供等候理发的顾客坐的椅子。

如果没有顾客，理发师就去睡觉。

如果顾客来时所有的椅子都有人，那么顾客就离去。

如果理发师在忙而有空闲的椅子，那么顾客就会坐在其中的一个空闲的椅子上。

如果理发师在睡觉，顾客会唤醒他。

请利用信号量（semaphores），写个程序来协调理发师和顾客进程。

【浙江大学2007】int count=0;//记录理发店里的顾客数量semaphore mutex=1;//用于互斥访问count变量所用的信号量semaphore barber_chair=0;//semaphore wait_chair=3;//顾客等待时可坐的椅子semaphore ready=0;//坐在等候椅子上等待理发的顾客数量Barber(){//理发师进程while(1){wait(ready);//是否有顾客在等待理发，没有则阻塞signal(barber_chair);//请等待时间最长的顾客坐到理发椅上signal(wait_chair);//坐到理发椅上的顾客让出一个等待时可坐的椅子barbering//给顾客理发}}Customer(){//顾客进程i{wait(mutex);if(count>=4){//如果理发店已经有四个顾客了signal(mutex);leave //走人}else{//理发店里顾客不足4个count++;//更新顾客人数signal(mutex);}wait(wait_chair);//先请求坐等待时坐的椅子signal(ready);//告诉理发师又有一位顾客准好了，等待理发wait(barber_chair);//再请求坐理发椅be barberedwait(mutex);count--;//更新店里的顾客人数signal(mutex);}}【练习1】 如图所示，有多个PUT 操作同时向BUFF1放数据，有一个MOVE 操作不断地将BUFF1的数据移到BUFF2，有多个GET 操作不断地从BUFF2中将数据取走。

操作系统--理发师问题正文：一：背景介绍理发师问题是一个经典的并发编程问题，涉及到同时访问共享资源的多个线程之间的同步问题。

该问题的背景可以描述为：在一个理发店里，有一个理发师和一排等待理发的顾客，每个顾客需要等待一段时间才能坐到理发椅上理发。

当有空闲的理发师时，顾客就会坐到椅子上进行理发，否则就需要等待其他顾客理发结束。

该问题需要设计一个合理的算法，保证每个顾客都能够得到理发椅上的理发服务。

二：问题分析1. 线程模型与同步机制考虑到理发师问题涉及到多个顾客同时访问共享资源（理发椅）的情况，可以使用线程模型来解决该问题。

其中，每个顾客作为一个线程，理发椅作为共享资源。

在本问题中，通过使用信号量进行同步机制的设计，保证每个顾客能够按顺序得到理发师的服务。

2. 线程同步的三个要素在解决理发师问题时，需要考虑线程同步的三个要素：互斥、有序性和死锁避免。

互斥可以通过互斥量来实现，保证只有一个线程同时访问共享资源；有序性可以通过信号量来控制，保证顾客能够按照先来后到的顺序进行理发；死锁避免可以通过设置超时等待时间来解决。

三：算法设计1. 初始条件设置首先，需要确定理发师数量、理发椅数量和顾客数量的初始设置。

可以通过命令行参数或配置文件进行设置，以适应不同场景的需求。

2. 创建线程根据顾客数量创建对应数量的线程，并将每个顾客线程的任务设置为等待理发的状态。

同时，创建理发师线程，并将理发师的任务设置为等待顾客的状态。

3. 理发师任务理发师从等待队列中取出一个顾客进行理发，理发时间可以通过随机数。

当该顾客理发结束后，理发师继续从等待队列中取出下一个顾客进行理发。

如果没有顾客在等待，则理发师进入休息状态。

4. 顾客任务顾客到达理发店后，首先判断是否有空闲的理发椅。

如果有空闲的椅子，则顾客坐下并进行理发；否则，顾客需要等待其他顾客离开理发椅后才能进行理发。

5. 同步机制使用互斥量保证理发师和顾客对共享资源的互斥访问。

Linux系统分析实验报告用信号量解决理发师问题061261008 蒋炎岩(一班)1 实验要求理发师问题：理发店理有一位理发师、一把理发椅和5把供等候理发的顾客坐的椅子。

如果没有顾客，理发师便在理发椅上睡觉一个顾客到来时，它必须叫醒理发师，如果理发师正在理发时又有顾客来到，则如果有空椅子可坐，就坐下来等待，否则就离开。

用Linux线程机制和信号量机制解决这个问题，并且：(1)每个顾客进入理发室后，即时显示“Entered”及其线程标识，还同时显示理发室共有几名顾客及其所坐的位置(2)至少有10个顾客，每人理发至少3秒钟。

(3)多个顾客须共享操作函数代码。

2 背景知识2.1 POSIX线程在一个程序中的多个执行路线称之为线程。

Linux在1996年第一次获得线程支持，现在已经有一套完整的与线程有关的函数库调用，大多数以pthread_开头，编译时需要用-lpthread选项进行连接。

我们用函数pthread_create创建一个新线程：#include <pthread.h>int pthread_create(pthread_t *thread, pthread_attr_t *attr,void *(*start_routine)(void *), void *arg);thread参数表示新线程的标识符；attr用于设置线程属性，如不需要设置，可设置为NULL；start_routine标识了线程启动程序的入口，arg为传入的参数。

调用pthread_create 就可以立即创建一个新的执行路线，与原有线程共享所有的主存空间，但拥有独立的堆栈。

2.2 信号量信号量通过一个计数器控制对共享资源的访问。

如果计数器大于0，则访问被允许，如果为0，则访问被禁止。

计数器计算的结果是允许访问共享资源的通行证。

因此，为了访问共享资源，线程必须从信号量得到通行证（P操作），如果该信号量的计数大于0，则此线程获得一个通行证，这将导致信号量的计数递减，否则，此线程将阻塞直到获得一个通行证为止。