بن بست

بن بست

اسلاید 1: 1سیستم های عامل توزیع شدهبن بست – Deadlock

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

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

اسلاید 4: 4مقدمه – ادامه 2منظور از منبعفیزیکیمنطقی : رکورد فایل – سمافور - ...منبع بایستی در هر لحظه توسط یک پردازه استفاده شود و non-preemptable باشد.منبع اختصاص یافته را نمی توان آزاد کرد مگر با درخواست مالک فعلی آن.

اسلاید 5: 5شرایط لازم برای بن بستشرط ممانعت دوجانبه: متقاضی بعدی باید منتظر بماند.شرط Hold & Wait: درخواست منبع جدید بدون آزادی منابع فعلی که در اختیار دارد.شرط No-Preemption: مالک مختارانه منبع را آزاد کند تا بتواند تخصیص یابد.شرط انتظار حلقویدر صورت برقرار بودن 4 شرط بالا بن بست رخ می دهد.

اسلاید 6: 6مدل کردن بن بستاستفاده از یک گراف جهت دار - دارای دو نوع نود و لبه Resource Allocation Graphنود پردازه هانود منابعلبه اختصاصلبه درخواستاین گراف بصورت پویا تغییر می کند و در واقع به عنوان ابزاری برای کنترل بن بست استفاده می شود.

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

اسلاید 8: 8شرایط لازم و کافی برای بن بست - ادامهشرط کافی در موارد مختلف متفاوت است:اگر از هر منبع تنها یکی وجود داشته باشد وجود حلقه شرط لازم و کافی است.اگر از هز منبع یکی یا بیشتر داشته باشیم شرط کافی برای بن بست یک Knot است.فرم ساده شده گراف تخصیص منابع این است که منابع را از گراف حذف کنیم. WFG وقتی از هر منبع تنها یکی داریم، می توان WFG و وجود حلقه در آن را شرط لازم و کافی دانست.مجموعه K نودی که در آن مجموعه قابل دسترس همه نودهای کل مجموعه باشد.

اسلاید 9: 9بن بست در سیستم توزیع شدهمفهوم همان است که در محیط متمرکز ولی پیچیده ترسه استراتژیاجتناب: اختصاص دقیق منابعپیش گیری: اعمال محدودیت در روش درخواست منابع توسط پردازه هاتشخیص و ترمیمدر مواردی تمایز بین:Resource DeadlockCommunication Deadlock: انتظار در بلاک برای رسیدن پیغامحالت ساده ای از بن بست منابع است.WFG

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

اسلاید 11: 11اجتناب از بن بست - ادامه 1اوضاع امن: اوضاع عاری از بن بست و وجود دنباله ای از منابع و تخصیص به پردازه ها وجود دارد که همه پردازه ها می توانند کار خود را تکمیل کنند. ممکن است دنباله های مختلفی چنین شرطی را برآورده سازند. بنابراین : دنباله امن (Safe Sequence) داریم.شرط امن بودن دنباله: منابعی که Pi می تواند درخواست کند، با منابع موجود و منابع در اختیار پردازه های موجود در دنباله (قبل از Pi) می تواند برآورده شود.مثال در کتاب Sinha

اسلاید 12: 12اجتناب از بن بست - ادامه 2موارد:حالت اولیه امن است. (همه منبع آزاد هستند)از یک حالت امن سیستم می تواند تضمین کند که همه پردازه ها می توانند تکمیل شوند.یک حالت نا امن، یک حالت بن بست نیست بلکه ممکن است به بن بست بیانجامد. تضمینی وجود ندارد.هدف از اجتناب از بن بست، نگهداری و اطمینان از حالت امن سیستم است.

اسلاید 13: 13اجتناب از بن بست - ادامه 3از نظر تئوری جذاب ولی در مواردی غیر عملی!نبود اطلاع از نیاز پردازه ها به منابعثابت نبودن تعداد پردازه های رقابت کننده برای منابعثابت نبودن تعداد منابع و امکان تغییر پویابر اساس بدترین حالت تصمیم گرفته می شود که در خیلی از موارد اتفاق نمی افتد.محدودیت های عملی+پیچیدگی های اضافه سیستم های توزیع شدهاستراتژی اجتناب از بن بست در محیط توزیع شده نداریم.

اسلاید 14: 14جلوگیری از بن بستطراحی سیستم به گونه ای که بن بست غیر ممکن شود. هیچ گونه تست زمان اجرا لازم نیست.شرط بن بست اجتماع 4 شرط:Mutual-ExclusionHold & WaitNo-PreemptionCircular-Waitاست. اگر یکی از این ها نباشد بن بست ممکن نیست.بنابراین تلاش در عدم وجود یکی از این شرایط.

