خلاصه فصل ۸ سیستم عامل: بن بست‌ها

خلاصه فصل ۸ سیستم عامل: بن بست‌ها

اسلاید 1: خلاصه ی فصل 8 سیستم عاملاستاد : آقای عسکری قاسمپوری میلاد جعفریرضا زاهدیآذین مهرپورشاداعضای گروه :1

اسلاید 2: فصل هشتمبن بست هاتعداد کل اسلاید522

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

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

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

اسلاید 6: فصل هشتم : بن بست ها درخواست و آزاد کردن منابع ، فراخوان های سیستم هستند (مثل Request ،Release device ، ... )درخواست و آزاد کردن منابع دیگر می تواند از طریق عملیات wait وsignal بروی سمافورها انجام شود.سیستم عامل برای کنترل منابع از جدول سیستم استفاده می کند.جدول سیستم مشخص می کند که آیا منبعی آزاد است یا تخصیص یافته است و چنانچه تخصیص یافته باشد ، به کدام فرآیند تخصیص یافته است.اگر فرآیندی منبع را درخواست کند و آن منبع در حال حاضر در اختیار منبع دیگری باشد ، آن فرآیند در صف انتظار آن منبع قرار می گیرد.6

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

اسلاید 8: فصل هشتم : بن بست ها 1-2-8 شرایط ضروری وضعیت بن بست در صورتی پیش می آید که چهار شرایط زیر هم زمان در سیستم وجود داشته باشند.انحصار متقابل نگهداری و انتظار (Hold & Wait)بدون قبضه کردنانتظار چرخشیحداقل یک منبع باید در حالت غیر اشتراکی نگهداری شود. یعنی در هر زمان فقط یک فرآیند می تواند از آن منبع استفاده کند.باید فرآیند وجود داشته باشد که حداقل یک منبع را در اختیار داشته باشد و منتظر بدست آوردن منبع دیگری باشد که فعلا در اختیار فرآیندهای دیگر است.منابع نمی توانند قبضه شوند ، یعنی آزادسازی منبع به عهده فرآیندی است که آن را در اختیار دارد که پس از کامل کردن وظیفه خود ، آن را آزاد می کند.باید مجموعه ای از فرآیندهای منتظر P0,P1,…,Pn وجود داشته باشند که P0 منتظر منبعی باشد که در اختیار P1 است و P1 منتظر منبعی باشد که در اختیار P2 است و به همین ترتیب ، Pn-1 منتظر منبعی است که در اختیار Pn است و Pn منتظر منبعی است که در اختیار P0 است. 8

اسلاید 9: فصل هشتم : بن بست ها 2-2-8 گراف تخصیص منبع گراف تخصیص منابع سیستم ، شامل مجموعه ای از رأس ها به نام V و مجموعه ای از یال ها به نام E است.مجموعه V به دو نوع گره مختلف به نام های P و R تقسیم می شود.حاوی تمام فرآیندهای فعال در سیستم است P = { P1,P2,…,Pn }حاوی انواع منابع موجود در سیستم است R = { R1,R2,…,Rn } 9

اسلاید 10: فصل هشتم : بن بست ها Pi Rj( یال درخواست ) : نشان می دهد که فرآیند Pi نمونه ای از منبع نوع Rj را درخواست کرده است و منتظر آن منبع است. Pi Rj( یال تخصیص ) : مشخص می کند که نمونه ای از منبع نوع Rj به فرآیند Pi تخصیص یافته است.هر فرآیند برای Pi را با یک دایره نشان می دهیمهر نوع منبع با یک مرجع نشان داده می شود و اگر چند نوع از منبع Rj وجود داشته باشد ، هر یک از نمونه ها به صورت نقطه ای در مرجع نشان داده می شود. 10

