سیستم های عامل توزیع شده (بن بست)

صفحه 1:
سیستم های عامل توزیع شده Deadlock - cy ‏بن‎ 

صفحه 2:
مقدمه gio ‏رقابت پردازه های همروند در اختصاص یک‎ O ممدودیت متبع تا دنباله وقایع لازم برای استفاده یک پردازنده از یک منبع: 1- درفواست: ارائه درخواست. در صورت اختصاص قبلی منبع به پردازنده دیکر. قرار گرفتن در صف انتظار .... تا آزادی یکی از نوع منبع درخواستی ۲- اختصاص در اولین فرصت ممکن: نگهداری جدولی از وضعیت منبع ‎-p‏ آزاد ساژی: بروز آوری ساختمان داده های مدیریتی ‎ 

صفحه 3:
مقدمه - ادامه ۱ لا اختصاص توسط سیستم و دو فراخوانی ۲60۱65۴ و 6 توسط پردازنده ها انجام می شود. ‎a‏ چون تعداد منابع محدود است. باید مواظبت شجد سناریوهای درستی از اختصاص انجام شود. ‎Hf‏ چنین سناریوهایی ممکن است منجر به بن بست شود. 

صفحه 4:
مقدمه - ادامه ۲ ‎O‏ منظور از منبع * فیزیکی ""! منطقی : رکورد فایل - سمافور - ..) ‏تا منبع بایستی در هر لمظه توسط یک پردازه استفاده شود و ‎NON-preemptable‏ باشد. ‎ 

صفحه 5:
شرایط لازم براى بن بست لا شرط ممانعت دوجانبه: متقاضی بعدی باید منتظر بماند. ‎Wait by Oo‏ 6 ۳۱۵۱۵: درخواست منبع جدید بدون آزادی منابع فعلی که در اختیار دارد. ‎Lo No-Preemption bys O‏ مفتارانه منبع را آزاد ‏كند تا بتواند تخصيص يابد. لا شرط انتظار حلقوى ‎ 

صفحه 6:
مدل كردن بن بست لا استفاده از یک گراف جهت دار - دارای دو نوع نود و ‎a)‏ ‎Resource Allocation Graph‏ نود پردازه ها ‎a‏ نود منابع ‏۴ لبه اختصاص ‏* لبه درخواست ‏۲7 این کراف بصورت پویا تغییر می کند و در واقع به عنوان ابزاری برای کنترل بن بست استفاده می شود. ‎ ‎ 

صفحه 7:
شرایط لازم و کافی برای بن بست ۲ شرط لازم. مجود یک سیکل در گراف اختصاص منابع است, معهذا شرط کافی نیست. یعنی وجود سیکل شرط لازم است ولی کافی نیست. 

صفحه 8:
شرایط لازم و کافی برای بن بست - ادامه لآ شرط کافی در موارد مختلف متفاوت است: * اگر از هر منبع تنها یکی وجود داشته باشد وجود حلقه شرط لازم و کافی است. "1 اکر از هر منبع یکی یا بیشتر داشته باشیم شرط کافی برای بن بست يى ‎uw! Knot‏ تک تا فرم ساده شده گراف تخصیص منابع این است که منابع را از گراف حذف کنیم. ۳ ۱۷۷۳ ۴ وقتی از هر منبع تنها یکی داریم. می توان ۷۷/۴6 9 ومود ملقه در آن را شرط لازم و کاهی دانست. 

صفحه 9:
بن بست در سیستم توزیع شده لا مفهوم همان است 055 در محيط متمرکز ولی پیچیده تر ‎O‏ سه استراتژی ‎MF‏ اجتناب: اختصاص دقیق منابع * پیش گیری: اعمال محدودیت در روش درفواست منابع توسط پردازه ها * تشفیص و ترمیم تا در مواردی تمایز بین: ‎Resource Deadlock ™‏ ‎Orunysh x59 ys ylaiil sCommunication Deadlock @‏ بيغم 

صفحه 10:
اجتناب از بن بست لا اين دسته از روش هاء دانش قبلى از مصرف منابع توسط پردازه ها را براى ييش بينى استفاده مى كنند. 1] مرامل مفتلف * با رسیدن درخواست. هتی اگر منبع مومود است بلافاصله تخصیص نمی یابد. سیستم فرض می کند که منبع اختصاص یافته اسحد "" بررسی می شود که آیا تخصیص "امن" یا "نا امن" است. با توجه به اطلاع از روند کار پردازه) * نتیجه بررسی می گوید که اگر امن است. تخصیص انجام شود و در غیر این صورت. (زمانی که نا امن است) به تعویق افتد. 10 

