بن بست توزیع شده

بن بست توزیع شده

اسلاید 1: بن بست توزیع شدهبلوکه شدن یک مجموعه از پروسس ها بخاطر دسترسی به منابع سیستم یا رد و بدل نمودن پیام با یکدیگرتعریف بن بست در سیستم های تکی برای سیستم های توزیع شده معتبر است.پیاده سازی بن بست توزیع شده بسیار پیچده تر است، زیرا گره ها از حالت سرتاسری سیستم اطلاعاتی ندارند. 1

اسلاید 2: انواع بن بست های توزیع شدهبن بست در اختصاص منابعچندین پروسس بخواهند به یک منبع دسترسی داشته باشند.بن بست در تبادل پیام هاهر پروسس در یک مجموعه منتظر پیام از پروسس های مجموعه دیگر است.هیچ پروسس در این حالت نمی توانند ارسال کنند، و هر کدام منتظر دیگری است. 2

اسلاید 3: بن بست در اختصاص منابعایجاد همزمان چهار شرط زیر باعث بن بست می شودانحصار متقابلHold and Waitمنابع انحصاری(No preemption)Circular Waitدر سیستم های توزیع شده پروسس کنترل کننده با دانش از نو حالت سرتاسری سیستم وجود ندارد. 3

اسلاید 4: پدیده بن بست فانتوم 4

اسلاید 5: راهکارهای مقابله با بن بستپیشگیری بن بست (Deadlock Prevention)اجتناب از بن بست(Deadlock Avoidance)شناسایی بن بست(Deadlock Detection) 5

اسلاید 6: پیشگیری بن بستبا نقض یکی از چهار شرط ذکر شده می توان از بن بست پیشگیری کنیم.بیشتر با حذف شرط های Circular-wait و Hold-and-wait از ایجاد بن بست جلوگیری می شود.حذف شرط انحصار متقابل برای دسترسی منابع غیر ممکن است. 6

اسلاید 7: پیشگیری بن بستمرتب سازی منابعاختصاص عدد منحصر بفرد به منابع سیستمیک پروسس در صورتی می تواند درخواست منبعی با شماره i را بدهد که منابع با شماره بالاتر i را در اختیار نداشته باشد.پیاده سازی در محیط توزیع شده ساده است و مقداری بالاسری دارد. 7

اسلاید 8: پیشگیری بن بست8روش مبتنی بر مهر زماناختصاص شماره های اختصاصی به پروسس هااولویت دهی به اعداد اختصاص داده شده با هر ترتیب مورد نظراگر Pi در خواست منبعی کند که در اختیار Pj باشد، در صورتی که اولویت Pi بیشتر از Pj باشد، آنگاه Pi منتظر می ماند، در غیر این صورت آن rolled-back می شود.روش جلوگیری از بن بست هابرای هر یال PiPj در گراف انتظار، Pi اولویت بالاتر از Pj دارد.بنابراین در گراف انتظار سیکلی نخواهیم نداشت.

اسلاید 9: پیشگیری بن بست9طرح Wait-Dieمبتنی بر تکنیک انحصاری است.اگر Pi در خواست منبعی کند که فعلا در اختیار Pj باشد، در صورتی که مهر زمان Pi کمتر از مهر زمان Pj باشد(Pi قدیمی تر از Pj است)، آن منتظر می ماند، در غیر این صورت Pi حذف یا rolled-back(Dies) می شود.مثال: فرض کنید پروسس های P1، P2 و P3 به ترتیب دارای مهر زمان 5، 10 و 15 باشند. اگر P1 در خواست منبعی کند که در اختیار P2 باشد، آن منتظر می ماند.اگر P3 در خواست منبعی کند که در اختیار P2 باشد، آن حذف می شود.

