فیلسوفان خورنده به همراه توضیحات کامل و کد مسئله در ۶ زبان برنامه نویسی


philsophia
کد سورس  فیلسوفان خورنده به همراه توضیحات کامل

پنج نفر فیلسوف را که زندگیشان را صرف فکر کردن و خوردن می نمایند در نظز بگیرید این فیلسوفان یک میز مدور و مشترک را با ۵ صندلی هر یک متعلق به یک فیلسوف محصور شده  به اشتراک دارند در وسط میز از ماکارونی و برنج قرار دارد و بر روی میز ۵ قاشق دارند وقتی در حال اندیشیدن هستن با همکار خود ارتباطی ندارند از زمانی به زمان دیگر فیلسوف احساس گرسنگی کرده و سعی میکند قاشق نزدیک به خود را (قاشقی که بین او و همسایه های چپ و راستش قرار دارد ) بردارد فیلسوف مجار هست که هر بار تنها یه قاشق را بردارد و به وضوح نمی تواند قاشقی را که قبلا در دست فیلسوف دیگری قرار گرفته بگیرد ولی فیلسوف گرسنه در یک لحظه هر دو قاشق  را در اختیار داشته باشد می تواند بدون وقفه به خوردن بپردازد وقتی به اتمام رسید هر دو قاشق را یکی یکی زمین گذاشته و دوباره به فکر  کردن بپردازد .

مساله اینطور است که این فیلسوف ها باید دو کار انجام دهند : ۱- فکر کنند ، ۲- بخورند با دو چنگال

وقتی فیلسوفی خوردنش تمام شد ، باید هر دو چنگال را رها کند و فیلسوف بعدی می تواند استفاده نماید.

در اصل ، ماکارونی و چنگال ها به عنوان Resource و فیلسوفان به عنوان Process یا Thread هستند.

یک الگوریتم حل اینست که:

گام ۱ : یک فیلسوف آنقدر فکر کند تا چنگال سمت چپ آزاد شود و آنرا بردارد.

گام ۲ : باز آنقدر فکر کند تا چنگال سمت راست آزاد شود و آن را بردارد.

گام ۳ : تا مقدار زمان خاص مثل کوانتوم یا Q از ماکارانی بخورد. ( اگر زمانبدی CPU از نوع 

  Round Robin باشد.)

گام ۴ :چنگال راست را رها کند . (Flush Right)

گام ۵ : چنگال چپ را نیز رها کند . ( Flush Left)

گام ۶ : برو به گام ۱٫

الگوریتم ضعیف بالا ، باعث میشود ما به deadlock برسیم. چرا ؟ چون فرض کنید همه فیلسوف ها بیایند و

چنگال سمت چپ را بردارند ، چون چنگال سمت راست هر فیلسوف ، چنگال سمت چپ فیلسوف دیگر است

و فیلسوف هایی که چنگال سمت چپ را برداشته اند باید منتظر بمانند تا چنگال سمت راستشان که در دست

فیلسوف دیگر است، آزاد شود ، و چون این حالت هیچگاه رخ نمیدهد ، به بن بست یا deadlock میرسیم

و سیستم عاملی که با این الگوریتم کار کند ، در این مورد ، به حالت Not Responding میرود.

در الگوریتم فوق حتی ممکن است گرسنگی منبع هم رخ دهد.

به هر حال ، راه حل هایی برای حل این بحران ارائه گردیده است که در زیر من به راه حل Conductor و

نیز راه حل Chandy/Misra اشاره میکنم :

راه حل اول  : Conductor یا راهنما

استفاده از یک خدمتکار یا waiter است که از تعداد چنگال های مانده و در حال استفاده آگاهی دارد ، هر

فیلسوفی که می خواهد ماکارونی بخورد، به خدمتکار میگوید تا برای خود نوبت بگیرد و سپس خدمتکار

چنگال را در اختیارش می گذارد . ( چنگال سمت چپ را به او میدهد)

واضح است که این همان سمافور است .

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

System.Threading.Semaphore

راه حل دوم  : راه Chandy/Misra

اساس این الگوریتم روش Message Passing است ، یعنی فیلسوف ها با هم حرف بزنند یا به بیان تخصصی

هر Process به Process های جانبی خود ( حالا میتواند از PCB شماره ID آنها را بیابد ) یک پیغام و درخواست

برای انحصار منبع یا Resource Allocation بفرستد و آن پرسه ای که منبع را به انحصار خود در آورده است ، آنرا

آزاد نماید برای پرسه درخواست کننده.

الگوریتم به شرح زیر است :

گام ۱ :چنگال ها دو حالت دارند : ۱-کثیف ، ۲-تمیز

گام ۲ : هنگامیکه یک فیلسوف می خواهد از ماکارونی اش بخورد ، باید چنگال هایش را از فیلسوف 

 های اطرفش بگیرد ، پس به ازای هر چنگالی که ندارد ، به فیلسوف های کناری اش ، درخواست

 میدهد.

گام ۳ : وقتی یک فیلسوف ، پیغام  ، چنگال بده را دریافت میکند ، اگر چنگالش تمیز باشد ، آن را 

نگاه  میدارد.اما اگر چنگال کثیف باشد ، آنرا تمیز میکند و به فیلسوف درخواست کننده میدهد.

گام ۴ : بعد از اتمام خوردن یک فیلسوف ، همه چنگالهایش کثیف میشود ، اگر در صف 

درخواست ها ،چشم فیلسوف دیگری به چنگالهایش بود ، باید آن چنگال درخواست شده 

را تمیز کند و در اختیار  فیلسوف درخواست کننده منتظر در صف waiting  ، قرار دهد.

کپی برداری بدون منبع گناه بوده چون نویسنده رضایت ندارد

دانلود شبه مسئله فیلسوفان خورنده

دانلود کد مسئله به زبان C

دانلود کد سورس به زبان  C++

دانلود کد سورس به زبان C#

دانلود کد سورس به زبان F#

دانلود کد سورس به زبان جاوا

دانلود کد سورس به زبان Perl
منبع: www.wavesoft.ir

دیدگاهتان را بنویسید

این سایت از اکیسمت برای کاهش هرزنامه استفاده می کند. بیاموزید که چگونه اطلاعات دیدگاه های شما پردازش می‌شوند.