سادگی زیباست...

بررسی انواع معماری های سیستم عامل و برنامه های سیستمی و روشهای توسعه آنها

سادگی زیباست...

بررسی انواع معماری های سیستم عامل و برنامه های سیستمی و روشهای توسعه آنها

سادگی زیباست...

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

يكشنبه, ۲۴ آذر ۱۳۹۲، ۰۳:۴۳ ب.ظ

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

"در یک آرایشگاه به تعداد 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()

نظرات (۶)

۱۲ دی ۹۲ ، ۱۳:۳۸ مجید رحیمی

سلام!

ممنون؛ 

- در کد آرایشگر، چرا cutHair بین customer.wait و barber.signal نیست؟


۱۴ دی ۹۲ ، ۱۴:۳۳ حامد شیخلو
آرایشگر منتظر یک مشتری هستش، مشتری به آرایشگر سیگنال میده و منتظر میمونه تا آرایشگر بهش جواب بده (شبیه مساله barrier).
۰۸ دی ۹۴ ، ۱۶:۲۱ حسین مومنی
سلام ..اگه کد پروژه ارایشگر رو به زبان سی شارپ داری برام بفرست...ممنون
پاسخ:
داشتنش رو که دارم، اما خودتون بنویسین به نظرم بهتر باشه
سلام...این کد ران میشه؟؟؟؟؟؟
پاسخ:
این شبه کد هست. باید به یه زبان برنامه نویسی ترجمه کنیدش
ببخشید من کد پروزه را میخواستم میتونید کمکم کنید؟؟
متن بالای سایت تون خوب بود. کاش بیشتر به فکر هم باشیم. مظالب هم خوب است خسته نباشید

ارسال نظر

ارسال نظر آزاد است، اما اگر قبلا در بیان ثبت نام کرده اید می توانید ابتدا وارد شوید.
شما میتوانید از این تگهای html استفاده کنید:
<b> یا <strong>، <em> یا <i>، <u>، <strike> یا <s>، <sup>، <sub>، <blockquote>، <code>، <pre>، <hr>، <br>، <p>، <a href="" title="">، <span style="">، <div align="">
تجدید کد امنیتی