Բանկիրի ալգորիթմ

Բանկիրի ալգորիթմը (անգլ.՝ Banker's algorithm‎) ռեսուրսների հատկացման և փակուղուց խուսափելու ալգորիթմ է մշակված Edsger Dijkstra-ի կողմից ։

Ալգորիթմը մշակվել օպերացիոն համակարգերի է նախագծման պրոցեսում. Անունը համանմանություն ունի այն եղանակի հետ որով բանկիրները բացատրություն են տալիս իրացվելիության սահմանափակումների համար։

Ալգորիթմ

Բանկիրի ալգորիթմը իրականացվում է օպերացիոն համակարգի կողմից ամեն անգամ երբ պրոցեսը հայցում է ռեսուրսներ։. Ալգորիթմը կանխում փակուղիները հետաձգելով կամ մերժելով հարցումները եթե այն պարզում է որ ընդունելով հարցումը կարող է համակարգը դնել վտանգավոր իրավիճակի։ Երբ նոր պրոցեսը մուտք է գործում համակարգ այն պետք է հայտարարի յուրաքանչյուր ռեսուրսի կողմից մեքենագրվող առնձին դեպքերի մաքսիմալ քանակը որը չպետք է գերազանցի համակարգում առկա ռեսուրսների ընդհանուր քանակը։ Նաև երբ պրոցեսը ստանում է բոլոր իր հայցված ռեսուրսները այն պետք վերադարձնի դրանք սահմանափակ քանակությամբ ժամանակում։

Ռեսուրսներ

Բանկիրի ալգորիթմին աշխատելու համար կարիք կա իմանալու 3 բան։

• Յուրաքանչյուր պրոցես առավելագույնը ինչքան ռեսուրս կարող է հայցել.
• Յուրաքանչյուր պրոցես ներկա պահին ինչքան ռեսուրս է զբաղեցնում
• Յուրաքանչյուր ռեսուրսից ներկա պահին համակարգում որքանն է .

Ռեսուրսները կարող են կինել հատկացված պրոցեսին միայն եթե այն բավարարում է հետևյալ պայմաններին։

1. հայցումը ≤ max, հակառակ դեպքում հայտարարի error վիճակ քանի որ պրոցեսր հատեց մաքսիմումի պայմանը արված իր։
2. հայցումը ≤ հասնելիից, հակառակ դեպքում պրոցեսը սպասւմ է մինչև որ ռեսուրսները հասանելի են։

Բանկիրի ալգորիթմը ստացել է իր անունը այն փաստից որ այս ալգորիթմը կարող է օգտագործվել բանկային համակարգում երաշխավորելու համար որ բանկի ռեսուրսները չեն սպառվում քանի որ բանկը երբեք չի հատկացնի իր փողը այն եղանակով որ այն այլևս չկարողանա բավարարել իր բոլոր հաճախորդների կարիքները։ Օգտագործելով բանկիրի ալգորիթմը բանկը երաշխաորումէ որ երբ հաճախորդները հայցեն փող բանկը երբեք չի լքի ապահով իրավիճակը . Երե հաճախորդների հայցը չի ստիպի բանկին թողնել իր ապահով վիճակը կանխիկ փողը կտրամադրվի հակառակ դեպքում հաճախորդը պետք է սպասի այնքան քանի դեռ ուրիշ հաճախորդները չեն ավանդագրել բավական Հիմնական տվյալների կառուցվածքները որոնք պետք է սահմանվեն իրականացնելու բանկիրի ալգորիթմը։ Թող n լինի համակարգում պրոցեսների քանակը և m-ը լինի ռեսուրսների տիպերի քանակը Այնուհետև մեզ անհրաժեշտ է հետևյալ տվյալների կառուցվածքները։

• Available(հասանելի)։ Մի վեկտոր m երկարությամբ որը ցույց է տալիս յուրաքանչյուր տիպի հասանելի ռեսուրսների քանակը։. Եթե Available [j] = k, այստեղ կա k հատ R_j հասանելի ռեսուրսի տիպի օրինակ.
• Max։ An n×m չափանի մատրից որը սահմանում է մաքսիմում պահանջարկը յուրաքանչյուր պրոցեսի If Max[i, j] = k, then P_i կարող է հայցել ամենաշատը k հատ R_j ռեսուրսի տիպի օրինակ.
• Allocation(հատկացում)։ n×m չափանի մատրից որը սահմանում է յուրաքանչյուր տիպի ռեսուրսների քանակը որոնք ներկա պահին հատկացված են ամեն պրոցեսի։. If Allocation[i, j] = k, then պրոցես P_i ներկա պահին հատկացված է k հատ R_j ռեսուրսի տիպի օրինակի.։
• Need(կարիք, պահանջ)։ An n×mչափանի մատրից որը ցույց է տալիս մնացած ռեսուրսների անհրաժեշտությունը յուրաքանչյուր պրոցեսում. If Need[i, j] = k, then P_iհնարավոր է կարիք ունենա մի քանի k հատ R_j ռեսուրսի տիպի օրինակ առաջադրանքը ավարտելու համար

Նշում։ Need = Max - Allocation.Պահանջ=Մաքսիմում-Հատկացված

Օրինակ

Ենթադրենք համակարգը տարբերակում է 4 տիպի ռեսուրսների (A, B, C և D) միջև, Հետևյալը մի օրինակ է թե ինչպես այդ ռեսուրսները կարող են բաշխվել։ . Նկատիր որ այս օրինակը ցույց է տալիս մի ակնթարթ մինչ ռեսուրսների նոր հայցումները կժամանեն։Նաև ռեսուրսների քանակը և տիպը վերացական է։ Իրական համակարգերն օրինակի համար գործ են ունենում յուրաքանչյուր տիպի ռեսուրսի ավելի մեծ քանակի հետ Համակարգում առկա ընդհանուր ռեսուրսները։

A B C D
6 5 7 6

Համակարգի հասանելի ռեսուրսներն են`
A B C D
3 1 1 2

պրոցեսները (ներկա պահին հատկացված ռեսուրսները)։
 A B C D
P1 1 2 2 1
P2 1 0 3 3
P3 1 2 1 0

պրոցեսները (Մաքսիմում ռեսուրսները)։
 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
պրոցեսներ (ռեսուրսների կարիք)։
 A B C D
P1 2 1 0 1
P2 0 2 0 1
P3 0 1 4 0

Ապահով և վտանգավոր իրավիճակներ

Իրավիճակը (ինչպես վերևի օրինակում) համարվում է ապահով եթե դա հնարավոր է բոլոր պրոցեսների համար ավարտել կատարվողը։Քանի որ համակարգը չի կարող իմանալ թե երբ է պրոցեսը ավարտվում կամ որքան ռեսուրսներ այն կհայցի հետո, համակարգը ենթադրում է որ բոլոր պրոցեսները վերջիվերջո կփորձեն ձեռք բերել իրենց կողմից հաստատած մաքսիմում ռեսուրսները և դրանից հետո շուտ կվերջացնեն։Սա խելամիտ ենթադրություն է շատ դեպքերում քանի որ համակարգը առանձնապես մտահոգված չէ թե որքան ժամանակ է յուրաքանչյուր պրոցես իրականացվում։Նաև եթե պրոցեսը ավարտվեց առանց օգտագործելով իր մաքսիմում ռեսուրսները այն միայն հեշտացնում է համակարգի աշխատանքը։ Ապահով իրավիճակը համրվում է որոշում կայացնող եթե այն պատրաստվում է իրագործել պատրասի հերթ։Տալով այդ ենթադրությունը ալգորիթմը պարզում է արդյոք իրավիճակը ապահով է փորձելով գտնել պրոցեսների ենթադրական հայցումների շարանը որը յուրաքանչյուրին թույլ կտա ձեռք բերել իր մաքսիմում ռեսուրսները այնուհետև ավարտել վերադարձնելով այդ ռեսուրսները համակարգին։ Ցանկացած իրավիճակ որտեղ այսպիսի համակցությունը բացակայում է համարվում է վտանգավոր իրավիճակ։

Օրինակ

Մենք կարող ենք ցույց տալ որ իրավիճակը նախորդ օրինակում ապահով իրավիճակ է ցույց տալով որ դա հնարավոր է յուրաքանչյուր պրոցեսի համար ձեռք բերել իր մաքսիմում ռեսուրսները և այնուհետև դադարեցնել։

1. P1 ձեռք է բերում 2 A, 1 B և 1 D ավել ռեսուրսներ հասնելով իր մաքսիմումին
   • [Հասանելի ռեսուրս։ <3 1 1 2> - <2 1 0 1> = <1 0 1 1>]
   • Համակարգը այժմ դեռ ունի 1 A, ոչ մի B, 1 C և 1 D ռեսուրս հասանելի

1. P1-ը դադարեցվում է վերադարձնելով 3 A, 3 B, 2 C և 2 D ռեսուրսներ համակարգին
   • [Հասանելի ռեսուրս։ <1 0 1 1> + <3 3 2 2> = <4 3 3 3>]
   • Համակարգը այժմ ունի 4 A, 3 B, 3 C և 3 D ռեսուրս հասանելի
2. P2-ը ձեռք է բերում 2 B և 1 D հավելյալ ռեսուրսներ այնուհետև դադարեցնում է վերադարձնելով բոլոր իր ռեսուրսները
   • [Հասանելի ռեսուրս։ <4 3 3 3>-<0 2 0 1>+<1 2 3 4> = <5 3 6 6>]
   • Համակարգը այժմ ունի 5 A, 3 B, 6 C և 6 D ռեսուրսներ
3. P3-ը ձեռք է բերում 1 B և 4 C ռեսուրսներ և դադարեցնում է
   • [ Հասանելի ռեսուրս։ <5 3 6 6> - <0 1 4 0> + <1 3 5 0> = <6 5 7 6>
   • Համակարգը այժմ ունի բոլոր ռեսուրսները։ 6 A, 5 B, 7 C և 6 D
4. Քանի որ բոլոր պրոցեսները ի վիճակի էին դադարեցնել այս իրավիճակը ապահով է։

Պետք է նկատել որ այս հայցումները և ձեռքբերումները ենթադրական են։Ալգորիմը ստեղծում է դրանք ստուգելու իրավիճակաի ապահովությունը բայց ոչ մի ռեսուրս չի տրամադրվում և ոչ մի պրոցես չի ավարտվում։Նաև պետք է նկատի ունենալ որ այն հերթականությունը որով այս հայցումները ստեղծվում են եթե մի քանիսը միայն կատարվեն պետք չէ մտահոգվել որովհետև բոլոր ենթադրական հայցումները թույլ են տալիս պրոցեսին ավարտվել դրա շնորհիվ մեծացնելով համակարգի ազատ ռեսուրսները։ Օրինակի համար անապահով իրավիճակ ենթադրենք թե ինչ կպատահի եթե պրոցես 2-ը պահում էր 1-ով ավելի միավոր B սկզբում։

Հարցումներ

Երբ համակարգը ստանում է հարցում ռեսուրսների համար այն իրականացնում է բանկիրի ալգորիթմը պարզելու համր արդյոք ապահով է թույլատրել հարցումը։Ալգորիթմը .արդարացիորեն հետապնդում է մի բան ապահով և վտանգավոր իրավիճակների միջև տարբերության միջև պատկերացում կազմել։

#Կարող է հարցումը թույլատրվել?

1. • Եթե ոչ հարցումը անհնար է և կամ պետք է մերժվի կամ հետաձգվի կամ սպասման ցուցակում մնա։

#Ենթադրենք որ հարցումը թույլատրված է։

1. Արդյոք նոր իրավիճակը ապահով է։
   • Եթե այո թույլատրի հարցումը
   • Եթե ոչ կամ մերժի հարցումը կամ դիր այն սպասման ցուցակում։

Եղանակը թե ինչպես է համակարգը մերժում կամ հետաձգում անհանարին կամ վտանգավոր հարցումները մի վճիռ է որը հատուկ է օպերացիոն համակարգին

Օրինակ

Սկսենք այն նույն վիճակից ինչպես նախորդ օրինակը սկսվեց ենթադրելով որ պրոցես 3-ը հայցում է 2 միավոր ռեսուրս C.

1. Չկա բավական ռեսուրս C հասանելի թույլատրելու հարցումը։
2. Հարցումը մերժվում է։

Մյուս կողմից ենթադրենք պրոցես 3-ը հայցում է 1 միավոր ռեսուրս C.

1. Կա բավական ռեսուրսներ թույլատրելու հայցումները
2. Ենթադրենք հայցումը թույլատրված է։
   • Համակարգի նոր վիճակը կլինի։

Համակարգի հասանելի ռեսուրսներն են

A B C D
Free 3 1 0 2

պրոցեսներ (ներկա պահին հատկացված ռեսուրսներ)։
A B C D
P1 1 2 2 1
P2 1 0 3 3
P3 1 2 2 0

պրոցեսներ (մաքսիմում ռեսուրսներ)։
A B C D
P1 3 3 2 2
P2 1 2 3 4
P3 1 3 5 0

1. Պարզել արդյոք նոր վիճակը ապահով է։
   1. P1 –ը կարող է ձեռք բերել 2 A, 1 B և 1 D ռեսուրսներ այնուհետև դադարեցնել։
   2. Հետո, P2-ը կարող է ձեռք բերել 2 B և 1 D ռեսուրսներ և դադարեցնել։
   3. Վերջապես, P3-ը կարող է ձեռք բերել 1B և 3 C ռեսուրսներ և դադարեցնել։
   4. Ուստի այս նոր վիճակը ապահով է։
2. Քանի որ նոր վիճակը ապահով է հայցումը թույլատրված է

Վերջապես այն վիճակից որից մենք սկսեցինք ենթադրեք որ պրոցես 2-ը հայցում է 1 միավոր ռեսուրս B.

1. Կան բավական ռեսուրսներ
2. Ենադրենք հայցումը թույլատրված է նոր վիճակը կլինի։

Համակարգի հասանելի ռեսուրսներն են։

A B C D
Free 3 0 1 2

պրոցեսներ (ներկա պահին հատկացված ռեսուրսներ)։
A B C D
P1 1 2 2 1
P2 1 1 3 3
P3 1 2 1 0

պրոցեսներ (մաքսիմում ռեսուրսներ)։

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

1. Արդյոք այս վիճակը ապահով է? Ենթադրենք P1, P2, և P3-ը հայցում են ավելի շատ ռեսուրս B և C.
   • P1-ը անկարող է ձեռք բերել բավական ռեսուրս B
   • P2 անկարող է ձեռք բերել բավական ռեսուրս B
   • P3 անկարող է ձեռք բերել բավական ռեսուրս B
   • Ոչ մի պրոցես չի կարող ձեռք բերել բավական ռեսուրսներ ավարտելու համար այպիսով այս վիճակը անապահով է։
2. Քանի որ վիճակը անապահով է մերժիր հարցումը։

Սահմանափակումներ

Նման այլ ալգորիթմներին բանկիրի ալգորիթմը ունի որոշ սահմանափակումներ երբ կարատված է։ Հատկապես այն կարիք ունի իմանալու թե յուրաքանչյուր ռեսուրսից որքան պրոցեսը առավելագույնը կհայցի։ Շատ համակարգերում այս ինֆորմացիան անհասանելի է դարձնելով այն անհնար իրականացնելու բանկիրի ալգորիթմը։ Նաև այն անիրատեսական է ենթադրել թե որ պրոցեսների քանակը ստատիկ է քանի որ ծատ համակարգերում պրոցեսների քանակը փոխվում է դնամիկորեն։ Դեռավելին պահանջը որ պրոցեսը վերջիվերջո ազատ կարձակի բոլոր իր ռեսուրսները (երբ պրոցեսը ավարտվում է) բավականչափ է ալգորիթմի ստույգության համար այնուամենայնիվ այն բավականաչափ չէ պռակտիկալ համակարգի համար։ Սպասելով ժամեր կամ նույնիսկ օրեր ռեսուրսների համար որ ազատվեն սովորաբար ընդունելի չէ։

Գրականություն

• "Operating System Concepts Արխիվացված 2010-10-13 Wayback Machine" by Silberschatz, Galvin, and Gagne (pages 259-261 of the 7th edition)
• Կաղապար:Cite EWD (1977), published as pages 308–312 of Edsger W. Dijkstra, Selected Writings on Computing: A Personal Perspective, Springer-Verlag, 1982. ISBN 0-387-90652-5

Արտաքին հղումներ

• Deadlock Recovery, Avoidance and Prevention Արխիվացված 2010-08-31 Wayback Machine