بن بست

بن بست

اسلاید 1: دکتر جلیلی - مفاهیم سیستم عامل دانشکده ی کامپیوتر- دانشگاه صنعتی شریفاسلایدهای فصل هفتم کتاب سیلبرشاتزدانشکده مهندسی کامپیوتردانشگاه شریف بن بست

اسلاید 2: دکتر جلیلی - مفاهیم سیستم عامل دانشکده ی کامپیوتر- دانشگاه صنعتی شریفمروری بر عناوین مطالبمساله بن بستمشخصه های بن بستروش های برخورد با بن بستپیشگیری از بن بستاجتناب از بن بستکشف بن بستترمیم از بن بستروش های ترکیبی برای برخورد با بن بست

اسلاید 3: دکتر جلیلی - مفاهیم سیستم عامل دانشکده ی کامپیوتر- دانشگاه صنعتی شریفمروری بر اهداف فصلآشنایی با مفهوم بن بست که مانع از انجام کار یک یا چندین پردازه می شود آشنایی با روش های مختلف مقابله با بن بست

اسلاید 4: دکتر جلیلی - مفاهیم سیستم عامل دانشکده ی کامپیوتر- دانشگاه صنعتی شریفیک مجموعه از پردازه ها در حالت بن بست هستند اگر هر یک از پردازه ها منبعی را در اختیار داشته باشند و منتظر منبع دیگری باشند که در اختیار پردازه ای دیگر در همین مجموعه است.نمونه: دو سمافور A و B با مقدار اولیه 1 P0 P1wait (A);wait(B)wait (B);wait(A)نمونه: پل میان گذرعرض پل به اندازه ای است که اجازه عبور یک ماشین را می دهد.مساله بن بست

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

اسلاید 6: دکتر جلیلی - مفاهیم سیستم عامل دانشکده ی کامپیوتر- دانشگاه صنعتی شریفمنابع سیستم از انواع مختلف R1, R2, . . ., Rm هستند.قطعه های زمانی پردازنده، فضای حافظه، ابزارهای خواندن / نوشتن، ...از هر منبع Ri ، Wi تا داریم.هر پردازه از هر منبع با رعایت توالی اعمال زیر بهره برداری می کند:درخواستاستفادهرهاسازیمدل سیستم

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

اسلاید 8: دکتر جلیلی - مفاهیم سیستم عامل دانشکده ی کامپیوتر- دانشگاه صنعتی شریفبرای رخ دادن بن بست برقراری همزمان چهار شرط زیر الزامی است:ممانعت دوجانبه (Mutual Exclusion): در هر زمان تنها یک پردازه می تواند از یک منبع استفاده کند.نگهدار و منتظر بمان (Hold and Wait): پردازه ای که حداقل یک منبع در اختیار دارد، منتظر است تا منابع دیگری که در اختیار پردازه های دیگر است نیز بگیرد.عدم پیشدستی (No Preemption): هر منبعی تنها پس از پایان کار پردازه ای که آن را در اختیار گرفته است و به صورت داوطلبانه توسط همان پردازه قابل رهاسازی است.مشخصه های بن بست

اسلاید 9: دکتر جلیلی - مفاهیم سیستم عامل دانشکده ی کامپیوتر- دانشگاه صنعتی شریفمشخصه های بن بست (ادامه)انتظار حلقوی (Circular Wait): مجموعه ای مانند {P0, P1, …, Pn} وجود دارد به گونه ای که P0 منتظر منبعی است که در اختیار P1 قرار دارد، P1 منتظر منبعی است که در اختیار P2 قرار دارد، ... ، و Pn منتظر منبعی است که در اختیار P0 قرار دارد.گرچه وقوع همزمان هر چهار شرط برای وقوع بن بست الزامی است، اما این شرایط کاملا از هم مستقل نیستند.برای مثال شرط «انتظار حلقوی»، شرط «نگهدار و منتظر بمان» را نتیجه می دهد.

