الگوریتم بانکدار

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

الگوریتم بانکدار یک الگوریتم تخصیص منابع و اجتناب از بن بست است که توسط ادسخر دیسترا توسعه یافته که امنیت آن به وسیله شبیه سازی تخصیص بیشترین مقدار ممکن از تمام منابع آزمایش شده به طوری که یک s-state ایجاد می کند تا برای همه فرایندهای در حال انتظار تمام شرایط بن بست را قبل از تصمیم گیری و اجازه تخصیص منبع بررسی کند.

این الگوریتم در طراحی فرایند در سیستم عامل THE توسعه یافته و در اصل (به هندی) در EWD108 شرح داده شده.[۱]

الگوریتم[ویرایش]

الگوریتم بانکدار هر زمان که یک فرایند درخواست منبع کند توسط سیستم عامل اجرا می شود.[۲] الگوریتم به وسیله انکار و یا تعویق درخواست از بن بست جلوگیری میکند. این در صورتی است که اگر تعیین شود که پذیرش درخواست میتواند سیستم را به حالت نا امن ببرد.(حالتی که بن بست میتواند رخ دهد). هنگامی که یک فرایند جدید وارد یک سیستم میشود باید حداکثر تعداد از هر نوع منبع را اعلام کند که ممکن نیست از تعداد کل منابع در سیستم تجاوز کند. همپنین هنگامی که یک فرایند همه منابع درخواستی را تحویل میگیرد باید آنها را در یک رمان محدود بازگرداند.

منابع[ویرایش]

الگوریتم بانکدار برای انجام کار نیاز به دانستن سه چیز دارد:

  • هر فرایند چه مقدار از هر نوع منبع را میتواند درخواست کند.
  • هر فرایند چه مقدار از هر نوع منبع را میتواند در اختیار داشته باشد.
  • چه تعدادی از هر نوع منبع موجود است.

منابع تنها در صورتی ممکن است اختصاص یابند که شرایط زیر وجود داشته باشد:

  1. request ≤ max. در غیر اینصورت خطا به عنوان درخواست بیش از ادعا منظور شود.
  2. request ≤ available. در غیر اینصورت فرابند صبر میکند تا منابع آزاد شوند.

برخی از منابعی که در سیستم های واقعی دنبال میشوند حافظه، سمافورها و رابط دسترسی هستند. نام الگوریتم بانکدار برگرفته از این حقیقت است که این الگوریتم که این الگوریتم میتواند در سیستم بانکی مورد استفاده قرار گیرد تا تضمین کند که بانک همه منابع خورد را از دست نمی‌دهد. چون بانک هیچ گاه پول را به نحوی تخصیص نمی‌دهد که نتواند نیازهای بقیه مشتری ها را برطرف نکند. با الگوریتم بانکدار بانک تضمین میکند که زمانی که مشتری ها پول درخواست میکنند بانک هیچ گاه به حالت ناامن نمی‌رود. اگر درخواست مشتری باعث نشود که بانک حالت امن را ترک کند، مبلغ اختصاص میابد در غیر اینصورت مشتری باید صبر کند تا زمانی که مشتری های دیگر سپرده کافی قرار دهند.

ساختمان داده های اولیه برای پیاده سازی الگوریتم بانکدار: n را شماره فرایند و m را شماره منابع موجود قرار دهید. حال به این ساختمتن داده ها نیاز است:

  • Available: یک بردار به طول m که نشان دهنده تعداد منابع موجود از هر نوع منبع است. اگر Available[j] = k باشد یعنی k تا از منبع نوع Rj موجود است.
  • Max: یک ماتریس n×m که حداکثر نیاز هر فرایند را به انواع منابع نشان میدهد. اگر Max[i,j] = k باشد آنگاه فرایند Pi حداکثر به k تا از منبع نوع Rj نیاز دارد.
  • Allocation: یک ماتریس n×m که تعداد منابع از هر نوع را که به هر فرایند اختصاص یافته است نشان میدهد. اگر Allocation[i,j] = k یعنی فرایند Pi در حال حاضر k تا از هر منبع نوع Rj را در اختیار دارد.
  • Need: یک ماتریس n×m که نیاز هر فرایند به هر منبع را نشان میدهد. اگر Need[i,j] = k یعنی Pi به k تا از منبع نوع Rj نیاز دارد.

توجه: Need = Max - Allocation

مثال[ویرایش]

با فرض اینکه سیستم دارای چهار نوع منبع A,B,C,D باشد. این مثال نشان میدهد منابع چگونه اختصاص می یابند. توجه که این مثال مشان میدهد سیستم یک لحظه قبل از درخواست جدید در چه حالتی است.

تعداد کل منابع در سیستم:

A B C D
6 5 7 6

Available:

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 2 1 0

Processes (maximum resources):

A B C D
P1 3 3 2 2
P2 1 2 3 4
P3 1 3 5 0

Need= maximum resources - currently allocated resources

Processes (need resources):

A B C D
P1 2 1 0 1
P2 0 2 0 1
P3 0 1 4 0

حالات امن و ناامن[ویرایش]