اسلاید 10: پیشگیری بن بست10طرح Wound-Waitمبتنی بر تکنیک غیرانحصاری است. نقطه مقابل روش Wait-Dieاگر Pi د خواست منبعی کند که در فعلا اختیار Pj باشد، در صورتی که مهر زمان Pi بیشتر از مهر زمان Pj باشد(Pi جوان تر از Pj است)، آن منتظر می ماند، در غیر این صورت Pj حذف یا rolled-back(Dies) می شود(Pj توسط Pi حذف می شود و منبع از آن گرفته می شود).مثال: فرض کنید پروسس های P1، P2 و P3 به ترتیب دارای مهر زمان 5، 10 و 15 باشند. اگر P1 در خواست منبعی کند که در اختیار P2 باشد، آنگاه منبع از P2 گرفته می شود و P2 حذف می شود.اگر P3 در خواست منبعی کند که در اختیار P2 باشد، آن منتظر می ماند.

اسلاید 11: پیشگیری بن بست11

اسلاید 12: اجتناب از بن بست12اجتناب از بن بست تکنیکی است که تصمیم گیری های خود را به صورت پویا و لحظه ای انجام می دهد. در این روش هر درخواست منبع توسط پروسس را بررسی می کند، آیا این در خواست مورد قبول است یا خیر؟پیاده سازی اجتناب از بن بست توزیع شده غیر ممکن است.هر گره باید حالت سرتاسری سیستم توزیع شده را دنبال کند.چک نمودن حالت امن سرتاسری توسط پروسس ها باید انحصار متقابل باشد.چک نمودن حالت امن سرتاسری بالاسری محاسبات بسیار زیادی دارد.

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

اسلاید 14: شناسایی بن بست14مثال 1 : گراف های انتظار محلی دو سایت S1 و S2

اسلاید 15: شناسایی بن بست15مثال 2 : گراف انتظار سرتاسری دو سایت S1 و S2 در مثال 1

اسلاید 16: شناسایی بن بست16روش های شناسایی بن بست توزیع شدهمتمرکز: یک سایت وظیفه شناسایی بن بست را بعهده دارد.سلسله مراتبی: سایت ها به صورت ساختار درختی بن بست را شناسایی می کنند.توزیع شده: تمامی پروسس ها در شناسایی بن بست با هم همکاری می کنند.

اسلاید 17: شناسایی بن بست17روش های شناسایی بن بست توزیع شده

اسلاید 18: شناسایی بن بست- روش متمرکز18هرسایت گراف انتظار محلی خود را ایجاد می کند.گراف انتظار سرتاسری در یک پروسس هماهنگ کننده ایجاد می شود.یکی از سه روش زیر برای ایجاد یا تغییر گراف انتظار سرتاسری ممکن است استفاده شود:موقعی که یال جدیدی به یکی از گراف های انتظار محلی اضافه شود یا یالی حذف شود.به صورت پریودیک، موقعی که تعدا مشخصی از تغییرات در گراف های انتظار محلی داشته باشیم.موقعی که گره هماهنگ کننده نیاز به الگوریتم شناسایی سیکل داشته باشد.

اسلاید 19: شناسایی بن بست- روش متمرکز19شناسایی بن بست برمبنای روش 3اضافه نمودن شناسگرهای منحصربفرد (مهرهای زمان) به در خواست های از سایت های مختلفموقعی که Pi از سایت A درخواست منبعی از Pj در سایت B می کند، یک پیام درخواست با مهر زمان TS ارسال می شود.یال PiPj با برچسب TS در گراف محلی سایت A اضافه می شود. اگر B پیام درخواست را دریافت نماید و نتواند بلافاصله به درخواست فوق پیام grant ارسال کند، یال فوق به گراف محلی سایت B اضافه می شود.

اسلاید 20: شناسایی بن بست- روش متمرکز20الگوریتم:گره هماهنگ کننده یک پیام آغازین به تمامی سایت ها ارسال می کند.هر سایت با دریافت پیام آغازین، گراف انتظار محلی خود را به گره هماهنگ کننده ارسال می کند.موقعی که گره هماهنگ کننده از تمامی سایت ها پاسخ دریافت نمود، گراف انتظار سرتاسری را به صورت زیر ایجاد می کند:ایجاد گراف انتظار سرتاسری، که هر گره آن به یک پروسس اختصاص داده می شود.گراف شامل یال PiPj است اگر و فقط اگریک یال PiPj در یکی از گراف های انتظار محلی داشته باشیم، یایک یال PiPj با تعدادی پرچسب TS در چند گراف انتظار محلی داشته باشیم.اگر گراف ایجاد شده سیکل داشته باشد، آنگاه سیستم در حالت بن بست قرار دارد.

