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

صفحه 1:


صفحه 2:


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

صفحه 4:
1-8 مدل سیستم هر سیستم متشکل از تعداد محدودی از منابع است که باید ‎ow‏ فرآیندهای رقیب توزیع شود. اگر فرآیندی نمونه ای از یک نوع منبع را درخواست کند , تخصیص هر نمونه از آن نوع ؛ آن درخواست را برآورده می کند. اگر درخواست برآورده نشود , آنگاه نمونه ها یکسان نیستند و نوع ‎wail esas Gai aus Gales yglo vax glia‏ 

صفحه 5:
دز عصلیات عادی هر فرآیند ممکن است به منورت زیر از یک منبع استفاده کند: ‎al‏ درخواست: اگر درخواست نتواند فورا عملی شود (مثلا منبع در اختیار فرآیند دیگری است) , فرآیند درخواست کننده باید منتظر بماند تا منبع را در اختیار گیرد. ‏ااءبه کارگیری : فرآیند می تواند منبع را در اختیار داشته باشد (مثلا اگر منبع درخواستی چاپگر باشد , می تواند عمل چاپ را در آن انجام دهد). ‏آزاد کردن : فرآیند , منابع را آزاد می کند. ‎ ‎1۳ 

صفحه 6:
۶ درخواست و آزاد کردن منابع , فراخوان های سیستم هستند (مثل سبط و6 سب :1 ... ) درخواست و آزاد كردن منابع ديكر مى تواند از طريق عمليات سم وكب< بروى سمافورها انجام شود. سيستم عامل براى كنترل منابع از جدول سيستم استفاده مى کند. جدول سیستم مشخص می کند که آیا منبعی آژاد است.یا تخصیص یافته است و چنانچه تخصیص ‎aish‏ باشد , به کدام فرآیند تخصیص بافته است. اگر فرآیندی منبع را درخواست کند و ‎ul‏ منبع در حال حاضر در واختیار منبع دیگری باشد , آن فرآیند در صف انتظار آن منبع قرار 

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

صفحه 8:
128 ترابظ وروی وضعیت بن بست در صورتی پیش می آید که چهار شرایط زیر هم زمان در سیستم وجود داشته باشند. باشند كه 00 منتظر منبعى باشد كه در اختيار 060 است و 0©) ‎pred ag cowl PC {Lisl 52 oS ash rerio plaiic‏ الل لا و۱ ۱ است و 05 منتظر منيفق 

صفحه 9:
2-2-8 گراف تخصبص منبع گراف تخصیص منابع سیستم , شامل مجموعه ای از رس ها به نام ‎٩‏ و مجموعه ای از یال ها به نام 0۵ است. مجموعه ۵ به دو نوع گره مختلف ‎sla eli a:‏ » و © تقسیم می شود. حاوی تمام فرآیندهای فعال در سیستم است =@ (م...,6066) حاوی انواع منابع موجود در سیستم است ‎R=‏ {RG,RO,...,Ra} 

صفحه 10:
6 ‏یال درخواست ) : نشان می دهد که فرآیند‎ (0 Rj ‏نمونه اى از منبع نوع 0 را درخواست كرذه است و منتظر آن‎ منبع است. 0 ۳( یال تخصیص ) : مشخص می کند که نمونه ای از منبع نوع ‎6٩‏ به فرآیند () تخصیص يافته است. هر فرآیند برای 6۱ را با یک دایره نشان می دهیم #هر نوع منبع با یک مرجع نشان داده می شود و اگر چند نوع از منبع ‎6٩‏ وجود داشته باشد , هر یک از نمونه ها به صورت نقطه ای در مرجع نشان داده می شود. 0 

صفحه 11:
P,PO,0O } RU,RO,RO,RE } PA RIGS RGRI PERI PARC ‏سوه مه‎ PO} aa Ro مثال : مجموعه هاى © و © و © كه عبارتند از : 

صفحه 12:
۷ اگر گراف فاقد چرخه (عع0) باشد , هیچ فرآیندی در بن بست نیست. ۷ اگر گراف حاوی چرخه باشد , ممکن است بن بست وجود داشته cee ee Sree vee Bcd ‏و بدون بست‎ 

صفحه 13:
3-8 روش هاى اداره كردن بن بست سه روش مختلف براى برخورد با مسئله بن بست وجود دارد : 1 می. تواان: ‎gl‏ پروتگلی اسستفاده كرد با اتصعين: توم أله براى حصول اطمينان از اينكه بن بست هركز رخ ندهد » سيستم ‎ely‏ یط سیستم دش واه الگورتمی ل 6 ۱ ب سب | بهتر است به جاى روش هاى كرافى معتل بيشكبرى از بن بست » اجتناب از بن بست , يا روش های کشف و ترمیم بن بست ‏ از 

صفحه 14:
4-8 پیشگیری از بن بست اگر تضمین کنیم که حداقل یکی از این شرایط برقرار نخواهد بود , می توانیم از وقوع بن بست پیشگیری کنیم. روش پیشگیری از بن بست , با بررسی هر یک از چهار شرط لازم برای وقوع بن بست ؛ تشریح می شود. 1-4-8 انحصار متقابل شرط انحصار متقابل باید برای منابع ‎pat‏ قابل اشتراک برقرار باشد. منابع قابل اشتراک ؛ نیاز به دستیابی انحصارمتقابل ندارد و در نتیجه نباید در بن بست حضور یابد. #هه طور کلی نمی توان با جلوگیری از شرط انحصار متقابل , از 

صفحه 15:
2-4-8 نگهداری و انتظار ( 6 ) برای اینکه تضمین شود شرط نگهداری و انتظار هرگز در سیستم رخ نمی دهد , باید اطمینان حاصل کنیم که وقتی فرآیندی منبعی را درخواست می کند , هیچ منبع دیگری را در اختیار ندارد. این روش مستلزم این است که هر فرآیند قبل از اجرا ؛ تمام منایع خود را درخواست کند و به آن تخصیص داده شود. که در واقع برای پیاده سازی این روش باید اجازه دهیم تا فراخوان های سیستمی که منابع را برای فرآیندی درخواست می کنند , مقدم بر سایر فراخوان ‎sl‏ سیستم باشند. الا پروتکل دیگری که می تواند مورد استفاده قرار گیرد این است که لک فرآیند در صورتی اجازه دارد منبعی را درخواست کند که هیچ 

صفحه 16:
3-4-8 بدون قبضه کردن ومين ترا لام بزای‌رین:بسب این( اسب گم سانسن كرشملا بد فرآیندهایی تخصیص یافته اند , توسط ساير فرآیندها قبضه نشوند. ‎sly‏ حصول اطمینان از عدم وقوع ای شرط از این پروتکل استفاده می کنیم که اگر فرآیندی که فعلا منبع را در اختیار ‎GIES gale 15,18‏ رآافرخوآنند اکتدکة فهرآآنمی:توانة بة.آن تخصیص یابد (یعنی فرآیند باید منتظر بماند) , تمام منابعی که فعلا در اختیارش است ؛ پس گرفته می شوند. ‏این منابع در لیست متابعی که اين فرآیند منتظر آنهاست اضافه می ‏بود. بدین ترئیب » فرآیند در صورتی می تواند دوباره شروع به 

صفحه 17:
3-4-8 بدون قبضه کردن ( ادامه... ) 2 در روش دیگر , اگو فرآیندی منبعی را درخواست کند , ابتدا بررسی می کنیم که آیا آن منابع مهیا هستند یا خیر که اگر ‎Lge‏ ‏باشند به آن تخصیص می دهیم وگرنه بررسی می کنیم ‎ol LT aS‏ منابع به فرآیندی دیگر تخصیص یافته اند که منتظر منابع دیگری هستند یا خیر. اگر اینطور باشد , منابع مطلوب را از فرآیند منتظر پس گرفته , آنها را به فرآیند درخواست کننده تخصیص می دهیم. ۷ اگر منابع درخواستی مهیا باشند یا در اختیار هیچ فرآیند منتظری نباشند , فرآیند درخواست کننده باید منتظر بماند. و 

صفحه 18:
4-4-8 انتظار چرخشی یکی از راه هایی که می توان تضمین شرط انتظار چرخشی برای ایجاد بن بست رخ نمی دهد , این است که یک ترتیب کلی به عنوان منابع اعمال شود و فرآیند , درخواست منابع را به ترتیب شمارش صعودی انجام دهد. روش ديكر اين است که , هر وقت فرآیندی نمونه ای از منبع نوع 6۱ را درخواست می کند » تمام منبع ‎cml sP(R) 2 PR) aLly Ri‏ + آزا سازد. زاد می سازد. مجموعه ای از انواع منابع ,60,86) 6 ‎R‏ © 6:6 ۳ 

صفحه 19:
5-8 اجتناب از بن بست الگوریتم هایی که در بخش (8-4) بررسی شدند , تضمین می کنند که حداقل یکی از شرایط لازم برای وقوع بن بست » رخ نمی دهند و در نتیجه بن بست به وجود نمی آید. روش دیگر برای اجتناب از بن بست ها , کسب اطلاعات در خصوص چگونگی تخصیص منابع است. حالت تخصیص منبع توسط تعداد منابع مهيا و تخصیص یافته و حداکثر تعداد تقاضای 6 ‏ار اه .ان ی‎ ae 

صفحه 20:
7 ee Oe 1-5-8 حالت امن حالت امن , حالتی است که سیستم بتواند منابعی را به ترتیب خاصی به هر فرآیند تخصیص دهد و از بن بست نیز اجتناب ورزد. به عبارت دیگر سیستم در صورتی در حالت امن است که , دنباله آمنی ‎»g>9 (Goer Gequewe)‏ داشته باشد. دنباله ای از فرآیندهای <م),...,0,6۵> در صورتی یک دنباله امن برای حالت تخصیص فعلی محسوب می شود که » برای هر ۱ , منابعی که ) می تواند درخواست کند , توسط منابع مهیا و تمام منابعی که در اختیار 6 که در آن ۲ است , برآورده شود. در اين وضعيت , چنانچه منابع مورد نیاز فرآیند 6۰ فورا مهیا نباشد , ‎PO‏ می تواند منتظر بماند تا تمام ها به اتمام برسند. 

