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

این مساله برای اولین بار توسط دایجسترا مطرح شد. در کتاب سیستم عامل سیلبرشاتس به صورت زیر آمده است:

"در یک آرایشگاه به تعداد n صندلی برای انتظار موجود و یک صندلی آرایشگری موجود است. اگر مشتری در مغازه نباشد، آرایشگر در این فرصت میخوابد. اگر یک مشتری وارد مغازه شد و همه صندلی ها پر باشد، مغازه را ترک میکند، اگر آرایشگر مشغول باشد، اما صندلی انتظار موجود باشد، مشتری در یک صندلی خالی مینشیند. اگر آرایشگر خوابیده باشد، مشتری او را بیدار میکند. یک برنامه برای هماهنگ سازی مشتری و ارایشگر بنویسید."

میتوان اطلاعات زیر را برای فهم بهتر مساله اشاره کرد:

• پردازش مشتری یک تابع با عنوان getHairCut را فراخوانی میکند.
• اگر پردازش مشتری زمانی که مغازه پر است وارد شود، میتواند balk را که چیزی بازگشت نمیدهد فراخوانی کند.
• پردازش آرایشگر باید cutHair را فراخوانی کند.
• زمانی که آرایشگر تابع cutHair را فراخوانی میکند، باید دقیقا یک پردازش getHairCut را فراخوانی کرده باشد.

مقدار درهی های اولیه:

customers = 0
mutex = Semaphore(1)
customer = Semaphore(0)
barber = Semaphore(0)

مقدار customers، تعداد مشتری های موجود در مغازه را مدیریت میکند و با میوتکس محافظت میشود.

آرایشگر برای customer منتظر میشود تا وارد مغازه شود و آنگاه مشتری منتظر مغازه دار میشود تا اجازه دهد که مشتری بر روی صندلی بنشیند.

کد مربوط به مشتری:

mutext.wait()
	if customers == n+1:
		mutext.signal()
		balk()
	customer += 1
mutex.signal()

customer.signal()
barber.wait()
getHairCut()

mutex.wait()
	customer -=1
mutex.signal()

اگر تعداد n صندلی پر باشد و یکی هم روی صندلی آرایش نشسته باشد (میشود n+1 نفر) یعنی مغازه پر است. مشتری در این شرایط وارد میشود و تابع bulk را صدا میزند. در غیر این صورت هر مشتری به مغازه دار یک سیگنال میدهد و منتظر آرایشگر میشود.

کد  آرایشگر:

customer.wait()
barber.signal()
cutHair()

Hilzer’s barbershop

در کتاب استالینگز یک مساله آرایشگر پیچیده تر مطرح شده است:

"مغازه دارای سه صندلی آرایش و سه آرایشگر و همچنین یک فضای انتظار که برای مشتری های جدید. تعداد مشتری هایی که میتواند منتظر باشند، 20 نفر میباشند.

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

میتوان گفت مسائل زیر در زمانبندی باید مد نظر باشد:

• مشتری این توابع را به ترتیب اجرا میکند: enterShop, sitOnSofa, sitInBarberChair, pay, exitShop
• آرایشگر توابع cutHair و AcceptPayment را فراخوانی میکند.
• مشتری در صورت پر بودن مغازه نمیتواند وارد مغازه شود.
• اگر کاناپه پر باشد، مشتری نمیتواند sitOnSofa را اجرا کند، مگر اینکه یکی از مشتری ها sitOnBarberChair را اجرا کرده باشد.
• اگر تمام صندلیهای آرایش پر باشد، یک مشتری که وارد مغازه میشود، نمیتواند sitOnBarberChair را اجرا کند، مگر آنکه یکی از مشتریها Pay را اجرا کرده باشد.
• مشتری باشد ابتدا pay را اجرا کند و سپس آرایشگر acceptPayment را اجرا کند.
• آرایشگر باید ابتدا acceptPayment را اجرا کند و سپس مشتری exitShop را اجرا کند.

دشواری مساله در مکانهایی است که باید بر روی آنها انتظار انجام شود.

مقداردهی های مساله:

customers = 0
mutex = Semaphore(1)
standingRoom = Fifo(16)
sofa = Fifo(4)
chair = Semaphore(3)
barber = Semaphore(0)
customer = Semaphore(0)
cash = Semaphore(0)
receipt = Semaphore(0)

کر مربوط به مشتری:

mutex.wait()
if customers == 20:
mutex.signal()
exitShop()
customers += 1
mutex.signal()

standingRoom.wait()
enterShop()

sofa.wait()
sitOnSofa()
standingRoom.signal()

chair.wait()
sitInBarberChair()
sofa.signal()

customer.signal()
barber.wait()
getHairCut()

pay()
cash.signal()
receipt.wait()

mutex.wait()
customers -= 1
mutex.signal()

exitShop()

کد مربوط به آرایشگر:

customer.wait()
barber.signal()
cutHair()

cash.wait()
acceptPayment()
receipt.signal()