理发师理发问题

理发师问题描述：

（1）理发店里有一位理发师、一把理发椅和n把供等候理发的顾客坐的椅子
（2）如果没有顾客，理发师便在理发椅上睡觉
（3）一个顾客到来时，它必须叫醒理发师
（4）如果理发师正在理发时又有顾客来到，则如果有空椅子可坐，就坐下来等待，否则就离开

问题分析：

1、对于理发师问题而言，是生产者-消费者（有界缓冲区）模型的一种。其中理发师和顾客之间涉及到进程之间的同步问题，理发师是生产者，顾客是消费者，生产者生产的速度（理发师理发的速度），和消费者消费的速度（顾客来到理发店的时间），这两者肯定是不同的。那么，题目中就涉及到了一个有界缓冲区，即有N把顾客可以坐着等候理发师的椅子。如果顾客来的太快了，就可以先坐在椅子上等候一下理发师，但是如果椅子坐满了，这时候顾客就直接走，不理发了。这个N是有界缓冲区的大小，如果缓冲区放不下消费者了，消费者就不进行消费。
2、同样的，在生产者-消费者（有界缓冲区）模型中，还存在进程之间的互斥，比如多个消费者同时访问缓冲区，那么肯定会改变缓冲区的状态，缓冲区就是临界资源，多个消费者不能同时去改变缓冲区的状态。在这个问题上，就相当于执行顾客任务的进程，就必须有互斥的操作，同样的，理发师改变缓冲区状态的操作也需要互斥。这个问题中，缓冲区的状态，就是还剩多少个在等待的顾客，顾客来一个，肯定等待理发的顾客数目就+1，理发师理一次发，等待理发的顾客数目就-1。
我们先确定初始状态，即：

  1. semaphore barbers = 0;
  2. semaphore customers = 0;

顾客之间被理发的时候，也需要一个互斥量：

  1. semaphore mutex = 1;

初始化有界缓冲区的大小是N，即

  1. #define CHAIRS 5

另外，我们还需要一个变量来记录目前缓冲区的大小是多少，看现在正在等待的顾客数量有没有超过缓冲区的大小，如果超过了，顾客就之间转身走了。

  1. int waiting = 0;

以上，初始化的操作已经完成了。
然后，考虑理发师进程需要执行的任务，首先理发师是不断进行理发操作的，只有一个生产者，所以肯定对任务有while(1)让它不断执行的操作。
在单次任务中，理发师先等待顾客，如果顾客没有来，理发师就在睡觉。

  1. P(consumers);

然后，如果等到了一个顾客来了，理发师就要更新缓冲区状态了，把正在等待理发的顾客数目-1，先进行加锁互斥。

  1. P(mutex);
  2. waiting = waiting - 1;

然后理发师睡起来了，准备开始理发了。

  1. V(barber);

因为理发操作，所需花费的时间是很长的，这里不能放在临界区去执行。理发师理发前，先解锁，离开临界区。

  1. V(mutex)
  2. cut_hair();

因此可得理发师的执行：

  1. void barber(void)
  2. {
  3.     while (TRUE) {
  4.         P(customers);      //若无顾客,理发师睡眠 
  5.         P(mutex);          //进程互斥,要求顾客等候
  6.         waiting = waiting − 1; //等候顾客数少一个
  7.         V(barbers);          //理发师去为一个顾客理发
  8.         V(mutex);            //开放临界区
  9.         cut_hair();            //正在理发（非临界区操作）    
  10.     }
  11. }

同样，再考虑顾客的任务，对于顾客来说，每次来的一个顾客就是一个单独的任务。
首先，顾客来了，要判断现在还有没有位置可以坐下，如果没有，就直接走了。对于waiting < CHAIRS的判断必须在临界区内进行判断，每次只能有一个顾客。如果出现10个顾客同时判断，这时候都是waiting < CHAIRS，那这10个顾客都能坐在了，但实际座位只有5个

  1. P(mutex)
  2. if(waiting < CHAIRS)
  3. {
  5. }
  6. else
  7. {
  8.     V(mutex);
  9.     cout << "现在没有位置，顾客转身就走了" << endl;
  10. }

然后，每个顾客来之后，如果发现现在还有位置坐，就先坐下来，然后正在等待的顾客数量+1，并且告诉理发师，现在有顾客来了，唤醒理发师，然后就阻塞在顾客等待理发理发的队列上，等待理发师理发。

  1. P(mutex)
  2. if(waiting < CHAIRS)
  3. {
  4.     waiting = waiting+1;    // 等候顾客数加1
  5.     V(customers);           //必要的话唤醒理发师
  6.     V(mutex);               //开放临界区
  7.     P(barbers);             //理发师在忙，顾客等待
  8.     get-haircut( );         //一个顾客坐下等候服务
  9. }
  10. else
  11. {
  12.     V(mutex);
  13.     cout << "现在没有位置，顾客转身就走了" << endl;
  14. }
  1. #define CHAIRS 5               /* # chairs for waiting customers */
  2. typedef int semaphore;         /* use your imagination */
  3. semaphore customers = 0;       /* # of customers waiting for service */
  4. semaphore barbers = 0;         /* # of barbers waiting for customers */
  5. semaphore mutex = 1;           /* for mutual exclusion */
  6. int waiting = 0;               /* customers are waiting (not being cut) */
  8. void barber(void)
  9. {
  10.     white (TRUE) {
  11.         down(&customers);      /* go to sleep if # of customers is 0 */
  12.         down(&mutex);          /* acquire access to 'waiting' */
  13.         waiting = waiting − 1; /* decrement count of waiting customers */
  14.         up(&barbers);          /* one barber is now ready to cut hair */
  15.         up(&mutex);            /* release 'waiting' */
  16.         cut_hair();            /* cut hair (outside critical region) */
  17.     }
  18. }
  20. void customer(void)
  21. {
  22.     down(&mutex);              /* enter critical region */
  23.     if (waiting < CHAIRS) {    /* if there are no free chairs, leave */
  24.         waiting = waiting + 1; /* increment count of waiting customers */
  25.         up(&customers);        /* wake up barber if necessary */
  26.         up(&mutex);            /* release access to 'waiting' */
  27.         down(&barbers);        /* go to sleep if # of free barbers is 0 */
  28.         get_haircut();         /* be seated and be serviced */
  29.     } else {
  30.         up(&mutex);            /* shop is full; do not wait */
  31.     }
  32. }