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

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

طُرحت هذه المشكلة في الأصل عام 1965 من قبل رائد علوم الحاسوب إدسكار ديكسترا ، ^{[ 2 ]} الذي استخدمها لتوضيح أن الإشارات العامة غالباً ما تكون زائدة عن الحاجة. ^{[ 3 ]}

تخيل صالون حلاقة افتراضيًا به حلاق واحد، وكرسي حلاقة واحد، وغرفة انتظار بها n كرسي ( قد يكون n يساوي صفرًا) للزبائن المنتظرين. تنطبق القواعد التالية: ^{[ 4 ]}

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

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

تتضمن مشكلة الحلاقين النائمين المتعددين تعقيدًا إضافيًا يتمثل في تنسيق عمل العديد من الحلاقين بين الزبائن المنتظرين. ^{[ 6 ]}

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

# أول اثنين عبارة عن مؤشرات تبادلية (القيم الممكنة 0 أو 1 فقط) Semaphore barberReady = 0 Semaphore accessWRSeats = 1 # إذا كانت القيمة 1، يمكن زيادة أو إنقاص عدد المقاعد في غرفة الانتظار Semaphore custReady = 0 # عدد العملاء الموجودين حاليًا في غرفة الانتظار، والمستعدين للخدمة int numberOfFreeWRSeats = N # إجمالي عدد المقاعد في غرفة الانتظاردالة Barber (): بينما صحيح : # تشغيل في حلقة لا نهائية. انتظر ( عميل جاهز ) # حاول الحصول على عميل - إذا لم يكن هناك أي عميل متاح، فانتقل إلى وضع السكون. انتظر ( الوصول إلى مقاعد غرفة الانتظار ) # استيقظ - حاول الوصول لتعديل عدد المقاعد المتاحة، وإلا فانتقل إلى وضع السكون. عدد مقاعد غرفة الانتظار الحرة += 1 # أصبح كرسي واحد في غرفة الانتظار شاغرًا. إشارة ( حلاق جاهز ) # أنا جاهز للقص. إشارة ( الوصول إلى مقاعد غرفة الانتظار ) # لم أعد بحاجة إلى قفل الكراسي. # (قص الشعر هنا.)دالة العميل (): بينما صحيح : # تشغيل في حلقة لا نهائية لمحاكاة عدة عملاء. انتظر ( الوصول إلى كراسي غرفة الانتظار ) # حاول الوصول إلى كراسي غرفة الانتظار. إذا كان عدد كراسي غرفة الانتظار المتاحة > 0 : # إذا كانت هناك أي مقاعد متاحة: عدد كراسي غرفة الانتظار المتاحة -= 1 # اجلس على كرسي إشارة ( العميل جاهز ) # إخطار الحلاق، الذي ينتظر حتى يكون هناك عميل إشارة ( الوصول إلى كراسي غرفة الانتظار ) # لا حاجة لقفل الكراسي بعد الآن انتظر ( الحلاق جاهز ) # انتظر حتى يكون الحلاق جاهزًا # (قص شعرك هنا.) وإلا : # وإلا، فلا توجد مقاعد متاحة؛ حظًا سيئًا -- إشارة ( الوصول إلى كراسي غرفة الانتظار ) # لكن لا تنسَ تحرير قفل المقاعد! # (اغادر بدون قص شعرك.)

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