اسلاید 10: دکتر جلیلی - مفاهیم سیستم عامل دانشکده ی کامپیوتر- دانشگاه صنعتی شریفگراف تخصیص منابع به صورت مجموعه رئوس V و مجموعه یال های جهت دار E تعریف می شود.دو نوع راس: پردازه ها و نوع منابع P = {P1, P2, …, Pn} مجموعه همه پردازه های سیستم R = {R1, R2, …, Rm} مجموعه همه انواع منابع سیستمهر یال جهت دار نشانگر درخواست یا اختصاص منبعدرخواست منبع: P1  Rjاختصاص منبع: Rj  Piگراف تخصیص منابع

اسلاید 11: دکتر جلیلی - مفاهیم سیستم عامل دانشکده ی کامپیوتر- دانشگاه صنعتی شریفگراف تخصیص منابع (ادامه)پردازه:نوع منبع با چهار نمونه: Pi یک نمونه از Rj را تقاضا می کند: Pi یک نمونه از Rj را در اختیار دارد:PiPiRjRj

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

اسلاید 13: دکتر جلیلی - مفاهیم سیستم عامل دانشکده ی کامپیوتر- دانشگاه صنعتی شریفگراف تخصیص منابع (با حلقه و بن بست)

اسلاید 14: دکتر جلیلی - مفاهیم سیستم عامل دانشکده ی کامپیوتر- دانشگاه صنعتی شریفگراف تخصیص منابع (با حلقه و بدون بن بست)

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

اسلاید 16: دکتر جلیلی - مفاهیم سیستم عامل دانشکده ی کامپیوتر- دانشگاه صنعتی شریفمروری بر عناوین مطالبمساله بن بستمشخصه های بن بستروش های برخورد با بن بستپیشگیری از بن بستاجتناب از بن بستکشف بن بستترمیم از بن بستروش های ترکیبی برای برخورد با بن بست

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

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

اسلاید 19: دکتر جلیلی - مفاهیم سیستم عامل دانشکده ی کامپیوتر- دانشگاه صنعتی شریفمروری بر عناوین مطالبمساله بن بستمشخصه های بن بستروش های برخورد با بن بستپیشگیری از بن بستاجتناب از بن بستکشف بن بستترمیم از بن بستروش های ترکیبی برای برخورد با بن بست

اسلاید 20: دکتر جلیلی - مفاهیم سیستم عامل دانشکده ی کامپیوتر- دانشگاه صنعتی شریفبرای پیشگیری از بن بست، باید یکی از شروط چهارگانه را نقض کرد.1.ممانعت دوجانبهاگر منبع قابل به اشتراک گذاری باشد (مانند یک پرونده فقط خواندنی) می توان در مورد آن از شرط ممانعت دوجانبه صرف نظر کرد.در حالت کلی این شرط قابل نقض نیست، چون ماهیت بسیاری از منابع (مانند چاپگر) وجود این شرط را الزامی می کند.پیشگیری از بن بست

اسلاید 21: دکتر جلیلی - مفاهیم سیستم عامل دانشکده ی کامپیوتر- دانشگاه صنعتی شریفپیشگیری از بن بست (ادامه)2.نگهدار و منتظر بمانبرای نقض این شرط هر پردازه تنها باید در صورتی تقاضای یک منبع را بکند که هیچ منبع دیگری در اختیار نداشته باشد.پردازه دو راه برای درخواست منبع دارد. یا باید همه منابع مورد نیاز خود را در ابتدای اجرای خود به صورت یکجا درخواست کند یا باید همه منابع در اختیار را آزاد کرده و سپس تقاضای منبع جدید کند.بهره وری منابع در این روش پایین است و احتمال قحطی نیز وجود دارد.