اسلاید 11: فصل هشتم : بن بست ها مثال : مجموعه های P و R و E که عبارتند از :11P = { P1,P2,P3 }R = { R1,R2,R3,R4 }E = { P1 R1,P2 R3,R1 P1,R1 P2,R2 P2,R2 P1,R3 P3}P1P2P3R1R3R2R4

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

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

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

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

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

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

اسلاید 18: فصل هشتم : بن بست ها 4-4-8 انتظار چرخشییکی از راه هایی که می توان تضمین شرط انتظار چرخشی برای ایجاد بن بست رخ نمی دهد ، این است که یک ترتیب کلی به عنوان منابع اعمال شود و فرآیند ، درخواست منابع را به ترتیب شمارش صعودی انجام دهد.روش دیگر این است که ، هر وقت فرآیندی نمونه ای از منبع نوع Rj را درخواست می کند ، تمام منبع Ri را که F(Ri) ≥ F(Rj) است ، آزاد می سازد.مجموعه ای از انواع منابع F : R N R R = {R1,R2,…,Rm} مجموعه ای از اعداد طبیعی است N 18

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

اسلاید 20: فصل هشتم : بن بست ها 1-5-8 حالت امنحالت امن ، حالتی است که سیستم بتواند منابعی را به ترتیب خاصی به هر فرآیند تخصیص دهد و از بن بست نیز اجتناب ورزد. به عبارت دیگر سیستم در صورتی در حالت امن است که ، دنباله امنی (Safe Sequence) وجود داشته باشد.دنباله ای از فرآیندهای <P1,P2,…,Pn> در صورتی یک دنباله امن برای حالت تخصیص فعلی محسوب می شود که ، برای هر Pi ، منابعی که Pi می تواند درخواست کند ، توسط منابع مهیا و تمام منابعی که در اختیار Pj که در آن i<j است ، برآورده شود.در این وضعیت ، چنانچه منابع مورد نیاز فرآیند Pi فورا مهیا نباشد ، Pi می تواند منتظر بماند تا تمام Piها به اتمام برسند.اگر چنین دنباله ای وجود نداشته باشد ، حالت سیستم نا امن است.20

اسلاید 21: فصل هشتم : بن بست ها 1-5-8 حالت امن ( ادامه... )همه ی حالتهای نا امن ، بن بست نیستند بلکه حالت نا امن ممکن است منجر به بن بست شود.تا رمانی که حالت سیستم امن است سیستم عامل می تواند از حالت های نا امن ( و بن بست ) اجتناب کند.در حالت نا امن ، سیستم عامل نمی تواند فرآیندها را از درخواست منابعی که منجربه بن بست می شوند منع کند ، یعنی رفتار فرآیندها ، حالت های نا امن را کنترل می کند.21نا امنامنبن بست

اسلاید 22: فصل هشتم : بن بست ها 2-5-8 الگوریتم گراف تخصیص منبعاگر یک سیستم تخصیص منبع داشته باشیم که فقط یک نمونه از هر نوع منبع وجود داشته باشد ، برای اجتناب از بن بست می توان از گراف های تخصیص منبع استفاده کرد.علاوه بر یال های درخواست و تخصیص ، نوع جدیدی از یال به نام یال ادعا ( Claim Edge ) را تعریف می کنیم.یال ادعای Pi Rj نشان می دهد که فرآیند Pi ممکن است در آینده منبع Rj را درخواست کند این یال همانند یال درخواست است ولی با خط چین مشخص می شود. تذکر : وقتی فرآیند Pi منبع Rj را درخواست می کند ، یال ادعای Pi Rj به یال درخواست تبدیل می شود به طور مشابه وقتی منبع Rj توسط Pi آزاد می شود ، یال تخصیص Rj Pi به یال ادعای Pi Rj تبدیل می شود. 22

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

