شام فیلسوفان
در بحث الگوریتم های موازی یا به اصطلاح Concurrent یا همروند ، مساله ای با نام شام فیلسوفان توسط
بنیان گذار اکثر مسائل مهندسی کامپیوتر یعنی ادگار دایجسترا یا دیکسترا ، مطرح گردید که به شرح زیر است:
در عکس بالا آیزاک ، یک مهمونی ترتیب داده و ماکارانی درست کرده و دوستان هم عصر و قبل از آیزاک
اومدن تا ماکارانی بزنن.
همه میان با هم شروع کنند به خوردن ماکارونی که می بینن ، ای وای چنگال کمه ... چون نیاز به دو چنگال
دارند تا بتوانند بخورند.(فرض شود یک چنگاله قبول نیست...)
مساله اینطور است که این فیلسوف ها باید دو کار انجام دهند : 1- فکر کنند ، 2- بخورند با دو چنگال
وقتی فیلسوفی خوردنش تمام شد ، باید هر دو چنگال را رها کند و فیلسوف بعدی می تواند استفاده نماید.
در اصل ، ماکارونی و چنگال ها به عنوان Resource و فیلسوفان به عنوان Process یا Thread هستند.
یک الگوریتم حل اینست که:
گام 1 : یک فیلسوف آنقدر فکر کند تا چنگال سمت چپ آزاد شود و آنرا بردارد.
گام 2 : باز آنقدر فکر کند تا چنگال سمت راست آزاد شود و آن را بردارد.
گام 3 : تا مقدار زمان خاص مثل کوانتوم یا Q از ماکارانی بخورد. ( اگر زمانبدی CPU از نوع
Round Robin باشد.)
گام 4 :چنگال راست را رها کند . (Flush Right)
گام 5 : چنگال چپ را نیز رها کند . ( Flush Left)
گام 6 : برو به گام 1.
الگوریتم ضعیف بالا ، باعث میشود ما به deadlock برسیم. چرا ؟ چون فرض کنید همه فیلسوف ها بیایند و
چنگال سمت چپ را بردارند ، چون چنگال سمت راست هر فیلسوف ، چنگال سمت چپ فیلسوف دیگر است
و فیلسوف هایی که چنگال سمت چپ را برداشته اند باید منتظر بمانند تا چنگال سمت راستشان که در دست
فیلسوف دیگر است، آزاد شود ، و چون این حالت هیچگاه رخ نمیدهد ، به بن بست یا deadlock میرسیم
و سیستم عاملی که با این الگوریتم کار کند ، در این مورد ، به حالت Not Responding میرود.
در الگوریتم فوق حتی ممکن است گرسنگی منبع هم رخ دهد.
به هر حال ، راه حل هایی برای حل این بحران ارائه گردیده است که در زیر من به راه حل Conductor و
نیز راه حل Chandy/Misra اشاره میکنم :
راه حل اول : Conductor یا راهنما
استفاده از یک خدمتکار یا waiter است که از تعداد چنگال های مانده و در حال استفاده آگاهی دارد ، هر
فیلسوفی که می خواهد ماکارونی بخورد، به خدمتکار میگوید تا برای خود نوبت بگیرد و سپس خدمتکار
چنگال را در اختیارش می گذارد . ( چنگال سمت چپ را به او میدهد)
واضح است که این همان سمافور است .
در سی شارپ برای استفاده از سمافور ها باید از کلاس زیر استفاده کرد :
System.Threading.Semaphore
راه حل دوم : راه Chandy/Misra
اساس این الگوریتم روش Message Passing است ، یعنی فیلسوف ها با هم حرف بزنند یا به بیان تخصصی
هر Process به Process های جانبی خود ( حالا میتواند از PCB شماره ID آنها را بیابد ) یک پیغام و درخواست
برای انحصار منبع یا Resource Allocation بفرستد و آن پرسه ای که منبع را به انحصار خود در آورده است ، آنرا
آزاد نماید برای پرسه درخواست کننده.
الگوریتم به شرح زیر است :
گام 1 :چنگال ها دو حالت دارند : 1-کثیف ، 2-تمیز
گام 2 : هنگامیکه یک فیلسوف می خواهد از ماکارونی اش بخورد ، باید چنگال هایش را از فیلسوف
های اطرفش بگیرد ، پس به ازای هر چنگالی که ندارد ، به فیلسوف های کناری اش ، درخواست
میدهد.
گام 3 : وقتی یک فیلسوف ، پیغام ، چنگال بده را دریافت میکند ، اگر چنگالش تمیز باشد ، آن را
نگاه میدارد.اما اگر چنگال کثیف باشد ، آنرا تمیز میکند و به فیلسوف درخواست کننده میدهد.
گام 4 : بعد از اتمام خوردن یک فیلسوف ، همه چنگالهایش کثیف میشود ، اگر در صف
درخواست ها ،چشم فیلسوف دیگری به چنگالهایش بود ، باید آن چنگال درخواست شده
را تمیز کند و در اختیار فیلسوف درخواست کننده منتظر در صف waiting ، قرار دهد.
یک راه دیگر هم وجود دارد ، که آنرا ان شا الله بعدا می گویم.
یک از دوستان مطلب را با کدهایشان کامل کرده اند : به اینجا برود .
توجه : در این وبلاگ پروژه انجام نمیشود.