صفحه 11:
امتناب از بن بست ‏ ادامه ۱ ‎O‏ اوضاع امن: ‏* اوضاع عارى از بن بست و ومود دنباله ای از منابع و تخصیص به پردازه ها وجود دارد که همه پردازه ها می توانند کار خود را تکمیل کنند. ممکن است دنباله های مختلفی چنین شرطی را برآورده سازند. بنابراین : دنباله امن (560۱/6۳6 68۴6) داریم. ‎Ml‏ شرط امن بودن دنباله: منابعی که , می تواند درخواست کندء با منابع موجود و منابع در اختیار پردازه های موجود در دنباله (قبل از ,۴) می تواند برآورده شود. ‎Sinha GUS). Jus * ‎11 ‎ 

صفحه 12:
اجتناب از بن بست - ادامه ۲ لا موارد: "" حالت اولیه امن است. (همه منبع آزاد هستند) 6 از یک حالت امن سیستم می تواند تضمین کند که همه پردازه ها می توانند تکمیل شوند. "1 یک حهالت نا امن. یک حالت بن بست. نیست بلکه ممکن است به بن بست بیانجامد. تضمینی ومود ندارد. لا هدف از اجتناب از بن بست. نگهداری و اطمینان از حالت ايمن سیستم است. 12 

صفحه 13:
اجتناب از بن بست - ادامه دلا لا از نظر تتورى جذاب ولى در مواردى غير عملى! ‎a‏ نبود اطلاع از نياز يردازه ها به منابع ‎a‏ ثابت نبودن تعداد پردازه های رقابت کننده برای منابع ‎a‏ ثابت نبودن تعداد منابع و امکان تغییر پویا * بر اساس بدترین حالت تصمیم گرفته می شود که در خیلی از موارد اتفاق نمی افتد. محدودیت های عملی+پیهیدگی هاى أضافه سیستم های توزیع شده استراتژی اجتناب از بن بست در محیط توزیع شده نداریم. 13 

صفحه 14:
جلوگیری از بن بست لا طراحى سيستم به كونه اى كه بن بست غير ممکن شود. هيج كونه تست زمان اجرا لازم نيست. لآ شرط بن بست اجتماع عا شرط: ‎Mutual-Exclusion ™‏ ‎Hold & Wait @‏ ‎No-Preemption 1#‏ ‎Circular-Wait !"‏ است. اگر یکی از اين ها نباشد بن بست ممکن نیست. لا بنابراين تلاش در عدم وجود یکی از این شرایط. 14 

صفحه 15:
جلوگیری از بن بست - ادامه ۱ لأ سه روش جلوگیری از بن بست: ‎Hold & Waityaa :Collective Requests 6‏ ‎Circular Waitysis Ordered Requests ®‏ ‎No-Preemptionsi :Preemption Requests ™‏ 15 

