مشكلة الحلاق النائم

في علوم الحاسوب، تعتبر مشكلة الحلاق النائم مشكلة كلاسيكية في الاتصال والتزامن بين العمليات التي توضح التعقيدات التي تنشأ عندما تكون هناك عمليات متعددة لنظام التشغيل.

تم اقتراح المشكلة في الأصل في عام 1965 من قبل رائد علوم الحاسوب أيدسكر دايكسترا، الذي استخدمها لتوضيح أن الإشارات العامة غالبًا ما تكون غير ضرورية.

عرض المشكلة

تخيل صالون حلاقة افتراضيًا به حلاق واحد وكرسي حلاقة وغرفة انتظار بها عدد من الكراسي (قد تكون 0) للعملاء المنتظرين. تطبق القواعد التالية:

• إذا لم يكن هناك زبائن، ينام الحلاق على الكرسي
• يجب على الزبون إيقاظ الحلاق إذا كان نائماً
• إذا وصل أحد العملاء أثناء عمل الحلاق، يغادر العميل إذا كانت جميع الكراسي مشغولة ويجلس على كرسي فارغ إذا كان متاحًا
• عندما ينتهي الحلاق من قصة شعره ، يتفقد غرفة الانتظار ليرى ما إذا كان هناك أي زبائن ينتظرون وينام إذا لم يكن هناك أي منهم

هناك نوعان من التعقيدات الرئيسية. أولاً، هناك خطر من حدوث حالة سباق، حيث ينام الحلاق أثناء انتظار العميل للحلاق ليقوم بقص شعره، بسبب جميع الإجراءات - التحقق من غرفة الانتظار، ودخول المتجر، وأخذ كرسي غرفة الانتظار —خذ قدرًا معينًا من الوقت. على وجه التحديد، قد يصل العميل ليجد الحلاق الذي يقص الشعر فيعود إلى غرفة الانتظار ليجلس، ولكن أثناء عودته إلى غرفة الانتظار، ينهي الحلاق قصة شعره ويذهب إلى غرفة الانتظار، التي يجدها فارغة (لأن يمشي العميل ببطء أو يذهب إلى الحمام) وبالتالي ينام على كرسي الحلاقة. ثانيًا، قد تحدث مشكلة أخرى عندما يصل عميلان في نفس الوقت عندما يكون هناك مقعد واحد فارغ في غرفة الانتظار ويحاول كلاهما الجلوس على كرسي واحد؛ لن يتمكن من الجلوس إلا أول شخص يصل إلى الكرسي.

مشكلة تعدد الحلاقين النائمين لها تعقيد إضافي يتمثل في تنسيق العديد من الحلاقين بين العملاء المنتظرين.

حلول

هناك العديد من الحلول الممكنة، لكن جميع الحلول تتطلب كائن المزامنة (mutex)، والذي يضمن أن واحدًا فقط من المشاركين يمكنه تغيير الحالة مرة واحدة. يجب أن يكتسب الحلاق كائن المزامنة الخاص بحالة الغرفة قبل التحقق من العملاء وتحريره عند بدء النوم أو قص الشعر؛ يجب على العميل الحصول عليها قبل دخولها إلى المحل والإفراج عنها بمجرد جلوسهم في غرفة الانتظار أو كرسي الحلاقة، وكذلك عند مغادرتهم المحل لعدم توفر مقاعد. هذا من شأنه أن يعالج كل من المشاكل المذكورة أعلاه. مطلوب أيضًا عدد من السيمافورات للإشارة إلى حالة النظام. على سبيل المثال، قد يقوم المرء بتخزين عدد الأشخاص في غرفة الانتظار.

التنفيذ

يضمن الرمز الكاذب (pseudocode) التالي التزامن بين الحلاق والعميل وهو خالي من الاستعصاء، ولكنه قد يؤدي إلى العميل من التضور جوعا. يمكن حل مشكلة التضور جوعا من خلال طابور الانتظار الوارد أولاً يصرف أولاً (FIFO). سيوفر السيمافور وظيفتين: wait() وsignal ()، والتي من حيث أكواد لغة C تتوافق مع P () و V ()، على التوالي.

# The first two are mutexes (only 0 or 1 possible)
Semaphore barberReady = 0
Semaphore accessWRSeats = 1 # if 1, the number 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.)

أنظر أيضا

• مشكلة الفلاسفة تناول الطعام
• مشكلة مدخني السجائر
• مشكلة المنتجين والمستهلكين
• مشكلة القُراء والكُتاب