صفحه 21:
1-5-8 حالت امن ( ادامه... ) هه ی حالتهای تا آنن »ین بست بیسعید بلگه. ممکن است منجر به بن بست شود. ۷ تا رمانی که حالت سیستم امن است سیستم عامل می تواند از حالت های نا امن ( و بن بست ) اجتناب کند. ۷در حالت نا امن , سیستم عامل نمی تواند فرآیندها را از درخواشنت صانعی ‎ways Ga eens Gi eee aS‏ ممع كته باتعتى مم‌رفتار فرآیندها , حالت های نا امن را کنترل می کند. 

صفحه 22:
7 5 ce 15 اگر یک سیستم تخصیص منبع داشته باشيم كه فقط يك نمونه از هر نوع متبع وجود داشته باشد ؛ برای اجتناب از بن بست مى توان از گراف های تخصیص منبع استفاده کرد. علاوه بر یال های درخواست و تخصیص , نوع جدیدی از یال به نام ‎Okto Oke Lleol JL‏ ( را تعریف می کنیم. یال ادعای 6 » نشان می دهد که فرآیند ) ممکن است در آینده منبع ‎6٩‏ را درخواست کند این یال همانند یال‌بدرخواست است ولى با خط جين مشخص مى شود. ها *** تذكر : وقترعفرآيند © منبع © را درخواست مى كند ؛ يال ادعاى ‎Tha. ow «age‏ و تا و ی و و د علد ور وی 

صفحه 23:
7 5 ce 15 2-5-8 الكوريتم كراف تخصيص منبع ( ادامه ... ) " نكته : دقت داشته باشيد كه قبل از اينكه فرآيند 40 شروع به اجرا كند ؛ تمام يال هاى ادعاى آن بايد در كراف تخصيص منبع قرار كيرد. ايق-شرط را بدين صورت مى توان بیان کرد که یال ادعای © ۵ وقتی به گراف اضافه مى شود كه تمام يال هاى وابسته به فرآيند ۱" , یال های ادعا باشند. ۴ نکته+ در صورت درخواهی فرآیند 6 منبع 6 پذیرفته می شود که تبدیل یال درخواست 0 ۵ به یال تخصیص ) 6 منجر به ایجاد چرخه در گراف تخصیص منبع نشود. ۴ نکته : اگر چرخه ای موجود نباشد , تخصیص منبع , سیستم را در عالت امن نگه می دارد. اگر چرخه ای وجود داشته باشد , 

صفحه 24:
برای تشریج این الگوریتم , گراف تخصیص شکل زیر را در نظر بگیرید. # فرض کنید 66 منبع 6 را درخواست می کند » اگرچه ۵6 فعلا آزاد است , نمی توانیم آن را به 6 تخصیص دهیم چون موجب حالت نا امن در گراف گراف تخصیص منبع برای تخصیص منبع اجتناب از بن بست 

صفحه 25:
3-5-8 الگوریتم بانکدار این الگوریتم برای سیستم هایی مناسب است که سیستم تخصیص منبع از هر نوع منبع , چند نمونه داشته باشد که در این حالت نمی توان از گراف تخصیص منبع استفاده کرد. وقتی فرآیند جدیدی به سیستم وارد می شود : * باید حداکثر تعداد نمونه هایی از هر نوع منبع را که نیاز دارد : اعلان نماید * این تعداد نمی تواند بیش از تعداد منابع موجود در سیستم باشد * وقتی کاربر مجموعه ای از منابع را درخواست می کند » سیستم ‎iS gad al‏ آبا تسین این متانم.سیستم را در حالّت امن:نگه ‎es‏ 

صفحه 26:
3-5-8 الگوریتم بانکداری ( ادامه ...۰ ) ۷ برای پیاده سازی الگوریتم بانکدار از چندین ساختمان داده می توان استفاده کرد که حالت سیستم تخصیص را رمزگذاری می 1 Ly oll ario E9i 5m olan oS w Jaleo w syly B vesuine | 2u1,9 5m slola; yiSla> oS Gul oto yaryile G& | 

صفحه 27:
3-5-8 الگوریتم بانکدار ( ادامه ...۰ ) * نکته : [,زسسساه - [رله0 > [رزلسه * اندازه و مقدار این ساختمان داده ها با گذشت زمان تغییر می کند. ** تذکر : می توان با هر سطر ماتریس های بسح 5 ‎Ored‏ به عنوان برداری برخورد کرد و به ترتیب با مسساه و 4 به آنها رایمه تمود: مسا < منابعی‌را مشخص‌می‌کند کم فعلا در اختیار فرآیند 6 ‎cowl‏ با ع ع عه ملهو سه به کید کم میک سم ‎“ele‏ 

صفحه 28:
1-3-5-8 الگوریتم امنیت الگوریتمی که تشخیص می دهد سیستم در حالت امن است با خیر به صورت زیر توصیف می شود. 1 فرض کنید مسب برداری به طول ‎Prick 9 w‏ برداری به طول » باشد. ود مقدار ‎Cc‏ ‎ee 1‏ ییات 4 ۳ 2. الى را بيدا كنيد كه : الف - ‎Abe‏ رم ا دهد work 2 Deed - 5 

صفحه 29:
1-3-5-8 الگوریتم امنیت ( ادامه ...۰ ) 3 4. Oork = work + @locuton, 1. Prctchfi] = Troe برو به مرحله ی ۱۱۱۰2 4 اگر برای تمام ‎Tre plas‏ - ۳۵۷ , ؛ باشد , سیستم در حالت امن است. کاکته : این الگوریتم به عملیاتی از مرتبه *م نیاز دارد تا 

صفحه 30:
2-3-5-8 الگوریتم درخواست منبع حصجح6< بردار درخواست مربوط به فرآیند :6 اگر ۲ < []بسجحه آنگاه فرآیند ۷ تعداد ۲ نمونه از منبع نوع 6 را درخواست می کند. وقتی فرآیند 6 منابعی را درخواست می کند , فعالیت های زیر صورت مى كيرد : ا. اگر لح 5 )دصجح©) : برو به مرحله 2 وكرنه شرط خطا را ايجاد کن , زیرا فرآیند بیش از ادعايش درخواست كرد ١ا.‏ اكر ططلس©) > دصجح2) : برو به مرحله 3 وكرنه :© بايد منتظر 60 11 

صفحه 31:
2-3-5-8 الگوریتم درخواست ‎Brio‏ ) ادامه ... ( ۰ جازه دهد که سیستم با تغییر حالت به شرح زیر , وانمود کند که تمام منابع ۵۱ را تخصیص داده ‎@uutuble - Request, ;‏ <: عاطدلم) ‎Bllocdon + Request, ;‏ -: مسا ‎QOved = Deed - Request ;‏ * اگر حالت جدیدی که ایجاد شده امن باشد , تراکنش کامل شده ‎cul‏ و فرآیند :0 منابع خودش را در اختیار گرفته است. ‏گر حالت جدید امن نباشد ؛ 6۱ باید منتظر )جح بماند و حالت 

صفحه 32:
3-3-5-8 منال سیستمی با 5 فرآیند 0 تا 0 و سه نوع منبع 0 ۰ 9 و ۵ را در نظر بگیرید. یه ‎Ow‏ مه © - منبع نوع © دارای10 نمونه و و و وه و وه 60 © = منبع نوع 6 دارای5 نمونه و هو وم و هه هم ‎ae‏ مس تست از 1 ۳ 9 0 < منبع نوع ۵ دارای7 نمونه و هو و هه هم در زمان ۲۵ وضعیت سیستم به صورت مفأل یرل : 8 © 8 ‎PO‏ ‏و و ع © ‎er ODO‏ 

صفحه 33:
3-3-5-8 منال( ادامه ... ) محتویات ماتریس ‎0٩‏ برابر است با هس6۳ - :0 و به صورت زیر است: 0 ادغا می کنیم که سیستم ققلا در حالت امن — 9 0 ۵ 9 است که در واقع دنباله ‎Ba Be‏ 9 699۵+ معيار امنيت را 6 6 نم برآورده می کند. ۱ وداج هع اکنون فرض می کنیم که فرآیند ‎٩‏ 0 نمونه از ‎oO‏ eo oad منبع 6 و 2 نمونه ‎ee eod‏ دیگر از منبع 0 درخواست می کند < ‎Reqest‏ ‏6 رونو 