اسلاید 22: دکتر جلیلی - مفاهیم سیستم عامل دانشکده ی کامپیوتر- دانشگاه صنعتی شریفپیشگیری از بن بست (ادامه)3.عدم پیشدستیبرای نقض این شرط می توان به سیستم عامل اجازه داد تا در صورت لزوم پیشدستی کرده و خود منابع در اختیار پردازه را آزاد کند.در صورتی که پردازه ای تقاضای منبع کرد و اختصاص منبع امکان پذیر نبود، سیستم عامل می تواند تمام منابع در اختیار پردازه متقاضی را آزاد کند.منابع آزادشده به لیست منابع مورد تقاضای پردازه افزوده می شوند.اجرای پردازه وقتی از سر گرفته می شود که پردازه بتواند منبع مورد نیاز و تمام منابع آزاد شده قبلی را در اختیار بگیرد.

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

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

اسلاید 25: دکتر جلیلی - مفاهیم سیستم عامل دانشکده ی کامپیوتر- دانشگاه صنعتی شریفدر این رهیافت سیستم تلاش می کند تا با استفاده از یک دانش قبلی درباره رفتار پردازه ها مانع از وقوع بن بست شود.رهیافت «پیشگیری از بن بست» بر نقض شرایط پیش نیازی وقوع بن بست و رهیافت «اجتناب از بن بست» بر نظارت مداوم و بررسی امکان یا عدم امکان وقوع بن بست تمرکز دارند.در ساده ترین و مفیدترین روش موجود هر پردازه قبل از شروع اجرا باید نوع و حداکثر تعداد منابع مورد نیاز از هر نوع را اعلان کند.اجتناب از بن بست

اسلاید 26: دکتر جلیلی - مفاهیم سیستم عامل دانشکده ی کامپیوتر- دانشگاه صنعتی شریفالگوریتم اجتناب از بن بست به صورت پویا حالت تخصیص منابع را بررسی می کند تا تضمین کند هیچ گاه انتظار حلقوی اتفاق نمی افتد.حالت تخصیص منابع از منابع موجود و تخصیص داده شده و همچنین حداکثر تقاضای پردازه ها برای هر نوع منبع تشکیل شده است.وقتی پردازه ای تقاضای اختصاص یک منبع موجود را می کند، سیستم باید تصمیم بگیرد که آیا اختصاص فوری منبع به پردازه سیستم را در حالت امن نگاه می دارد یا خیر؟حالت تخصیص منابع و حالت امن

اسلاید 27: دکتر جلیلی - مفاهیم سیستم عامل دانشکده ی کامپیوتر- دانشگاه صنعتی شریفحالت امنسیستم در حالت امن است در صورتی که یک ترتیب امن از پردازه ها وجود داشته باشد.ترتیب <P1, P2, …, Pn> یک ترتیب امن است در صورتی که برای هر Pi، منابعی که Pi می تواند تقاضا کند زیرمجموعه ای از منابع موجود و منابع در اختیار Pj ها باشد ( j < i).اگر منابع مورد نیاز Pi همه فراهم نیستند، Pi می تواند تا پایان تمام Pj ها که منابع مورد نیاز را در اختیار دارند صبر کند.وقتی منابع آماده شد، Pi می تواند آنها را در اختیار بگیرد، اجرا شود و سپس منابع در اختیار را آزاد کند.وقتی Pi پایان یافت، Pi+1 می تواند اجرا شود و به همین صورت اجرا ادامه می یابد.

اسلاید 28: دکتر جلیلی - مفاهیم سیستم عامل دانشکده ی کامپیوتر- دانشگاه صنعتی شریفاگر سیستم در یک حالت امن است ...سیستم بن بست ندارد.اگر سیستم در یک حالت ناامن است ...ممکن است بن بست رخ داده باشد.اجتناب از بن بست تضمین می کند سیستم هیچ گاه وارد یک حالت ناامن نشود.معیار تشخیص اولیه

اسلاید 29: دکتر جلیلی - مفاهیم سیستم عامل دانشکده ی کامپیوتر- دانشگاه صنعتی شریفامنیت – عدم امنیت و بن بست

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