اسلاید 21: شناسایی بن بست- روش متمرکز21مثال 3: گراف های انتظار محلی دو سایت و گراف انتظار سرتاسری ایجاد شده

اسلاید 22: شناسایی بن بست- روش سلسله مراتبی22

اسلاید 23: شناسایی بن بست- روش سلسله مراتبی23

اسلاید 24: شناسایی بن بست- روش توزیع شده کامل24الگوریتم:تمامی سایت ها مسئولیت یکسان در شناسایی بن بست دارند.هر سایت گراف انتظار محلی خود را ایجاد می کند که آن بخشی از گراف سرتاسری است.در این حالت یک گره اضافی Pex به هر گراف انتظار محلی اضافه می کنیم.PiPex : پروسس محلی Pi منتظر منبعی در سایت دیگر است که فعلا در اختیار پروسس دیگری باشد.PexPj: پروسسی از سایت دیگر منتظر گرفتن منبعی است که فعلا در اختیار پروسس محلی Pj است.اگر گراف انتظار محلی در یکی از سایت ها شامل سیکل بدون گره Pex باشد، در این حالت سیستم در حالت بن بست است.اگر گراف انتظار محلی شامل سیکل با گره Pex باشد، در این حالت سیستم احتمالا د ر حالت بن بست قرار دارد.برای اثبات اینکه سیستم در حالت بن بست است یا خیر، باید الگوریتم توزیعی شناسایی بن بست اجرا شود.

اسلاید 25: شناسایی بن بست- روش توزیع شده کامل25مثال 4: فرض کنید دو سایت S1 و S2 دو گراف انتظار محلی به صورت شکل زیر ایجاد نموده باشند. اگر شروع کننده شناسایی بن بست سایت S1 باشد، مراحل شناسایی بن بست را شرح دهید.

اسلاید 26: شناسایی بن بست- روش توزیع شده کامل26حل مثال 4:شناسایی سیکل PexP2P3Pex در سایت S1ارسال سیکل فوق به S2تغییر گراف انتظار محلی در سایت S2گراف جدید ایجاد شده به صورت شکل زیر است.

اسلاید 27: شناسایی بن بست- روش توزیع شده کامل27مثال 5: مثال 4 را برای حالتی تکرار کنید که شروع کننده سایت S2 باشد.حل:شناسایی سیکلPex PexP3P4P2 در سایت S2ارسال سیکل به S1تغییر گراف انتظار محلی

اسلاید 28: شناسایی بن بست- روش توزیع شده کامل28 

اسلاید 29: شناسایی بن بست- روش دوم توزیع شده29به ازای هر شئی داده(Data Object) دو پارامتر شناسگر منحصر بفرد Di و متغییر Locked_by(Di) تعریف می شود.به ازای هر تراکنش j چهار پارامتر زیر تعریف می شود:شناسگر منحصربفرد Tjمتغییر Held_by(Tj)متغییر Wait_for(Tj)صف Request_Q(Tj)

اسلاید 30: شناسایی بن بست- روش دوم توزیع شده30مثال 6: فرض کنید تراکنش T2 منتظر شئی داده ای است که در اختیار T1 است و T1 منتظر شئی داده ای است که در اختیار T0 است، جدول توزیعی پارامترهای تراکنش را بدست آورید.

اسلاید 31: شناسایی بن بست- روش دوم توزیع شده31شبه کد الگوریتم