صفحه 34:
3-3-5-8 منال( ادامه ... ) پس وانمود می شود که درخواست انجام پذیر است و به حالت جدید عع رسة لس ‎Clowes Om‏ تاق اكه سگرن دوت ‎a gil‏ ات ‎ee‏ 0 6 86 0 6 86 6 easiest حيزاز الگوزیتم امتیت اشتفاده ی ۴ ۳ ۴ ۳ ۲۱۳ متخ شود ل © © © 6 0 6 ‎ed‏ ee 8006 ‏وه‎ © oars” eo 6 0 0 Oda 5 . ‏ل 1 بقم‎ 1 ce 8} Baad va ‏قبول‎ Luss eal saath 51 ¥ ‏توسط ۵6: زیرا اين‎ )3,3,0( cast 34241 <PULPO,PH,PO,PO> ‎us‏ منابع آزاد نیستند ل5اگفورا درخواست ۵ برآور «رخهاست (0,2,0) توسط 0: نتیجه 

صفحه 35:
‎uS 2-8‏ ف بن , 5 ‏اگر از الگوریتم های پیشگیری يا اجتناب از بن بست استفاده نکند , شرایط بن بست ممکن است رخ دهند. در چنین محیطی , سیستم باید موارد زیر را فراهم کند : ‏26 الگوریتمی که حالت سیستم رت بررسی کند تا تعیین نماید بن بست وجود دارد يا خير ‏6 الگوریتمی که سیستم را از حالت بن بست ترمیم کند ‏02 ‏تذکر: الگوی کشف و ترمیم بن بست شامل سربارهایی است که نه تنها هزینه زمان اجرا برای نگهداری اطلاعات واجرای وللگوریتم کشف بن بست را در بر می گیرد,بلکه زیانهای ناشی از 

صفحه 36:
1-6-8: کشف بن بست در حالتی که یک نمونه از هر منبع وجود دارد در لین حالت الگوريم کشفبن بست ازیک نوع كرف تخصيص منبع به نام كراف ‎Wait) ail‏ 20 ۶0۲) استفاده می کند. برای بدست آوردن لین گراف از گراف تخصیص منبع. گره های نوع منبع را حذف کرده.یالهای مناسبى را از بين مى بريم. نكات: 1 يال از ۳ به 3 در ییک گراف انتظار بیانگر لین است که فرآیند 3 منتظر ۳ است تا منبعی را که مورد نیاز ۳ است آزاد کند. 2 یال (69 6۳۱ در گراف انتظار وجود دارد اگر و فقط آگر تخصیص منبع متناظربا آن برای منبعى مثل 29) حاوی دو یال ‎bb Rais POR‏ 8 

صفحه 37:


صفحه 38:
3. اگر در گراف انتظار چرخه ای وجود داشته باشد. به معنای وجود بن بست در سیستم است. 4 برای کشفبن بست لازم است سیستم گراف انتظار را نگهداری کند وبه طور تناوبی الگوریتمی را اجرا کند تا وجود چرخه ای را در اين گراف جستجو نماید. 5. الگوریتم کشفبن بست در گراف مستلزم عملیلتیبه مرتبه 210 استد 12 - تعداد رآسهای موجود در گراف). 

صفحه 39:
2-6-4:کشف بن بست در حالی که هر نوع منبع دارای چندین نمونه است از الگوی گراف انتظار نمی توان برای سیستم تخصیص منبعی بکار برد که در آن هر نوع منبع دارای چندین نمونه است. #لمالگوریتمی که در اینجا ارلئه می شود.دارای چندین ساختمان داده است که بر حسب زمان تغییر می کند(مثل الگوردتم بانکدار). عاتن/9): بسرداروسه طول وه کسه تسعداد مظبع آزاد مربوط بسه هر نوع منبع را نشانسی دهد لوصا (!): بسكماتريس»*>لستكه مشخصمىكند جه تعداد از هر نوع منبع به هر فييك تخصيصواده ث ت ‎otal Request‏ لسنکسه در خولستف-علی‌هر فولیند را نشان‌می‌دهد. ‎Aish shes Pande Recent [i]‏ از منیع )را دوخواستک ود لست 

صفحه 40:
کامل شود بررسی می کند. 1. فرض كنيد 5801116 بردارى به طول 322 و 171121512 بردارى به طول 12 است. ‎work := Available‏ : مقادير اوليه ‎Finish [i] False : Allocation i # 0‏ ‎A=1,2,3,....0‏ ‎Tru :Oow‏ 2. اندیس ژرا بیابید بطوری که :1( ‎Finish [i] = False‏ ۵ > 1[ 13600651 أكر لين 1 بيدا نشدبه مرحله 4 برو + ‎I. work := work‏ ‎Allocation i 3‏ ‎IL. Finish [i] = True ۵‏ 

صفحه 41:
6نکته : لین الگوریتم نیازبه عملیلتی از مرتبه 10*002 دارد غا کشف کند یا سیستم در حالت بن بست قرار دارد یا خیر. نکر : علت اینکه پس از مرحلة ب مرحله 2 «منلبع فرآ بند 83 آزاد مى شوند لين است كه جون ‎work‏ > [ 13600651 است لذا 3 در بن بست نیستبنابیین حالت بهینه را در نظر می گیریم و فرض می کنیم 3 برای انجام وظیفه اش‌به منلبع دیگری نیاز ندارد.بنابرین تمام منابع در اختیارش آزاد می شود. اگر فرض ما نادرست باشد.ممکن است‌بن بست رخ دهد که وقتی الگوریتم کشف‌بن بست اجرا شد.این بن بست تشخیص داده می شود. 

صفحه 42:
تشریح این الگوریتم با مثال : © © 0 © © © © © © eo © 40000 © © © 60 ‏و‎ © © © © © = P digas ee 8 098000 = ‏نمونه‎ ‎eo 6© 0 000 © © OF © ‏نمهنه‎ ‏هم‎ © © © © © © ادعا هى كنيم سيستم در حللت.ين بست نيست: دنبلله <00©,:0,06:03, ©0,0)كببه ازاى هر امنجر به اين می شوند که ه" -[] ۳۳#) است. 

صفحه 43:
‎gee Leal‏ نیم سیستم در خللت بن بست قراز دارد.اگر منابع تخصیص یافته به 0 را آزاد کنیم.برای پذیرفتن تقاضا کافی نیستبنابرین بن بست وجود دارد که فرآیندهای 000 و ۳ و ۳6و ‏درآن شرکت دارند. ‎ 

صفحه 44:
60 کاربرد الگوریتم کشف بن بست اینکه کی باید الگوریتم کشف بن بست را فراخوانی کرد؛ به دو عامل بستگی دارد: 1 _ بن بست هرچند وقت یکبار ممکن است رخ دهد؟ 1 درصورت بروز بن بست. چه تعدادی از فرآیندها تحت تاثیر قرار می گیرند؟ لااكر بن بست به كرات اتفاق افتدء الكوريتم كشف بن بست نيز بايد به كرات اجرل شود ۷منابع فرآیندهایی که در بن بست قرار دارنده بيكارى ‎ale‏ تابن بست شكسته شود. تعداد فرآیندهایی که در بن بست قراردارند ممکن است رشد کند. لابن بست فقط در صورتی رخ می دهد که فرآیندی درخواستی داشته باشد که فورا برآورده نشود. به طور کلی هر وقت كه درخواستى نتواند فورا برآورده شود الكوريتم كشف بن بست را اجرا كنيم. "در اين حالت نه تنها مى توان فرآيندهاى موجود در بن بست را شناسايى كرد بلكه مى توان فرآيندى كه موجب ايجاد بن بست شده را شناسايى كرد ‎er‏ 

صفحه 45:
8 نکته ی سربار زمانی دارد» مناسبتر است که در فواصل زمانی خاص مثل هرساعت یا هر وقت که بهره وری 06۳00 به زیر 60 درصد رسید فراخوانی گردد. مج ترمیم از حالت بن بست وقتی للگوریتم کشف بن بست ۰ وجود بن بستی را تشخیص » تصمیمات گوناگونی اتخلذ کرد. یک روش لین است که به اپراتور خبرداده شود که بن بست اتفاق افتاده و کاربر سیستم را به طور دستی از حالت بن بست خارج کند روش دیگر این است که به سیستم اجازه داده شود به طور خودکار از حالت بن بست ترمیم (حسح؟) شرد دو روش براى از بين بردن بن بست وجود دارد: ). اجراى يكى از فرآيندهاى موجود در انتظار جرخشى خاتمه يابد. ‎CO 66‏ ند له نیا دق ند گنه کت ده هافر گر که گنه هر 

صفحه 46:
0-0 خروج از بن بست با خاتمه فرآیندها برای خروج از بن بست از طریق خاتمه فرآیندهاء به یکی از 6 روش ممکن است عمل کنیم. در هر دو روش سیستم تمام منابعی را که در اختيار فرآيند خاتمه يافته قرار دارد؛ يس مى كيرد. - تمام فرآيندهاى شركت كننده در بن بست خاتمه يابند: در اين روش ‎٠‏ جرخه بن بست شکسته می شود ولی هزینه آن زیاد است؛ زيرا كله محاسبات انجام شده توسط فرآيندهاء دوباره بايد انجام كيرد. ©- فرآيندهاى شركت کننده در بن بست» یکی یکی خاتمه یابند تا بن بست برطرف شود: این روش منجر به سربار زیادی می شود» پس از خاتمه هر فرآیند. الگوریتم کشف بن بست اجرا می شود تا تعبین کند آیا هنوز فرآیندهایی در بن بست قرار دارند یا خیر 8 

صفحه 47:
|[ نکته : اگر از روش درم استفاده شود در مجموعه ای از فرآیندها که در بن بست قرار دارند؛ بايد فرآیند (یا فرآیندهایی) را برای خاتمه انتخاب کنیم که به بن بست خاتمه دهند. عوامل زیادی برای خاتمه دادن فرآیند وجود در بن بست موثرند: )- اولویت فرآیند چیست؟ ©- فرآیند چه مدتی اجرا شده» و چه مدتی نیاز به اجرا دارد؟ ©- فرآيند از جه نوع منابع و از چند تا از آنها استفاده تر است؟ (مثلا آیا پس گرفتن منابع ساده لست؟) “6 به چه منابع دیگری نیاز دارد تا کامل شود؟ ©- جند فرآيند بايد خاتمه یابند؟ جج©- فرآيند به صورت محاوره اى است يا دسته اى؟ 

صفحه 48:
‎O-P-O‏ خروج از بن بست با قبضه كردن منابع ‏براى خروج از بن بست از طریق قبضه کردن منابع» منابعی را از فرآیندهایی پس می گیریم و در اختيار فرآيندهاى ديكر قرار مى دهيم تا بن بست از بين برود. ‏در اين روش به سه موضوع بايد توجه داشت: ‏انتخاب یک قربانی: چه منابع و چه فرآیندهایی باید قبضه (قربانی) شوند؟ قبضه کردن طوری باشد که کمترین هزینه را داشته باشد؟ ‏©- عقبكرد: اكر منبعى را از فرآيندى بس مى كيريم, با آن فرآيند جه بايد بكنيم؟ بايد اين فرايند را به حالت امنى ببريم و اجراى آن را از آن حالت امن آغاز كنيم. ‏©- كرسنكى: جكونه تضمين كنيم كه حالت كرسنكى رخ نمى دهد؟ يعنى جكونه تضمين كنيم كه ‏هميشه منابع از يك فرآيند يس كرفته نمى شوند؟ ‎eo‏ 

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