اسلاید 24: فصل هشتم : بن بست ها برای تشریح این الگوریتم ، گراف تخصیص شکل زیر را در نظر بگیرید. فرض کنید P2 منبع R2 را درخواست می کند ، اگرچه R2 فعلا آزاد است ، نمی توانیم آن را به P2 تخصیص دهیم چون موجب ایجاد چرخه در گراف می شود. P1R1P2R2گراف تخصیص منبع برای اجتناب از بن بستP1R1P2R2حالت نا امن در گراف تخصیص منبع24

اسلاید 25: فصل هشتم : بن بست ها 3-5-8 الگوریتم بانکداراین الگوریتم برای سیستم هایی مناسب است که سیستم تخصیص منبع از هر نوع منبع ، چند نمونه داشته باشد که در این حالت نمی توان از گراف تخصیص منبع استفاده کرد.وقتی فرآیند جدیدی به سیستم وارد می شود :باید حداکثر تعداد نمونه هایی از هر نوع منبع را که نیاز دارد ، اعلان نمایداین تعداد نمی تواند بیش از تعداد منابع موجود در سیستم باشدوقتی کاربر مجموعه ای از منابع را درخواست می کند ، سیستم باید تعیین کند آیا تخصیص این منابع سیستم را در حالت امن نگه می دارد یا خیراگر حالت امن نگه دارد منابع تخصیص می یابند وگر نه فرآیند باید منتظر بماند تا فرآیندهای دیگر ، منابع کافی را آزاد کنند.25

اسلاید 26: فصل هشتم : بن بست ها 3-5-8 الگوریتم بانکداری ( ادامه ... )برای پیاده سازی الگوریتم بانکدار از چندین ساختمان داده می توان استفاده کرد که حالت سیستم تخصیص را رمزگذاری می کنند.اگر n= تعداد فرآیندهای موجود در سیستم و m= تعداد انواع منابع باشد آنگاه به ساختمان داده های زیر نیاز داریم :AvailableMaxAllocationNeedبرداری به طول m که تعداد هر نوع منبع آزاد را نشان می دهد اگر Available[j] = k آنگاه k نمونه از منبع نوع Rj آزاد است.یک ماتریس n*m است که حداکثر تقاضای هر فرآیند را مشخص می کند اگر Max[i,j] = k باشد ، آنگاه Pi ممکن است حداکثر k نمونه از منبع نوع Rj را درخواست کند.یک ماتریس n*m است که تعداد هر نوع منبع ای را که فعلا به هر فرآیند تخصیص داده شده است مشخص می کند. اگر Allocation[i,j] = k آنگاه Pi فعلا k نمونه از منبع نوع Rj را در اختیار دارد.یک ماتریس n*m است که مشخص می کند هر فرآیند به چند منبع دیگر نیاز دارد. اگر Need[i,j] = k باشد آنگاه Pi به k نمونه دیگر از منبع نوع Rj نیاز دارد تا وظیفه اش را انجام دهد.26

اسلاید 27: فصل هشتم : بن بست ها 3-5-8 الگوریتم بانکدار ( ادامه ... )نکته : Need[i,j] = Max[i,j] – Allocation[i,j]اندازه و مقدار این ساختمان داده ها با گذشت زمان تغییر می کند. تذکر : می توان با هر سطر ماتریس های Allocation و Need به عنوان برداری برخورد کرد و به ترتیب با Allocationi و Needi به آنها مراجعه نمود.Allocationi = منابعی را مشخص می کند که فعلا در اختیار فرآیند Pi است.Needi = تعداد منابعی را مشخص می کند که ممکن است Pi برای تکمیل کردن وظیفه خود به آنها نیاز داشته باشد.27

اسلاید 28: فصل هشتم : بن بست ها 1-3-5-8 الگوریتم امنیتالگوریتمی که تشخیص می دهد سیستم در حالت امن است یا خیر به صورت زیر توصیف می شود.فرض کنید work برداری به طول m و Finish برداری به طول n باشد. work:= Available مقدار اولیه Finish := false , i = 1,2,3,…,n2. iای را پیدا کنید که : الف - Finish[i] = false ب - work ≥ Needi اگر نتوانستید این i را پیدا کنید، مرحله 4 را انجام دهید28