اسلاید 31: دکتر جلیلی - مفاهیم سیستم عامل دانشکده ی کامپیوتر- دانشگاه صنعتی شریفاجزای الگوریتم:وقتی ممکن است پردازه Pi منبع Rj را تقاضا کند، یک یال خواسته (claim edge) به صورت خط چین بین رئوس مربوطه می کشیم.وقتی پردازه منبع را درخواست می کند، یال خواسته به یال تقاضای منبع تبدیل می شود.وقتی پردازه منبع را آزاد می کند، یال تخصیص به یال خواسته تبدیل می شود.منابع مورد نیاز باید از قبل از سیستم خواسته شوند.الگوریتم گراف تخصیص منابع

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

اسلاید 33: دکتر جلیلی - مفاهیم سیستم عامل دانشکده ی کامپیوتر- دانشگاه صنعتی شریفحالت ناامن در گراف تخصیص منابع

اسلاید 34: دکتر جلیلی - مفاهیم سیستم عامل دانشکده ی کامپیوتر- دانشگاه صنعتی شریفالگوریتم گراف تخصیص منابعفرض کنیم پردازه Pi منبع Rj را تقاضا کنددرخواست تنها هنگامی پاسخ داده می شود که تبدیل یال تقاضا به یال تبدیل باعث ایجاد یک حلقه در گراف نشود

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

اسلاید 36: دکتر جلیلی - مفاهیم سیستم عامل دانشکده ی کامپیوتر- دانشگاه صنعتی شریففرض کنید m تعداد پردازه ها و n تعداد نوع منابع باشد.int available [m];available [j] = k یعنی k نمونه از منبع Rj موجود هستند.int max [n][m];max [i][j] = k یعنی پردازه Pi حداکثر ممکن است k نمونه از منبع Rj را درخواست کند.int allocation [n][m];allocation [i][j] = k یعنی پردازه Pi، k نمونه از منبع Rj را در اختیار دارد.int need [n][m];need [i][j] = k یعنی پردازه Pi به k نمونه دیگر از منبع Rj نیاز دارد تا کارش را تمام کند.Need [i,j] = Max[i,j] – Allocation [i,j]ساختار داده الگوریتم بانکدارها

اسلاید 37: دکتر جلیلی - مفاهیم سیستم عامل دانشکده ی کامپیوتر- دانشگاه صنعتی شریف1.فرض کن Work و Finish دو بردار به طول m و n باشند. این بردارها را به این صورت مقداردهی اولیه کن:Work = Available;Finish = {False};2.اندیس i را به گونه ای پیدا کن که:Finish [i] = False;Needi  Work;اگر چنین i پیدا نکردی به گام 4 برو.Work = Work + Allocationi;Finish [i] = True; 3.به گام 2 برو.4.اگر i: Finish [i] == True آنگاه سیستم در یک حالت امن است.الگوریتم ایمنی – آيا سيستم در حالت امن است؟

اسلاید 38: دکتر جلیلی - مفاهیم سیستم عامل دانشکده ی کامپیوتر- دانشگاه صنعتی شریفالگوریتم درخواست منبع برای پردازه Piبردار Requesti را به عنوان بردار نیاز پردازه Pi تعریف می کنیم.Requesti [j] == k یعنی پردازه Pi به k نمونه از منبع Rj نیاز دارد.1.اگر Requesti  Needi به گام 2 برو، وگرنه اعلام خطا.2.اگر Requesti  Available به گام 3 برو، وگرنه Pi باید منتظر بماند تا منابع مورد نیاز آزاد شوند.3.فرض کن منابع مورد نیاز Pi را اختصاص داده ای. حالت تخصیص منابع را به صورت زیر به روز کن:Available = Available – RequestiAllocationi = Allocationi + Requesti;Needi = Needi – Requesti;اگر حالت سیستم امن بود  منابع به Pi اختصاص یافته اند.اگر حالت سیستم ناامن بود  Pi باید منتظر بماند، حالت قبلی سیستم را بازیابی کن.

اسلاید 39: دکتر جلیلی - مفاهیم سیستم عامل دانشکده ی کامپیوتر- دانشگاه صنعتی شریفمثالی از الگوریتم بانکدارهاپنج پردازه P0 تا P4 و سه منبع A (10 نمونه)، B (5 نمونه) و C (7 نمونه).حالت تخصیص منابع در T0:AllocationMaxAvailableA B CA B C A B CP00 1 07 5 3 3 3 2P12 0 0 3 2 2 P23 0 2 9 0 2P32 1 1 2 2 2P40 0 24 3 3

