این صفحه باعث اجتناب از بن بست در ارتباط است. برای گرد کردن به نزدیک ترین حالت، به بخش گردکردن بانکدار مراجعه کنید.
الگوریتم بانکدار ، الگوریتم اجتناب از بن بست و مقدار منبع می باشد که توسط 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 <= A ) {
/* 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 که منابع اضافی به شمار می روند را به دست می آورد ،سپس خاتمه می یابد با برگشت همگی منابعش.