مسئله آرایشگر خواب‌آلود

در علوم رایانه، مسئلهٔ آرایشگر خواب‌آلود یک مسئلهٔ همگام‌سازی و ارتباط داخل فرایندیِ کلاسیک بین چند فرایند سیستم عامل است. مسئلهٔ مشابه حالتی است که آرایشگر به‌کار مشغول می‌شود زمانی که مشتری باشد، زمانی که کسی نباشد استراحت می‌کند و تکرار این امر به شیوه‌ای منظم.

مسئله

قیاس بر پایهٔ یک آرایشگاه فرضی با یک آرایشگر است. آرایشگر یک صندلی آرایش دارد و یک اتاق انتظار با تعدادی صندلی در آن. وقتی که آرایشگر کوتاه کردن موی یک مشتری را تمام می‌کند، او مشتری را مرخص کرده و سپس به اتاق انتظار می‌رود تا ببیند که آیا مشتری منتظر دیگری هست یا نه. اگر بود، او یکی از آنها را به صندلی می‌برد و موها را کوتاه می‌کند. اگر مشتری منتظر دیگری نباشد، به صندلی خود برگشته و روی آن می‌خوابد. هر مشتری، زمانی که می‌رسد، نگاه می‌کند که آرایشگر چه‌کار می‌کند. اگر آرایشگر خواب باشد، پس مشتری او را بیدار کرده و روی صندلی می‌نشیند. اگر آرایشگر در حال کوتاه کردن مو باشد، مشتری به اتاق انتظار می‌رود. اگر صندلی خالی در اتاق انتظار باشد، مشتری روی آن نشسته و منتظر می‌شود تا نوبتش شود. اگر صندلی خالی نباشد، مشتری آنجا را ترک می‌کند. بر اساس یک تحلیل ساده، توصیف بالا باید تضمین کند که مغازه به درستی عمل می‌کند، با کوتاه کردن موی هر کسی که می‌رسد توسط آرایشگر تا وقتی که مشتری دیگری نباشد، و سپس خوابیدن تا زمانی که مشتری بعدی برسد. در عمل، امکان رخ دادن تعدادی مشکل وجود دارد که بیانگر مشکلات عمومی زمان‌بندی هستند.

تمامی مشکلات مرتبط با این واقعیت هستند که هم اعمال آرایشگر و هم مشتری (چک کردن اتاق انتظار، واردشدن به مغازه، انتخاب یک صندلی از اتاق انتظار و ...)، همگی زمان نامعلومی به‌طول می‌انجامند. به‌عنوان مثال، ممکن است مشتری وارد شود و بیند که آرایشگر در حال کوتاه کردن مو است، پس به اتاق انتظار می‌رود. زمانی که در این مسیر قرار دارد، آرایشگر کار اصلاحی که در حال انجام بود را تمام می‌کند و می‌رود که اتاق انتظار را بررسی کند. چون کسی در آنجا وجود ندارد، (مشتری هنوز به آنجا نرسیده)، به صندلی خود برگشته و می‌خوابد. آرایشگر الآن منتظر یک مشتری و مشتری منتظر آرایشگر است. در یک مثال دیگر، دو مشتری ممکن است همزمان برسند، زمانی که یک صندلی خالی در اتاق انتظار وجود دارد. آنها مشاهده می‌کنند که آرایشگر در حال کوتاه کردن مو است، به اتاق انتظار می‌روند و هر دو قصد دارند که تک صندلی را اشغال کنند.

مسئلهٔ آرایشگر خوابیده معمولاً به ادسخر دیسترا نسبت داده می‌شود، یکی از پیشگامان علوم رایانه.

راه حل

تعداد زیادی راه حل ممکن وجود دارد. عنصر اصلی هر کدام، یک قفلِ mutex (انحصار متقابل) است، که ضمانت می‌کند فقط یکی از سهم داران در لحظه می‌تواند وضعیت را تغییر دهد. آرایشگر بایستی این قفل محرومیت را قبل از بررسی کردن مشتری‌ها بدست آورد و آن را زمانی که می‌خواهد بخوابد یا مو کوتاه کند، آزاد کند. یک مشتری باید آن را قبل از وارد شدن به مغازه بدست آورد و زمانی که می‌خواهد روی صندلی بنشیند، چه صندلی اتاق انتظار و چه صندلی آرایگشر، آن را رها کند. در این صورت هر دو مشکل اشاره شده در قسمت قبل از بین خواهد رفت. تعدادی semaphore (نشانبر) نیز لازم هستند تا وضعیت سیستم را نشان دهند. به عنوان مثال، یکی از آنها باید تعداد مشتری‌های داخل اتاق انتظار را ذخیره کند.

یک مسئلهٔ چند آرایشگر خوابیده دارای پیچیدگی‌های بیشتری برای هماهنگی چند آرایشگر در بین مشتریان منتظر است.

پیاده‌سازی

شبه کد زیر همگام سازی بین آرایشگر و مشتری را ضمانت کرده و بدون بن‌بست است، اما ممکن است منجر به قحطی یک مشتری شود. توابع ()wait و ()signal توابعی هستند که توسط سمافور(نشانبر)ها تأمین می‌شوند.

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

منابع

• Modern Operating Systems (2nd Edition) by اندرو تننبام (ISBN 0-13-031358-0)
• The Little Book of Semaphores by Allen B. Downey, http://greenteapress.com/semaphores
• Cooperating sequential processes by E.W. Dijkstra. Technical Report EWD-123, 1965, Technological University, Eindhoven, The Netherlands.