مشكلة الحلاق النائم
على سبيل التعريف، في علوم الحاسوب، تعتبر مشكلة الحلاق النائم مشكلة كلاسيكية في الاتصال والتزامن بين العمليات التي توضح التعقيدات التي تنشأ عندما تكون هناك عمليات متعددة لنظام التشغيل. وتعرض الأقسام التالية جوانب أخرى من الموضوع.
وفي هذا الصدد، تم اقتراح المشكلة في الأصل في عام 1965 من قبل رائد علوم الحاسوب أيدسكر دايكسترا، الذي استعملها لتوضيح أن الإشارات العامة غالبًا ما تكون غير ضرورية.
التنفيذ
إضافةً إلى ذلك، يضمن الرمز الكاذب (pseudocode) التالي التزامن بين الحلاق والعميل وهو خالي من الاستعصاء، ولكنه قد يؤدي إلى العميل من التضور جوعا. يمكن حل مشكلة التضور جوعا من خلال طابور الانتظار الوارد أولاً يصرف أولاً (FIFO). سيوفر السيمافور وظيفتين: wait وsignal ، والتي من حيث أكواد لغة C تتوافق مع P و V ، على التوالي.
# The first two are mutexes (only 0 or 1 possible)
Semaphore barberReady = 0
ومن جهة أخرى، wait(accessWRSeats) # Awake - try to get access to modify # of available seats, otherwise sleep.
من جهة ثانية، wait(custReady) # Try to acquire a customer - if none is available, go to sleep.
- int numberOfFreeWRSeats = N # total number of seats in the waiting room
- def Barber:
- while true: # Run in an infinite loop.
ومن ناحية أخرى، Semaphore custReady = 0 # the number of customers currently in the waiting room, ready to be served
كذلك، Semaphore accessWRSeats = 1 # if 1, the number of seats in the waiting room can be incremented or decremented
- 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.)
- أنظر كذلك
- مشكلة الفلاسفة تناول الطعام
- مشكلة مدخني السجائر
- مشكلة المنتجين والمستهلكين
- مشكلة القُراء والكُتاب
عرض المشكلة
وفي السياق ذاته، مشكلة تعدد الحلاقين النائمين لها تعقيد إضافي يتمثل في تنسيق الكثير من الحلاقين بين العملاء المنتظرين.
إضافةً إلى ذلك، هناك نوعان من التعقيدات الرئيسية. أولاً، هناك خطر من حدوث حالة سباق، حيث ينام الحلاق أثناء انتظار العميل للحلاق ليقوم بقص شعره، بسبب جميع الإجراءات - التحقق من غرفة الانتظار، ودخول المتجر، وأخذ كرسي غرفة الانتظار —خذ قدرًا معينًا من الوقت. على وجه التحديد، قد يصل العميل ليجد الحلاق الذي يقص الشعر فيعود إلى غرفة الانتظار ليجلس، ولكن أثناء عودته إلى غرفة الانتظار، ينهي الحلاق قصة شعره ويذهب إلى غرفة الانتظار، التي يجدها فارغة (لأن يمشي العميل ببطء أو يذهب إلى الحمام) وبالتالي ينام على كرسي الحلاقة. ثانيًا، قد تحدث مشكلة أخرى عندما يصل عميلان في نفس الوقت عندما يكون هناك مقعد واحد فارغ في غرفة الانتظار ويحاول كلاهما الجلوس على كرسي واحد؛ لن يتمكن من الجلوس إلا أول شخص يصل إلى الكرسي.
إذا لم يكن هناك زبائن، ينام الحلاق على الكرسي
يجب على الزبون إيقاظ الحلاق إذا كان نائماً
وفي السياق ذاته، إذا وصل أحد العملاء أثناء عمل الحلاق، يغادر العميل إذا كانت جميع الكراسي مشغولة ويجلس على كرسي فارغ إذا كان متاحًا
إضافةً إلى ذلك، تخيل صالون حلاقة افتراضيًا به حلاق واحد وكرسي حلاقة وغرفة انتظار بها عدد من الكراسي (قد تكون 0) للعملاء المنتظرين. تطبق القواعد التالية:
وعلى صعيد آخر، عندما ينتهي الحلاق من قصة شعره ، يتفقد غرفة الانتظار ليرى ما إذا كان هناك أي زبائن ينتظرون وينام إذا لم يكن هناك أي منهم
حلول
في هذا الإطار، هناك الكثير من الحلول الممكنة، لكن جميع الحلول تتطلب كائن المزامنة (mutex)، والذي يضمن أن واحدًا فقط من المشاركين يمكنه تغيير الحالة مرة واحدة. يجب أن يكتسب الحلاق كائن المزامنة الخاص بحالة الغرفة قبل التحقق من العملاء وتحريره عند بدء النوم أو قص الشعر؛ يجب على العميل الحصول عليها قبل دخولها إلى المحل والإفراج عنها بمجرد جلوسهم في غرفة الانتظار أو كرسي الحلاقة، وكذلك عند مغادرتهم المحل لعدم توفر مقاعد. هذا من شأنه أن يعالج كل من المشاكل المذكورة أعلاه. مطلوب كذلك عدد من السيمافورات للإشارة إلى حالة النظام. مثلًا، قد يقوم المرء بتخزين عدد الأشخاص في غرفة الانتظار.
📝 هل في هذه المقالة خطأ؟
إذا وجدت معلومة تحتاج تصحيحاً أو إضافة، أو أردت حذف المقالة، أرسل لنا طلباً وسنراجعه.
ما رأيك في هذه المقالة؟