صفحه 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