صفحه 50:
©-© رهیافت ترکیبی برای مسئله بن بست محققین معنقدند که هیچکدام از راه حل های مسئله بن بست (پیشگیری» اجتناب و کشف بن بست) به تنهایی برای مسئله تخصیص منبع در سیستم های عامل مناسب نیستند و می بایست اين سه رهيافت با هم ترکیب شوند تا برای هر دسته از فرآیندهای موجود در سیستم » رهیافت مناسبی انتخاب گردد. ۷راه حل پیشنهادی »براین ایده استوار است که منابع می توانند به دسته هایی شوند که ترتیب مراتبی دارند که تکنیک ترتیب منبع که در بخش 0-6-۴ توضیح داده شد به اين دسته از منایع اعمال می شود. در هردسته از منابع » مناسبترین تکنیک برای برطرف کردن بن بست مورد استفاده قرار مى كيرد so 

صفحه 51:
برای تشریح این تکنیک سیستمی را در نظر می گیریم که شامل 6 دسته از منابع به شرح زیر باشد: [] مذابع داخل: منایعی که توسط سیستم مورد لستفاده قرار می گیرند» مثل بلوک کنترل فریند. [] حافظه مرکزی: حافظه ای که توسط کار کاربر مورد استفاده قرار می گیرد. [] منابع کار: دستگاههای قابل تخصیص (مثل گرداننده نوار) و فایل ها [] فضای قابل تعویض: فضای مورد نیاز کار هر کاربر در حافظه پشتیبان 60 

صفحه 52:
راه حل ترکیبی مسئله بن بست برای اين سیستم » دسته های منابع را به صورت فوق مرتب می کند و برای هر دسته از منابع از رهیافت های زیر استفاده می کند: [] منابع داخلی: از طریق ترتیب منابع می توان از بن بست پیشگیری کرد» زیرا نیاز به انتخاب های زمان اجرا برای به تعویق انداختن درخواست ها نیست. [۲] حافظه مرکزی: از طریق قبضه کردن می توان از بن بست پیشگیری کرد. زیرا هر کاری همواره می تواند از حافظه خارج شود و حافظه پس گرفته شود. [] منابع کار: می توان از بن بست اجتناب کرد زیرا اطلاعات مورد نیاز» برای نیازمندیهای منبع» از طریق کارت های کنترل کار به دست می آیند. [] فضای قابل تعویض: فضا را می توان از قبل تخصیص داد زیرا حداکثر فضای لازم همواره مشخص است. ‎se‏ 

