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

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

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

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

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

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

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

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

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

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

  1. Claim ≤ Resource: تعداد درخواست های یک فرایند از یک منبع ، کوچکترمساوی تعداد کل آن منبع باشد.
  2. request ≤ available : تعداد نیازهای یک فرایند به یک منبع، کوچکترمساوی تعداد موجود از آن منبع باشد. (نیاز = درخواست ها - تخصیص یافته ها)

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

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

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

  • Resources(بردار منابع کل): یک بردار به طول m که نشان دهنده تعداد کل منابع موجود از هر نوع منبع است.
  • Available(بردار موجودی): یک بردار به طول m که نشان دهنده تعداد منابع موجود از هر نوع منبع است. اگر Available[j] = k باشد یعنی k تا از منبع نوع Rj موجود است.
  • Claim (کل درخواست ها): یک ماتریس 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 = Claim- Allocation

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

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

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

R1 R2 R3
6  3  9

بردار موجودی(Available) :

(تعداد به کاررفتن هر منبع در کل فرایندها - تعداد کل آن منبع = موجودی آن منبع )

R1 R2 R3 
1  1  0

ماتریس منابع تخصیص یافته (Allocation) :

R1 R2 R3 
P1  1  0  0 
P2  6  1  2 
P3  2  1  1
P4  0  0  2 

ماتریس کل درخواست ها(Claim) :

R1 R2 R3 
P1  3  2  2 
P2  6  1  3 
P3  3  1  4
P4  4  2  2

ماتریس منابع مورد نیاز فرایند ها برای اتمام (Need) :

(کل درخواست - تخصیص یافته =نیاز)

R1 R2 R3 
P1  2  2  2 
P2  0  0  1 
P3  1  0  3
P4  4  2  0

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

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

طبیعی است که حالتی که امن نباشد ،حالت ناامن است.

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

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

  • فرایند p1 برای کامل شدن به <2 2 2> واحد به ترتیب از R1,R2,R3 نیاز دارد.اما این تعداد از منابع از تعداد بردار موجودی بیشتر است.پس درخواست رد میشود.
  • فرایند p2 برای کامل شدن به <1 0 0 > نیاز دارد.منابع موجود است.پس اختصاص داده میشود و بردار موجودی به حالت زیر در می آید :
    • [<available : <0 1 1 > - <0 0 1> = <0 1 0]
  • فرایند p2 تمام منابع درخواستی اش را در اختیار دارد پس تا تمام شدن اجرا میشود و بعد از آن منابعش را آزاد میکند و منابع آزاد شده به بردار موجودی اضافه میشود.
    • [<available: <0 1 0>+<6 1 3>= <6 2 3]
    • ماتریس درخواست های کل (Claim) به صورت زیر تغییر میکند :
R1 R2 R3 
P1  3  2  2 
P2  0  0  0 
P3  3  1  4
P4  4  2  2
ᗛ پس از اتمام هر فرایند ، باید دوباره از اولین ردیف ، نیازمندی ها بررسی شود.[ویرایش]
  • فرایند p1 برای کامل شدن به <2 2 2> نیاز دارد.منابع موجود است.پس اختصاص داده میشود فرایند کامل شده و منابعش را آزاد میکند  :
    • [<available: <6 2 3>-<2 2 2> + <3 2 2>= <7 3 4]
    • ماتریس درخواست های کل :
R1 R2 R3 
P1  0  0  0 
P2  0  0  0 
P3  3  1  4
P4  4  2  2
  • فرایند p3 برای کامل شدن به <3 0 1> نیاز دارد.منابع موجود است.پس اختصاص داده میشود فرایند کامل شده و منابعش را آزاد میکند:
  • [<available: <7 2 3>-<1 0 3> + <3 1 4>= <9 3 4]
  • ماتریس درخواست های کل :
R1 R2 R3 
P1  0  0  0 
P2  0  0  0 
P3  0  0  0
P4  4  2  2
  • فرایند p4 برای کامل شدن به <0 2 4> نیاز دارد.منابع موجود است.پس اختصاص داده میشود فرایند کامل شده و منابعش را آزاد میکند:
  • [<available : <9 3 4> - <4 2 0> + <4 2 2> = <9 3 6]
R1 R2 R3 
P1  0  0  0 
P2  0  0  0 
P3  0  0  0
P4  0  0  0
ᗛبدیهی است که پس از پایان فرایندها ، آخرین مقدار بردار موجودی باید با مقدار کل منابع برابر باشد.[ویرایش]
ᗛبنابراین ما "ترتیبی" از اجرای فرایندها یافتیم ، که از آن ، حالت امن نتیجه گرفته می شود.[ویرایش]

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

در مثال قبل فرض کنید مقادیر تخصیص یافته فرایند p2 از <2 1 6> به <1 1 5> و فرایند p1 از <0 0 1> به <1 0 2> تغییر حالت دهند.با این تغییر ماتریس نیازها هم تغییر خواهد کرد.یعنی :

ماتریس تخصیص یافته ها :

R1 R2 R3 
P1  2  0  1 
P2  5  1  1 
P3  2  1  1
P4  0  0  2

ماتریس نیاز ها :

R1 R2 R3 
P1  1  2  1 
P2  1  0  1 
P3  1  0  3
P4  4  2  0

بردار موجودی :

R1 R2 R3 
1  1  0
  • همانگونه که مشاهده میشود تمامی فرایند ها به حداقل یک واحد از منبع R1 نیازمندند ؛ اما بردار موجودی R1 صفر است.پس این حالت از تخصیص ، حالت نا امن است.

'

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

  1. .  (original; 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. 

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

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