اسلاید 29: فصل هشتم : بن بست ها 1-3-5-8 الگوریتم امنیت ( ادامه ... )3. Work := work + Allocationi Finish[i] = Trueبرو به مرحله ی 2اگر برای تمام مقادیر i ، Finish[i] = True باشد ، سیستم در حالت امن است.نکته : این الگوریتم به عملیاتی از مرتبه m*n2 نیاز دارد تا مشخص کند سیستم در حالت امن است یا خیر.29

اسلاید 30: فصل هشتم : بن بست ها 2-3-5-8 الگوریتم درخواست منبع Requesti= بردار درخواست مربوط به فرآیند Pi اگر Requesti[j] = k آنگاه فرآیند Pi تعداد k نمونه از منبع نوع Rj را درخواست می کند.وقتی فرآیند Pi منابعی را درخواست می کند ، فعالیت های زیر صورت می گیرد :اگر Requesti ≤ Need : برو به مرحله 2 وگرنه شرط خطا را ایجاد کن ، زیرا فرآیند بیش از ادعایش درخواست کرداگر Requesti ≤ Available : برو به مرحله 3 وگرنه Pi باید منتظر بماند ، زیرا منابع آزاد نیستند30

اسلاید 31: فصل هشتم : بن بست ها 2-3-5-8 الگوریتم درخواست منبع ( ادامه ... ) .IIIاجازه دهد که سیستم با تغییر حالت به شرح زیر ، وانمود کند که تمام منابع Pi را تخصیص دادهAvailable := Available - Requesti ; Allocationi := Allocatoni + Requesti ;Needi := Needi - Requesti ;اگر حالت جدیدی که ایجاد شده امن باشد ، تراکنش کامل شده است و فرآیند Pi منابع خودش را در اختیار گرفته است.اگر حالت جدید امن نباشد ، Pi باید منتظر Requesti بماند و حالت قبلی باید بازیابی شود.31

اسلاید 32: فصل هشتم : بن بست ها 3-3-5-8 مثالسیستمی با 5 فرآیند P0 تا P4 و سه نوع منبع A ، B و C را در نظر بگیرید.A = منبع نوع A دارای 10 نمونه B = منبع نوع B دارای 5 نمونه C = منبع نوع C دارای 7 نمونه در زمان T0 وضعیت سیستم به صورت مقابل است : Allocation Max Available A B C A B C A B CP0 0 1 0 7 5 3 3 3 2P1 2 0 0 3 2 2P2 3 0 2 9 0 2P3 2 1 1 2 2 2P4 0 0 2 4 3 332

اسلاید 33: فصل هشتم : بن بست ها 3-3-5-8 مثال( ادامه ... )محتویات ماتریس Need برابر است با Max - Allocation و به صورت زیر است: Need A B CP0 7 4 3P1 1 2 2 P2 6 0 0P3 0 1 1P4 4 3 1ادعا می کنیم که سیستم فعلا در حالت امن است که در واقع دنباله <P1,P3,P4,P2,P0> معیار امنیت را برآورده می کند.اکنون فرض می کنیم که فرآیند P1 1 نمونه از منبع A و 2 نمونهدیگر از منبع C درخواست می کند Request1 = (1,0,2)چون Request1 ≤ Available است یعنی (1,0,2) ≤ (3,3,2)33

