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

صفحه 1:
یک اگوریتم تحمل پذیر دربرابر خطا جهت ایجاد انحصار متقابل توزیع شده استاد سرکار خانم مهندس فاطمه نجفی یونس شیخ ‎٩۲۲۵۰۲۲۱6‏ ‏نیمسال دوم ‎٩۲-۹۳‏ ‏دانشگاه ازاد اسلامی واحدایذه 

صفحه 2:
> فهرست مطالب هديكج)١‎ ۲)مقدمه ۳)مووری بر کارهای گذشته ‎١‏ ۴)نحوه کار مدل مورد نظو 4 ۴-) ایجاد گروه و کسب ناحیه بحوانی —- ۲-۴)بررسی بن بست گرسنگی و انتظار محدود ۳-۴)بیرسی شوط پیشرفت و عادلانه بودن آن ۴-۴)تحمل پذییی خطا ۵-۴)گره هایی که خراب می شوند دیگوان چطور متوجه می شوند 3 ۶-۴)تعداد پیامها جهت اخذ ناحیه بحیانی چقدر است 6 ۵)مقایسه الگوریتم پیشنهادی با سایر الگوریتمها ۶)نتیجه گیری 1/۹ 

صفحه 3:


صفحه 4:
مقدمه: الگوریتمهای زیادی جهت گرفتن ناحیه بحرانی وجود دارند: 

صفحه 5:
مروری بر کارهای گذشته: ني ۱ Presenter’ 

صفحه 6:
نحوه کار مدل مورد نظر: 7 ‎ag‏ ١)ايجاد‏ گروه و کسب ناحیه بحرانی: ‎Presenter‏ 

صفحه 7:
نحوه کار مدل مورد نظر: Presenter 

صفحه 8:
نحوه کار مدل مورد نظر: Presenter G) ‏(شکل : گروهبندی گره های درختی)‎ te ay ‏و‎ G3={3,1} G4={4,2,1},G5={5,2,1},G6={6,3, 1}G7={7,3,1} 

صفحه 9:
نحوه کار مدل مورد نظر: ‎Presenter‏ ASL ote ‏از آن طرف ۵ اقدام به قفل هم گروه دیگرش یعنی گره ۱ می‌کند.‎ 

صفحه 10:
:نحوه کار مدل مورد نظر De, (شکل ۳: ارسال جواب قفل) گره: ۸ تخود موسط كرما اذيكن قعل ‎piece setts Salant‏ yy 2 قفل را به گره ۵ ارسال می‌کند و درخواست۵ را به صف می‌برد(شکل ۲). 

صفحه 11:
:نحوه کار مدل مورد نظر 07 اسان" 

صفحه 12:
: بررسی بن بست» گرسنگی و انتظار محدود 

صفحه 13:
بررسی شرط پیشرفت و عادلانه بودن آن : 

صفحه 14:
تحمل پذیری در برابر خطا Presenter 

صفحه 15:
گره هایی که خراب شود؛دیگران چگونه مطلع می گردند /™. SMS ‏ما‎ (شکل ۵: با زسازی درخت) 

صفحه 16:
تفاوت سطح گره دررخواست کننده با گره خراب شده بیشتر از یک سطح باشد 611-)11,52.1( 1 گروه 6 به [2,1)-02 Presenter 

صفحه 17:
> مقایسه الگوریتم پیشنهادی با الگوریتم های موجود تحمل پدیری در برابر خطا ندارد تحمل پدیری در برابر خطا ندارد ]2/)0+1([ 31090-3 n-1)2 (sqrt(n-1))2 (logn-1)2 (logn-1)2 Recart&Agrawala Meakawa El-Abbadi الگوریتم پیشنهادی3۳000۲] 

صفحه 18:
۳۳656۳۵۳۵ 

صفحه 19:
1 

