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

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

## عرض المشكلة

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

## حلول

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

### التنفيذ

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

## أنظر أيضا

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

## مراجع

* ↑ John H. Reynolds (ديسمبر 2002). "Linda Arouses a Sleeping Barber" (PDF). Proceedings of the Winter Simulation Conference. San Diego, CA: IEEE. DOI:10.1109/WSC.2002.1166471. مؤرشف من الأصل (PDF) في 2022-01-08. اطلع عليه بتاريخ 2022-01-08.
* ↑ Allen B. Downey (2016). The Little Book of Semaphores (PDF) (ط. 2.2.1). Green Tea Press. ص. 121. مؤرشف من الأصل (PDF) في 2021-10-23. اطلع عليه بتاريخ 2022-01-08.
* 1 2 Edsger W. Dijkstra (1965). Technical Report EWD-123: Cooperating Sequential Processes. Eindhoven, The Netherlands: Eindhoven University of Technology. ص. 38. مؤرشف من الأصل في 2022-01-01. اطلع عليه بتاريخ 2022-01-08.
* ↑ Andrew S. Tanenbaum (2001). Modern Operating Systems (PDF) (ط. 2nd). Upper Saddle River, NJ: Pearson. ص. 129. ISBN:9780130313584. مؤرشف من الأصل (PDF) في 2022-01-08. اطلع عليه بتاريخ 2022-01-08.
* ↑ Cooperating Sequential processes by E.W. Dijkstra. Technical Report EWD-123, 1965, Eindhoven University of Technology, The Netherlands. نسخة محفوظة 1 يناير 2022 على موقع واي باك مشين.
* ↑ Fukuda، Munehiro. "Program 2: The Sleeping-Barbers Problem" (PDF). University of Washington. مؤرشف من الأصل (PDF) في 2022-01-08. اطلع عليه بتاريخ 2022-01-08.
* بوابة علم الحاسوب
* بوابة تقانة المعلومات
* بوابة تقانة