بن بست

بن بست اسالیدهای فصل هفتم کتاب سیلبرشاتز دانشکده مهندسی کامپیوتر دانشگاه شریف دکتر جلیلی -مفاهیم سیستم عامل دانشکده ی کامپیوتر -دانشگاه صنعتی شریف مروری بر عناوین مطالب ‏ ‏ ‏ ‏ ‏ ‏ ‏ ‏ مساله بن بست مشخصه های بن بست روش های برخورد با بن بست پیشگیری از بن بست اجتناب از بن بست کشف بن بست ترمیم از بن بست روش های ترکیبی برای برخورد با بن بست دکتر جلیلی -مفاهیم سیستم عامل دانشکده ی کامپیوتر -دانشگاه صنعتی شریف 5.2 مروری بر اهداف فصل ‏ ‏ آشنایی با مفهوم بن بست که مانع از انجام کار یک یا چندین پردازه می شود آشنایی با روش های مختلف مقابله با بن بست دکتر جلیلی -مفاهیم سیستم عامل دانشکده ی کامپیوتر -دانشگاه صنعتی شریف 5.3 مساله بن بست ‏ ‏ یک مجموعه از پردازه ها در حالت بن بست هستند اگر هر یک از پردازه ها منبعی را در اختیار داشته باشند و منتظر منبع دیگری باشند که در اختیار پردازه ای دیگر در همین مجموعه است. نمونه :دو سمافور Aو Bبا مقدار اولیه 1 ‏P0 ‏P1 )wait(B )wait(A ‏ ;)wait (A ;)wait (B نمونه :پل میان گذر ‏ عرض پل به اندازه ای است که اجازه عبور یک ماشین را می دهد. دکتر جلیلی -مفاهیم سیستم عامل دانشکده ی کامپیوتر -دانشگاه صنعتی شریف 5.4 مساله بن بست ‏ ‏ ‏ ‏ (ادامه) هر قسمت از پل یک منبع محسوب می شود. اگر بن بست رخ دهد ،می توان با بازگرداندن یک ماشین آن را حل کرد. ممکن است نیاز باشد چندین ماشین برگردانده شوند. احتمال قحطی وجود دارد. دکتر جلیلی -مفاهیم سیستم عامل دانشکده ی کامپیوتر -دانشگاه صنعتی شریف 5.5 مدل سیستم ‏ منابع سیستم از انواع مختلف R1, R2, . . ., Rmهستند. ‏ قطعه های زمانی پردازنده ،فضای حافظه ،ابزارهای خواندن /نوشتن... ، ‏ از هر منبع Ri ، Wiتا داریم. ‏ هر پردازه از هر منبع با رعایت توالی اعمال زیر بهره برداری می کند: ‏ ‏ ‏ درخواست استفاده رهاسازی دکتر جلیلی -مفاهیم سیستم عامل دانشکده ی کامپیوتر -دانشگاه صنعتی شریف 5.6 مروری بر عناوین مطالب ‏ ‏ ‏ ‏ ‏ ‏ ‏ ‏ مساله بن بست مشخصه های بن بست روش های برخورد با بن بست پیشگیری از بن بست اجتناب از بن بست کشف بن بست ترمیم از بن بست روش های ترکیبی برای برخورد با بن بست دکتر جلیلی -مفاهیم سیستم عامل دانشکده ی کامپیوتر -دانشگاه صنعتی شریف 5.7 مشخصه های بن بست ‏ برای رخ دادن بن بست برقراری همزمان چهار شرط زیر الزامی است: ‏ ‏ ‏ ممانعت دوجانبه ( :)Mutual Exclusionدر هر زمان تنها یک RپرداRزه می توRاند از یک منبع استفاده کند. نگهدار و منتظر بمان ( :)Hold and Waitپردازه ای که حداقل یک منبع در اختیار دارد ،منتظر است تا منابع دیRگری که در اخRتیار پردازه های دیگر است نیز بگیرد. عدم پیشدستی ( :)No Preemptionهر منبعی تنها پس از پایان کار پردازه ای که آن را Rدر اختیار گرفته است و به صورت داوطلبانه توسط Rهمان پردازه قابل رهاسازی است. دکتر جلیلی -مفاهیم سیستم عامل دانشکده ی کامپیوتر -دانشگاه صنعتی شریف 5.8 مشخصه های بن بست ‏ ‏ (ادامه) انتظار حلقوی ( :)Circular Waitمجموعه ای مانند { }P0, P1, …, Pnوجود دارد به گونه ای که P0منتظر منبعی است که Rدر اختیار P1قرار داردP1 ، منتظر منبعی است که در اختیار P2قرار دارد ، ... ،و Pnمنتظر منبعی است که در اختیار P0قرار دارد. گرچه وقوع همزمان هر چهار شرط برای وقوع بن بست الزامی است ،اما این شرایط کامال از هم مستقل نیستند. ‏ برای مثال شرط «انتظار حلقوی» ،شرط «نگهدار و منتظر بمان» را نتیجه می دهد. دکتر جلیلی -مفاهیم سیستم عامل دانشکده ی کامپیوتر -دانشگاه صنعتی شریف 5.9 گراف تخصیص منابع ‏ ‏ ‏ گراف تخصیص منابع به صورت مجموعه رئوس Vو مجموعه یال های جهت دار Eتعریف می شود. دو نوع راس :پردازه ها و نوع منابع ‏ } P = {P1, P2, …, Pnمجموعه همه پردازه های سیستم ‏ } R = {R1, R2, …, Rmمجموعه همه انواع منابع سیستم هر یال جهت دار نشانگر درخواست یا اختصاص منبع ‏ ‏ ‏P1  Rj درخواست منبع: اختصاص منبعRj  Pi : دکتر جلیلی -مفاهیم سیستم عامل دانشکده ی کامپیوتر -دانشگاه صنعتی شریف 5.10 گراف تخصیص منابع ‏ پردازه: ‏ نوع منبع با چهار نمونه: (ادامه) ‏ Piیک نمونه از Rjرا تقاضا می کند: ‏ Piیک نمونه از Rjرا در اختیار دارد: ‏Pi ‏Rj ‏Pi صنعتیRشریف دکتر جلیلی -مفاهیم سیستم عامل دانشکده ی کامپیوتر -دانشگاه ‏j 5.11 یک نمونه از گراف تخصیص منابع دکتر جلیلی -مفاهیم سیستم عامل دانشکده ی کامپیوتر -دانشگاه صنعتی شریف 5.12 گراف تخصیص منابع (با حلقه و بن بست) دکتر جلیلی -مفاهیم سیستم عامل دانشکده ی کامپیوتر -دانشگاه صنعتی شریف 5.13 گراف تخصیص منابع (با حلقه و بدون بن بست) دکتر جلیلی -مفاهیم سیستم عامل دانشکده ی کامپیوتر -دانشگاه صنعتی شریف 5.14 معیار تشخیص اولیه ‏ اگر گراف تخصیص منابع حلقه ندارد ... ‏ ‏ سیستم بن بست ندارد. اگر گراف تخصیص منابع حلقه دارد ... ‏ ‏ اگر از هر نوع منبع درگیر در حلقه فقط یک نمونه داریم ،یک بن بست رخ داده است. اگر از هر نوع منبع درگیر در حلقه چندین نمونه داریم ،ممکن است بن بست رخ داده باشد. دکتر جلیلی -مفاهیم سیستم عامل دانشکده ی کامپیوتر -دانشگاه صنعتی شریف 5.15 مروری بر عناوین مطالب ‏ ‏ ‏ ‏ ‏ ‏ ‏ ‏ مساله بن بست مشخصه های بن بست روش های برخورد با بن بست پیشگیری از بن بست اجتناب از بن بست کشف بن بست ترمیم از بن بست روش های ترکیبی برای برخورد با بن بست دکتر جلیلی -مفاهیم سیستم عامل دانشکده ی کامپیوتر -دانشگاه صنعتی شریف 5.16 روش های برخورد با بن بست ‏ ‏ در حالت کلی به سه گونه می توان با مساله بن بست برخورد کرد: تضمین عدم وقوع بن بست ،ترمیم بن بست ،و اجتناب از بن بست. برای تضمین اینکه هیچ گاه بن بست در سیستم رخ نمی دهد... ‏ ‏ باید مکانیزمی وجود داشته باشد که قبل از تخصیص منابع به پردازه ها صحت شروط تضمین عدم امکان وقوع بن بست را ارزیابی کند. پیشگیری از بن بست و اجتناب از بن بست هر دو در این دسته جای می گیرند. دکتر جلیلی -مفاهیم سیستم عامل دانشکده ی کامپیوتر -دانشگاه صنعتی شریف 5.17 روش های برخورد با بن بست ‏ ترمیم بن بست ‏ ‏ ‏ (ادامه) در این رهیافت به سیستم اجازه داده می شود وارد حالت بن بست شود و سپس تالش می شود بن بست رفع شود. نیاز به مکانیزم هایی است که وقوع بن بست را تشخیص دهند و سپس آن را برطرف کنند. صرف نظر کردن از بن بست ‏ ‏ در بسیاری از سیستم ها بن بست به ندرت رخ می دهد ،بنابراین به جای استفاده از راه حل های گران قبلی به سادگی فرض Rمی شود هیچ گاه بن بست رخ نمی دهد. راه حل مورد استفاده در UNIX دکتر جلیلی -مفاهیم سیستم عامل دانشکده ی کامپیوتر -دانشگاه صنعتی شریف 5.18 مروری بر عناوین مطالب ‏ ‏ ‏ ‏ ‏ ‏ ‏ ‏ مساله بن بست مشخصه های بن بست روش های برخورد با بن بست پیشگیری از بن بست اجتناب از بن بست کشف بن بست ترمیم از بن بست روش های ترکیبی برای برخورد با بن بست دکتر جلیلی -مفاهیم سیستم عامل دانشکده ی کامپیوتر -دانشگاه صنعتی شریف 5.19 پیشگیری از بن بست ‏ برای پیشگیری از بن بست ،باید یکی از شروط چهارگانه را نقض کرد. .1ممانعت دوجانبه ‏ ‏ اگر منبع قابل به اشتراک گذاری باشد (مانند یک پرونده فقط خواندنی) می توان در مورد آن از شرط ممانعت دوجانبه صرف نظر کرد. در حالت کلی این شرط قابل نقض نیست ،چون ماهیت بسیاری از منابع (مانند چاپگر) وجود این شرط را الزامی می کند. دکتر جلیلی -مفاهیم سیستم عامل دانشکده ی کامپیوتر -دانشگاه صنعتی شریف 5.20 پیشگیری از بن بست (ادامه) .2نگهدار و منتظر بمان ‏ ‏ ‏ برای نقض این شرط هر پردازه تنها باید در صورتی تقاضای یک منبع را بکند که هیچ منبع دیگری در اختیار نداشته باشد. پردازه دو راه برای درخواست منبع دارد .یا باید همه منابع مورد نیاز خود را در ابتدای اجرای خود به صورت یکجا درخواست کند یا باید همه منابع در اختیار را آزاد کرده و سپس تقاضای منبع جدید کند. بهره وری منابع در این روش پایین است و احتمال قحطی نیز وجود دارد. دکتر جلیلی -مفاهیم سیستم عامل دانشکده ی کامپیوتر -دانشگاه صنعتی شریف 5.21 پیشگیری از بن بست (ادامه) .3عدم پیشدستی ‏ ‏ ‏ ‏ برای نقض این شرط می توان به سیستم عامل اجازه داد تا در صورت لزوم پیشدستی کرده و خود منابع در اختیار پردازه را آزاد کند. در صورتی که پردازه ای تقاضای منبع کرد و اختصاص منبع امکان پذیر نبود ،سیستم عامل می تواند تمام منابع در اختیار پردازه متقاضی را آزاد کند. منابع آزادشده به لیست منابع مورد تقاضای پردازه افزوده می شوند. اجرای پردازه وقتی از سر گرفته می شود که پردازه بتواند منبع مورد نیاز و تمام منابع آزاد شده قبلی را در اختیار بگیرد. دکتر جلیلی -مفاهیم سیستم عامل دانشکده ی کامپیوتر -دانشگاه صنعتی شریف 5.22 پیشگیری از بن بست (ادامه) .4انتظار حلقوی ‏ برای نقض این شرط می توان یک ترتیب کلی روی همه منابع موجود در سیستم اعمال کرد و سپس از هر پردازه خواست منابع مورد نیاز خود را فقط در یک ترتیب افزایشی درخواست کند. دکتر جلیلی -مفاهیم سیستم عامل دانشکده ی کامپیوتر -دانشگاه صنعتی شریف 5.23 مروری بر عناوین مطالب ‏ ‏ ‏ ‏ ‏ ‏ ‏ ‏ مساله بن بست مشخصه های بن بست روش های برخورد با بن بست پیشگیری از بن بست اجتناب از بن بست کشف بن بست ترمیم از بن بست روش های ترکیبی برای برخورد با بن بست دکتر جلیلی -مفاهیم سیستم عامل دانشکده ی کامپیوتر -دانشگاه صنعتی شریف 5.24 اجتناب از بن بست ‏ ‏ ‏ در این رهیافت سیستم تالش می کند تا با استفاده از یک دانش قبلی درباره رفتار پردازه ها مانع از وقوع بن بست شود. رهیافت «پRیشگیری از بن بست» بر نقض شرایط پیش نیازی وقوع بن بست و رهیافت «اجتناب از بن بست» بر نظارت مداوم و بررسی امکان یا عدم امکان وقوع بن بست تمرکز دارند. در ساده ترین و مفیدترین روش موجود هر پردازه قبل از شروع اجرا باید نوع و حداکثر تعداد منابع مورد نیاز از هر نوع را اعالن کند. دکتر جلیلی -مفاهیم سیستم عامل دانشکده ی کامپیوتر -دانشگاه صنعتی شریف 5.25 حالت تخصیص منابع و حالت امن ‏ ‏ ‏ الگوریتم اجتناب از بن بست به صورت پویا حالت تخصیص منابع را بررسی می کند تا تضمین کند هیچ گاه انتظار حلقوی اتفاق نمی افتد. حالت تخصیص منابع از منابع موجود و تخصیص داده شده و همچنین حداکثر تقاضای پردازه ها برای هر نوع منبع تشکیل شده است. وقتی پردازه ای تقاضای اختصاص یک منبع موجود را می کند، سیستم باید تصمیم بگیرد که آیا اختصاص فوری منبع به پردازه سیستم را در حالت امن نگاه می دارد یا خیر؟ دکتر جلیلی -مفاهیم سیستم عامل دانشکده ی کامپیوتر -دانشگاه صنعتی شریف 5.26 حالت امن ‏ ‏ سیستم در حالت امن است در صورتی که یک ترتیب امن از پردازه ها وجود داشته باشد. ترتیب < >P1, P2, …, Pnیک ترتیب امن است در صورتی که برای هر ،Piمنابعی که Piمی تواند تقاضا کند زیرمجموعه ای از منابع موجود و منابع در اختیار Pjها باشد (.) j < i ‏ ‏ ‏ اگر منابع مورد نیاز Piهمه فراهم نیستند Pi ،می تواند تا پایان تمام Pjها که منابع مورد نیاز را در اختیار دارند صبر کند. وقتی منابع آماده شد Pi ،می تواند آنها را در اختیار بگیرد ،اجرا شود و سپس منابع در اختیار را آزاد کند. وقتی Piپایان یافت Pi+1 ،می تواند اجرا شود و به همین صورت اجرا ادامه یابد.مفاهیم سیستم عامل دانشکده ی کامپیوتر -دانشگاه صنعتی شریف میجلیلی - دکتر 5.27 معیار تشخیص اولیه ‏ اگر سیستم در یک حالت امن است ... ‏ ‏ اگر سیستم در یک حالت ناامن است ... ‏ ‏ سیستم بن بست ندارد. ممکن است بن بست رخ داده باشد. اجتناب از بن بست تضمین می کند سیستم هیچ گاه وارد یک حالت ناامن نشود. دکتر جلیلی -مفاهیم سیستم عامل دانشکده ی کامپیوتر -دانشگاه صنعتی شریف 5.28 امنیت – عدم امنیت و بن بست دکتر جلیلی -مفاهیم سیستم عامل دانشکده ی کامپیوتر -دانشگاه صنعتی شریف 5.29 الگوریتم های جلوگیری از بن بست ‏ ‏ هنگامی که از هر منبع تنها یک نمونه موجود است .از الگوریتم گراف تخصیص منابع استفاده می کنیم . هنگامی که بیش از یک نمونه ازمنبع موجود است .از الگوریتم بانکدار استفاده می کنیم . دکتر جلیلی -مفاهیم سیستم عامل دانشکده ی کامپیوتر -دانشگاه صنعتی شریف 5.30 الگوریتم گراف تخصیص منابع ‏ اجزای الگوریتم: ‏ ‏ ‏ ‏ وقتی ممکن است پردازه Piمنبع Rjرا تقاضا کند ،یک یال خواسته )edgeبه صورت خط چین بین رئوس مربوطه می کشیم. وقتی پردازه منبع را درخواست می کند ،یال خواسته Rبه یال تقاضای منبع تبدیل می شود. وقتی پردازه منبع را آزاد می کند ،یال تخصیص به یال خواسته تبدیل می شود. منابع مورد نیاز باید از قبل از سیستم خواسته شوند. (claim دکتر جلیلی -مفاهیم سیستم عامل دانشکده ی کامپیوتر -دانشگاه صنعتی شریف 5.31 گراف تخصیص منابع برای اجتناب از بن بست دکتر جلیلی -مفاهیم سیستم عامل دانشکده ی کامپیوتر -دانشگاه صنعتی شریف 5.32 حالت ناامن در گراف تخصیص منابع دکتر جلیلی -مفاهیم سیستم عامل دانشکده ی کامپیوتر -دانشگاه صنعتی شریف 5.33 الگوریتم گراف تخصیص منابع ‏ فرض کنیم پردازه Piمنبع Rjرا تقاضا کند ‏ درخواست تنها هنگامی پاسخ داده می شود که تبدیل یال تقاضا به یال تبدیل باعث ایجاد یک حلقه در گراف نشود دکتر جلیلی -مفاهیم سیستم عامل دانشکده ی کامپیوتر -دانشگاه صنعتی شریف 5.34 الگوریتم بانکدارها ‏ این الگوریتم از حالتی که از هر نوع منبع چندین نمونه داشته باشیم پشتیبانی می کند. ‏ ‏ ‏ ‏ الگوریتم گراف تخصیص منابع برای این حالت جواب نمی دهد. هر پردازه باید از پیش حداکثر تعداد منابع مورد نیاز خود را اعالم کند. وقتی پردازه ای تقاضای منبعی را می کند ،ممکن است مجبور شود منتظر بماند. وقتی پردازه ای تمام منابع مورد نیاز را می گیرد ،باید همه را در زمان محدود بازگرداند. دکتر جلیلی -مفاهیم سیستم عامل دانشکده ی کامپیوتر -دانشگاه صنعتی شریف 5.35 ساختار داده الگوریتم بانکدارها ‏ فرض کنید mتعداد پردازه ها و nتعداد نوع منابع باشد. ;]int available [m available [j] = kیRRعنی kنRRمونRه از مRنبع RjمRوجود هستند. ;]int max [n][m مRمکنRسRت kنRRمونRه از مRنبع Rjرا درRخواRسRتکRRند. ا max [i][j] = kیRRعنیپRRردازRه Pi RحRداRکRثر ;]int allocation [n][m allocation [i][j] = kیRRعنیپRRردازRه Pi، k RنRRمونRه از مRنبع Rjرا در اRخRتیار دارد. ;]int need [n][m need [i][j] = kیRRعنیپRRردازRه Pi RبRRRه kنRRمونRه دRیRگر از مRنبع RjنRRیاز دارد تRRا کRRارRشرا تRRمام کRRند. ]Need [i,j] = Max[i,j] – Allocation [i,j دکتر جلیلی -مفاهیم سیستم عامل دانشکده ی کامپیوتر -دانشگاه صنعتی شریف 5.36 الگوریتم ایمنی – آيا سيستم در حالت امن است؟ .1فرض کن Workو Finishدو بردار به طول mو nباشند .این بردارها را به این صورت مقداردهی اولیه کن: ;}Finish = {False ;Work = Available .2اندیس iرا به گونه ای پیدا کن که: ;Needi  Work ;Finish [i] = False اگر چنین iپیدا نکردی به گام 4برو. ; Work = Work + Allocation ;Finish [i] = True 3. به گام 2برو. .4اگر i: Finish [i] == Trueآنگاه Rسیستم در یک حالت امن است. ‏i دکتر جلیلی -مفاهیم سیستم عامل دانشکده ی کامپیوتر -دانشگاه صنعتی شریف 5.37 الگوریتم درخواست منبع برای پردازه ‏ ‏Pi بردار Requestiرا به عنوان بردار نیاز پردازه Piتعریف می کنیم. ‏ Requesti [j] == kیRRعنیپRRردازRه Pi RبRRRه kنRRمونRه از مRنبع RjنRRیاز دارد. .1اگر Requesti  Neediبه گام 2برو ،وگرنه اعالم خطا. .2اگر Requesti  Availableبه گام 3برو ،وگرنه Piباید منتظر بماند تا منابع مورد نیاز آزاد شوند. .3فرض کن منابع مورد نیاز Piرا اختصاص داده ای .حالت تخصیص منابع را به صورت زیر به روز کن: ‏Available = Available – Requesti ;Allocationi = Allocationi + Requesti ;Needi = Needi – Requesti اگر حالت سیستم امن بود منابع به Piاختصاص یافته اند. شریفقبلی سیستم را بازیابی کن. حالت اگر حالت سیستم ناامن بود  Pباید منتظر بماند، دکتر جلیلی -مفاهیم سیستم عامل iدانشکده ی کامپیوتر -دانشگاه صنعتی 5.38 مثالی از الگوریتم بانکدارها ‏ ‏ پنج پردازه P0تا P4و سه منبع 10( Aنمونه) 5( B ،نمونه) و 7( C نمونه). حالت تخصیص منابع در :T0 ‏Allocation ‏Max ‏Available ‏ABC ABC ABC 010 753 332 ‏P0 200 322 ‏P1 302 902 ‏P2 211 ‏P3 002 433 ‏P4 222 دکتر جلیلی -مفاهیم سیستم عامل دانشکده ی کامپیوتر -دانشگاه صنعتی شریف 5.39 مثالی از الگوریتم بانکدارها (ادامه) ‏ مقادیر ماتریس Needرا محاسبه می کنیم: ‏ سیستم در یک حالت امن است چون ترتیب >Pشرط امنیت را تامین می کند و یک ترتیب امن است. ‏Need ‏ABC 743 ‏P0 122 ‏P1 600 ‏P2 011 ‏P3 431 ‏P4 < P1, P3, P4, P2, 0 دکتر جلیلی -مفاهیم سیستم عامل دانشکده ی کامپیوتر -دانشگاه صنعتی شریف 5.40 مثال P1 :برای ( )1,0,2درخواست می دهد ‏ ببین آیا Request  Availableاست؟ یعنی : ‏ ( (3,3,2)  true )1,0,2 دکتر جلیلی -مفاهیم سیستم عامل دانشکده ی کامپیوتر -دانشگاه صنعتی شریف 5.41  اجرای الگوریتم ایمنی نشان می دهد رشته ی < >P1, P3, P4, P0, P2 شرایط امنیت را برقرار می کند. ‏ آیا می توان درخواست ( )3,3,0را برای P4اجابت کرد؟ ‏ آیا می توان درخواست( )0,2,0را برای P0اجابت کرد؟ دکتر جلیلی -مفاهیم سیستم عامل دانشکده ی کامپیوتر -دانشگاه صنعتی شریف 5.42 مروری بر عناوین مطالب ‏ ‏ ‏ ‏ ‏ ‏ ‏ ‏ مساله بن بست مشخصه های بن بست روش های برخورد با بن بست پیشگیری از بن بست اجتناب از بن بست کشف بن بست ترمیم از بن بست روش های ترکیبی برای برخورد با بن بست دکتر جلیلی -مفاهیم سیستم عامل دانشکده ی کامپیوتر -دانشگاه صنعتی شریف 5.43 کشف بن بست ‏ به سیستم اجازه داده می شود وارد حالت بن بست شود و سپس تالش می شود بن بست کشف شده و ترمیم شود. ‏ ‏ ‏ مکانیزم کشف بن بست ؟ مکانیزم ترمیم بن بست ؟ در حالتی که از هر نوع منبع یکی موجود باشد ،می توان از گراف انتظار ( )wait-for graphاستفاده کرد. ‏ ‏ ‏ هر پردازه یک گره. Pi  Pjیعنی Piمنتظر Pjاست. به صورت دوره ای گراف انتظار برای یافتن حلقه جستحو می شود. پیچیدگی زمانی این الگوریتم ) O(n2است ( nتعداد پردازه ها). دکتر جلیلی -مفاهیم سیستم عامل دانشکده ی کامپیوتر -دانشگاه صنعتی شریف 5.44 گراف تخصیص منابع و گراف انتظار گراف انتظار گراف تخصیص منابع دکتر جلیلی -مفاهیم سیستم عامل دانشکده ی کامپیوتر -دانشگاه صنعتی شریف 5.45 الگوریتم کشف بن بست در حالت وجود چند نمونه از هر منبع ‏ ساختار داده الگوریتم: ‏ 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 دکتر جلیلی -مفاهیم سیستم عامل دانشکده ی کامپیوتر -دانشگاه صنعتی شریف 5.46 الگوریتم کشف بن بست در حالت وجود چند نمونه از هر منبع (ادامه) ‏ ادامه الگوریتم .2اندیس iرا به گونه Rای پیدا کن که: ;Requesti  Work ;Finish [i] = False اگر چنین iپیدا نکردی به گام 4برو. ;Finish [i] = True 3. ;Work = Work + Allocationi به گام 2برو. .4اگر  i: Finish [i] == Falseآنگاه سیستم در حالت بن بست است و Piنیز در بن بست قرار دارد. ‏ پیچیدگی زمانی این الگوریتم ) O(m x n2است. دکتر جلیلی -مفاهیم سیستم عامل دانشکده ی کامپیوتر -دانشگاه صنعتی شریف 5.47 نمونه ای از کاربرد الگوریتم کشف بن بست ‏ پنج پردازه P0تا P4و سه منبع 7( Aنمونه) 2( B ،نمونه) و 6( Cنمونه). حالت تخصیص منابع در :T0 ‏AllocationRequest Available ‏ABC ABC ABC ‏P0 010 000 000 200 202 ‏P1 303 000 ‏P2 211 ‏P3 002 002 ‏P4 100 ‏ با در نظر گرفتن ترتیب < >P0, P2, P3, P1, P4داریم: ‏ i: Finish [i] == True دکتر جلیلی -مفاهیم سیستم عامل دانشکده ی کامپیوتر -دانشگاه صنعتی شریف 5.48 نمونه ای از کاربرد الگوریتم کشف بن بست (ادامه) ‏ P2یRRکنRRمونRه دRیRگر از CدرRخواRسRتمRیکRRند. ‏ حالت سیستم: 000 201 001 100 002 ‏ ‏ ‏Request ‏ABC ‏P0 ‏P1 ‏P2 ‏P3 ‏P4 سیستم تنها می تواند پاسخگوی باقیمانده منابع مورد نیاز P0باشد. بن بست وجود دارد .پردازه های P1تا P4در بن بست قرار دارند. دکتر جلیلی -مفاهیم سیستم عامل دانشکده ی کامپیوتر -دانشگاه صنعتی شریف 5.49 استفاده از کشف بن بست ‏ فواصل زمانی و چگونگی فراخوانی الگوریتم به موارد زیر بستگی دارد: ‏ ‏ معموال هر چند مدت یکبار در سیستم بن بست رخ می دهد؟ چه تعداد پردازه باید عقب کشیده شوند؟ ‏ ‏ در هر حلقه بن بست حداقل یکی از پردازه ها باید عقب کشیده شود. اگر الگوریتم در زمان دلخواه و بدون در نظر گرفتن معیارهای باال فراخوانی شود ،ممکن است ما با تعداد زیادی حلقه در گراف منابع و پردازه گرفتارشده در بن بست مواجه شویم و نتوانیم تشخیص دهیم کدام پردازه باعث ایجاد زنجیر بن بست شده است. دکتر جلیلی -مفاهیم سیستم عامل دانشکده ی کامپیوتر -دانشگاه صنعتی شریف 5.50 مروری بر عناوین مطالب ‏ ‏ ‏ ‏ ‏ ‏ ‏ ‏ مساله بن بست مشخصه های بن بست روش های برخورد با بن بست پیشگیری از بن بست اجتناب از بن بست کشف بن بست ترمیم از بن بست روش های ترکیبی برای برخورد با بن بست دکتر جلیلی -مفاهیم سیستم عامل دانشکده ی کامپیوتر -دانشگاه صنعتی شریف 5.51 ترمیم از بن بست ‏ می توان بن بست را با پایان دهی به تعدادی پردازه و رهاسازی منابع در اختیار آنها ترمیم کرد. ‏ ‏ ‏ ‏ پایان دهی به همه پردازه های درگیر پایان دهی به یکی از پردازه های درگیر در انتخاب پردازه قربانی باید هزینه پرداختی پایان دهی به پردازه را مینیمم کرد. پRس از پایان دهی به پRردازه قربانی ،سیستم به یک حالت امن عقبگرد می کند و اجرای پردازه قربانی را از آن حالت مجددا شروع می کند. دکتر جلیلی -مفاهیم سیستم عامل دانشکده ی کامپیوتر -دانشگاه صنعتی شریف 5.52 ترمیم از بن بست ‏ برای انتخاب پردازه قربانی می توان معیارهایی در نظر گرفت... ‏ ‏ ‏ ‏ ‏ ‏ (ادامه) اولویت پردازه ها زمان پردازنده مصرف شده ،و تخمین موجود از زمان پردازنده مورد نیاز برای تکمیل کار پردازه منابع مصرف شده و منابع مورد نیاز پردازه برای تکمیل کار تعداد پردازه هایی که برای رفع همه بن بست ها باید به آنها پایان داده شود. تعاملی یا دسته ای بودن پردازه. خطر قحطی :یک پردازه همیشه قربانی شود ‏ می توان تعداد عقبگرد های هر پردازه را نیز یک معیار در نظر گرفت. دکتر جلیلی -مفاهیم سیستم عامل دانشکده ی کامپیوتر -دانشگاه صنعتی شریف 5.53 مروری بر عناوین مطالب ‏ ‏ ‏ ‏ ‏ ‏ ‏ ‏ مساله بن بست مشخصه های بن بست روش های برخورد با بن بست پیشگیری از بن بست اجتناب از بن بست کشف بن بست ترمیم از بن بست روش های ترکیبی برای برخورد با بن بست دکتر جلیلی -مفاهیم سیستم عامل دانشکده ی کامپیوتر -دانشگاه صنعتی شریف 5.54 روش های ترکیبی برای برخورد با بن بست ‏ ‏ می توان پیشگیری ،اجتناب و کشف بن بست را با هم ترکیب کرد و برای هر منبع از روشی که برای آن منبع مناسب تر است استفاده کرد. برای این کار می توان منابع را کالس بندی کرد و سپس برای برخورد با بن بست در هر یک از کالس های منابع از مناسبترین روش موجود استفاده کرد. دکتر جلیلی -مفاهیم سیستم عامل دانشکده ی کامپیوتر -دانشگاه صنعتی شریف 5.55  پایان فصل هفتم دکتر جلیلی -مفاهیم سیستم عامل دانشکده ی کامپیوتر -دانشگاه صنعتی شریف 5.56