اسلاید 34: فصل هشتم : بن بست ها 3-3-5-8 مثال( ادامه ... )پس وانمود می شود که درخواست انجام پذیر است و به حالت جدید می رسد Allocation Max Available A B C A B C A B CP0 0 1 0 7 4 3 2 3 0P1 3 0 2 0 2 0P2 3 0 2 6 0 0P3 2 1 1 0 1 1P4 0 0 2 4 3 1برای اینکه مطمئن شویم این حالت امن است یا خیراز الگوریتم امنیت استفاده می شود و چون این الگوریتم <P1,P3,P4,P0,P2> تأیید می کندلذا فورا درخواست P1 برآورده می شود. از جمله درخواست های غیرقابل قبول در این حالت :درخواست (3,3,0) توسط P4: زیرا این منابع آزاد نیستنددرخواست (0,2,0) توسط P0: نتیجه امن نخواهد بود 34

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

اسلاید 36: فصل هشتم : بن بست ها 361-6-8: کشف بن بست در حالتی که یک نمونه از هر منبع وجود دارددر این حالت الگوریم کشف بن بست از یک نوع گرف تخصیص منبع به نام گراف انتظار(wait-for graph) استفاده می کند.برای بدست آوردن این گراف از گراف تخصیص منبع، گره های نوع منبع را حذف کرده،یالهای مناسبی را از بین می بریم.نکات:یال از Pi به Pj در یک گراف انتظار بیانگر این است که فرآیند Pi منتظر Pj است تا منبعی را که مورد نیاز Pi است آزاد کند.یال Pi  Pj در گراف انتظار وجود دارد اگر و فقط اگر تخصیص منبع متناظر با آن برای منبعی مثل Rq حاوی دو یال PiRq و RqPj باشد.

اسلاید 37: فصل هشتم : بن بست ها 37P1P2P3P4P2R1R3R5R2R5P1P2P3P4P2گراف تخصیص منبعگراف انتظار و متناظر با آن

اسلاید 38: فصل هشتم : بن بست ها 383. اگر در گراف انتظار چرخه ای وجود داشته باشد، به معنای وجود بن بست در سیستم است.4. برای کشف بن بست لازم است سیستم گراف انتظار را نگهداری کند و به طور تناوبی الگوریتمی را اجرا کند تا وجود چرخه ای را در این گراف جستجو نماید.5. الگوریتم کشف بن بست در گراف مستلزم عملیاتی به مرتبه ²n است( n = تعداد رأسهای موجود در گراف).

اسلاید 39: فصل هشتم : بن بست ها 392-6-4:کشف بن بست در حالی که هر نوع منبع دارای چندین نمونه استاز الگوی گراف انتظار نمی توان برای سیستم تخصیص منبعی بکار برد که در آن هر نوع منبع دارای چندین نمونه است.الگوریتمی که در اینجا ارائه می شود،دارای چندین ساختمان داده است که بر حسب زمان تغییر می کند(مثل الگوردتم بانکدار).Available: برداری به طول m که تعداد منابع آزاد مربوط به هر نوع منبع را نشان می دهد.Allocation: یک ماتریس n*m است که مشخص می کند چه تعداد از هر نوع منبع به هر فرآیند تخصیص داده شده است.Request:یک ماتریس n*m است که درخواست فعلی هر فرآیند را نشان می دهد.Request [i,j]: یعنی فرآیند Pi به تعداد k نمونه از منبع Rj را درخواست کرده است.

اسلاید 40: فصل هشتم : بن بست ها 40الگوریتم کشف بن بست،هر دنباله ای از تخصیص را برای هر فرآیندی که باید کامل شود بررسی می کند.1. فرض کنید work برداری به طول m و Finish برداری به طول n است،مقادیر اولیه : work := Available Finish [i] False : Allocation i ≠ 0 ,i=1,2,3,…,n True : ow2. اندیس i را بیابید بطوری که : 1) Finish [i] = False 2)Request i ≤ work اگر این i پیدا نشد به مرحله 4 برو.3. work := work + Allocation i Finish [i] = True برو به مرحله 2