صفحه 16:
جلوگیری از بن بست - ادامه ۲ Collective Requests O ‏وقتی پردازه ای درخواست یک منبع می کند منبع دیگری در افتیار ندارد.‎ ‏وقتی پردازه ای شروع می شود باید همه منابع مورد نیازش را یکجا دریافت نماید. (یا‎ -۱ ‏همه و یا هیم لاند/۱)‎ ‏به تدريج برحسب نيازء ولی هرگاه یک منبع می خواهد: آزاد سازی منابع در اختیار و‎ -( ‏سپس درخواست مجدد برای قبلی ها به اضافه منبع جدید‎ :)(( ‏مزاياى اين روش‎ ‏سازكار با طبيعت پردازه ها در عدم اطلاع از كل منابع مورد نياز در ابتدا‎ 1 ‏لآ تخصيص منابع در موقع نياز - مثلا در انتهاى كار يردازه‎ sw O :)۲( ‏معایب این روش‎ ‏ری کم از منابع‎ O ‏قمطی برای پردازه هایی که منابع زیادی لازم دارند.‎ O ‏بالا رفتن هزینه پردازه: ۸0۱۳/39 بر مسب منابع تخصیص یافته‎ O 16 

صفحه 17:
جلوگیری از بن بست - ادامه ۳۲ ‎Ordered Requests 41‏ ‎Mf‏ هر نوع منبع یک شماره سراسری انمصاری دارد. هر بار یک درخواست از طرف هر پردازه ولی درخواست برای منبعی با شماره بزرگتر از آخرین منبع تخصیص یافته به آن پردازه و در حال استفاده. ‏"! درخواست برای چند منبع از یک نوع باید یک جا داده شود. ‎17 ‎ 

صفحه 18:
جلوكيرى از بن بست - ادامه عا ‎Preemption 0‏ * یک منبع مداخله پذیر (0۳66۳۵۵0۱6) منبعی است که ‎Ol ols‏ بتواند ذخیره شود و سپس بازیابی شود. ۱- اگر منبع مورد درخواست متقافی موجود نبود منابع تخصیص یافته فعلی به آن نیز گرفته شده و پردازه بلوکه می شود. ‏۲- اگر منبع درفواستی در اختیار پردازه بلوکه شده ای است از او گرفته شده و تخصیص می یابد و در غير اين صورت ‎Wait‏ ‏تا کارپرد ۳۲66۲۳۵10۳ محدود به منابع 2۲۳۵6۳۲۵۵016 است. ‎ ‎18 ‎ 

صفحه 19:
کشف بن بست - ۲۳6166110۳ ۱26601061 ‎Bae‏ کنترل بن بست و سپس راه هل هایی برای ترمیم ‏آن است. ‏* به طور كلى روش هاى تشخيص بن بست در سیستم های متمركز و توزيع شده يكى است. و مبتنى است بر نكهدارى منابع تخصیص يافته در قالب 6۳۵0۳ ‎Resource Allocation‏ و سپس کنترل حلقه. ‏"" به دلیل سادگی فرض می کنیم که از هر نوع منبع تنها یک دانه وجود دارد. ۳ ۷۷۲۵ معیار کار است. ‎19 ‎ 

صفحه 20:
كشف بن بست - ادامه لا مرامل بنای ۷۷۳6 در يك سيستم توزيع شده: لا مشکل اصلی نگهداری ۷۷۲۵ در یک سیستم توزیع شده است. در مورد درستی الگوریتم های تشخیص بن بست نیز صفاتی تعریف شده است: * پیشرفت (55ع۳۲۳۵9۲): بن بست باید در زمان متنامی تشخیص داده شود. "" سامت (62760۷): اگر بن بست تشفیص داده ‎«ai‏ واقعا ومود داشته باشد. تاخیر پیغامی ویا ۷۷۴6 های کهنه باعث وجود حلقه های نادرست می شوند. 

صفحه 21:
روش متمرکز برای تشخیص بن بست [] یک هماهنگ کننده محلی برای مدیریت ۷۷/۲ محلی و یک هماهنگ کننده مرکزی برای بنای ۷۷۳۵ سراسری تشخیص وجود حلقه در ۷۷۳6 محلی با هماهنگ کننده محلی * تشخیص وجود حلقه در ۷۷۴6 سراسری با هماهنگ کننده سراسری لآ ضرورت ارسال اطلاعات هماهنگ کننده های محلی به یکی از روش ‎ty) Slo‏ 1# هرگاه لبه ای اضافه یا مذف شد. "1 بطور پریودیک ارسال مابه التفاوت ۷۷۴۵ جدید با آخرین حالت ارسال شده قبلی 1# حسب درخواست هماهنگ کننده مرگزی لا عدم دریافت پیغام های هماهنگ کننده های محلی باعث رخداد بن بست کاذب ۱۱۱ 21 

صفحه 22:
روش سلسله مراتبی برای تشخیص بن بست لا تجربیات نشان می دهد که 79۰ بن بست ها شامل فقط ۲ پردازه هستند. ‎cae‏ سوه ‎Es‏ ‎ 

صفحه 23:
روش سلسله مراتبی برای تشخیص بن بست - ادامه لا درفتی از تشخیص دهنده های بن بست (کنترلرها) تشکیل می شود و سپس هر کنترلر مسئول تشخیص در ناهیه پایین دست خود است. نودهای برگ ۷۷۲ محلی خود را دارند. 6 نودهای غیربرگ, اتمادی از ۳6 ۷۷های فرزندان خود را نگه می دارد. 23 

صفحه 24:
روش کاملا توزیع شده در تشخیص بن بست لأ هر سايت سهم یکسانی با دیگر سایت ها دارد. روش های مختلفی وجود دارند که در این جا به دو روش زیر خواهیم پرداخت: ‎WFG-based 6‏ ‎Probe-based 6‏ 24 

صفحه 25:
WFG-based ‏روش‎ لا ارائه شده توسط 51106۳56012 و 62/۷15 در 1999 لا تغيير يافته اى از روش محلى نكهدارى ۷۷۴۵ که در آن یک نود بی۴ به گراف اضافه شده است. همچنین: © ببه بی۳,) به ۷۷۳6۵ اضافه می شود اگر ,۳ منتظر منبعی در دیگر سایت. ها باشد که توسط پردازه ای تخصیص يافته است. 1# ليه ‎Pi‏ می؟) به )۷۷۳ اضافه مى شود اگر م (پردازه خارجی) منتظر منبعى باشد كه توسط يك پردازه محلی در حال استفاده است. 25 