اسلاید 15: 15جلوگیری از بن بست – ادامه 1سه روش جلوگیری از بن بست:Collective Requests: نقض Hold & WaitOrdered Requests: نقض Circular WaitPreemption Requests: نقض No-Preemption

اسلاید 16: 16جلوگیری از بن بست – ادامه 2Collective Requestsوقتی پردازه ای درخواست یک منبع می کند، منبع دیگری در اختیار ندارد.1- وقتی پردازه ای شروع می شود باید همه منابع مورد نیازش را یکجا دریافت نماید. (یا همه و یا هیچ[wait])2- به تدریج برحسب نیاز، ولی هرگاه یک منبع می خواهد: آزاد سازی منابع در اختیار و سپس درخواست مجدد برای قبلی ها به اضافه منبع جدیدمزایای این روش (2):سازگار با طبیعت پردازه ها در عدم اطلاع از کل منابع مورد نیاز در ابتداتخصیص منابع در موقع نیاز – مثلا در انتهای کار پردازهسادگیمعایب این روش (2):بهره وری کم از منابعقحطی برای پردازه هایی که منابع زیادی لازم دارند.بالا رفتن هزینه پردازه: Accounting بر حسب منابع تخصیص یافته

اسلاید 17: 17جلوگیری از بن بست – ادامه 3Ordered Requestsهر نوع منبع یک شماره سراسری انحصاری دارد. هر بار یک درخواست از طرف هر پردازه ولی درخواست برای منبعی با شماره بزرگتر از آخرین منبع تخصیص یافته به آن پردازه و در حال استفاده.درخواست برای چند منبع از یک نوع باید یک جا داده شود.

اسلاید 18: 18جلوگیری از بن بست – ادامه 4Preemptionیک منبع preemption منبعی است که حالت آن بتواند ذخیره شود و سپس بازیابی شود.1- اگر منبع مورد درخواست متقاضی موجود نبود، منابع تخصیص یافته فعلی به آن نیز گرفته شده و پردازه بلوکه می شود.2- اگر منبع درخواستی در اختیار پردازه بلوکه شده ای است از او گرفته شده و تخصیص می یابد و در غیر این صورت Waitکاربرد Preemption محدود به منابع Preemptable است.

اسلاید 19: 19کشف بن بست - Deadlock Detectionهدف کنترل بن بست و سپس راه حل هایی برای ترمیم آن است.به طور کلی روش های تشخیص بن بست در سیستم های متمرکز و توزیع شده یکی است و مبتنی است بر نگهداری منابع تخصیص یافته در قالب Resource Allocation Graph و سپس کنترل حلقه.به دلیل سادگی فرض می کنیم که از هر نوع منبع تنها یک دانه وجود دارد. WFG معیار کار است.

اسلاید 20: 20کشف بن بست – ادامهمراحل بنای WFG در یک سیستم توزیع شده:مشکل اصلی نگهداری WFG در یک سیستم توزیع شده است.در مورد درستی الگوریتم های تشخیص بن بست نیز صفاتی تعریف شده است:پیشرفت (Progress): بن بست باید در زمان متناهی تشخیص داده شود.سلامت (Safety): اگر بن بست تشخیص داده شد، واقعا وجود داشته باشد. تاخیر پیغامی و یا WFG های کهنه باعث وجود حلقه های نادرست می شوند. 1- بنای یک RAG جداگانه برای کل منابع محلی هر سایت. پردازه ها ممکن است محلی و یا غیر محلی باشند.2- بنای WFG متناظر با حذف نود مربوط به منابع3- ترکیب WFG های محلی و بنای یک WFG سراسری

اسلاید 21: 21روش متمرکز برای تشخیص بن بستیک هماهنگ کننده محلی برای مدیریت WFG محلی و یک هماهنگ کننده مرکزی برای بنای WFG سراسریتشخیص وجود حلقه در WFG محلی با هماهنگ کننده محلیتشخیص وجود حلقه در WFG سراسری با هماهنگ کننده سراسریضرورت ارسال اطلاعات هماهنگ کننده های محلی به یکی از روش های زیر:هرگاه لبه ای اضافه یا حذف شد.بطور پریودیک ارسال مابه التفاوت WFG جدید با آخرین حالت ارسال شده قبلیحسب درخواست هماهنگ کننده مرکزیعدم دریافت پیغام های هماهنگ کننده های محلی باعث رخداد بن بست کاذب !!!