اسلاید 41: فصل هشتم : بن بست ها 41نکته : این الگوریتم نیاز به عملیاتی از مرتبه m*n² دارد تا کشف کند آیا سیستم در حالت بن بست قرار دارد یا خیر.تذکر : علت اینکه پس از مرحلۀ ب مرحله 2 ،منابع فرآیند Pi آزاد می شوند این است که چون Request i ≤ work است لذا Pi در بن بست نیست،بنابرین حالت بهینه را در نظر می گیریم و فرض می کنیم Pi برای انجام وظیفه اش به منابع دیگری نیاز ندارد،بنابرین تمام منابع در اختیارش آزاد می شود.اگر فرض ما نادرست باشد،ممکن است بن بست رخ دهد که وقتی الگوریتم کشف بن بست اجرا شد،این بن بست تشخیص داده می شود.

اسلاید 42: فصل هشتم : بن بست ها 42تشریح این الگوریتم با مثال : Allocation Request Available A B C A B C A B CP0 0 1 0 0 0 0 0 0 0P1 2 0 0 2 0 2 A= 7 نمونه P2 3 0 3 0 0 0 B= نمونه P3 2 1 1 1 0 0 C= 6 نمونه P4 0 0 2 0 0 2ادعا می کنیم سیستم در حالت بن بست نیست: دنباله <P0,P2,P3,P1,P4> به ازای هر i منجر به این می شوند که Finish [i]= True است.

اسلاید 43: فصل هشتم : بن بست ها 43اگر P2نمونه دیگری از منبع c را درخواست کند، ماتریس Request به صورت مقابل در می آید.ادعا می کنیم سیستم در حالت بن بست قرار دارد،اگر منابع تخصیص یافته به P0 را آزاد کنیم،برای پذیرفتن تقاضا کافی نیست.بنابرین بن بست وجود دارد که فرآیندهای P1 وP2 و P3و P4 درآن شرکت دارند. Request A B CP0 0 0 0P1 2 0 2P2 0 0 1P3 1 0 0P4 0 0 2

اسلاید 44: فصل هشتم : بن بست ها 443-6-8 کاربرد الگوریتم کشف بن بستاینکه کی باید الگوریتم کشف بن بست را فراخوانی کرد، به دو عامل بستگی دارد: بن بست هرچند وقت یکبار ممکن است رخ دهد؟ درصورت بروز بن بست، چه تعدادی از فرآیندها تحت تاثیر قرار می گیرند؟اگر بن بست به کرات اتفاق افتد، الگوریتم کشف بن بست نیز باید به کرات اجرا شودمنابع فرآیندهایی که در بن بست قرار دارند، بیکاری مانند تابن بست شکسته شود.تعداد فرآیندهایی که در بن بست قراردارند ممکن است رشد کند.بن بست فقط در صورتی رخ می دهد که فرآیندی درخواستی داشته باشد که فورا برآورده نشود.به طور کلی هر وقت که درخواستی نتواند فورا برآورده شود، الگوریتم کشف بن بست را اجرا کنیم.در این حالت نه تنها می توان فرآیندهای موجود در بن بست را شناسایی کرد، بلکه می توان فرآیندی که موجب ایجاد بن بست شده را شناسایی کرد

اسلاید 45: فصل هشتم : بن بست ها 45نکته :چون فراخوانی الگوریتم کشف بن بست در هر درخواست ،سربار زمانی دارد، مناسبتر است که در فواصل زمانی خاص مثل هرساعت، یا هر وقت که بهره وری CPU به زیر 40 درصد رسید فراخوانی گردد.7-8 ترمیم از حالت بن بستوقتی الگوریتم کشف بن بست ، وجود بن بستی را تشخیص ، تصمیمات گوناگونی اتخاذ کرد.یک روش این است که به اپراتور خبرداده شود که بن بست اتفاق افتاده و کاربر سیستم را به طور دستی از حالت بن بست خارج کندروش دیگر این است که به سیستم اجازه داده شود به طور خودکار از حالت بن بست ترمیم (Recover) شوددو روش برای از بین بردن بن بست وجود دارد: 1. اجرای یکی از فرآیندهای موجود در انتظار چرخشی خاتمه یابد. 2. منابعی از یک یا چند فرآیند شرکت کننده در بن بست ، پس گرفته شود.

