c - 使用信号量在 Sleeping Barber 中打印

Question

我正在尝试使用 pthreads 和信号量在 C 中实现 sleep 理发师问题的解决方案，只有部分要求是每个操作发生时都必须打印出来，例如:

• 理发师睡着了
• 顾客叫醒了理发师
• 顾客正在等待理发师
• 客户因没有空位而离开(仅在稍后随机一段时间返回)
• 顾客正在理发
• 顾客已离开商店

我已经在这个问题上工作了一段时间，只是遇到了各种死锁或语句打印无序。

classical solution因为这个问题在这里并不完全适用，因为它会导致每次都打印语句(例如“理发师睡着了”，然后是“顾客叫醒了理发师”)，或者因此打印的语句不按顺序上下文切换(这可能是也可能不是真正的问题)。

我当前的解决方案(伪代码)是这样的:

int chairs       = N # available chairs
bool is_sleeping = false
bool is_cutting  = false 
bool finished    = false # All customers taken care of (Changed in main)

# Semaphores for read/write access
semaphore rw_chairs   = 1
semaphore rw_sleeping = 1
semaphore rw_cutting  = 1

semaphore barber_ready = 0 # Barber ready to cut hair
semaphore sleeping     = 0 # Barber is sleeping
semaphore cutting      = 0 # Barber cutting a customer's hair

def Barber():
   while not finished:
      wait(rw_chairs)
      wait(rw_sleeping)
      # If no chairs are being used
      if chairs == N:
         is_sleeping = true
         print("Barber is sleeping!")
         signal(rw_chairs)     # Allow others to read/write
         signal(rw_sleeping)
         wait(sleeping)        # Wait for customer to wake him up
         signal(barber_ready)  # Allow customers into the chair
         print("Barber woke up!")
      else:
         signal(rw_signal)
         chairs += 1
         signal(barber_ready)
         signal(rw_chairs)
      # If the barber isn't done for the day, help the customer
      if not finished:
         print("Helping a customer")
         # Wait a random amount of time
         print("Finished helping a customer")
         signal(cutting) # Let the customer leave after the hair cut
      else:
         print("Barber is done for the day!")

def Customer():
   bool helped = false
   while not helped:
      wait(rw_chairs)
      wait(rw_cutting)
      if chairs == N and not is_cutting: # If the barber is free
         wait(rw_sleeping)
         if is_sleeping:
            signal(sleeping) # Wake the barber up
            is_sleeping = false
            print("Customer has woken the barber up")
         signal(rw_sleeping)
         is_cutting = true
         signal(rw_chairs)
         signal(rw_cutting)
         wait(barber_ready) # Wait for the barber to be ready
         wait(cutting)      # Wait for him to finish cutting hair
         print("Customer has had his hair cut")
         helped = true
      else if chairs > 0:
         chairs -= 1
         print("Customer is waiting in a chair")
         signal(rw_chairs)
         signal(rw_cutting)
         wait(barber_ready)
         wait(cutting)
         print("Customer has had his hair cut")
         helped = true
      else:
         signal(rw_chairs)
         signal(rw_office)
         print("All chairs taken, will return later")
         # Wait a random amount of time 
   print("Customer is leaving the barbershop")

当这没有陷入僵局时，使用 3 张椅子我会得到以下输出:

Barber has fallen asleep
Customer is waiting in a chair
Customer is waiting in a chair
Customer is waiting in a chair
All chairs used, will return later
All chairs used, will return later
... (repeat the above line infinitely)

我很清楚，理发师没有正确地让顾客进来——但即使如此，我也觉得我的结构完全错误。我认为我处理问题的方法是错误的，并且可能使问题过于复杂化。

如果这里有人对如何构建可行的解决方案有任何建议，或者对重组我当前的解决方案有任何建议，我们将不胜感激。或者，如果我走在正确的轨道上，可能会朝着正确的方向插入。

谢谢!

Answer 1

我设法让它工作。

由于我之前没有在这里的任何地方看到过这个问题，所以我会回答我自己的问题，以防其他人像我一样遇到这个问题寻求帮助。

我原来的方法并没有完全失败，但是需要进行一些小的调整才能使其正常工作。我没有使用 6 个信号量，而是只使用了 5 个:2 个控制读/写访问，3 个​​控制排队/ sleep 。

伪代码如下:

# Constants
SLEEPING = 0
AWAKE    = 1
BUSY     = 2

# Read/Write semaphores
Semaphore rw_chairs = 1      # Access to chairs
Semaphore rw_status = 1      # Access to barber status

# Access semaphores
Semaphore waiting   = 0      # Line for waiting customers
Semaphore cutting   = 0      # Semaphore to hold customer while getting hair cut
Semaphore sleeping  = 0      # Semaphore for barber to sleep

int   chairs        = n      # Available chairs to sit in
int   status        = AWAKE  # Barber Status (could also be a boolean for sleeping)
bool  finished      = false  # Is the program finished

def Barber():
   while not finished:
      wait(rw_chairs)
      wait(rw_status)
      # If there is nobody waiting and the barber isn't asleep
      if chairs == n and status != SLEEPING:
         barber = SLEEPING;
         print("Barber went to sleep!")
         signal(rw_status)
         signal(rw_chairs)
         wait(sleeping)    # Go to sleep
         print("Barber woke up!")
         signal(waiting)   # Let the next customer in
      else:
         signal(waiting)   # Let the next customer in
         chairs += 1       # Free the chair they sat in
         barber = BUSY     # Set the barber to busy
         signal(rw_status)
         signal(rw_chairs)

      # Once it gets here, the barber is awake and must help someone
      if not finished:
         print("Barber is cutting a customer's hair")
         # Cut the customer's hair
         print("Barber finished cutting the customer's hair")
         signal(cutting) # Release the customer so they can leave

    # barber's finally done
    print("Barber finished work for the day");

def Customer():
    bool helped = false

    print("Customer arrived at the Barber Shop!")
    while not helped:
       wait(rw_chairs)
       wait(rw_status)
       if chairs == n and status == SLEEPING:
          status = AWAKE
          print("Customer woke up the barber")
          signal(rw_status)
          signal(sleeping)  # Wake up the barber
          wait(waiting)     # Be the next customer to get helped (happens immediately)
          signal(rw_chairs)

          helped = true; // This customer is being helped
       else:
          signal(rw_status)
          if chairs > 0:
             chairs -= 1  # Claim a chair
             signal(rw_chairs)
             print("Customer sitting in a chair")
             wait(waiting) # Wait for the barber

             helped = true; // This customer is being helped
          else:
             print("Barber Shop is busy, will return later")
             signal(rw_chairs)
             # Wait a while before returning
       # If the customer is being helped
       if helped:
          print("Customer is getting a hair cut")
          wait(cutting)
          print("Customer is finished getting a haircut")

在main中，一旦所有客户线程都被加入，它就会将finished设置为true，并唤醒(可能)休眠的Barber来完成程序。

通过这种方法，理发师和顾客都首先读取椅子，然后读取状态，并以相反的顺序释放它(防止循环等待造成任何死锁)。