Պետերսոնի ալգորիթմ

Պետերսոնի ալգորիթմ
Տեսակ	համընկնող վերահսկման ալգորիթմ

Դանիացի մաթեմատիկոս Դեկկերն առաջինն էր, ով մշակեց փոխադարձ բացառման խնդրի ծրագրային լուծումը, որը չէր պահանջում խիստ հաջորդականություն։ 1981 թվականին Պետերսոնը ստեղծեց փոխադարձ բացառման զգալիորեն ավելի հեշտացված ալգորիթմ։ Այդ պահից սկսած Դեկկերի տարբերակը համարում է հնացած։ Պետերսոնի ալգորիթմը ներկայացվում է ցուցակային տեսքով, բաղկացած է 2 գործընթացից, որոնք գրված են C լեզվով։ Ի սկզաբենե Պետերսոնի ստեղծծ ալգորիթմը նախատեսված էր միայն 2 պրոցեսի հետ աշխատելու համար, սակայն այն կարելի է ընդհանրացնել երկուսից ավել կամայական թվով պրոցեսների համար, ինչպես ցույց կտրվի ստորև։ Պետերսոնի ալգորիթմը միաժամանակյա ծրագրավորման ալգորիթմ է փոխադարձ հակասման համար, ինչը թույլ է տալիս 2 պրոցոսի կիսել մեկանգամյա օգտագործման ռեսուրսը առանց կոնֆլիկտի, օգտագործելով միայն համատեղ օգտագործվող հիշողությունը՝ կապի համար։

Պետերսոնի ալգորիթմը

Մինչ ընդհանուր փոփոխականներին անդրադառնալը /այսինքն՝մինչ կրիտիկական բաժին մուտք գործելը/ պրոցեսը կանչում է enter_region գործողությունը իր 0 կամ 1 համարով որպես արգումենտ։ Այդ պատճառով պրոցեսն անհրաժեշտության դեպքում ստիպված է սպասել մինչ կրիտիկական բաժին իր մուտք գործելը։ Կրիտիկական բաժնից դուրս գալուց հետո պրոցեսը կանչում է leave_region գործողությունը, որպեսզի նշի իր ելքը և այդպիսով թույլ տա ուրիշ պրոցեսի մուտքը կրիտիկական բաժին։ Դիտարկենք ալգորիթմը ավելի մանրամասն։ Ի սկզբանե 2 պրոցեսները գտնվում են կրիտիկական հատվածից դուրս։ Պրոցես 0-ն կանչում է enter_region գործողությունը, սահմանում է դասավորության տարրերը և turn փոփոխականին տալիս է 0 արժեք։ Քանի որ 1 պրոցեսը հետաքրքրված չէ կրիտիկական հատված ընկնելու մեջ տեղի է ունենում վերադարձ գործողությունից։ Այժմ, եթե 1 պրոցեսը կանչի enter_region գործողությունը, ապա այն ստիպված է լինելու սպասել, մինչև interested[0] ընդունի FALSE արժեքը, իսկ դա տեղի կունենա միայն այն պահին, երբ 0 պրոցեսը կանչի leave_region գործողությունը լքելով կրիտիկական հատվածը։ Պատկերացնենք, որ 2 պրոցեսը կանչել են enter_region գործողությունը գրեթե միաժամանակ։ Երկուսն էլ կհիշեն իրենց համարը turn-ում։ Սակայն կպահպանվի այն պրոցեսի համարը, որը երկրորդն էր, իսկ նախորդ համարը կկորի։ Ենթադրենք երկրորդը 1 պրոցեսն էր, այստեղից turn=1։ Երբ 2 պրոցեսը հասնեն while-ին, 0 պրոցեսը մուտք կգործի կրիտիկական հատված, իսկ 1 պրոցեսը կմնա ցիկլի մեջ և կսպասի, մինչև 0 պրոցեսը դուրս գա կրիտիկական հատվածից։ Պետերսոնի ալգորիթմի լուծումը հստակ է, բայց օժտված է մեկ բավականին ազդեցիկ թերությամբ՝ ակտիվ սպասման առկայությամբ։

Ալգորիթմ

Ալգորիթմը օգտագործում է 2 փոփոխական՝ flag/դրոշ/ և turn /հերթ/։ Ճշգրիտ ինդիկատորների flag-ը հաղորդում է, որ n պրոցեսը ցանկանում է մտնել կրիտիկական հատված։ Փոփոխականի turn-ը պարունակում է այն պրոցեսի ID-ն, որի հերթն է։ Կրիտիկական հատված մուտք գործելը շնորհվում է P0 պրոցեսին, եթե P1-ը չի ցանկանում մուտք գործել իր կրիտիկական հատված, կամ եթե P1-ը առավելությունը տվել է P0-ին՝ turn= 0 արժեք տալով։

