使用信號量在睡眠理髮師中打印

Question

我試圖在C中使用pthread和信號量來實現睡眠理髮師問題的解決方案，只有部分要求是每個動作都必須在發生時打印出來，例如：

• 理髮睡着
• 客戶已意識到理髮了
• 客戶正在等待理髮
• 客戶離開是因爲沒有座位是可用的（後來才返回的隨機時間段）
• 客戶得到他的頭髮剪
• 客戶已經離開了商店

我在這個問題一點點在努力，只拿到打印出來的無序各種死鎖或有聲明。

該問題的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

我設法讓它工作。

鑑於我之前沒有看到這個問題，我會回答我自己的問題，以防其他人遇到此問題時尋求我的幫助。

我原來的方法並沒有完全關閉，但是需要做一些小的調整才能使它正常工作。我只用5：2來控制讀/寫訪問，而用3來控制排隊/休眠，而不是使用6個信號量。

的僞代碼如下：

# 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") 

在主，一旦所有的客戶線程已經加入了，它設置完成後爲真，並喚醒（可能）睡覺理髮完成計劃。

通過這種方法，理髮師和客戶都先閱讀椅子，然後按照相反的順序發佈（防止循環等待的任何死鎖）。