Դեկկերի ալգորիթմ
| Դեկկերի ալգորիթմ | |
|---|---|
| Տեսակ | համընկնող վերահսկման ալգորիթմ |
Փոխադարձ բացառման խնդրի առաջին հայտնի կորեկտ որոշումը մրցակցային ծրագրավորման մեջ։ Էդսգեր Դեյկստրան իր աշխատանքում նկատի ունի Տ. Դեկկերին որպես միջպրոցեսային փոխազդեցության ալգորիթմի հեղինակ[1], 1965</ref>։ Նա թույլ է տալիս 2 կատարումների հոսքերին միասին օգտագործել չբաժանվող ռեսուրսը առանց կոնֆլիկտի առաջացման՝օգտագործելով միայն ընդհանուր հիշողությունը կոմունիկացիաների համար։
Նախաբան
[խմբագրել | խմբագրել կոդը]Եթե 2 պրոցեսներ փորձում են միաժամանակ անցնել կրիտիկական սեկցիան, ալգորիթմը թույլ է տալիս դա նրանցից միայն մեկին՝ հիմնվելով՝ ում հերթն է այդ պահին։ Եթե մի պրոցեսը արդեն մտել է կրիտիկական սեկցիա, մյուսը պետք է սպասի մինչև առաջինը կլքի այն։ Այն իրականացվում է 2 դրոշների օգնությամբ ("մտադրություն" ինդիկատրով մտնել կրիտիկական սեկցիա ) և փոփոխական հերթ (ցույց տվող, թե որ պրոցեսի հերթն է եկել)։
Մակակոդ
[խմբագրել | խմբագրել կոդը]
flag[0] = false flag[1] = false turn = 0 // or 1 | |
p0։
flag[0] = true
while flag[1] = true {
if turn !=0 {
flag[0] = false
while turn != 0 {
}
flag[0] = true
}
}
// կրիտիկական սեկցիա
...
turn = 1
flag[0] = false
// կրիտիկական սեկցիայի ավարտ
...
|
p1։
flag[1] = true
while flag[0] = true {
if turn != 1 {
flag[1] = false
while turn !=1 {
}
flag[1] = true
}
}
// կրիտիկական սեկցիա
...
turn = 0
flag[1] = false
// կրիտիկական սեկցիայի ավարտ
|
Պրոցեսները հայտարարում են իրենց ցանկության մասին՝ մտնել կրիտիկական սեկցիա. այն ստուգվում է «while» արտաքին ցիկլով։ Եթե մյուս պրոցեսը չի հայտնել այդպիսի ցանկություն, կարելի է անվտանգ մտնել կրիտիտկական սեկցիա (հաշվի չառնելով, թե ում հերթն է այդ պահին)։ Փոխադարձ բացառումը միևնույն է պետք է ապահովվի, այնպես որ պրոցեսներից ոչ մեկը չի կարող մտնել կրիտիկական սեկցիա մինչ այդ դրոշի տեղադրումը (նշանակում է, որ ծայրահեղ դեպքում մի պրոցեսը կմտնի «while» ցիկլ)։ Այն նույնպես երաշխավորում է, որ չի լինելու պրոցեսի սպասում. կրիտիկական սեկցիա մտնելու «մտադրությունը» թողած։ Այլ դեպքում, եթե սահմանված լինի փոփոխական պրոցեսը, «while» ցիկլ կմտնի և փոփոխական հերթը՝ turn, ցույց կտա թե ում է թույլատրված մտնել կրիտիկական սեկցիա։ Պրոցեսը, որի հերթը չի եկել, թողնում է կրիտիկական սեկցիա մտնելու մտադրությունը այնքան ժամանակ, քանի դեռ չի եկել իր հերթը (ներքին «while» ցիկլ)։ Պրոցեսը, որի հերթը եկել է, դուրս կգա «while» ցիկլից և կմտնի կրիտիկական սեկցիա։
Դեկկերի ալգորիթմը ապահովում է փոխադարձ բացառումը, ազատում խցանումից և պակասորդից։ Քննարկենք, թե ինչու է ճիշտ վերջին հատկությունը։ Ենթադրենք, որ p0-ն ընդմիշտ մնացել է «while flag[1]» ցիկլի ներսում։ Քանի որ փոխադարձ արգելափակում տեղի ունենալ չի կարող, ուշ թե շուտ p1-ը կհասնի իր կրիտիկական սեկցիային և կսահմանի turn=0(turn-ի արժեքը կլինի մշտական մինչև p0-ն չտեղաշարժվի)։ p0-ն դուրս կգա ներքին ցիկլից՝«while turn≠0»(եթե այնտեղ է գտնվում)։ Դրանից հետո այն կտա flag[0]-ին true արժեք և կսպասի մինչև flag[1]-ը ընդունի false արժեք(turn=0 երբեք «while» ցիկլում գործողություն չի կատարում)։ Հաջորդ անգամ, երբ p1-ը փորձի մտնել կրիտիկական սեկցիա, նա ստիպված պետք է կատարի գործողություն «while flag[0]» ցիկլում։ Մասնավորապես, այն flag[1]-ին կտա false արժեք և կկատարի «while turn≠1» ցիլկը(այնպես, որ turn-ը մնում է հավասար 0-ի)։ Երբ մյուս անգամ կառավարումն անցնի p0-ին, այն դուրս կգա «while flag[1]» ցիկլից և կմտնի կրիտիկական սեկցիա։
Եթե ալգորիթմը փոփոխվի այնպես, որ գործողությունները «while flag[1]»-ում կատարվեն առանց «turn=0» ստուգման պայմանների, ապա կարող է առաջանալ պակասորդի հնարավորություն։ Այսպիսով ալգորիթմի բոլոր քայլերը հանդիսանում են անհրաժեշտ։
Յուրահատկություններ
[խմբագրել | խմբագրել կոդը]Դեքքերի ալգորիթմի առավելություններից մեկն այն է, որ չի պահանջում Test-and-set կարգավորումներ, այդ իսկ պատճառով լայնորեն կիրառելի է տարբեր լեզուներում և մեքենայի տարբեր կառուցվածքներում։ Դեկկերի ալգորիթի թերություն է հանդիսանում այն հանգամանքը, որ սահմանափակվում է երկու պրոցեսներով և օգտագործում է զբաղված սպասում՝ պրոցեսների կրճատման փոխարեն(զբաղված սպասումը ենթադրում է, որ պրոցեսները պետք է գտնվեն կրիտիկական սեկցիայում որոշակի մինիմալ ժամանակահատավածում)։
Ժամանակակից օպերացիոն համակարգերը օգտագործում են պարզ ընդհանուր բացառում, որն ավելի ընդհանուր և ճկուն է, քան Դեկկերի ալգորիթմը։ Այնուամենայնիվ, երկու պրոցեսների միջև մրցակցության բացակայության պատճառով մուտքը և ելքը կրիտիկական սեկցիայից շատ արդյունավետ է, երբ օգտագործվում է Դեկկերի ալգորիթմը։
Բազմաթիվ ժամանակակից CPU-ներ իրականացում են իրենց կարգավորումները ոչ կարգավորված ձևով, նույնիսկ հիշողության հասանելիությունը կարող է լինել վերակարգավորված։ Այս ալգորիթմը չի աշխատում SMP մեքենաների վրա, որոնք օգտագործում են այսպիսի CPU-ներ, եթե չօգտագործենք հիշողության կրիչներ ։