اسلاید 22: 22روش سلسله مراتبی برای تشخیص بن بستتجربیات نشان می دهد که 90% بن بست ها شامل فقط 2 پردازه هستند.وجود یک سایت مرکزی سربار زیادی دارد چرا که پیغام باید بین همه سایت ها مبادله شود.مناسب است که بن بست در محدوده جغرافیایی کوچکتری تشخیص داده شود.

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

اسلاید 24: 24روش کاملا توزیع شده در تشخیص بن بستهر سایت سهم یکسانی با دیگر سایت ها دارد. روش های مختافی وجود دارند که در این جا به دو روش زیر خواهیم پرداخت:WFG-basedProbe-based

اسلاید 25: 25روش WFG-basedارائه شده توسط Silberschotz و Galvin در 1999تغییر یافته ای از روش محلی نگهداری WFG که در آن یک نود Pex به گراف اضافه شده است. همچنین:لبه (Pi,Pex) به WFG اضافه می شود اگر Pi منتظر منبعی در دیگر سایت ها باشد که توسط پردازه ای تخصیص یافته است.لبه (Pex, Pj) به WFG اضافه می شود اگر Pj (پردازه خارجی) منتظر منبعی باشد که توسط یک پردازه محلی در حال استفاده است.

اسلاید 26: 26مثال:PexP4P3P2P1PexP3P5P1ABA’B’WFG در سایت S1WFG پس از افزودن PexP1 منتظر منبعی در S2 است که بوسیله P3 در حال استفاده است.P3 پردازه ای مربوط به S2 است که منتظر منبعی است که در حال استفاده توسط P2 (پردازه محلی) است. P1 پردازه ای در S1 است که منتظر P3 (پردازه محلی) است.P3 منتظر منبعی است که در S1 (به وسیله P2) است. WFG در سایت S2WFG پس از افزودن Pex

اسلاید 27: 27روش WFG-based – روش تشخیص بن بستاگر WFG محلی حلقه ای داشته باشد (بدون Pex) که بن بست محلی رخ داده است.اگر WFG محلی شامل حلقه ای با حضور Pex باشد احتمال دارد بن بست توزیع شده داشته باشیم. بدین منظور، الگوریتم تشخیص بن بست را آغاز می کند.در صورت وجود حلقه در سایت Si خواهیم داشت :(Pex,Pi,Pj,…,Pk,Pex)که به معنای انتظار Pk برای منبعی خارجی (متعلق به سایت Sj) است.  Si پیغام تشخیص بن بست به Sj می فرستد. پیغام حاوی بخش حلقه دار WFG خواهد بود. مثلا (Pex,P3,P2,P1,Pex) از S1 به S2.

اسلاید 28: 28روش WFG-based – روش تشخیص بن بست – ادامه 1با رسیدن پیغام ، Sj ، WFG خود را به روز می آورد. افزودن لبه های غیر از لبه های Pexدر S2 که حلقه ای بدون Pex دارد و لذا بن بست وجود دارد. در عین حال حلقله ای وجود دارد شامل Pex ! و لذا Sj پیغامی را برای سایت مربوطه می فرستد و رویه بالا تکرار می شود.پس از مدتی یا بن بست تشخیص دادهمی شود . یا الگوریتم خاتمه می یابد.PexP3P5P1P2

اسلاید 29: 29روش WFG-based – روش تشخیص بن بست – ادامه 2نکته: دو سایت ممکن است بطور مستقل الگوریتم تشخیص بن بست را برای پردازه های یکسانی آغاز کنند. مثلا S1 و S2 ممکن است حلقه های (Pex,P3,P2,P1,Pex) و (Pex,P1,P3,Pex)را در WFG محلی خود تشخیص دهند و پیغامی را سایت دیگر بفرستند. هر دو WFG خود را بروز رسانیده و مکانیزم ترمیم را آغاز می کنند که: ممکن است به کشته پردازه های زیادتر از حد لازم بیانجامد + سربار پیغامییک راه حل: اختصاص ID انحصاری به هر پردازه و سپس ارسال پیغام تشخیص بن بست منوط به اینکه ID(Pk)<ID(Pi) باشد در (Pex,Pi,Pj,…,Pk,Pex)

اسلاید 30: 30الگوریتم مبتنی بر Probeمشهور به CMH (Chandy-Misra-Hass) و مربوط به سال 1983 و شهرت به عنوان بهترین.ارسال Probe به سایت دارنده منبع و انتشار آن به دیگر سایت ها توسط گیرنده. اگر پیغام به ارسال کننده اولیه Probe رسید معلوم می شود که بن بست رخ داده است.

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