اسلاید 46: فصل هشتم : بن بست ها 461-7-8 خروج از بن بست با خاتمه فرآیندهابرای خروج از بن بست از طریق خاتمه فرآیندها، به یکی از 2 روش ممکن است عمل کنیم.در هر دو روش سیستم تمام منابعی را که در اختیار فرآیند خاتمه یافته قرار دارد، پس می گیرد.1- تمام فرآیندهای شرکت کننده در بن بست خاتمه یابند: در این روش ، چرخه بن بست شکسته می شود ولی هزینه آن زیاد است، زیرا کل محاسبات انجام شده توسط فرآیندها، دوباره باید انجام گیرد.2- فرآیندهای شرکت کننده در بن بست، یکی یکی خاتمه یابند تا بن بست برطرف شود: این روش منجر به سربار زیادی می شود، پس از خاتمه هر فرآیند، الگوریتم کشف بن بست اجرا می شود تا تعیین کند آیا هنوز فرآیندهایی در بن بست قرار دارند یا خیر

اسلاید 47: فصل هشتم : بن بست ها 47نکته : اگر از روش دوم استفاده شود، در مجموعه ای از فرآیندها که در بن بست قرار دارند، باید فرآیند (یا فرآیندهایی) را برای خاتمه انتخاب کنیم که به بن بست خاتمه دهند.عوامل زیادی برای خاتمه دادن فرآیند وجود در بن بست موثرند: 1- اولویت فرآیند چیست؟ 2- فرآیند چه مدتی اجرا شده، و چه مدتی نیاز به اجرا دارد؟ 3- فرآیند از چه نوع منابع و از چند تا از آنها استفاده تر است؟ (مثلا آیا پس گرفتن منابع ساده است؟) 4- به چه منابع دیگری نیاز دارد تا کامل شود؟ 5- چند فرآیند باید خاتمه یابند؟ 6- فرآیند به صورت محاوره ای است یا دسته ای؟

اسلاید 48: فصل هشتم : بن بست ها 482-7-8 خروج از بن بست با قبضه کردن منابعبرای خروج از بن بست از طریق قبضه کردن منابع، منابعی را از فرآیندهایی پس می گیریم و در اختیار فرآیندهای دیگر قرار می دهیم تا بن بست از بین برود.در این روش به سه موضوع باید توجه داشت:1- انتخاب یک قربانی: چه منابع و چه فرآیندهایی باید قبضه (قربانی) شوند؟ قبضه کردن طوری باشد که کمترین هزینه را داشته باشد؟2- عقبگرد: اگر منبعی را از فرآیندی پس می گیریم، با آن فرآیند چه باید بکنیم؟ باید این فرایند را به حالت امنی ببریم و اجرای آن را از آن حالت امن آغاز کنیم.3- گرسنگی: چگونه تضمین کنیم که حالت گرسنگی رخ نمی دهد؟ یعنی چگونه تضمین کنیم که همیشه منابع از یک فرآیند پس گرفته نمی شوند؟

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

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

اسلاید 51: فصل هشتم : بن بست ها 51برای تشریح این تکنیک سیستمی را در نظر می گیریم که شامل 4 دسته از منابع به شرح زیر باشد: منابع داخل: منابعی که توسط سیستم مورد استفاده قرار می گیرند، مثل بلوک کنترل فرآیند. حافظه مرکزی: حافظه ای که توسط کار کاربر مورد استفاده قرار می گیرد. منابع کار: دستگاههای قابل تخصیص (مثل گرداننده نوار) و فایل ها فضای قابل تعویض: فضای مورد نیاز کار هر کاربر در حافظه پشتیبان

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