صفحه 26:
د پردازه لی‌مریوط به ر5 لستقه | | ,۴ منتظر منبعی‌در رو منتظر منبعرملسحقه در مللستفادم لستقه بوسيله رط در | توسطءظ (يردازه محلئ لست هلزإستفاده لست @ \p A رط يردازه لى در ,5 لست که منتظر بط (پردازم | ۷۷۴6 پ-ساز لفزودم,۴ ۳ \ ۳ منتظر منبعی‌لستقه در رس ایک 5 :5 (به وسیله ر۳) لست 6 پساز لفزودن ,۴ 26 \ 1/< سايكة 5 

صفحه 27:
روش ۷۷۳۵-0۵560 - روش تشفیص بن بست لا ذكر ۷۷۲6۵ محلی حلقه ای داشته باشد (بدون بی۳) که بن بست مهلی رخ حلده است. لا 351 ۷۷۲6۵ محلی شامل حلقه ای با حضور ,0 باشد لمتمال دارد بن بست توزیع شده داشته باشیم. بدین منظور, الگوریتم تشخيص بن بست را آغاز می کند. 1 در صورت وجود حلقه در سایت ,5 خواهیم داشت: ] که به معنای انتظار ,۴ برای منبعی خارجی (متعلق به سایت ر5) است. ,5 > پیفام تشخیص بن بست به ,5 می فرستد. پیغام هاوی بفش هلقه دار انالا فواهد بود. مثلا لي ,رط روط روط ريى2) از رك به ر5. 27 

صفحه 28:
روش ۷۷۳۵-۵۵560 - روش تشخیص بن بست - ادامه ۱ ۴ با رسیدن پیغام . ۰۷۷۴6 ر5 خود را به روز می آورد. لا افزودن له های غیر از لبه های پم 6 در ر5 که حلقه ای بدون ‎Pa,‏ دارد و لذا بن بست وجود دا "" در عین حال حلقله ای وجود دارد شامل ۱۳ و لذا 5 پیغامی را برای سایت مربوطه = می فرستد و رویه بالا تکرلبصی شود. Hee MT ۱ 1 پس از مدتی یا بن بست تشفیص داده 1 لذ ۱ می شود . یا الگوریتم خاتمه می یابد. 7 = ~ 28 

صفحه 29:
روش ۷۷۳۵-۵۵560 - روش تشخیص بن بست - ادامه ۲ لا نکته: دو سایت ممکن است بطور مستقل الگوریتم تشفیص بن بست را برای پردازه های یکسانی آغاز کنند. مثلا ,5و ر5 ممکن است حلقه هاى ‎(Pox P3,Po,Pr,Pex)‏ 9 لوبو طنوطيو5) ۱ در ۷۷۳6 محلی خود تشخیص دهند و پیغامی را سایت دیگر بفرستند. ح-ه7ده6 ۷۷۳ خود را بروز رسانیده و مکانیزم ترمیم را آغاز می کنند که: ممكن است به کشته شدن پرداژه های (یادتر از مد لزم بیانمامد + سربار پیضامی لآ یک راه مل: اختصاص ۱2 انمصاری به هر پردازه و سپس ارسال چیغام تشخیص بن بست منوط به اينكه ‎(PoeP),P,,---1P,,P.,) 2 Mbb ID(P,)<ID(P,)‏ زاین 29 

صفحه 30:
الگوریتم مبتنی بر ۲۲۳۵0 ‎CMH (Chandy-Misra-Hass) a jggiin0 1‏ 9 مربوط به سال ۱۹۸۳ و شهرت به عنوان بهترین. ‏۲ ارسال ۴۲۵6 به سایت دارنده منبع و انتشار آن به دیگر سایت ها توسط گيرنده. اگر پیغام به ارسال کننده ‎Probe aslo!‏ رسید معلوم می شود که بن بست رخ داده است. ‎ 

صفحه 31:
ترمیم از بن بست لا درخواست از اپراتور برای دخالت "1 نا مناسب براى سيستم هاى امروزى (حتى متمركز) )> gilo ¢sjlw sij1 9 (Termination) ‏ختم یک یا چند پردازه‎ oO ‏اختیار‎ ل انتفاب قربانن << مداقل هزینه ترمیم لا جلوكيرى از قمطى ۲7 بازگشت پردازه ها (80۱۱0۵61) * پردازه ها نقطه مقابله می سازند (تصویر حافظه پردازه و لیستی از منابع در اختیار) > به جای اختتام. تا هدی به عقب برمی گردیم تا دیگر بن بست نباشد. 31