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

Վիքիպեդիայից՝ ազատ հանրագիտարանից

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

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

Ալգորիթմը[խմբագրել]

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

Ռեսուրսներ[խմբագրել]

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

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

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

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

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

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

Նշում։ 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. Արդյոք նոր իրավիճակը ապահով է:
    • Եթե այո թույլատրի հարցումը
    • Եթե ոչ կամ մերժի հարցումը կամ դիր այն սպասման ցուցակում:
Եղանակը թե ինչպես է համակարգը մերժում կամ հետաձգում անհանարին կամ վտանգավոր հարցումները մի վճիռ է որը հատուկ է օպերացիոն համակարգին

Օրինակ[խմբագրել]

Սկսենք այն նույն վիճակից ինչպես նախորդ օրինակը սկսվեց ենթադրելով որ պռոցես 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. Քանի որ վիճակը անապահով է մերժիր հարցումը։

Սահմանափակումներ[խմբագրել]

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

References[խմբագրել]

  1. Կաղապար:Cite EWD (in Dutch; An algorithm for the prevention of the deadly embrace)
  2. (2003) Operating System Principles։ Prentice Hall։ ISBN 0-13-026611-6։ 

Further reading[խմբագրել]

External links[խմբագրել]