D&C

今天做操作系统作业碰到的问题，一时想不出怎么做，后来Google了一下发现是个经典问题。
=========================================================================
以下英文内容转载自：http://www.answers.com/topic/sleeping-barber-problem
本人的理解继续往下看。
In computer science, the sleeping barber problem is a classic inter-process communication and synchronization problem between multiple operating system processes. The problem is analogous to that of keeping a barber working when there are customers, resting when there are none and doing so in an orderly manner.
The analogy is based upon a hypothetical barber shop with one barber. The barber has one barber chair and a waiting room with a number of chairs in it. When the barber finishes cutting a customer’s hair, he dismisses the customer and then goes to the waiting room to see if there are other customers waiting. If there are, he brings one of them back to the chair and cuts his hair. If there are no other customers waiting, he returns to his chair and sleeps in it.
Each customer, when he arrives, looks to see what the barber is doing. If the barber is sleeping, then the customer wakes him up and sits in the chair. If the barber is cutting hair, then the customer goes to the waiting room. If there is a free chair in the waiting room, the customer sits in it and waits his turn. If there is no free chair, then the customer leaves. Based on a naïve analysis, the above description should ensure that the shop functions correctly, with the barber cutting the hair of anyone who arrives until there are no more customers, and then sleeping until the next customer arrives. In practice, there are a number of problems that can occur that are illustrative of general scheduling problems.
The problems are all related to the fact that the actions by both the barber and the customer (checking the waiting room, entering the shop, taking a waiting room chair, etc.) all take an unknown amount of time. For example, a customer may arrive and observe that the barber is cutting hair, so he goes to the waiting room. While he is on his way, the barber finishes the haircut he is doing and goes to check the waiting room. Since there is no one there (the customer not having arrived yet), he goes back to his chair and sleeps. The barber is now waiting for a customer and the customer is waiting for the barber. In another example, two customers may arrive at the same time when there happens to be a single seat in the waiting room. They observe that the barber is cutting hair, go to the waiting room, and both attempt to occupy the single chair.
The Sleeping Barber Problem is often attributed to Edsger Dijkstra (1965), one of the pioneers in computer science.
Many possible solutions are available. The key element of each is a mutex, which ensures that only one of the participants can change state at once. The barber must acquire this mutex exclusion before checking for customers and release it when he begins either to sleep or cut hair. A customer must acquire it before entering the shop and release it once he is sitting in either a waiting room chair or the barber chair. This eliminates both of the problems mentioned in the previous section. A number of semaphores are also required to indicate the state of the system. For example, one might store the number of people in the waiting room.
A multiple sleeping barbers problem has the additional complexity of coordinating several barbers among the waiting customers.

Implementation

• The following pseudocode guarantees synchronization between barber and customer and is deadlock free, but may lead to starvation of a customer. The functions wait() and signal() are functions provided by the semaphores.

# The first two are mutexes (only 0 or 1 possible)
Semaphore barberReady = 0
Semaphore accessWRSeats = 1     # if 1, the # of seats in the waiting room can be incremented or decremented
Semaphore custReady = 0         # the number of customers currently in the waiting room, ready to be served
int numberOfFreeWRSeats = N     # total number of seats in the waiting room
def Barber():
  while true:                   # Run in an infinite loop.
    wait(custReady)             # Try to acquire a customer - if none is available, go to sleep.
    wait(accessWRSeats)         # Awake - try to get access to modify # of available seats, otherwise sleep.
    numberOfFreeWRSeats += 1    # One waiting room chair becomes free.
    signal(barberReady)         # I am ready to cut.
    signal(accessWRSeats)       # Don't need the lock on the chairs anymore.
    # (Cut hair here.)
def Customer():
  while true:                   # Run in an infinite loop to simulate multiple customers.
    wait(accessWRSeats)         # Try to get access to the waiting room chairs.
    if numberOfFreeWRSeats > 0: # If there are any free seats:
      numberOfFreeWRSeats -= 1  #   sit down in a chair
      signal(custReady)         #   notify the barber, who's waiting until there is a customer
      signal(accessWRSeats)     #   don't need to lock the chairs anymore
      wait(barberReady)         #   wait until the barber is ready
      # (Have hair cut here.)
    else:                       # otherwise, there are no free seats; tough luck --
      signal(accessWRSeats)     #   but don't forget to release the lock on the seats!
      # (Leave without a haircut.)

============================

本人观点：
其中需要共享的数据应该只有可用的座椅数目(numberOfFreeWRSeats)，但是需要改动这个座椅数目的过程比较繁杂…原本以为N是用作信号量里面的，但是这个解决方案来看是把他作为额外的变量。
为什么N不能做信号量？后来想了一下..这个东西是共享的资源…明显不能拿来做信号量的吧。
文中3个信号量

Semaphore barberReady = 0
Semaphore accessWRSeats = 1     # if 1, the # of seats in the waiting room can be incremented or decremented
Semaphore custReady = 0         # the number of customers currently in the waiting room, ready to be served

其中barberReady是理发师就绪的信号量，barber讲客人请入理发室后，signal一下，然后示意客户可以开始理发了，客户那边wait这个信号量，等到了就开始理发过程。这个是一个同步的关系，因为肯定是要理发师先准备好，然后客人才可以开始理发，这两个动作有顺序要求，所以信号量初值设置成0.
第二个accessWRSeats是用来锁座椅数目改变的，锁住（=0）的时候，说明waitingroom内有人员变动中，要阻塞其他人对人员变动的尝试。显然这是一个互斥量（mutex），当客人进入理发室准备理发时、或者理发店外有人进入时，都要改变numberOfFreeWRSeats这个量，这种操作显然是独占的，同时只能有一方来修改这个值，所以引入此信号量协调。
第三个嘛..客人就绪的信号量，主要原因是barber空闲下来的时候需要睡大觉。这个与第一个信号量一样，是一个同步的问题。即客人先要准备好了，才能把理发师唤醒做事情，不然就别吵到他。
三个信号量理解了，后面的过程也就一目了然了。不知道我说的对不对…
这个问题应该有另一(或多)种解法，另一种解法是指会导致barber的starvation的解法，或者是权衡两者折中的办法，这个没有多想过。