اسلاید 40: دکتر جلیلی - مفاهیم سیستم عامل دانشکده ی کامپیوتر- دانشگاه صنعتی شریفمثالی از الگوریتم بانکدارها (ادامه)مقادیر ماتریس Need را محاسبه می کنیم:NeedA B C P07 4 3 P11 2 2 P26 0 0 P30 1 1 P44 3 1 سیستم در یک حالت امن است چون ترتیب < P1, P3, P4, P2, P0> شرط امنیت را تامین می کند و یک ترتیب امن است.

اسلاید 41: دکتر جلیلی - مفاهیم سیستم عامل دانشکده ی کامپیوتر- دانشگاه صنعتی شریفمثال : P1 برای (1,0,2) درخواست می دهدببین آیا Request  Available است؟ یعنی :(1,0,2)  (3,3,2)  true

اسلاید 42: دکتر جلیلی - مفاهیم سیستم عامل دانشکده ی کامپیوتر- دانشگاه صنعتی شریفاجرای الگوریتم ایمنی نشان می دهد رشته ی < P1, P3, P4, P0, P2> شرایط امنیت را برقرار می کند.آیا می توان درخواست (3,3,0) را برای P4 اجابت کرد؟آیا می توان درخواست(0,2,0) را برای P0 اجابت کرد؟

اسلاید 43: دکتر جلیلی - مفاهیم سیستم عامل دانشکده ی کامپیوتر- دانشگاه صنعتی شریفمروری بر عناوین مطالبمساله بن بستمشخصه های بن بستروش های برخورد با بن بستپیشگیری از بن بستاجتناب از بن بستکشف بن بستترمیم از بن بستروش های ترکیبی برای برخورد با بن بست

اسلاید 44: دکتر جلیلی - مفاهیم سیستم عامل دانشکده ی کامپیوتر- دانشگاه صنعتی شریفبه سیستم اجازه داده می شود وارد حالت بن بست شود و سپس تلاش می شود بن بست کشف شده و ترمیم شود.مکانیزم کشف بن بست ؟مکانیزم ترمیم بن بست ؟در حالتی که از هر نوع منبع یکی موجود باشد، می توان از گراف انتظار (wait-for graph) استفاده کرد.هر پردازه یک گره. Pi  Pj یعنی Pi منتظر Pj است.به صورت دوره ای گراف انتظار برای یافتن حلقه جستحو می شود. پیچیدگی زمانی این الگوریتم O(n2) است (n تعداد پردازه ها).کشف بن بست

اسلاید 45: دکتر جلیلی - مفاهیم سیستم عامل دانشکده ی کامپیوتر- دانشگاه صنعتی شریف گراف انتظارگراف تخصیص منابعگراف تخصیص منابع و گراف انتظار

اسلاید 46: دکتر جلیلی - مفاهیم سیستم عامل دانشکده ی کامپیوتر- دانشگاه صنعتی شریفساختار داده الگوریتم: m تعداد نوع منابع و n تعداد پردازه هاint available [m];int allocation [n][m];int Request [n][m];الگوریتم:1. فرض کن Work و Finish دو بردار به طول m و n باشند. این بردارها را به این صورت مقداردهی اولیه کن:Work = Available;if (Allocationi ≠ 0) Finishi = False; else Finishi = True;الگوریتم کشف بن بست در حالت وجود چند نمونه از هر منبع

اسلاید 47: دکتر جلیلی - مفاهیم سیستم عامل دانشکده ی کامپیوتر- دانشگاه صنعتی شریفادامه الگوریتم2.اندیس i را به گونه ای پیدا کن که:Finish [i] = False;Requesti  Work;اگر چنین i پیدا نکردی به گام 4 برو.Work = Work + Allocationi;Finish [i] = True; 3.به گام 2 برو.4.اگر  i: Finish [i] == False آنگاه سیستم در حالت بن بست است و Pi نیز در بن بست قرار دارد.پیچیدگی زمانی این الگوریتم O(m x n2) است.الگوریتم کشف بن بست در حالت وجود چند نمونه از هر منبع (ادامه)