یک اگوریتم تحمل پذیر دربرابر خطا جهت ایجاد انحصار متقابل توزیع شده استاد سرکار خانم مهندس فاطمه نجفی یونس شیخ 922502214 نیمسال دوم 92-93 دانشگاه ازاد اسالمی واحدایذه فهرست مطالب )1چکیده )2مقدمه 3وری بر کارهای گذشته )3مر 3 )4نحوه کار مدل مورد نظر 3انی )1-4ایجاد گروه و کسب ناحیه بحر ) 2-4بررسی بن بست،گرسنگی و انتظار محدود 3ط پیشرفت و عادالنه بودن آن 3رسی شر )3-4بر 3ی خطا )4-4تحمل پذیر 3ان چطور متوجه می شوند )5-4گره هایی که خراب می شوند دیگر 3انی چقدر است )6-4تعداد پیامها جهت اخذ ناحیه بحر ) 5مقایسه الگوریتم پیشنهادی با سایر الگوریتمها )6نتیجه گیری 1/19 چکیده 3ع شده ارائه شده 3یستم توزی 3ل در س 3ار متقاب 3ل انحص 3ل مشک 3ت ح 3م های زیادی جه الگوریت است.اما درآنها تعداد پیامهای ارسالی خیلی باال بوده و پیچیدگی زمانی باالیی دارند. 3ت را بیان می 3ه شده اس 3ل ارائ 3ن مشک 3ل ای 3ت ح 3ه جه 3م جدیدی ک 3ا الگوریت 3ق م 3ن تحقی در ای 3ی می 3ه لگاریتم 3ی از درج 3ه بحران 3ت آوردن ناحی 3الی برای بدس 3ه تعداد پیامهای ارس 3م ک کنی 3ی تواند 3ا م 3ا خراب شدن فراینده 3ا بوده و ب 3ر در برابر خط 3ل پذی 3م تحم 3ن الگوریت باشد.ای 3ن الگوریتم 3ه ای 3د ک 3ی ده 3ان م 3ت نش 3ه دهد .در نهای 3ه کار خود ادام 3ازی گردد وب دوباره بازس آزاد از بن بست و قطحی زدگی می باشد 2/19 مقدمه: الگوریتمهای زیادی جهت گرفتن ناحیه بحرانی وجود دارند: الف)الگوریتم متمرکز ب)الگوریتم توزیع شده ج)الگوریتمهای مبتنی بر توکن 3/19 مروری بر کارهای گذشته: الف)الگوریتمی که به وسیله RICARD&AGRAWALAپیشنهاد شد ب) الگوریتمی که به وسیلهGIFORD&SKEENمطرح شد ج) الگوریتمی که LAMPORارائه داد د) الگوریتمی که RAYMONDارائه داد و)الگوریتم معرفی شده توسط MEAKAWA 4/19 نحوه کار مدل مورد نظر: )1ایجاد گروه و کسب ناحیه بحرانی: هر فرایند که ایجاد شد،شماره ای یکه به آن نسبت داده می شود در الگوریتم LAMPORهر 3ر دوبار وارد سیستم گردد باید عددی دیگر به آن 3د از ایجاد شدن خراب شود اگ 3ه بع گره ای ک 3ه گره ای با 3ه فرض ک 3ا او برخورد شود .ب 3د ب 3د گروههای جدی 3ی همانن 3بت داده شود یعن نس 3د،گروهی برای خود 3بت داده ش 3ن نس 3ه آ 3ه ب 3ک عدد یک 3ه ی 3د از آنک شمارهiایجاد شود ،هرگره بع تشکیل می دهند.نحوه ایجاد این گرو ه به صورت برنامه زیر است 5/19 نحوه کار مدل مورد نظر: 3ار متقابل 3ئله انحص 3ه قرار گیرد مس 3رد توج 3د مو 3ی بای 3ه بحران 3ن ناحی 3ه در گرفت 3ن موردی ک اولی 3چ دو فرایندی نمی 3ت و هی 3ل برقرار اس 3ار متقاب 3ه انحص 3د ک 3ن کن 3م تضمی 3ن الگوریت 3ه ای 3ت و اینک اس توانند همزمان وارد ناحیه بحرانی شوند. فرض که هر گره ای برای خود گروهی تشکیل دهند. 6/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 7/19 نحوه کار مدل مورد نظر: :نحوه کار مدل مورد نظر :نحوه کار مدل مورد نظر  :بررسی بن بست،گرسنگی و انتظار محدود 3ر دو درخواست را 3د ،گره 1ه 3ک را نماین 3ل گره ی 3ت قف 3ه گره 3و 2همزمان درخواس فرض ک 3ی دهد 3ت قرار م 3د را در اولوی 3ی باش 3ر م 3ا شماره کوچکت 3ه از فرآیندی ب 3تی ک 3ه و درخواس گرفت 3ه صف میرود و هرگاه گره2 3ت گره 3ب 3ک شده و درخواس 3ل گره ی 3ه قف 3ق ب 3ت گره 2موف در نهای از ناحیه بحرانی خارج شود گره 1پیام آزادسازی از گره 2را دریافت می کند و گره 3را از 3ی می گردد. 3ه بحران 3ی شود ،گره 3وارد ناحی 3ل م 3ف خارج کرده و گره 1برای گره 3قف ص 3ی که وجود 3ق اولویت 3ر حال طب 3ه ه 3تی وجود ندارد زیرا ب 3ن بس 3چ ب 3م هی 3ن الگوریت 3س در ای پ 3رسنگی و دارد بن بست درخواست قفل بین چندین فرآیند شکسته می شود و همچنین هیچ گ 3ن به 3ر رفت 3ه اندازه نامحدود منتظ 3ی ب 3چ گره ای 3د و هی 3ی آی 3ش نم 3ز پی انتظار نامحدودی نی 3ی که یاد 3ق اولویت 3ه انجام شده و طب 3ی ک 3ق شماره گذاری های 3ت زیرا طب 3ی نیس 3ه بحران ناحی شده است مسئله نیز به درستی رفع می گردد. بررسی شرط پیشرفت و عادالنه بودن آن : 3ی خود قرار می گیرد 3ش پایان 3ی شود و در بخ 3ی خارج م 3ه بحران 3ه از ناحی فرآیندی ک 3د ،وارد ناحیه 3ی نشده ان 3ه بحران 3ه هنوز وارد ناحی 3د گره های دیگری ک 3د اجازه ده بای بحرانی گردند و خودش دوباره تالش نکند .این مسئله به صورت زیر قابل حل است: 3ت می توان 3ن اس 3تفاده آ 3ه مورد اس 3ی ک 3ه بحران 3ه ناحی 3بت ب 3د و نس 3ر فرآین برای ه 3د بعد استفاده از ناحیه بحرانی شماره 3ن اینکه هر فرآین 3ی قائل شد و آ 3ت های محدودی خود(اولوی3ت خود) را پ3س داده و شماره ای دیگ3ر را بگیرد .در ای3ن حال3ت همه 3د او را قفل نمایند. 3د می توانن 3ن لحظه به بع 3ت از ای 3ت کننده در رقاب 3د های شرک فرآین 3ی استفاده 3ه بحران 3ر از ناحی 3د های درگی 3ه فرآین 3ا کلی 3د ت 3ی یاب 3ه م 3ی ادام 3ا زمان 3ن کار ت ای 3ی گردد با 3ت ایجاد م 3ه در درخ 3ن کار ک 3ی از ای 3ل ناش 3د و کارشان تمام شود.خل کنن همان ترفند اولیه که یاد شد برطرف می گردد. تحمل پذیری در برابر خطا 3د خراب شدن هر کدام از 3ی آی 3ش م 3ع شده پی 3یستم توزی 3ک س 3ه در ی 3ی ک 3کالت 3ن مش 3اسی تری اس 3ن الگوریتم کامال 3ه ای 3م ک 3ی دهی 3ان م 3ه نش 3ت .در ادام 3ر اس 3ا بدون اطالع گره های دیگ گره ه تحمل پذیر خطا بوده و در برابر خرابی گره ها خللی در روند کار ایجاد نمی گردد. ‏L=LOCK,FL=Free Lock,R=Request E=rEleas  گره هایی که خراب شود،دیگران چگونه مطلع می گردند 3ی بخواهد 3ر گره های 3ک گروه قرار دارد و اگ 3ل در ی 3ت حداق 3ه خراب شده اس 3ی ک گره های 3ف می 3ی را کش 3د خراب 3ت آورد و گره خراب شده در ان گروه باش 3ی را بدس 3ه بحران ناحی کند(شکل .)5 تفاوت سطح گره درخواست کننده با گره خراب شده بیشتر از یک سطح باشد 3ه بحرانی را نماید و گره دو خراب شود .گره 11خودش و گره 3ت ناحی مثال گره 11درخواس 3ت .طبق 3د گره 2خراب شده اس 3ی بین 3ه م 3ل گره 2را دارد ک 3د قف 3د و قص 3ی کن 3ل م 5را قف الگوریتم پیشنهادی باید گره 11جایگزین گره 2شود. مقایسه الگوریتم پیشنهادی با الگوریتم های موجود تعداد پیام در بدترین حالت تعداد پیام در بهترین حالت الگوریتم تحمMل پدیری در برابر خطا )n-1(2 ندارد ‏Recart&Agrawala تحمMل پدیری در برابر خطا )sqrt(n-1)(2 ندارد ‏Meakawa [(]2/)n+1 )logn-1(2 ‏El-Abbadi 3logn-3 )logn-1(2 الگوریتم پیشنهادیlampor نتیجه گیری در این الگوریتم نشان میدهیم که تعداد پیامهای ارسالی برای بدست آوردن ناحیه بحرانی،از 3ا می 3ا خراب شده فراینده 3ت و ب 3ا اس 3ر در برابر خط 3ل پذی 3م تحم 3ی بوده و الگوریت 3ه لگاریتم درج تواند دوباره بازسازی گردد و دیدیم که الگوریتم آزاد از بن بست و قحطی زدگی بود. سپاس از حضار محترم