Դեկկերի ալգորիթմ
Փոխադարձ բացառման խնդրի առաջին հայտնի կորեկտ որոշումը մրցակցային ծրագրավորման մեջ: Էդսգեր Դեյկստրան իր աշխատանքում նկատի ունի Տ.Դեկկերին որպես միջպրոցեսային փոխազդեցության ալգորիթմի հեղինակ:[1]. Նա թույլ է տալիս 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-ներ, եթե չօգտագործենք հիշողության կրիչներ :
[խմբագրել] Նշումներ
- ↑ E.W. Dijkstra, Cooperating Sequential Processes, 1965.
