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

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

Բանկիրի ալգորիթմը (անգլ.՝ 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 Սպասելով ժամեր կամ նույնիսկ օրեր ռեսուրսների համար որ ազատվեն սովորաբար ընդունելի չէ ։

Ծանոթագրություններ[խմբագրել]

  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[խմբագրել]

Արտաքին հղումներ[խմբագրել]