اسلاید 48: دکتر جلیلی - مفاهیم سیستم عامل دانشکده ی کامپیوتر- دانشگاه صنعتی شریفنمونه ای از کاربرد الگوریتم کشف بن بستپنج پردازه P0 تا P4 و سه منبع A (7 نمونه)، B (2 نمونه) و C (6 نمونه). حالت تخصیص منابع در T0:AllocationRequestAvailableA B C A B C A B CP00 1 0 0 0 0 0 0 0P12 0 0 2 0 2P23 0 30 0 0 P32 1 1 1 0 0 P40 0 2 0 0 2با در نظر گرفتن ترتیب <P0, P2, P3, P1, P4> داریم:  i: Finish [i] == True

اسلاید 49: دکتر جلیلی - مفاهیم سیستم عامل دانشکده ی کامپیوتر- دانشگاه صنعتی شریفنمونه ای از کاربرد الگوریتم کشف بن بست (ادامه)P2 یک نمونه دیگر از C درخواست می کند.RequestA B CP00 0 0P12 0 1P20 0 1P31 0 0 P40 0 2حالت سیستم:سیستم تنها می تواند پاسخگوی باقیمانده منابع مورد نیاز P0 باشد.بن بست وجود دارد. پردازه های P1 تا P4 در بن بست قرار دارند.

اسلاید 50: دکتر جلیلی - مفاهیم سیستم عامل دانشکده ی کامپیوتر- دانشگاه صنعتی شریفاستفاده از کشف بن بستفواصل زمانی و چگونگی فراخوانی الگوریتم به موارد زیر بستگی دارد:معمولا هر چند مدت یکبار در سیستم بن بست رخ می دهد؟چه تعداد پردازه باید عقب کشیده شوند؟در هر حلقه بن بست حداقل یکی از پردازه ها باید عقب کشیده شود.اگر الگوریتم در زمان دلخواه و بدون در نظر گرفتن معیارهای بالا فراخوانی شود، ممکن است ما با تعداد زیادی حلقه در گراف منابع و پردازه گرفتارشده در بن بست مواجه شویم و نتوانیم تشخیص دهیم کدام پردازه باعث ایجاد زنجیر بن بست شده است.

اسلاید 51: دکتر جلیلی - مفاهیم سیستم عامل دانشکده ی کامپیوتر- دانشگاه صنعتی شریفمروری بر عناوین مطالبمساله بن بستمشخصه های بن بستروش های برخورد با بن بستپیشگیری از بن بستاجتناب از بن بستکشف بن بستترمیم از بن بستروش های ترکیبی برای برخورد با بن بست

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

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

اسلاید 54: دکتر جلیلی - مفاهیم سیستم عامل دانشکده ی کامپیوتر- دانشگاه صنعتی شریفمروری بر عناوین مطالبمساله بن بستمشخصه های بن بستروش های برخورد با بن بستپیشگیری از بن بستاجتناب از بن بستکشف بن بستترمیم از بن بستروش های ترکیبی برای برخورد با بن بست

اسلاید 55: دکتر جلیلی - مفاهیم سیستم عامل دانشکده ی کامپیوتر- دانشگاه صنعتی شریفمی توان پیشگیری، اجتناب و کشف بن بست را با هم ترکیب کرد و برای هر منبع از روشی که برای آن منبع مناسب تر است استفاده کرد.برای این کار می توان منابع را کلاس بندی کرد و سپس برای برخورد با بن بست در هر یک از کلاس های منابع از مناسبترین روش موجود استفاده کرد.روش های ترکیبی برای برخورد با بن بست

اسلاید 56: دکتر جلیلی - مفاهیم سیستم عامل دانشکده ی کامپیوتر- دانشگاه صنعتی شریفپایان فصل هفتم