//flag[] is boolean array; and turn is an integer flag[0] = false; flag[1] = false; turn;
P0: flag[0] = true; turn = 1; while (flag[1] == true && turn == 1) { // busy wait } // critical section ... // end of critical section flag[0] = false;	P1: flag[1] = true; turn = 0; while (flag[0] == true && turn == 0) { // busy wait } // critical section ... // end of critical section flag[1] = false;

Ալգորիթմը բավարարում է 3 հիմնական չափանիշների՝ կրիտիկական հատվածի խնդիրը լուծելու համար, այն պայմանով, որ turn, flag[0] և flag[1] փոփոխականների փոփոխությունները կատարվեն միանգամից և ավտոմատ կերպով։ Երեք չափանիշներն են փոխադարձ բացառումը, առաջընթացը և սահմանափակ սպասումները։

Փոխադարձ բացառում

P0 և P1 միաժամանակ երբեք չեն կարող լինել կրիտիկական հատվածում։ Եթե P0-ն իր կրիտիկական հատվածում է, ապա կամ flag1-ը սխալ է /նշանակում է, որ P1-ը լքել է իր կրիտիկական հատվածը/, կամ turn=0 /նշանակում է P1-ը նոր փորձում է մտնել իր կրիտիկակն հատված, բայց համբերատար սպասում է/։ Երկու դեպքում էլ P1-ը չի կարող լինել կրիտիկակն հատվածում, երբ P0-ն իր կրիտիկական հատվածում է գտնվում։

Առաջընթաց

Առաջընթացը սահմանվում է հետևյալ կերպ։ Եթե ոչ մի պրոցես չի կատարվում իր կրիտիկական հատվածում և որոշ պրոցեսներ ցանկանում են մուտք գործել իրենց կրիտիկական հատված, ապա միայն այն պրոցեսները, որոնք չեն կատարվում իրենց մնացորդային հատվածում, կարող են մասնակցել այն որոշման ընդունմանը, որից հետո պրոցեսը մուտք կգործի իր կրիտիկական հատված։ Պրոցեսը չի կարող անմիջապես նորից մտնել կրիտիկական հատված, եթե մեկ այլ պրոցես սահմանել է իր flag-ը՝ կրիտիկական հատված մուտք գործելու մասին իր ցանկությունը հայտնելու համար։

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

Սահմանափակ սպասումները նշանակում են որ սահմանափակվում է դրված պրոցեսների իրենց կրիտիկական հատված մուտք գործելու թվի վրա այն բանից հետո, երբ պրոցեսը հարցում է կատարում իր կրիտիկական հատված մուտք գործելու մասին և մինչև այդ հարցումը ընդունվում է։ Պետերսոնի ալգորիթմում պրոցեսը չի սպասի ավելի երկար քան մեկ հերթ՝ կրիտիկական հատված մուտք գործելու համար։ Այլ պրոցեսին առավելություն տալուց հետո այս պրոցեսը կավարտվի և իր flag-ին կտա 0 արժեք, այդպիսով թույլ տալով մյուս պրոցեսներին մուտք գործել կրիտիկական հատված։

Պետերսոնի ալգորիթմը N թվով պրոցոսների համար

Այս դեպքում օգտագործվում են N տարբեր մակարդակներ, որոնցից յուրաքանչյուրն իրենից ներկայացնում է կրիտիկական հատվածին նախորդող «սպասող սենյակ»։ Յուրաքանչյուր մակարդակը թույլ կտա մեկ պրոցեսսին զարգանալ՝ մեկ այլ պրոցեսի սպասման մեջ պահելով։

// initialization
level[N] = { 0 }; // current level of each process
waiting[N - 1] = { 0 }; // the waiting process of each level 1..N

// code for process #i
for(l = 1; l < N; ++l) {
    level[i] = l;
    waiting[l] = i;
    while((there exists k ≠ i, such that level[k] ≥ l)
      && waiting[l] == i)
    {
        // busy wait
    }
}

// critical section

level[i] = 0; // exit section

Նշումներ

Սարքավորման մակարդակում աշխատելիս Պետերսոնի ալգորիթմը սովորաբար միջուկային մուտքին հասնելու կարիք չունի։ Որոշ պրոցեսորներ ունեն հատուկ ուղղեցույցներ, ինչպիսիք են test-and-set կամ compare-and-swap, որոնք կողպելող հիշողության սկավառակը կարող են կիրառվել SMP /բազմապրոցեսորային/ համակարգում փոխադարձ բացառումը ապահովելու համար։ Ժամանակակից պրոցեսորներից շատերը վերադասավորում են հիշողության հասանելիությունը կատարման արդյունավետությունը բարելավելու համար։ Այսպիսի պրոցեսորներ անփոխարինելի կերպով հնարավորություն են տալիս պարտադրաբար պատվերներ կատարել հասանելի հիշողության հոսքերում, որպես կանոն հիշողության ուղեցույցի արգելքը անտեսելով։ Պետերսոնի ռեալիզացումը և դրա հետ կապված ալգորիթմները պրոցեսորների վրա, որոնք վերադասավորում են հիշողության հասանելիությունը գլխավորապես պահանջում է ճշգրիտ աշխատանքի համար այնպիսի օպերացիաների կիրառում, որպեսզի հաջորդական պրոցեսերը անճշտությունից հետ պահելու համար։ Նշենք, որ հիշողության վերադասավորումը կարող է տեղի ունենալ անգամ այնպիսի պրոցեսորների վրա, որոնք չեն վերադասավորում ուղղեցույցները /այդպիսիք են PowerPC պրոցեսորը Xbox 360–ում/։ Այսպիսի պրոցեսորներից շատերը նաև ունեն երաշխավորված միջուկային օպերացիայի տիպ, ինչպիսիք են XCHG/x86/ պրոցեսորները և Load-Link/Stoe-Conditional/Alpha/, MIPS, PowerPC և այլ կառուցվածքներ։ Այս ուղեցույցների նպատակն է ապահովել, որ սինխրոնիզացիայի արդյունավետությունը լինի առավելագույնը։

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

1. G. L. Peterson։ "Myths About the Mutual Exclusion Problem", Information Processing Letters 12(3) 1981,
2. As discussed in Operating Systems Review, January 1990 ("Proof of a Mutual Exclusion Algorithm", M Hofri).
3. Silberschatz. Operating Systems Concepts։ Seventh Edition. John Wiley and Sons, 2005.,