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

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

اسلاید 1: استاد سرکار خانم مهندس فاطمه نجفی یونس شیخ 922502214 نیمسال دوم 93-92دانشگاه ازاد اسلامی واحدایذهیک اگوریتم تحمل پذیر دربرابر خطا جهت ایجاد انحصار متقابل توزیع شده

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

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

اسلاید 4: 3/19مقدمه:الگوریتمهای زیادی جهت گرفتن ناحیه بحرانی وجود دارند: الف)الگوریتم متمرکزب)الگوریتم توزیع شدهج)الگوریتمهای مبتنی بر توکن

اسلاید 5: 4/19مروری بر کارهای گذشته: الف)الگوریتمی که به وسیله RICARD&AGRAWALAپیشنهاد شد ب) الگوریتمی که به وسیلهGIFORD&SKEENمطرح شد ج) الگوریتمی که LAMPOR ارائه دادد) الگوریتمی که RAYMOND ارائه دادو)الگوریتم معرفی شده توسط MEAKAWA

اسلاید 6: 5/19نحوه کار مدل مورد نظر: 1)ایجاد گروه و کسب ناحیه بحرانی:هر فرایند که ایجاد شد،شماره ای یکه به آن نسبت داده می شود در الگوریتم LAMPORهر گره ای که بعد از ایجاد شدن خراب شود اگر دوبار وارد سیستم گردد باید عددی دیگر به آن نسبت داده شود یعنی همانند گروههای جدید با او برخورد شود. به فرض که گره ای با شمارهiایجاد شود ،هرگره بعد از آنکه یک عدد یکه به آن نسبت داده شد،گروهی برای خود تشکیل می دهند.نحوه ایجاد این گرو ه به صورت برنامه زیر است

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

اسلاید 8: 7/19نحوه کار مدل مورد نظر: شکل منطقی قرارگیری گره ها به صورت درخت زیر است: (شکل 1: گروهبندی گره های درختی)G1={1},G2={2,1},G3={3,1} G4={4,2,1},G5={5,2,1},G6={6,3,1}G7={7,3,1}

اسلاید 9: 8/19نحوه کار مدل مورد نظر:

اسلاید 10: 9/19نحوه کار مدل مورد نظر:

اسلاید 11: 10/19نحوه کار مدل مورد نظر:

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

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

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

اسلاید 15: 14/19گره هایی که خراب شود،دیگران چگونه مطلع می گردند گره هایی که خراب شده است حداقل در یک گروه قرار دارد و اگر گره هایی بخواهد ناحیه بحرانی را بدست آورد و گره خراب شده در ان گروه باشد خرابی را کشف می کند(شکل 5).

اسلاید 16: 15/19 تفاوت سطح گره درخواست کننده با گره خراب شده بیشتر از یک سطح باشد مثال گره 11 درخواست ناحیه بحرانی را نماید و گره دو خراب شود. گره 11 خودش و گره 5 را قفل می کند و قصد قفل گره 2 را دارد که می بیند گره 2 خراب شده است. طبق الگوریتم پیشنهادی باید گره 11 جایگزین گره 2 شود.

اسلاید 17: 16/19 مقایسه الگوریتم پیشنهادی با الگوریتم های موجود

اسلاید 18: 17/19نتیجه گیری در این الگوریتم نشان میدهیم که تعداد پیامهای ارسالی برای بدست آوردن ناحیه بحرانی،از درجه لگاریتمی بوده و الگوریتم تحمل پذیر در برابر خطا است و با خراب شده فرایندها می تواند دوباره بازسازی گردد و دیدیم که الگوریتم آزاد از بن بست و قحطی زدگی بود.

اسلاید 19: سپاس از حضار محترم 18/19