اسلاید 32: شناسایی بن بست- روش دوم توزیع شده32مثال 7: در الگوریتم شناسایی بن بست توزیع شده، جدول زیر را با توجه شکل گراف تراکنش های داده شده کامل نمائید.اگر تراکنش T0 یک درخواست برای شئی داده (data-object) نگه داشته توسط T3 ارسال نماید، جدول تغییر یافته پارامترها را بدست آورید و نحوه ی تشخیص بن بست را در این الگوریتم شرح دهید.

اسلاید 33: شناسایی بن بست- روش دوم توزیع شده33حل مثال 7

اسلاید 34: بن بست در تبادل پیام ها34انواعبن بست انتظار متقابل و دو جانبهعدم دسترسی بافرهای پیام ها

اسلاید 35: بن بست در تبادل پیام ها-انتظار متقابل35بن بست انتظار متقابل در تبادل پیام موقعی رخ می دهد که هر کدام از عضوهای پروسس یک گروه منتظر پیام از عضو دیگر از همان گروه است و پیامی ارسال نمی شود.تعریف مجموعه وابستگی(DS)برای پروسس Pi که متوقف و منتظر دریافت پیام است، DS(Pi) شامل تمامی پروسس های است که از Pi انتظار دریافت حداقل یک پیام دارند.Pi در صورتی می تواند به کار خود ادامه دهد که حداقل یک پیام از مجموعه وابستگی DS(Pi) در یافت نماید.

اسلاید 36: بن بست در تبادل پیام ها-انتظار متقابل36بن بست در یک مجموعه پروسس های S را می توان به صورت زیر تعریف نمود:تمامی پروسس های مجموعه S متوقف و منتظر دریافت پیام(ها) هستند.مجموعه S شامل مجموعه های وابستگی تمامی پروسس ها با عضوهای مجموعه ی S است.پیامی بین عضوهای S ارسال نمی شود.

اسلاید 37: بن بست در تبادل پیام ها-انتظار متقابل37مثال 8: دو گراف انتظار داده شده در شکل زیر را در نظر بگیرید و بن بست تبادل پیام را بررسی نمایید.

اسلاید 38: بن بست در تبادل پیام ها-انتظار متقابل38حل مثال 8:در شکل(a) داریم: S={P1,P2,P3} ، DS(P1)={P5,P2} ، DS(P2)={P3} و DS(P3)={P. پروسس P1 منتظر دریافت پیام از P2 یا P5 است، چون P5 منتظر پیام نمی باشد و می تواند پیام به P1 ارسال کند، در نتیجه پیوند (P1,P5) و (P1,P2) حذف می شوند و بنابراین بن بست نداریم.در شکل(b) داریم: S={P1,P2,P3,P5} ، DS(P1)={P5,P2} ، DS(P2)={P3} و DS(P3)={P. در این شکل یک وابستگی اضافه می شود. در این حالت P5 منتظر پیام از P2، P2 منتظر پیام از P3، P3 منتظر پیام از P1 و P1 منتظر پیام از P2 است. در نتیجه در این شکل بن بست تبادل پیام خواهیم داشت.

اسلاید 39: بن بست در تبادل پیام ها-عدم دسترسی بافرهای پیام ها39عموماَ در شبکه های راهگزینی بسته ای وجود دارد.ساده ترین شکل بن بست شبکه های راهگزینی بسته ای، بن بست ذخیره سازی و انتشار به جلو (Store and forward) است.برای هر گره، صف گره مجاور در یک جهت با بسته های جهت ارسال به گره بعدی پر شده است.

اسلاید 40: بن بست مستقیم ذخیره سازی و انتشار به جلو40

اسلاید 41: بن بست غیر مستقیم ذخیره سازی و انتشار به جلو41برای هر گره، صف گره مجاور در یک جهت با بسته های جهت ارسال به گره بعدی پر شده است.

اسلاید 42: منبع بافر ساختیافته42منبع حافظه ی سطح صفر بدون محدودیت است و هر بسته ورودی می تواند در این سطح ذخیره شود.برای سطوح 1 تا N : (1) بافرهای سطوح 1 تا k برای بسته های با k گام (2) اگر تمامی بافرها تا سطح k پر شده باشند، بسته های رسیده با k گام یا کمتر حذف می شوند.