زمانی یک حالت را امن گوییم که امکان پایان یافتن همه فرایند ها وجود داشته باشد. از آنجایی که سیستم نمی‌تواند بداند یک فرایند کی به پایان میرسد و یا چه تعداد منابع درخواست خواهد شد، پس سیستم فرض میکند همه فرایند ها تلاش میکنند که حداکثر منابع را در اختیار داشته باشند تا زودتر به پایان برسند. از آنجایی که سیستم به طور ویژه اهمیت نمی‌دهد که اجرای هر فرایند چقدر طول میکشد پس این یک فرض معقول در اکثر موارد است. همچنین اگر یک فرایند بدون دستیابی به حداکثر منابع پایان یابد فقط اجرا را روی سیستم ساده تر کرده است. حالت امن در نظر گرفته شده که تصمیم بگیرد فرایند به صف آماده برود. حالت امن ایمنی را تضمین میکند.

مثال[ویرایش]

میتوانیم با نشان دادن اینکه هر فرایند حداکثر منابع مورد نیاز را دریافت و به پایان میرسد حالت امن را در مثال قبل نشان دهیم.

  1. p1 درخواست 2A, 1B, 1D میکند تا به حداکثر برسد.
    • [<available : <3 1 1 2> - <2 1 0 1> = <1 0 1 1]
  2. p1 تمام میشود و 3A, 3B, 2C, 2D به سیستم بازمیگردد.
    • [<available : <1 0 1 1> + <3 3 2 2> = <4 3 3 3]
  3. p2 درخواست 2B, 1D را میفرستدو سپس تمام میشود و همه منابع را بازمیگرداند.
    • [<available: <4 3 3 3>-<0 2 0 1>+<1 2 3 4> = <5 3 6 6]
  4. p3 درخواست 1B, 4C را میکند و به پایان میرسد.
    • [<available : <5 3 6 6> - <0 1 4 0> + <1 3 5 0> = <6 5 7 6]
  5. چون که همه فرایند ها به پایات رسیدند این حالت یک حالت امن است.

برای مثال اگر فرایند ۲ در ابتدا یک منبع دیگر از نوع B درخواست میکرد سیستم به حالت ناامن میرفت.

درخواست ها[ویرایش]

هنگامی که سیستم یک درخواست منبع دریافت میکند الگوریتم بانکدار اجرا میشود تا تعیین کند سیستم را به حالت ناامن نمی‌برد.

  1. آیا میتوان درخواست را اعطا کرد؟
    • اگر نه، میتوان آن را به صف انتظار فرستاد.
  2. فرض کنید درخواست اعطا شد.
  3. آیا حالت جدید امن است؟
    • اگر بله درخواست تخصیص یابد.
    • اگر نه یا درخواست را رد و یا در صف انتظار قرار دهید.

مثال[ویرایش]

در مثال قبل فرض کنید فرایند ۳ درخواست ۲ واحد از منبع C داشته باشد.

  1. منابع C به اندازه کافی وجود ندارد تا درخواست تخصیص داده شود.
  2. درخواست رد میشود.

از طرف دیگر فرض کنید فرایند ۳ درخواست ۱ واحد از منبع C را داشته باشد.

  1. به اندازه کافی منبع برای تخصیص وجود دارد.
  2. فرض کنید منبع تخصیص داده شد.
    • حالت جدید سیستم به این صورت خواهد بود:
Available:
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 2 2 0
(Processes (maximum resources:
A B C D
P1   3 3 2 2
P2   1 2 3 4
P3   1 3 5 0
  1. تعیین کنید اگر حالت جدید امن است.
    1. p1 میتواند 2A, 1B ,1D بگیرد و تمام شود.
    2. p2 میتواند 2B, 1D بگیرد و تمام شود.
    3. در نهایت p3 میتواند 1B, 3C بگیرد و تمام شود.
    4. پس این یک حالت امن است.
  2. از آنجایی که حالت امن است درخواست ها تخصیص داده شوند.

در نهایت در مرحله ای که شروع کردیم فرض کنید فرایند ۲ یک واحد از منبع B درخواست کند

  1. منابع کافی وجود دارد
  2. فرض کنید منابع تخصیص داده شدند. پس حالت جدید به این شکل است:
Available:
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 2 1 0
(Processes (maximum resources:
A B C D
P1   3 3 2 2
P2   1 2 3 4
P3   1 3 5 0
  1. آیا این حالت امن است؟ فرض کنید فرایند های ۱و۲و۳ تعداد بیشتری از منابع B, C درخواست کنند.
    • p1 نمی‌تواند به مقدار کافی منبع B دسترسی داشته باشد.
    • p2 نمی‌تواند به مقدار کافی منبع B دسترسی داشته باشد.
    • p3 نمی‌تواند به مقدار کافی منبع B دسترسی داشته باشد.
  2. از آنحایی که حالت ناامن است درخواست رد میشود.

منابع[ویرایش]

  1. Dijkstra, Edsger W. Een algorithme ter voorkoming van de dodelijke omarming (EWD-108). E.W. Dijkstra Archive. Center for American History, دانشگاه تگزاس در آستین.  (الگو:Cite EWD/forxxxx/EWD108.PDF original; الگو:Cite EWD/forxxxx/EWD108.html transcription) (in Dutch; An algorithm for the prevention of the deadly embrace)
  2. Bic, Lubomir F.; Shaw, Alan C. (2003). Operating System Principles. Prentice Hall. ISBN 0-13-026611-6. 

مطالعه بیشتر[ویرایش]

پیوند به بیرون[ویرایش]