سری گری گوری لیبینز

به نام خدا

سری معروف به سری گری گوری و لیبیز به صورت زیر است که هر چه n بزرگتر باشد ، عدد PI یعنی 3.14 را

بهتر تقریب میزند.

همانطور که معلوم است کل برنامه به یک حلقه for نیاز دارد که مقدار UpperBound آن باید مشخص شود تا

n ، از بازه 0 تا U یعنی UpperBound تغییر نماید.

دانلود سورس کد + فایل اجرایی

شام فیلسوفان

به نام خدا

در بحث الگوریتم های موازی یا به اصطلاح 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  ، قرار دهد.

یک راه دیگر هم وجود دارد ، که آنرا ان شا الله بعدا می گویم.

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