صه ی فصل 8سیستم عامل دانشگاه آزاد اسالمي واحد قائم‌شهر استاد :آقای عسکری ‏میالد ‏میالد قاسمپوری اعضای جعفری جعفری گروه : زاهدی رضا ‏ زاهدی رضا آذین ‏ آذین مهرپورشاد مهرپورشاد 1 فصل هشتم بن بست عداد کل اسالید 2 5 2 دانشگاه آزاد اسالمي واحد قائم‌شهر LOGO فصل هشتم :بن بست ها در محیط چندپردازنده ای ،چندین فرآیند ممک4ن است برای تعداد محدودی از منابع با هم رقابت کنند. فرآیندی ،منابع4ی را درخو4اس4ت م4ی کن4د ،اگ4ر ای4ن مناب4ع در آن زمان فراه4م نباش4د ،فرآین4د ب4ه حال4ت انتظار م4ی رود .ممکن اس4ت مناب4ع درخواس4تی ای4ن فرآین4د توسط فرآیندهای دیگری ک4ه در انتظار هس4تند ،نگهداری شون4د و ای4ن فرآین4د هرگز از حالت انتظار خارج نشود .این وضعیت را بن بست گویند. 3 LOGO فصل هشتم :بن بست ها 1-8مدل سیستم ه4ر س4یستم متشک4ل از تعداد محدودی از مناب4ع اس4ت ک4ه بای4د بین فرآیندهای رقیب تو4زیع شو4د. اگ4ر فرآیندی نمون4ه ای از ی4ک نوع منب4ع را درخواس4ت کن4د ،تخصیص هر نمونه از آن نوع ،آن درخواست را برآورده می کند. اگ4ر درخواس4ت برآورده نشو4د ،آنگاه نمون4ه ه4ا یکس4ان نیستند و نوع منابع به طور مناسب دسته بندی نشده اند. 4 LOGO فصل هشتم :بن بست ها در عملیات عادی ه4ر فرآین4د ممک4ن اس4ت ب4ه ص4ورت زیر از یک منبع استفاده کند: .I درخواس4ت: اگ4ر درخواس4ت نتوان4د فورا عمل4ی شود (مثال منبع در اختیار فرآیند دیگری است) ،فرآیند درخواست کننده باید منتظر بماند تا منبع را در اختیار گیرد. .IIب4ه کارگیری : فرآین4د م4ی توان4د منب4ع را در اختیار داشت4ه باشد (مثال اگ4ر منب4ع درخواس4تی چاپگ4ر باش4د ،م4ی توان4د عمل چاپ را در آن انجام دهد). 5 .IIIآزاد کردن : فرآیند ،منابع را آزاد می کند. LOGO فصل هشتم :بن بست ها درخواس4ت و آزاد کردن مناب4ع ،فراخوان های س4یستم هستند (مثل ) ... ، Request ،Release device درخواست و آزاد کردن منابع دیگر می تواند از طر4یق عملیات wait و signalبروی سمافورها انجام شود. س4یستم عام4ل برای کنترل مناب4ع از جدول س4یستم اس4تفاده می کند. جدول س4یستم مشخ4ص م4ی کن4د ک4ه آی4ا منبع4ی آزاد اس4ت ی4ا تخصیص یافت4ه اس4ت و چنانچ4ه تخص4یص یافت4ه باش4د ،ب4ه کدام فرآیند تخصیص یافته است. اگ4ر فرآیندی منب4ع را درخواس4ت کن4د و آ4ن منب4ع در حال حاضر در 6اختیار منبع دیگری باشد ،آن فرآیند در ص4ف انتظار آن منبع قرار LOGO فصل هشتم :بن بست ها 2-8مشخص کردن بن بست بدیهی است که بن بست ها مطلوب نیستند .در بن بست ها : • • اجرای فرآیندها خاتمه نمی یابد مناب4ع س4یستم ب4ه ه4م گره م4ی خورد و از شروع کار جلوگیری می شود 7 LOGO فصل هشتم :بن بست ها 1-2-8شرایط ضروری وضعی4ت ب4ن بس4ت در ص4ورتی پی4ش م4ی آی4د ک4ه چهار شرای4ط زی4ر هم زمان در سیستم وجود داشته باشند. .1انحصار متقابل اختیار نگهداریدر یک منبع را غیرحداقل حالت که داشته باشد وجود فرآیند باید یعنی شود. اشتراکی در باید منبع یک حداقل وجودعهده منبع به منتظر آزادسازی قبضه شوند ،یعنی توانند نمی داشته ‏P0,P1,…,Pn واز ای 4عه منابعمجمو باید فرآیندهای& )Hold انتظار (Wait نگهداری .2 در فعال که باشد دیگری منبع آوردن بدست منتظر و باشد داشته کردنکند استفاده منبع از آن تواند می فرآیند یک فقط زمان .در هر کامل از پس که دارد اختیار در را آن که است فرآیندی منبعی باشد که در اختیار P1است و P1 منتظر ‏P0 باشند که قبضه بدون .3 کردناست فرآیندهای دیگر .اختیار درمی آزاد منبعی ،آن .وظیفه خود کند P2است و به همین ترتیب Pn- ، اختیار را که باشد منتظر .4انتظار چرخشی 1منتظر منبعی است که در اختیار Pnاست و Pnمنتظر منبعی است که در اختیار P0است. 8 LOGO فصل هشتم :بن بست ها 2-2-8گراف تخصیص منبع گراف تخص4یص مناب4ع س4یستم ،شام4ل مجمو4ع4ه ای از رأ4س ه4ا به نام Vو مجموعه ای از یال ها به نام Eاست. مجموع4ه Vب4ه دو نوع گره مختل4ف ب4ه نام های Pو Rتقس4یم می شود. حاوی تمام فرآیندهای فعال در سیستم است =P } { P1,P2,…,Pn حاوی انواع منابع موجود در سیستم است =R } { R1,R2,…,Rn 9 LOGO فصل هشتم :بن بست ها ‏Rj (Piیال درخواس4ت ) :نشان م4ی ده4د ک4ه فرآیند Pi نمون4ه ای از منبع نوع Rjرا درخواست کرده است و منتظ4ر آن منبع است. ‏Rj (Piیال تخص4یص ) :مشخ4ص می کند ک4ه نمونه ای از منبع نوع Rjبه فرآیند Piتخصیص یافته است. ‏هر فرآیند برای Piرا با یک دایره نشان می دهیم ‏ه4ر نوع منب4ع ب4ا ی4ک مرج4ع نشان داده م4ی شود و اگ4ر چند نوع از منب4ع Rjوجود داشت4ه باش4د ،ه4ر ی4ک از نمون4ه ه4ا ب4ه صورت نقطه ای در مرجع نشان داده می شود. 10 LOGO فصل هشتم :بن بست ها } P1,P2,P3 مثال :مجموعه های Pو Rو Eکه عبارتند از : }P3 ‏P1,R3 ‏P2,R2 ‏P2,R2 ‏R3 ‏P 3 11 ‏P1,R1 ‏R3,R1 ‏R1 ‏P 2 ‏R4 } R1,R2,R3,R4 ‏P1 ‏R2 ‏R1,P2 ‏P1 LOGO فصل هشتم :بن بست ها اگر گراف فاقد چرخه ( )Cycleباشد ،هیچ فرآیندی در بن بست نیست. اگر گراف حاوی چرخه باشد ،ممکن است بن بست وجود داشته باشد. R3چرخه R1 نشان دهنده R1ی4ک نمون4ه داشت4ه باشن4د ، اگ4رPه4ر نو4ع منب4ع دقیق4ا گراف تخصیص منبع با 2 بست4ر نو4ع منب4ع دارای چن4د نمون4ه باشند ، بن4ا اگ4ر ه وجود ب4ن بس4ت اس4ت ام ‏P وجود چرخه الزاما به معنای وجود بن بست نیست. 3 ‏P1 ‏P ‏P ‏R2 3 ‏P1 2 12 ‏P 4 گراف تخصیص منبع با چرخه R4و بدون بست ‏R2 LOGO فصل هشتم :بن بست ها 3-8روش های اداره کردن بن بست سه روش مختلف برای برخورد با مسئله بن بست وجود دارد : .1م4ی توان از پروتکل4ی اس4تفاده کرد ت4ا تضمی4ن شود که رودهرگز رخ ندهد ،سیستم بست بستبن بناینکه اطمینان از برای حصو4ل نمی سیستم هرگز به اجتناب از بن بست الگوبست تواند بن پیشگیری از محیطالگوی تواند از می مهیا یا برا 4ریتمی در حالتاز کند وکهسپس شود س4ت وارد ب4ن میس4یستم سیستمداد توان اجازه این4ی .2م نمی اتفاق شرایط بن تعییناز تا یکی تستحداقل کنند ( افتد)و یا خیر است بستداده بست رخ کند بن استفادهرا سیستم گردد کند خارج حالت بن بست بنابراین بکار گیرد. میآنافتد ترمیم اتفاق برای ندرت الگوریتمی بست بست به بنها بن سیستم بعضی وجود درصو4رت در .3م4ی توان از مس4ئله ب4ن بس4ت ص4رفه نظر کرد و اینطور بهتر است به جای روش های گرافی مثل پیشگیری از بن بست ، وانمود کرد ک4ه ب4ن بس4ت در س4یستم رخ نم4ی ده4د (این روش اجتناب از بن بست ،یا روش های کشف و ترمیم بن بست ،از 4تفاده می در اغل4ب س4یستم عام4ل های مجموع4ه یونیک4س اس این روش ارزان استفاده کرد. شود) 13 LOGO فصل هشتم :بن بست ها 4-8پیشگیری از بن بست اگر تضمین کنیم که حداقل یکی از این شرایط برقرار نخو4اهد بود ، م4ی توانی4م از وقوع ب4ن بست پیشگیری کنیم .روش پیشگیری از ب4ن بس4ت ،ب4ا بررس4ی ه4ر ی4ک از چهار شرط الزم برای وقوع بن بست ،تشریح می شود. 1-4-8انحصار متقابل شرط انحص4ار متقاب4ل بای4د برای مناب4ع غی4ر قابل اشتراک برقرار باشد .مناب4ع قاب4ل اشتراک ،نیاز ب4ه دس4تیابی انحصارمتقابل ندارد و در نتیجه نباید در بن بست حضور یابد. 414ه طور کل4ی نم4ی توان ب4ا جلوگیری از شرط انحص4ار متقابل ،از ‏ب LOGO فصل هشتم :بن بست ها 2-4-8نگهداری و انتظار ()Hold & Wait برای اینک4ه تضمی4ن شود شرط نگهداری و انتظار هرگ4ز در سیستم رخ نم4ی ده4د ،بای4د اطمینان حاص4ل کنی4م ک4ه وقت4ی فرآیندی منبعی را درخواست می کند ،هیچ منبع دیگری را در اختیار ندارد. ای4ن روش مس4تلزم ای4ن اس4ت ک4ه ه4ر فرآین4د قب4ل از اجرا ،تمام منابع خود را درخواس4ت کن4د و ب4ه آ4ن تخص4یص داده شود .ک4ه در واقع برای پیاده س4ازی ای4ن روش بای4د اجازه دهی4م تا فراخوان های س4یستمی ک4ه مناب4ع را برای فرآیندی درخواس4ت م4ی کنند ،مقدم بر سایر فراخوان های سیستم باشند. پروتکل دیگری که می تواند مورد استفاده قرار گیرد این است که 415ک فرآین4د در ص4ورتی اجازه دارد منبع4ی را درخواس4ت کن4د ک4ه هیچ ی LOGO فصل هشتم :بن بست ها 3-4-8بدون قبضه کردن س4ومین شرط الزم برای ب4ن بس4ت ای4ن اس4ت ک4ه ،منابع4ی ک4ه فعال به فرآیندهای4ی تخص4یص یافت4ه ان4د ،توس4ط س4ایر فرآینده4ا قبضه نشوند. برای حص4ول اطمینان از عدم وقوع ای شرط از ای4ن پروتکل اس4تفاده م4ی کنی4م ک4ه اگ4ر فرآیندی ک4ه فعال منبع را در اختیار دارد ،مناب4ع دیگری را درخواس4ت کن4د ک4ه فورا نم4ی توان4د ب4ه آن تخص4یص یاب4د (یعن4ی فرآین4د بای4د منتظ4ر بمان4د) ،تمام منابع4ی که فعال در اختیارش است ،پس گرفته می شوند. ای4ن مناب4ع در لیس4ت منابع4ی ک4ه ای4ن فرآین4د منتظ4ر آنهاست اضاف4ه می 16شود .بدی4ن ترتی4ب ،فرآین4د در ص4ورتی م4ی توان4د دوباره شروع به LOGO فصل هشتم :بن بست ها 3-4-8بدون قبضه کردن ( ادامه) ... در روش دیگ4ر ،اگ4ر 4فرآیندی منبع4ی را درخواس4ت کند ،ابتدا بررس4ی م4ی کنی4م ک4ه آی4ا آ4ن مناب4ع مهی4ا هس4تند ی4ا خی4ر ک4ه اگ4ر مهیا باشن4د ب4ه آ4ن تخص4یص م4ی دهی4م وگرن4ه بررس4ی م4ی کنی4م ک4ه آی4ا آن مناب4ع ب4ه فرآیندی دیگ4ر تخص4یص یافت4ه ان4د ک4ه منتظ4ر منابع دیگری هس4تند ی4ا خیر .اگ4ر اینطور باش4د ،مناب4ع مطلوب را از فرآیند منتظ4ر پ4س گرفت4ه ،آنه4ا را ب4ه فرآین4د درخواس4ت کننده تخصیص می دهیم. اگ4ر مناب4ع درخواس4تی مهی4ا باشن4د ی4ا در اختیار هی4چ فرآیند منتظری نباشند ،فرآیند درخواست کننده باید منتظر بماند. 17 LOGO فصل هشتم :بن بست ها 4-4-8انتظار چرخشی یک4ی از راه های4ی ک4ه م4ی توان تضمی4ن شرط انتظار چرخشی برای ایجاد ب4ن بس4ت رخ نم4ی ده4د ،ای4ن اس4ت ک4ه ی4ک ترتی4ب کل4ی به عنو4ان مناب4ع اعمال شود و فرآین4د ،درخو4اس4ت مناب4ع را ب4ه ترتیب شمارش صعودی انجام دهد. روش دیگ4ر ای4ن اس4ت ک4ه ،ه4ر وق4ت فرآیندی نمون4ه ای از منبع نو4ع Rj را درخواس4ت م4ی کن4د ،تمام منب4ع Riرا ک4ه ) F(Ri) ≥ F(Rjاست ، آزاد می سازد. مجموعه ای از انواع منابع R = {R1,R2, ‏R ‏N ‏F:R }…,Rm 18 LOGO فصل هشتم :بن بست ها 5-8اجتناب از بن بست الگوریت4م های4ی ک4ه در بخ4ش ( )8-4بررس4ی شدن4د ،تضمی4ن م4ی کنند ک4ه حداق4ل یک4ی از شرای4ط الزم برای وقوع ب4ن بس4ت ،رخ نمی دهند و در نتیجه بن بست به وجود نمی آید. روش دیگ4ر برای اجتناب از ب4ن بس4ت ه4ا ،کس4ب اطالعات در خصوص چگونگی تخص4یص منابع است. الگوریت4م های گوناگون4ی وجود دارن4د ک4ه از نظ4ر نیاز ب4ه اطاعات ،با ‏ نکت4ه :حال4ت تخص4یص منب4ع توس4ط تعداد منابع یکدیگ4ر متفاوتند .در س4اده تری4ن و مفیدتری4ن مدل الزم اس4ت که تقاضای تعداد حداکثر 4ر نو یافت4ه مهی4ا و اعالن نیاز دارد ، را که و4ع منبع4ی تخص4یص تعداد ه فرآین4د ،حداکث4ر ه4ر کند. فرآیندها تعریف می شود. 19 LOGO فصل هشتم :بن بست ها 1-5-8حالت امن حال4ت ام4ن ،حالت4ی اس4ت ک4ه س4یستم بتو4ان4د منابع4ی را ب4ه ترتیب خاص4ی ب4ه ه4ر فرآین4د تخص4یص ده4د و از ب4ن بس4ت نیز اجتناب ورزد. ب4ه عبارت دیگ4ر س4یستم در ص4ورتی در حال4ت ام4ن اس4ت ک4ه ،دنباله امنی ( )Safe Sequenceوجود داشته باشد. دنبال4ه ای از فرآیندهای < >P1,P2,…,Pnدر ص4ورتی ی4ک دنبال4ه امن برای حال4ت تخص4یص فعل4ی محس4وب م4ی شود ک4ه ،برای هر ، Pi منابع4ی ک4ه Piم4ی تو4ان4د درخواس4ت کن4د ،توس4ط مناب4ع مهیا و تمام منابعی که در اختیار Pjکه در آن i<jاست ،برآورده شود. در ای4ن وضعی4ت ،چنانچ4ه مناب4ع مورد نیاز فرآین4د Piفورا مهی4ا نباشد ، 20 Piمی تو4اند منتظر بماند تا تمام Piها به اتمام برسند. LOGO فصل هشتم :بن بست ها 1-5-8حالت امن ( ادامه) ... بن نا امن بست همه ی حالتهای نا امن ،بن بست نیستند بلکه حالت نا امن ممکن است منجر به بن بست شود. امن ت4ا رمان4ی ک4ه حال4ت س4یستم ام4ن اس4ت س4یستم عام4ل م4ی تواند از حالت های نا امن ( و بن بست ) اجتناب کند. در حال4ت ن4ا ام4ن ،س4یستم عام4ل نم4ی توان4د فرآیندها را از درخواس4ت منابع4ی ک4ه منجرب4ه ب4ن بس4ت م4ی شون4د من4ع کن4د ،یعنی 21رفتار فرآیندها ،حالت های نا امن را کنترل می کند. LOGO فصل هشتم :بن بست ها 2-5-8الگوریتم گراف تخصیص منبع اگ4ر ی4ک سیستم تخص4یص منبع داشته باشیم ک4ه فقط ی4ک نمون4ه از هر نوع منب4ع وجود داشت4ه باش4د ،برای اجتناب از ب4ن بس4ت می توان از گراف های تخصیص منبع استفاده کرد. عالوه بر یال های درخواس4ت و تخص4یص ،نوع جدیدی از یال به نام یال ادعا ( ) Claim Edgeرا تعریف می کنیم. یال ادعای Rj Piنشان م4ی ده4د ک4ه فرآین4د Piممک4ن است در آینده منب4ع Rjرا درخواس4ت کن4د ای4ن یال همانن4د یال درخواس4ت است ولی با خط چین مشخص می شود. ‏ تذک4ر :وقت4ی فرآین4د Piمنب4ع Rjرا درخواس4ت م4ی کند ،یال ادعای 22 LOGO فصل هشتم :بن بست ها 2-5-8الگوریتم گراف تخصیص منبع ( ادامه ) ... ‏ نکت4ه :دق4ت داشت4ه باشی4د ک4ه قب4ل از اینک4ه فرآین4د Piشروع به اجرا کن4د ،تمام یال های ادعای آ4ن بای4د در گراف تخص4یص منبع قرار گیرد .ای4ن شرط را بدی4ن ص4ورت م4ی توان بیان کرد که یال ادعای ‏Rj Piوقتی ب4ه گراف اضافه می شود ک4ه تمام یال های وابسته به فرآیند ، Piیال های ادعا باشند. ‏ نکته :در صورت درخواست فرآیند Piمنبع Rjپذیرفته می شود که تبدی4ل یال درخو4اس4ت ‏Rj Piب4ه یال تخص4یص Pi Rjمنجر به ایجاد چرخه در گراف تخصیص منبع نشود. ‏ نکت4ه :اگ4ر چرخ4ه ای موجود نباش4د ،تخص4یص منب4ع ،سیستم را در 23 حال4ت ام4ن نگ4ه م4ی دارد .اگ4ر چرخ4ه ای وجود داشت4ه باشد ، LOGO فصل هشتم :بن بست ها برای تشری4ح ای4ن الگوریت4م ،گراف تخص4یص شک4ل زی4ر را در نظر بگیرید. ‏ فرض کنی4د P2منب4ع R2را درخواس4ت م4ی کن4د ،اگرچه R2فعال آزاد اس4ت ،نم4ی توانی4م آ4ن را ب4ه P2تخص4یص دهی4م چون موجب ‏R1 ‏R1 گراف می شود. ایجاد چرخه در ‏P 1 ‏P 2 ‏R 2 حالت نا امن در گراف تخصیص منبع 24 ‏P 1 ‏P 2 ‏R 2 گراف تخصیص منبع برای اجتناب از بن بست LOGO فصل هشتم :بن بست ها 3-5-8الگوریتم بانکدار ای4ن الگوریت4م برای س4یستم های4ی مناس4ب اس4ت ک4ه س4یستم تخصیص منب4ع از ه4ر نوع منب4ع ،چن4د نمو4ن4ه داشت4ه باش4د ک4ه در ای4ن حالت نمی توان از گراف تخصیص منبع استفاده کرد. وقتی فرآیند جدیدی به سیستم وارد می شود : • بای4د حداکث4ر تعداد نمون4ه های4ی از ه4ر نوع منب4ع را که نیاز دارد ، اعالن نماید • • این تعداد نمی تواند بیش از تعداد منابع موجود در سیستم باشد وقت4ی کاربر مجموع4ه ای از مناب4ع را درخواس4ت م4ی کن4د ،سیستم بای4د تعیی4ن کن4د آی4ا تخص4یص ای4ن مناب4ع س4یستم را در حال4ت ام4ن نگه 25 LOGO فصل هشتم :بن بست ها 3-5-8الگوریتم بانکداری ( ادامه ) ... برای پیاده س4ازی الگوریت4م بانکدار از چندی4ن س4اختمان داده می توان اس4تفاده کرد ک4ه حال4ت س4یستم تخص4یص را رمزگذاری می کنند. برداری به طول mکه تعداد هر نوع منبع آزاد را نشان می دهد اگ4ر =nتعداد فرآیندهای موجود در س4یستم و =mتعداد انواع منابع است .مشخص فرآیند را تقاضای ماتریس n*m یک هرآزاد نوع Rj حداکثرمنبع است kکهنمونه از ] Available[jآنگاه اگر = k باشد آنگاه به ساختمان داده های زیر نیاز داریم : می کند اگر Max[i,j] = kباشد ،آنگاه Piممکن است حداکثر kنمونه یک ماتریس n*mاست که تعداد هر نوع منبع ای را که فعال به هر Availableنوع Rjرا درخواست کند. از منبع ]Allocation[i,j اگر = هرکند. می مشخص شده است ‏n*mداده تخصیص فرآیند به چند منبع فرآیند کند مشخص می است که ماتریس یک ‏Max  آنگاهدر باشد Rjرا منبع نوع نمونه از Piفعال آنگاه دارد.دیگر از اختیارنمونه Piبه k ]Need[i,j داردk .اگر = k نیاز ‏kدیگر ‏Allocation  منبع نوع Rjنیاز دارد تا وظیفه اش را انجام دهد. ‏Need 26 LOGO فصل هشتم :بن بست ها 3-5-8الگوریتم بانکدار ( ادامه ) ... ‏ نکته Need[i,j] = Max[i,j] – Allocation[i,j] : ‏ اندازه و مقدار ای4ن س4اختمان داده ه4ا ب4ا گذش4ت زمان تغیی4ر می کند. ‏ تذک4ر :م4ی توان ب4ا ه4ر س4طر ماتری4س های Allocationو Needبه عنوان برداری برخو4رد کرد و ب4ه ترتی4ب ب4ا Allocationiو Neediب4ه آنها مراجعه نمود. = Allocationiم4ناب4ع4یرا م4شخ4صم4یک44ن4د ک44ه 4ف44عال در ا4ختیار ف44رآ4ی4ند Pi 4ت ا4س . 27 = Needت444ع4داد م4ناب4ع4یرا م4شخ4ص م4یک44ن4د ک44ه 4م4مک4نا4س4ت Piب44را4ی LOGO فصل هشتم :بن بست ها 1-3-5-8الگوریتم امنیت الگوریتمی که تشخیص می دهد سیستم در حالت امن است یا خیر به صورت زیر توصیف می شود. .1فرض کنی4د workبرداری ب4ه طول mو Finishبرداری به طول n باشد. ‏work:= Available مقدار اولیه .2 28 ‏Finishرا این i اگر نتوانستید := false , i = 1,2,3,…,n پیدا کنید ،مرحله 4را ‏iای را پیدا کنید که :الف Finish[i] = false - انجام دهید ب work ≥ Needi - LOGO فصل هشتم :بن بست ها 1-3-5-8الگوریتم امنیت ( ادامه ) ... .3 ‏I. Work := work + Allocationi ‏II. Finish[i] = True برو به مرحله ی III.2 .4اگ4ر برای تمام مقادی4ر i ، Finish[i] = Trueباش4د ،سیستم در حالت امن است. ‏ 29نکت4ه :ای4ن الگوریت4م ب4ه عملیات4ی از مرتب4ه m*n2نیاز دارد تا LOGO فصل هشتم :بن بست ها 2-3-5-8الگوریتم درخواست منبع =Requestiبردار درخواست مربوط به فرآیند Pi اگ4ر Requesti[j] = kآنگاه فرآین4د Piتعداد kنمون4ه از منبع نوع Rjرا درخواست می کند. وقت4ی فرآین4د Piمنابع4ی را درخواس4ت م4ی کن4د ،فعالی4ت های زیر صورت می گیرد : .Iاگر : Requesti ≤ Need برو به مرحله 2وگرنه شرط خطا را ایجاد کن ،زیرا فرآیند بیش از ادعایش درخواست کرد .IIاگ4ر : Requesti ≤ Available 30 برو ب4ه مرحل4ه 3وگرن4ه Piبای4د منتظر LOGO فصل هشتم :بن بست ها 2-3-5-8الگوریتم درخواست منبع ( ادامه ) ... ‏III.اجازه ده4د ک4ه س4یستم ب4ا تغیی4ر حال4ت ب4ه شرح زی4ر ،وانمود کن4د که تمام منابع Piرا تخصیص داده ; Available := Available - Requesti ; Allocationi := Allocatoni + Requesti ; Needi := Needi - Requesti اگر حالت جدیدی که ایجاد شده امن باشد ،تراکنش کامل شده است و فرآیند Piمنابع خودش را در اختیار گرفته است. 31اگر حالت جدید امن نباشد Pi ،باید منتظر Requestiبماند و حالت ‏ LOGO فصل هشتم :بن بست ها 3-3-5-8مثال س4یستمی ب4ا 5فرآین4د P0ت4ا P4و س4ه نوع منبع A ، Bو Cرا در نظر بگیرید. = Aم4نبع ن44وع Aدارا4ی 10ن44مون4ه4 = Bم4نبع ن44وع Bدارا4ی 5ن44مون4ه4 = Cم4نبع ن44وع Cدارا4ی 7ن44مون4ه4 ‏Available ‏A B 3 ‏Max ‏A B C 3 7 5 3 2 2 9 0 2 است : در زمان T0وضعیت سیستم به صو4رت مقابل 2 2 2 4 3 3 32 ‏Allocation ‏A B C 0 1 0 0 0 2 1 1 0 2 ‏C ‏P0 0 3 2 ‏P1 2 ‏P2 3 ‏P3 2 ‏P4 0 LOGO فصل هشتم :بن بست ها 3-3-5-8مثال( ادامه ) ... محتویات ماتری4س Needبرابر اس4ت ب4ا Max - Allocationو ب4ه ص4ورت زیر است: ادع4ا م4ی کنی4م ک4ه س4یستم فعال در حال4ت امن ‏A B C 7 4 است که در واقع دنباله <>P1,P3,P4,P2,P0 معیار امنیت را برآورده می کند. اکنون فرض م4ی کنی4م ک4ه فرآین4د P1 1نمونه از منبع Aو 2نمو4نه دیگ4ر از منب4ع Cدرخواس4ت م4ی کند = Request1 33 )(1,0,2 ‏Need 2 1 2 6 0 0 1 1 4 3 1 ‏P0 3 ‏P1 ‏P2 0 ‏P3 ‏P4 LOGO فصل هشتم :بن بست ها 3-3-5-8مثال( ادامه ) ... پ4س وانمود م4ی شود ک4ه درخواس4ت انجام پذی4ر اس4ت و ب4ه حال4ت جدید می رسد برای اینک4ه مطمئ4ن شوی4م ای4ن حالت ‏Available ‏A B ‏Max ‏A B C ‏Allocation ‏A B C امن است یا ‏C ‏P0 0 1 0 7 4 3 2 خیراز الگوریت4م امنی4ت اس4تفاده می 3 0 ‏P1 3 0 2 0 2 0 شود و چو4ن ‏P2 3 0 2 6 0 0 ‏P3 2 1 1 0 1 1 الگوریتم ای444444444ن : حالت این در قبول غیرقابل های درخواست از جمله ‏P4 0 0 2 4 3 1 <.I >P1,P3,P4,P0,P2تأیی4د می درخواست ( )3,3,0توسط :P4زیرا این ‏ کند منابع آزاد نیستند درخواست ( )0,2,0توسط :P0نتیجه 34فورا درخواس4ت .II P1 برآورده می لذا LOGO فصل هشتم :بن بست ها 2-8کشف بن بست اگر از الگوریتم های پیشگیری یا اجتناب از بن بست استفاده نکند ، شرای4ط ب4ن بس4ت ممک4ن اس4ت رخ دهند .در چنی4ن محیطی ، سیستم باید موارد زیر را فراهم کند : الگوریتم4ی ک4ه حال4ت س4یستم رت بررس4ی کن4د ت4ا تعیی4ن نمای4د بن بست وجو4د دارد یا خیر الگوریتمی که سیستم را از حالت بن بست ترمیم کند ‏ تذک4ر :الگوی کش4ف و ترمی4م ب4ن بس4ت شام4ل س4ربارهایی است ک4ه ن4ه تنه4ا هزینه زمان اجرا برای نگهداری اطالعات واجرای الگوریتم کشف بن بست را در بر می گیرد،بلکه زیانهای ناشی از 35 LOGO فصل هشتم :بن بست ها :1-6-8کشف بن بست در حالتی که یک نمونه از هر منبع وجود دارد در ای*ن حالت الگوری*م کش*فب*ن بس*ت از ی*ک نوع گرف تخص*یص منب*ع به نام گراف انتظار(wait- )for graphاستفاده می کند. برای بدس*ت آوردن ای*ن گراف از گراف تخص*یص منب*ع ،گره های نوع منبع را حذف کرده،یالهای مناسبی را از بین می بریم. نکات: .1 .2 یال از Piب*ه Pjدر ی*ک گراف انتظار بیانگ*ر ای*ن اس*ت ک*ه فرآین*د Piمنتظ*ر Pjاس*ت تا منبعی را که مورد نیاز Piاست آزاد کند. یال Pi  Pjدر گراف انتظار وجود دارد اگ*ر و فق*ط اگ*ر تخص*یص منب*ع متناظ*ر ب*ا آن برای منبعی مثل Rqحاوی دو یال PiRqو RqPjباشد. 36 LOGO فصل هشتم :بن بست ها ‏P 2 گراف انتظار و متناظر با آن ‏R5 ‏P 2 ‏P 3 ‏P 2 ‏P 4 37 ‏P1 ‏R3 ‏P 3 ‏R5 گراف تخصیص منبع ‏R1 ‏P 2 ‏P 4 ‏P1 ‏R2 LOGO فصل هشتم :بن بست ها .3 اگر در گراف انتظار چرخه ای وجود داشته باشد ،به معنای وجود بن بست در سیستم است. .4 برای کش*فب*ن بس*ت الزم اس*ت س*یستم گراف انتظار را نگهداری کن*د وب*ه طور تناوب*ی الگوریتمی را اجرا کند تا وجود چرخه ای را در این گراف جستجو نماید. .5 الگوریت*م کش*فب*ن بس*ت در گراف مس*تلزم عملیات*یب*ه مرتب*ه ²nاس*ت(* = nتعداد رأسهای موجود در گراف). 38 LOGO فصل هشتم :بن بست ها :2-6-4کشف بن بست در حالی که هر نوع منبع دارای چندین نمونه است از الگوی گراف انتظار نم*ی توان برای س*یستم تخص*یص* منبع*ی بکار برد ک*ه در آ*ن ه*ر نوع منبع دارای چندین نمونه است. الگوریتم*ی ک*ه در اینج*ا ارائ*ه م*ی شود،دارای چندی*ن س*اختمان داده اس*ت ک*ه بر حسب زمان تغییر می کند(مثل الگوردتم بانکدار). :Availableب**ردار*یب**ه ط*ول mک**ه ت**ع*داد م*ناب*ع آزاد م*ربوط ب**ه هر ن*وع م*نب*ع را ن**شانم*ی د*هد. *ک*اتری*س n*mا*س*تک**ه م*شخ*صم*یک**ند چ*ه ت**ع*داد از هر ن*وع م*نب*ع ب**ه هر :Allocationی* م *ت ف*رآ*ی*ند ت**خصیصداد*ه* ش*ده* ا*س . *ت**علیهر ف*رآ*ی*ند را ن**شانم*ید*هد. ی*ک*اتری*س n*mا*س*تک**ه در*خوا*س ف :Requestم *ت ] :Request [i,jی*عنیف*رآ*ی*ند Piب**ه ت**ع*داد kن**مون*ه از م*نبع Rjرا در*خوا*س*تک**رد*ه* ا*س . 39 LOGO فصل هشتم :بن بست ها الگوریت*م کش*فب*ن بس*ت،ه*ر دنبال*ه ای از تخص*یص را برای ه*ر فرآیندی ک*ه باید کامل شود بررسی می کند. .1فرض کنید workبرداری به طول mو Finishبرداری به طول nاست، : work := Availableمقادیر اولیه : Allocation i ≠ 0 ‏False ]Finish [i ,i=1,2,3,…,n ‏True : ow .2اندیس iرا بیابید بطوری که Finish [i] = False )1 : ‏Request i ≤ work)2 برو. .3 40 ‏work := work + اگ*ر ای*ن iپیدا نش*دب*ه مرحله 4 ‏I. ‏Allocation i ‏II. Finish [i] = True LOGO فصل هشتم :بن بست ها نکت*ه :ای*ن الگوریت*م نیاز ب*ه عملیات*ی از مرتب*ه m*n²دارد ت*ا کش*ف کن*د آی*ا سیستم در حالت بن بست قرار دارد یا خیر. *ر :عل*ت اینک*ه پ*س از مرحل*ۀ ب مرحل*ه ، 2مناب*ع فرآین*د Piآزاد م*ی شون*د ای*ن اس*ت که تذک چون Request i ≤ workاست لذا Piدر بن بست نیست،بنابری*ن حالت بهینه را در نظر م*ی گیری*م و فرض م*ی کنی*م Piبرای انجام وظیف*ه اش ب*ه مناب*ع دیگری نیاز ندارد،بنابرین تمام منابع در اختیارش آزاد می شود. اگ*ر فرض م*ا نادرس*ت باش*د،ممک*ن اس*تب*ن بس*ت رخ ده*د ک*ه وقت*ی الگوریت*م کش*فب*ن بست اجرا شد،این بن بست تشخیص داده می شود. 41 LOGO فصل هشتم :بن بست ها تشریح این الگوریتم با مثال : ‏Available ‏C ‏A B C 0 0 0 0 ن**مون*ه A= 7 0 ن**مون*ه =B 0 ن**مون*ه C= 6 2 ‏Request ‏C ‏A B 1 0 0 0 0 2 0 2 0 3 0 0 1 1 1 0 0 2 0 0 ‏Allocation ‏A B 0 2 0 3 2 0 ‏P0 ‏P1 ‏P2 ‏P3 ‏P4 ادع*ا م*ی کنیم س*یستم در حال*تب*ن بس*ت نیس*ت :دنبال*ه <>P0,P2,P3,P1,P4ب*ه ازای هر iمنجر به این می شوند که Finish [i]= Trueاست. 42 LOGO فصل هشتم :بن بست ها ‏اگر P2نمونه دیگری از منبع cرا درخواست کند ،ماتریس Requestبه صورت مقابل در می آید. ادع*ا م*ی کنی*م س*یستم در حال*ت ب*ن بست قرار دارد،اگ*ر مناب*ع تخص*یص* یافت*ه به P0را آزاد کنی*م،برای پذیرفت*ن تقاض*ا کاف*ی نیس*ت.بنابرین بن بس*ت وجود دارد ک*ه فرآیندهای P1و P2و P3و P4درآن شرکت دارند. 43 0 1 0 2 ‏Request ‏A B C 0 0 2 0 2 0 0 1 0 0 0 ‏P0 ‏P1 ‏P2 ‏P3 ‏P4 LOGO فصل هشتم :بن بست ها 3-6-8کاربرد الگوریتم کشف بن بست اینکه کی باید الگوریتم کشف بن بست را eفراخوانی کرد ،به دو عامل بستگی دارد: .I .IIدرصورت بروز بن بست ،چه تعدادی از فرآیندها تحت تاثیر قراeر می گیرند؟ ‏اگر بن بست به کرات اتفاق افتد ،الگوریتم کشف بن بست نیز باید به کرات اجرا eشود ‏منابع فرآیندهایی که در بن بست قرار داeرند ،بیکاری مانند تابن بست شکسته شود. ‏تعداد فرآیندهایی که در بن بست قراردارند ممکن است رشد کند. ‏بن بست فقط در صورتی رخ می دهد که فرآeیندی درخواستی داشته باشد که فورا برآورده نشود. به طور کلی هر وقت که درخواستی نتواند فورا برآورده شود ،الگوریتم کشف بن بست را اجرا کنیم. ‏در ایeن حالeت نeه تنهeا مeی توان فرآیندهای موجود در بeن بسeت را شناسeایی کرد ،بلکeه می توان فرآیندی بن بست هرچند وقت یکبار ممکن است رخ دهد؟ که موجب ایجاد بن بست شده را شناسایی کرد 44 LOGO فصل هشتم :بن بست ها نکته :چون فراخوانی الگوریتم کشف بن بست در هر درخواست ،سربار زمانی دارد ،مناسبتر است کeه در فواصeل زمانeی خاص مثeل هرسeاعت ،یeا هeر وقeت کeه بهره وری CPUبeه زیeر 40درصد رسید فراخوانی گردد. 7-8ترمیم از حالت بن بست وقتی اeلگوریتم کشف بن بست ،وجود بن بستی را تشخیص ،تصمیمات گوناگونی اتخاذ کرد. یeک روش اeیeن اسeت کeه بeه اپراتور خeبرداده شود کeه بeن بسeت اتفاق افتاده و کاربر سeیستم را به طور دستی از حالت بن بست خارج کند روش دیگeر ایeن اسeت کeه بeه سeیستم اجازه داده شود بeه طور خودکار از حالeت بeن بسeت ترمیم ( )Recoverشود دو روش برای از بین بردن بن بست وجود دارد: .1اجرای یکی از فرآیندهای موجود در انتظار چرخشی خاتمه یابد. 45 LOGO فصل هشتم :بن بست ها 1-7-8خروج از بن بست با خاتمه فرآیندها برای خروج از بن بست از طریق خاتمه فرآیندها ،به یکی از 2روش ممکن است عمل کنیم. در هر دو روش سیستم تمام منابعی را که در اختیار فرآیند خاتمه یافته قرار دارد ،پس می گیرد. -1تمام فرآیندهای شرکeت کننده در بeن بسeت خاتمeه یابنeد :در ایeن روش ،چرخeه بeن بست شکسeته مeی شود ولeی هزینeه آeن زیاد اسeت ،زیرا کeل eمحاسeبات انجام شده توسeط فرآیندهeا ،دوباره باید انجام گیرد. -2فرآیندهای شرکeت کننده در بeن بسeت ،یکeی یکeی خاتمeه یابنeد تeا بeن بست برطرف شود :ایeن روش منجر بeه سeربار زیادی مeی شود ،پeس از خاتمeه هeر فرآeینeد ،الگوریتeم کشeف بeن بست اجرا می شود تا تعیین کند آیا هنوز فرآeیندهایی در بن بست قرار دارند یا خیر 46 LOGO فصل هشتم :بن بست ها نکتeه :اگeر اeز روش دوم اسeتفاده شود ،در مجموعeه ای از فرآیندهeا کeه در بeن بسeت قرار دارنeد ،باید فرآیند (یا فرآیندهایی) را برای خاتمه انتخاب کنیم که به بن بست خاتمه دهند. عوامل زیادی برای خاتمه دادن فرآیند وجود در بن بست موثرند: -1اولویت فرآیند چیست؟ -2فرآیند چه مدتی اجرا شده ،و چه مدتی نیاز به اجرا دارد؟ -3فرآینeد از چeه نوع منابeع و از چنeد تeا از آنهeا اسeتفاده تeر اسeت؟ (مثال آیeا پeس گرفتeن منابع ساده اeست؟) -4به چه منابع دیگری نیاز دارد تا کامل شود؟ -5چند فرآیند باید خاتمه یابند؟ -647فرآیند به صورت محاوره ای است یا دسته ای؟ LOGO فصل هشتم :بن بست ها 2-7-8خروج از بن بست با قبضه کردن منابع برای خروج از بeن بسeت از طریeق قبضeه کردن منابeع ،منابعeی را از فرآیندهایeی پeس مeی گیریم و در اختیار فرآیندهای دیگر قرار می دهیم تا بن بست از بین برود. در این روش به سه موضوع باید توجه داشت: -1انتخاب یeک قربانeی :چeه منابeع و چeه فرآیندهایeی بایeد قبضeه (قربانeی) شونeد؟ قبضه کردن طوری باشد که کمترین هزینه را داشته باشد؟ -2عقبگرد :اگeر منبعeی را از فرآیندی پeس مeی گیریeم ،بeا آeن فرآینeد چeه بایeد بکنیeم؟ بایeد ایeن فرایند را به حالeت امنی ببریم و اجرای آن را از آن حالت امن آغاز کنیم. -3گرسeنگی :چگونeه تضمیeن کنیeم کeه حالeت گرسeنگی رخ نمeی دهeد؟ یعنeی چگونeه تضمیeن کنیم که همیشه منابع از یک فرآیند پس گرفته نمی شوند؟ 48 LOGO فصل هشتم :بن بست ها تذکeر :در سeیستمی کeه انتخاب قربانeی براسeاس عوامeل هزینeه اسeت ممکeن اسeت همیشeه یک فرآیند به عنوان قربانی انتخاب شود و در نتیجه هیچگاه وظیفه اش را به طور کامل انجام نمی دهد و یک حالت گرسنگی در سیستم بوجود می آید. بنابرایeن بایeد تضمیeن کنیeم کeه هeر فرآeینeد بeه تعداد دفعات محدودی بeه عنوان قربانی انتخاب شود. متداولترین راه حل این است که تعداد عقبگردها به عنوان عامل هزینه منظور شود. 49 LOGO فصل هشتم :بن بست ها 8-8رهیافت ترکیبی برای مسئله بن بست محققیeن معتقدنeد کeه هیچکدام از راه حeل های مسeئله بeن بسeت (پیشگیری ،اجتناب و کشeف بeن بسeت) به تنهایی برای مسئله تخصیص منبع در سeیستم های عامل مناسeب نیسeتند و می بایست ایeن سeه رهیافت با هم ترکیب شوند تا برای هر دسته اeز فرآیندهای موجود در سیستم ،رهیافت مناسبی انتخاب گردد. ‏راه حeل پیشنهادی ،برایeن ایده اسeتوار اسeت کeه منابeع مeی تواننeد بeه دسeته هایeی شونeد کeه ترتیب مراتبeی دارنeد کeه تکنیeک ترتیeب منبeع کeه در بخeش 8-4-4توضیeح داده شeد بeه ایeن دسeته از منابع اعمال می شود. ‏در هردسeته از منابeع ،مناسeبترین تکنیeک برای برطرف کردن بeن بسeت مورد اسeتفاده قرار می گیرد 50 LOGO فصل هشتم :بن بست ها برای تشریeح ایeن تکنیeک سeیستمی را در نظeر مeی گیریeم کeه شامeل 4دسeته از منابeع به شرح زیر باشد: منابع داخل :منابعی که توسط سیستم مورد اeستفاده قرار می گیرند ،مثل بلeوک کنترل فرآیند. حافظه مرکزی :حافظه ای که توسط کار کاربر مورد استفاده قرار می گیرد. منابع کار :دستگاههای قابل تخصیص (مثل گرداننده نوار) و فایل ها فضای قابل تعویض :فضای مورد نیاز کار هر کاربر در حافظه پشتیبان 51 LOGO فصل هشتم :بن بست ها راه حeل ترکیبeی مسeئله بeن بسeت برای ایeن سeیستم ،دسeته های منابeع را بeه صورت فوق مرتب می کند و برای هر دسته از منابع از رهیافت های زیر استفاده می کند: منابeع داخلeی :از طریeق ترتیeب منابeع مeی توان از بeن بسeت پیشگیری کرد ،زیرا نیاز به انتخاب های زمان اجرا برای به تعویق انداختن درخواست ها نیست. حافظeه مرکزی :از طریeق قبضeه کردن مeی توان از بeن بسeت پیشگیری کرد ،زیرا eهر کاری همواره می تواند از حافظه خارج شود و حافظه پس گرفته شود. منابeع کار :مeی تواeن از بeن بست اجتناب کرد ،زیرا اطالعات مورد نیاز ،برای نیازمندیهای منبع ،از طریق کارت های کنترل کار به دست می آیند. فضای قابل تعویض :فضا را می توان از قبل تخصیص داد ،زیرا حداکثر فضای الزم همواره مشخص است. 52