Lecture 6: Deadlocks in Operating Systems PDF

‫سیستم عامل‬ Operating system Click to edit Master subtitle style Lecture 6 DeadLock ‫بن بست‬  ‫‪2‬‬ ‫‪[email protected]‬‬ ‫مدل سیستم‬ ‫‪ ‬منابع سیست...

‫سیستم عامل‬ Operating system Click to edit Master subtitle style Lecture 6 DeadLock ‫بن بست‬  ‫‪2‬‬ ‫‪[email protected]‬‬ ‫مدل سیستم‬ ‫‪ ‬منابع سیستم از انواع مختلف ‪ R1,R2,…….Rn‬هستند‪.‬‬ ‫‪ ‬قطعه هاي زماني پردازنده‪ ،‬فضاي حافظه‪ ،‬ابزارهاي خواندن ‪ /‬نوشتن‪... ،‬‬ ‫‪ ‬از هر منبع ‪ Ri‬به تعداد ‪ Wi‬در سیستم وجود دارد‪.‬‬ ‫‪ ‬مراحل استفاده از منابع توسط فرآیندها عبارت است از‪:‬‬ ‫‪ (1‬درخواست منبع‬ ‫تا زماني‌که درخواست قبول شود و منبع را دریافت کند‪ ،‬فرآیند منتظر خواهد ماند‪.‬‬ ‫‪ (2‬استفاده از منبع‬ ‫‪ (3‬آزاد سازي‬  ‫‪3‬‬ ‫‪[email protected]‬‬ ‫بن بست‪:‬‬ ‫‪ ‬بن بست را به صورت مسدود بودن دائمي مجموعه اي از فرایندها‪ ،‬که براي منابع‬ ‫سیستم رقابت میکنند یا با یکدیگر در ارتباط هستند‪ ،‬تعریف میکنند‪.‬این مسدود‬ ‫بودن ادامه مي‌یابد تا سیستم عامل عمل فوق العاده‌اي انجام دهد‪ ،‬مثال فرایندي‬ ‫را حذف کند یا مجبور به برگشت به عقب کند‪.‬‬ ‫‪ ‬براي بن بست راه حل کارآمدي وجود ندارد‪.‬‬ ‫‪ ‬تمام بن‌بست‌ها با نیازهاي متضاد دو فرایند یا بیشتر‪ ،‬براي منابع همراه هستند‪.‬‬  ‫‪4‬‬ ‫‪[email protected]‬‬ ‫مثال بن بست‬ ‫‪ ‬یک مثال بن بست‪ ،‬ترافیک است‪.‬در رانندگي قانون این است که هر خودرو باید‬ ‫تسلیم خودروي سمت راست باشد‪.‬در این صورت در حالت زیر چه رخ میدهد؟‬  ‫‪5‬‬ ‫‪[email protected]‬‬ ‫مثال بن بست در فرایندها‬ ‫‪ ‬ساده ترین نوع بن بست زماني اتفاق مي افتد که دو فرایند مجزا و همزمان‬ ‫منتظر بدست آوردن منبعي هستند که در اختیار دیگریست و خود نیز‬ ‫منابعشان را تا اتمام فرایند آزاد نمیکنند‪.‬‬ ‫‪Process P2‬‬ ‫‪Process P1‬‬ ‫‪Get B‬‬ ‫‪Get A‬‬ ‫‪Get A‬‬ ‫‪Get B‬‬ ‫‪Release B‬‬ ‫‪Release A‬‬ ‫‪Release A‬‬ ‫‪Release B‬‬ ‫‪.‬‬ ‫‪.‬‬ ‫‪.‬‬ ‫‪.‬‬ ‫‪6‬‬ ‫‪[email protected]‬‬ ‫انواع منابع‪:‬‬ ‫‪ ‬منابع‌نقش‌تعیین‌کننده‌اي‌در‌بن‌بست‌دارند‪.‬‬ ‫‪ ‬منابع‌به‌دو‌دسته‌تقسیم‌میشوند‪:‬‬ ‫‪ ‬منابع‌قابل‌استفاده‌مجدد‬ ‫‪ ‬منابع‌مصرف‌شدني‌یا‌غیر‌قابل‌استفاده‌مجدد‬  ‫‪7‬‬ ‫‪[email protected]‬‬ ‫منابع قابل استفاده مجدد‪:‬‬ ‫‪ ‬منابعي هستند که در هر لحظه از زمان تنها توسط یک فرایند قابل استفاده اند و‬ ‫استفاده از آنها موجب به پایان رسیدن آنها نمیشود(بدون آسیب دیدن آزاد میشوند)‬ ‫‪ ‬فرایند ها منابع را بدست مي آورند و سپس آنها را براي استفاده مجدد توسط سایر‬ ‫فرایند ها آزاد میکنند‪.‬‬ ‫‪ ‬پردازنده‪ ،‬کانالهاي ‪ ،I/O‬حافظه اصلي و ثانوي‪ ،‬دستگاه ها و ساختمان داده هایي مثل‬ ‫پرونده ها‪ ،‬پایگاه هاي داده و راهنماها از این دسته اند‪.‬‬ ‫‪ ‬بن بست زماني رخ میدهد که یک فرایند منابع را نگه دارد و منبع دیگري درخواست‬ ‫کند‪.‬‬  ‫‪8‬‬ ‫‪[email protected]‬‬ ‫مثالی از بن بست منابع قابل استفاده مجدد‪:‬‬ ‫‪ ‬فرض کنید فضاي حافظه که میتواند به فرایند ها تخصیص یابد ‪ 200 KB‬باشد‪.‬در‬ ‫این صورت ترتیب زیر موجب بروز بن بست میشود‪.‬‬ ‫‪P1‬‬ ‫‪P2‬‬ ‫‪...‬‬ ‫‪...‬‬ ‫;‪Request 80 Kbytes‬‬ ‫;‪Request 70 Kbytes‬‬ ‫‪...‬‬ ‫‪...‬‬ ‫;‪Request 60 Kbytes‬‬ ‫;‪Request 80 Kbytes‬‬  ‫‪9‬‬ ‫‪[email protected]‬‬ ‫منابع مصرف شدنی‪:‬‬ ‫‪ ‬این‌منابع‌تولید‌میشوند‌و‌از‌بین‌مي‌روند‪.‬‬ ‫‪ ‬وقفه ها‪ ،‬عالمتها‪ ،‬پیامها و اطالعات بافر ‪ I/O‬از این نمونه اند‪.‬‬ ‫‪ ‬کشف‌بن‌بستهاي‌حاصل‌از‌این‌منابع‌‌بسیار‌مشکل‌است‌و‌ممکن‌است ترکیب‌‬ ‫نادري‌از‌حوادث‌آنها‌را‌ایجاد‌کند‪.‬‬  ‫‪10‬‬ ‫‪[email protected]‬‬ ‫مثالی از بن بست منابع مصرف شدنی‪:‬‬ ‫‪ ‬در‌صورتیکه‌عمل‌‪ Receive‬مسدود‌کننده‌باشد‌بن‌بست‌اتفاق‌مي‌افتد‪.‬‬ ‫‪P1‬‬ ‫‪P2‬‬ ‫‪...‬‬ ‫‪...‬‬ ‫;)‪Receive(P2‬‬ ‫;)‪Receive(P1‬‬ ‫‪...‬‬ ‫‪...‬‬ ‫;)‪Send(P2, M1‬‬ ‫;)‪Send(P1, M2‬‬  ‫‪11‬‬ ‫‪[email protected]‬‬ ‫شرایط الزم برای ایجاد بن بست ‪:‬‬ ‫اگر چهار شرط زیر همزمان در سیستمي وجود داشته باشد‪ ،‬بن بست رخ میدهد(شرایط کافمن)‪:‬‬ ‫‪ (1‬انحصار متقابل(‪)Mutual Exclusion‬‬ ‫در هر لحظه تنها یک فرایند میتواند از یک منبع استفاده کند‪ ،‬اگر فرایند دیگري درخواست همان منبع‬ ‫را کند‪ ،‬باید منتظر بماند تا منبع آزاد شود‪.‬‬ ‫‪ (2‬نگهداری و انتظار(‪)Hold and Wait‬‬ ‫هنگام درخواست منبع جدید فرایند منابع قبلي تخصیص یافته را آزاد نمیکند‪.‬به عبارت دیگر فرایندي‬ ‫وجود دارد که حداقل یک منبع را در اختیار داشته باشد(نگهداري) و منتظر به دست آوردن منبع دیگري‬ ‫باشد که فعال در اختیار فرایند دیگري است‪.‬‬ ‫‪ (3‬انحصاری بودن (قبضه نشدنی)(‪)Non Preemption‬‬ ‫هنگامي که فرایندي منبعي را در اختیار دارد‪ ،‬نتوان آن منبع را به زور باز پس گرفت‪.‬‬ ‫‪ (4‬انتظار چرخشی (‪)Circular Wait‬‬ ‫یک زنجیره بسته اي از فرایندها وجود دارد به طوري که هر فرایند منتظر منبعي باشد که در اختیار‬ ‫فرایند دیگري است‪.‬‬  ‫‪12‬‬ ‫‪[email protected]‬‬ ‫گراف تخصیص منابع‪:‬‬ ‫‪ ‬گراف تخصیص منابع یک گراف جهت دار است که نحوه تخصیص منابع به فرایند ها را‬ ‫در هر لحظه از زمان نشان میدهد‪.‬‬ ‫‪ ‬براي تشخیص بن بست باید گراف تخصیص منابع را بعد از هر درخواست‪ ،‬هر تخصیص‪،‬‬ ‫یا هر ترخیص به روز کرد‪.‬‬ ‫‪ ‬در گراف ‪ ،‬منابع را با مربع (تعداد در آن مشخص)و فرایند را با دایره نشان میدهیم‪.‬‬ ‫‪ ‬وجود دور یا چرخه در گراف بیانگر بروز بن بست است‪.‬و اگر گراف تخصیص منابع فاقد‬ ‫چرخه باشد‪ ،‬حالت بن بست وجود ندارد‪.‬‬ ‫‪P‬‬ ‫‪S‬‬ ‫‪P‬‬ ‫‪S‬‬ ‫فرایند‌‪ P‬در‌انتظار‌منبع‌‪ S‬است‬ ‫فرایند‌‪ P‬منبع‌‪ S‬را‌در‌اختیار‌دارد‬ ‫‪13‬‬ ‫‪[email protected]‬‬ ‫مثال انتظار مدور یا چرخشی‬ ‫‪14‬‬ ‫‪[email protected]‬‬ ‫مثال‬ ‫در گراف مقابل وضعیت بن بست را بررسي نمایید‪.‬‬ ‫حل‪ :‬سه فرایند ‪ p1,p2,p3‬در بن‌بست هستند‬ ‫و این مثال (وجود چرخه همراه با بن‌بست)‬  ‫‪15‬‬ ‫‪[email protected]‬‬ ‫مثال‬ ‫در گراف مقابل وضعیت بن بست را بررسي نمایید‪.‬‬ ‫حل‪ :‬با وجود چرخه ‪ P1->R1 ->P3 ->R2 ->P1‬بن بست رخ نمي دهد‪.‬چون‬ ‫فرایند‪ P4‬میتواند منبع نمونه ‪ R2‬را آزاد کند و آنگاه منبع ‪ R2‬به فرایند‪ P3‬داده‬ ‫مي‌شود و چرخه از بین برود ‪.‬‬ ‫‪ ‬اگر چرخه‌اي در گراف وجود داشته باشد‪ ،‬ممکن است بن‌بست وجود داشته باشد‪.‬‬ ‫به عبارت دیگر وجود چرخه شرط الزم وقوع بن‌بست است اما کافي نیست!‬  ‫‪16‬‬ ‫‪[email protected]‬‬ ‫معیار تشخیص اولیه در گراف تخصیص منابع‬ ‫‪ ‬اگر گراف تخصیص منابع حلقه ندارد‪.‬‬ ‫‪ ‬سیستم بن بست ندارد‪.‬‬ ‫‪ ‬اگر گراف تخصیص منابع حلقه دارد‪.‬‬ ‫‪ ‬اگر از هر نوع منبع درگیر در حلقه فقط یک نمونه داریم‪ ،‬یک بن بست رخ داده است‪.‬‬ ‫‪ ‬اگر از هر نوع منبع درگیر در حلقه چندین نمونه داریم‪ ،‬ممکن است بن بست رخ داده‬ ‫باشد‪.‬‬  ‫‪17‬‬ ‫‪[email protected]‬‬ ‫روشهای برخورد با بنبست‬ ‫‪ (1‬نادیده گرفتن بن‌بست(شترمرغ)‬ ‫فرض میشود هیچگاه بن‌بست رخ نمي‌دهد‪ ،‬هیچ عملي در مقابل بن‌بست انجام نمي‌شود‪ ،‬پس از‬ ‫وقوع بن‌بست ري‌استارت مي‌شود‪.‬‬ ‫‪ (2‬پیشگیری یا جلوگیری از بن بست(‪)Prevention‬‬ ‫سیستم طوري طراحي شود که از قبل امکان بن‌بست از بین برود‪ ،‬یعني تضمین کنیم که‬ ‫حداقل یکي از چهار شرط بن‌بست رخ ندهد‪.‬‬ ‫‪ (3‬اجتناب از بن بست (‪)Avoidance‬‬ ‫در مورد درخواستهاي منبع طوري رفتار شود که حداقل یکي از چهار شرط بن بست رخ ندهد‪.‬‬ ‫‪ (4‬کشف بن بست (‪)Detection‬‬ ‫هرجا که ممکن باشد‪ ،‬منابع درخواستي به فرایندها داده میشود‪.‬سیستم عامل به طور متناوب‬ ‫الگوریتمي را دنبال میکندتا وجود شرط انتظار چرخشي را کشف کند‪.‬‬  ‫‪18‬‬ ‫‪[email protected]‬‬ ‫جلوگیری از بن بست‪:‬‬ ‫جلوگیري از بن بست با نقض کردن یکي از شرایط چهارگانه الزم براي بن بست‬ ‫انجام میشود‪:‬‬ ‫‪ (1‬نقض انحصار متقابل‬ ‫‪ (2‬نقض نگهداشت و انتظار‬ ‫‪ (3‬نقض شرط انحصاري بودن‬ ‫‪ (4‬نقض شرط انتظار مدور‬  ‫‪19‬‬ ‫‪[email protected]‬‬ ‫‪.1‬نقض انحصار متقابل‬ ‫‪ ‬این شرط را نمیتوان رد کرد‪ ،‬چرا که بعضي از منابع ذاتا‌ انحصاري هستند‪.‬مثال‌‬ ‫یک چاپگر تنها میتواند به یک فرایند پاسخ دهد یا نوشتن بر روي یک بانک‬ ‫اطالعاتي تنها توسط یک فرایند انجام میشود‪.‬‬  ‫‪20‬‬ ‫‪[email protected]‬‬ ‫‪.2‬نقض نگهداشت و انتظار‬ ‫‪ ‬میتوان فرایند ها را ملزم ساخت که اختصاص منابع تنها زماني انجام شود که‬ ‫تمام منابع مورد نیاز فرایند آزاد باشد و حتي اگر یک منبع آماده نبود هیچ‬ ‫اختصاصي انجام نشود‪.‬‬ ‫‪ ‬معایب این روش‪:‬‬ ‫‪ ‬انتظار طوالني فرایند براي تکمیل منابعش‬ ‫‪ ‬احتمال قحطي‬ ‫‪ ‬بیکار ماندن یک منبع به مدت طوالني منجر به بهره‌وري پایین منابع‬ ‫‪ ‬عدم پیش بیني منابع مورد نیاز در آینده‬  ‫‪21‬‬ ‫‪[email protected]‬‬ ‫‪.3‬نقض شرط انحصاری بودن‬ ‫براي پیشگیري از بروز این شرط دو راه پیشنهاد شده است‪:‬‬ ‫‪ ‬اگر فرایندي منابعي را در اختیار دارد‪ ،‬درخواست جدیدش موافقت نشود‪.‬در این حالت باید‬ ‫منابع قبلي خود را آزاد کند و در صورت نیاز‪ ،‬مجددا با منابع اضافي درخواست نماید‪.‬‬ ‫‪ ‬قبضه کردن فرایند با اولویت پایینتر‪ :‬زماني که یک فرایند نیاز به منبعي دارد که فرایند دیگري‬ ‫آن را نگه داشته است‪ ،‬سیستم عامل آنرا قبضه کرده و منابعش را آزاد میکند‪.‬‬ ‫‪ ‬در فرایند هاي اولویت بندي شده استفاده میشود‪.‬‬ ‫‪ ‬حالت منبع باید براحتي قابل ذخیره باشد تا بعدها بازیابي شود‪.‬‬  ‫‪22‬‬ ‫‪[email protected]‬‬ ‫‪.4‬نقض شرط انتظار مدور‬ ‫‪ ‬مرتب کردن منابع به صورت خطي‪ :‬به هر منبع یک شاخص نسبت داده میشود‪.‬‬ ‫در این صورت فرایند میتواند ابتدا منبع ‪ Ri‬و سپس منبع ‪ Rj‬را درخواست کند‬ ‫اگر ‪i