دانلود فایل پاورپوینت الگوریتم تحمل پذیر جهت ایجاد انحصار متقابل توزیع شده

بخشی از پاورپوینت

--- پاورپوینت شامل تصاویر میباشد ----

اسلاید 1 :

1)چکیده
2)مقدمه
3)مروری بر کارهای گذشته
4)نحوه کار مدل مورد نظر
1-4) ایجاد گروه و کسب ناحیه بحرانی
2-4)بررسی بن بست،گرسنگی و انتظار محدود
3-4)بررسی شرط پیشرفت و عادلانه بودن آن
4-4)تحمل پذیری خطا
5-4)گره هایی که خراب می شوند دیگران چطور متوجه می شوند
6-4)تعداد پیامها جهت اخذ ناحیه بحرانی چقدر است
5)مقایسه الگوریتم پیشنهادی با سایر الگوریتمها
6)نتیجه گیری

اسلاید 2 :

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

اسلاید 3 :

الف)الگوریتم متمرکز

ب)الگوریتم توزیع شده

ج)الگوریتمهای مبتنی بر توکن

اسلاید 4 :

الف)الگوریتمی که به وسیله RICARD&AGRAWALAپیشنهاد شد

ب) الگوریتمی که به وسیلهGIFORD&SKEENمطرح شد

ج) الگوریتمی که LAMPOR ارائه داد

د) الگوریتمی که RAYMOND ارائه داد

و)الگوریتم معرفی شده توسط MEAKAWA

اسلاید 5 :

1)ایجاد گروه و کسب ناحیه بحرانی:

هر فرایند که ایجاد شد،شماره ای یکه به آن نسبت داده می شود در الگوریتم LAMPORهر گره ای که بعد از ایجاد شدن خراب شود اگر دوبار وارد سیستم گردد باید عددی دیگر به آن نسبت داده شود یعنی همانند گروههای جدید با او برخورد شود. به فرض که گره ای با شمارهiایجاد شود ،هرگره بعد از آنکه یک عدد یکه به آن نسبت داده شد،گروهی برای خود تشکیل می دهند.نحوه ایجاد این گرو ه به صورت برنامه زیر است

اسلاید 6 :

اولین موردی که در گرفتن ناحیه بحرانی باید مورد توجه قرار گیرد مسئله انحصار متقابل است و اینکه این الگوریتم تضمین کند که انحصار متقابل برقرار است و هیچ دو فرایندی نمی توانند همزمان وارد ناحیه بحرانی شوند.
فرض که هر گره ای برای خود گروهی تشکیل دهند.

اسلاید 7 :

شکل منطقی قرارگیری گره ها به صورت درخت زیر است:

اسلاید 8 :

فرض که گره 3و2 همزمان درخواست قفل گره یک را نمایند، گره 1 هر دو درخواست را گرفته و درخواستی که از فرآیندی با شماره کوچکتر می باشد را در اولویت قرار می دهد در نهایت گره 2 موفق به قفل گره یک شده و درخواست گره3 به صف میرود و هرگاه گره2 از ناحیه بحرانی خارج شود گره1 پیام آزادسازی از گره2 را دریافت می کند و گره 3 را از صف خارج کرده و گره 1 برای گره3 قفل می شود، گره 3 وارد ناحیه بحرانی می گردد. پس در این الگوریتم هیچ بن بستی وجود ندارد زیرا به هر حال طبق اولویتی که وجود دارد بن بست درخواست قفل بین چندین فرآیند شکسته می شود و همچنین هیچ گرسنگی و انتظار نامحدودی نیز پیش نمی آید و هیچ گره ایی به اندازه نامحدود منتظر رفتن به ناحیه بحرانی نیست زیرا طبق شماره گذاری هایی که انجام شده و طبق اولویتی که یاد شده است مسئله نیز به درستی رفع می گردد.

اسلاید 9 :

فرآیندی که از ناحیه بحرانی خارج می شود و در بخش پایانی خود قرار می گیرد باید اجازه دهد گره های دیگری که هنوز وارد ناحیه بحرانی نشده اند، وارد ناحیه بحرانی گردند و خودش دوباره تلاش نکند. این مسئله به صورت زیر قابل حل است:
برای هر فرآیند و نسبت به ناحیه بحرانی که مورد استفاده آن است می توان محدودیت هایی قائل شد و آن اینکه هر فرآیند بعد استفاده از ناحیه بحرانی شماره خود(اولویت خود) را پس داده و شماره ای دیگر را بگیرد. در این حالت همه فرآیند های شرکت کننده در رقابت از این لحظه به بعد می توانند او را قفل نمایند. این کار تا زمانی ادامه می یابد تا کلیه فرآیند های درگیر از ناحیه بحرانی استفاده کنند و کارشان تمام شود.خلل ناشی از این کار که در درخت ایجاد می گردد با همان ترفند اولیه که یاد شد برطرف می گردد.

اسلاید 10 :

اساسی ترین مشکلاتی که در یک سیستم توزیع شده پیش می آید خراب شدن هر کدام از گره ها بدون اطلاع گره های دیگر است. در ادامه نشان می دهیم که این الگوریتم کاملا تحمل پذیر خطا بوده و در برابر خرابی گره ها خللی در روند کار ایجاد نمی گردد.
L=LOCK,FL=Free Lock,R=Request E=rEleas