الگوریتم بانکدار
برگرفته ازWikipedia دایرهامعارف مجانی.
این صفحه باعث اجتناب از بن بست در ارتباط است.
برای گرد کردن به نزدیک ترین حالت، به بخش گردکردن بانکدار مراجعه کنید.
الگوریتم بانکدار ، الگوریتم اجتناب از بن بست و مقدار منبع می باشد که توسط Edsger Dijkstra ارائه شده است.
این الگوریتم توسط شبیه سازی حداکثر مقدار ممکن از پیش تعیین شده منابع، ایمنی منابع را مورد آزمایش قرار می دهد و سپس قبل از تصمیم در مورد اینکه آیا این مقدار اختصاص یافته مجاز به ارائه است یا نه ف یک وضعیت ایمنی را به منظور آزمایش شرایط بن بست موجود بری کلیه فعالیتهای معلق ، ایجاد می نماید.
انتخاب نام برای الگوریتم:
این الگوریتم در قرایند طراحی برای سیستم عامل THE ارائه شده بود که البته در EWD108 به طور مفصل به زبان آلمانی توضیح داده شده است.
این نام از مقایسه آن با شیوه ای است که بانکداران برای محدودیتهای بازپرداختی استفاده می کنند.
الگوریتم
الگوریتم بانکدار هر زمانی که فرایندی نیاز به منابعی داشته باشد، توسط سیستم عامل اجرا می گردد.
این الگوریتم، به وسیله ردکردن یا به تعویق انداختن درخواست، از بن بست جلوگیری می کند البته اگر درخواست تعیین کننده این باشد که قبول درخواست ممکن است سیستم را در وضعیت ناامن قرار دهد( شرایطی که بن بست می توانند در آن رخ دهد ).
منابع
به منظور به کارگیری الگوریتم بانکدار ، سه چیز لازم به ذکر است:
• هر فرایند چقدر از هر منبع می تواند نیاز داشته باشد.
• هر فرایند چقدر از هر منبع را دردست دارد.
• هر سیستم چقدر از هر منبع را موجود دارد.
برخی از منابع مه در سیستم های واقعی یافت می شوند عبارتند از ک حافظه ،سمافورها (Semaphores) دسترسی مقدماتی ( interface access).
مثال:
با فرض اینکه سیستمی 4 نوع منبع را مشخص می کند (A,B,C and D) مثالی می آوریم از اینکه این منابع چقدر می توانند تقسیم شوند و یا بسط یابند.
توجه داشته باشد که این مثال سیستم را در لحظه ای قبل از رسیدن درخواستی برای منابع ، نشان می دهد.
همچنین نوع و تعداد منابع هم خلاصه شده اند.
به عنوان مثال ، سیستم های واقعی با مقادیر وسیعتری از هر منبع سرو کار دارند.
Available system resources:
A B C D
3 1 1 2
:Processes ( currently allocated resources )
A B C D
P1 1 2 2 1
P2 1 0 3 3
P3 1 1 1 0
Processes ( maximum resources)
A B C D
P1 3 3 2 2
P2 1 2 3 4
P3 1 1 5 0
وضعیت های امن و ناامن:
شرایطی مثل مثال بالا در صورتی امن در نظر گرفته می شود که امکان خاتمه یافتن برای همه فرایندها وجود داشته باشد .
از آنجایی که سیستم نمی تواند تشخیص دهد که چه زمانی فرایندی به اتمام خواهد رسید یا تا قبل از خاتمه چه تعداد منبع نیاز خواهد داشت ، فرض را بر این می گذارد که تمامی فرایندها سعی به بدست آوردن حداکثر منابعشان دارند که خیلی سریع هم به اتمام خواهد رسید.
این در بسیاری از موارد فرضیه مناسبی به نظر می رسد چرا که سیستم مشخصاً با اینکه هر فرایندی چه مدت اجرا خواهد شد ، در ارتباط با نیست (حداقل نه از نظر اجتناب با بن بست) .
همچنین اگر فرایندی بدون بدست آوردن حداکثر منابعش خاتمه یابد ، تنها آن فرایند را روی سیستم تسهیل می کند.
با ارائه آن فرضیه، الگوریتم با سعی برای یافتن مجموعه فرضی از درخواست ها توسط فرایندها که به هر کدام این فرصت رابرای بدست آوردن حداکثر منابعشان و سپس خاتمه یافتن را می دهد، ( با برگشت دادن منابعشان به سیستم) تعیین می کند که آیا یک وضعیت امن است یا خیر.
هر وضعیتی که چنین مجموعه ای در آن وجود نداشته باشد ، وضعیت ناامن به شمار می رود.
هر وضعیتی که چنین مجموعه ای در آن وجود نداشته باشد ، وضعیت ناامن به شمار می رود.
کد-غیر حقیقی : P- مجموعه فرایندها Mp- حداکثر نیاز به منابع برای فرایند Cp- فرایند اختصاص منابع موجود A- منابع موجود مثال: While ( P != 0 ) { Found = FALSE; Foreach ( p c P) { If ( Mp – Cp /* p can obtain all it needs */ /* assume it dose so, terminates , and */ /* releases what it already has.
*/ A = A + Cp ; P = P-{p} ; Found = TRUE ; } } If ( !
found ) return FAIL; } return OK; مثال: با نشان دادن اینکه برای هر فرایندی این امکان وجود دارد که حداکثر منابع را بدست آورد و سپس خاتمه یابد می توانیم عنوان کنیم که .ضعیت ارائه شده در مثال قبل یک وضعیت امن می باشد.
P1 دو A را به دست می آورد ،D1,B1 منابع بیشتری هستند که به بالاترین حد خود رسیده.
حالا سیستم هنوز1 A و هیچ B و 1D, 1C را به عنوان منابع موجود دارد.
P1 با باز گرداندن A3 و B3 و C2وD2 به سیستمف پایان می دهد.
اکنون سیستم A4و B3 وC3 وD3 را موجود دارد.
P2 منابع B 2 وD1 که منابع اضافی به شمار می روند را به دست می آورد ،سپس خاتمه می یابد با برگشت همگی منابعش.
P3 منابع C 4 را بدست می آورد و خاتمه می یابد.
سیستم حالا همگی منابع را A6 و B4و C7وD6 را دارد.
5.
به خاطر اینکه همه فرایند ها قادر بودند خاته یابند ،پس این وضعیت امن است.
توجه داشته باشید که این درخواستها و اکتسابات همگی فرضی هستند.
الگوریتم آنها را به منظور چک کردن امنیت وضعیت موجود ساخته است ، اما در واقع هیچگونه منبعی ارائه نشده است و هیچگونه فرایندی خاتمه نمی یابد.
همچنین توجه داشته باشید که ترتیب ساخته شدن این درخواست ها - اگر چندتا قابل اجرا باشند – مهم نیست، چرا که همگی درخواست های فرضی باعث خاتمه یافتن فرایند می شوند، که منجر به افزایش منابع آزاد سیستم می شوند.
به عنوان مثال از وضعیت ناامن ،فرض کنید که چه می شد اگر فرایند شماره 2 در ابتدا یک واحد بیشتر از منبع B را دربرداشت.
درخواست ها: هنگامی که سیستم درخواستی را برای منابع دریافت می کند ، الگوریتم بانکدار را برای تعیین اینکه دادن درخواست امن است یا نه را اجرا می کند.
هنگامی که تفاوت بین وضعیت امن و ناامن مشخص شود این الگوریتم نسبتاً ساده است.
آیا می شود درخواست داده شود.
اگر نه، درخاست غیر ممکن خواهد بود و می بایستی که رد شود یا اینکه در لیست انتظار قرار گیرد.
فرض کنید درخواست داده شود.
آیا وضعیت جدید امن است؟
اگر بله، درخواست را بدهد.
اگر نه، با درخواست را رد کند یا آن را در لیست انتظار قرار دهد.
اینکه سیستم ف یک درخواست غیر ممکن یا ناامن را رد کند و یا به تعویق بیاندازد ، تصمیمی است ویژه سیستم عامل.
در ادامه مثال قبل ،فرض کنید فرایند 3 ، 2 واحد از منبع C درخواست کند.
منبع C به اندازه کافی برای پوشش درخواست، وجود ندارد.
درخواست رد می شود.
از سری دیگر ،فرض کنید فرایند 3 ، یک واحد از منبع C را درخواست کند.
منابع لازم برای پوشش درخواست وجود دارد.
فرض کنید درخواست داده شده است.
وضعیت جدید سیستم از این قرار خواهد بود: Available system resources: A B C D Free 3 1 0 2 Processes ( currently allocated resources): A B C D P1 1 2 2 1 P2 1 0 3 3 P3 1 1 2 0 Processes ( maximum resources): A B C D P1 3 3 2 2 P2 1 2 3 4 P3 1 1 5 0 مشخص می کند که آیا این وضعیت جدید امن است یا خیر.
P1 می توانند منابع A2 و B1وD1 را بدست اورد و خاتمه یابد.
سپس P2 منابع B2وD1را بدست آورد و خاتمه یابد.
سرانجام،P3 منابع C3 را بدست می آورد و ختمه می یابد.
بنابراین، این ضعیت تازه ، امن است.
از آنجا که وضعیت جدید امن است ، درخواست را صادر می کند.
بلاخره ف رض کنید فرایند 2 یک واحد از منبع B درخواست کند.
منابع کافی وجود دارد.
با فرض اینکه، درخواست پوشش داده شده باشد، وصعیت جدید به قرار زیر خواهد بود: Available system resources: A B C D Free 3 0 1 2 Processes ( currently allocated resources): A B C D P1 1 2 2 1 P2 1 1 3 3 P3 1 1 1 0 Processes ( maximum resources): A B C D P1 3 3 2 2 P2 1 2 3 4 P3 1 1 5 0 آیا وضعیت اکن است ؟با فرض اینکه P3,P2,P1 منابع بیشتر از C,B درخواست کنند.
P1 قادر نیست منبع کافی از B را بدست آورد.
P2 هم قادر نیست منبع کافی از B را بدست آورد.
P3 قادر نیست منبع کافی از C را بدست آورد.
هیچ فرایندی نمی تواند منبع کافی را برای خاتمه یافتن بدست آورد ،پس این وضعیت حالت ناامن است.
2.از آنجائیکه حالت ناامن است ، درخواست رد می شود.
توجه داشته باشید که در این مثال ، هیچ فرایندی قادر به خاتمه یافنی نیست.
ممکن است که برخی فرایندها قادر به خاتمه یافتن باشند، اما نه همه آنها.
هنوز هم آن یک حالت ناامن به شمار می رود.
تعاملات با اختیارات: مانند اکثر الگوریتم ها، الگوریتم بانکدار هم دارای اختیاراتی می باشد.
به ویژه ، لازم به دانستن است که یک فرایند چه مقدار از منبع می تواند درخواست کند.
در اکثر سیستم ها ، این اطلاعات موجود نمی باشند که باعث می شوند الگوریتم بانکدار بی فایده به نظر آید.
علاوه به این، غیر واقعی به نظر می آید اگر فرض کنیم که تعداد فرایندها غیرقابل تغییرند ، در اکثر سیستم ها تعداد فرایندها به طور متغیری فرق می کنند.
به علاوه ، این نیاز که یک فرایند بلاخره تمامی منابعش را (هنگامی که خاتمه می یابد) آزاد می کند، برای تصحیح الگوریتم کفایت می کند، اما این مقدار برای یک سیستم واقعی کافی نیست .
ساعت ها و حتی روزها انتظار برای آزاد شدن منابع معمولا پذیرفتنی نیست .
پایان با تشکر فراوان