Լեմպորտի ալգորիթմ

Լեմպորտի ալգորիթմ
Տեսակ	համընկնող վերահսկման ալգորիթմ
Հայտնաբերող	Լեսլի Լեմպորտ
Անվանված է	Լեսլի Լեմպորտ և Փուռ

Լեմպորտի ալգորիթմը համակարգչային ալգորիթմ է, որը նախագծվել է համակարգչային գիտնական Leslie Lamport-ի կողմից և նախատեսված է փոխադարձ բացառության միջոցով բազմաթիվ գծերի մեջ բաժանված ռեսուրսների օգտագործման անվտանգությունը կատարելագործելու համար։

Համակարգչային գիտության մեջ բազմաթիվ գծերի համար ընդհանուր է միաժամանակ ստանալ միևնույն ռեսուրսները։ Տվյալների աղավաղում կարող է տեղի ունենալ, երբ երկու կամ ավելի գծեր փորձում են գրել հիշողության միևնույն տեղամասի մեջ, կամ երբ գծերից մեկը կարդում է հիշողության տեղամասը մինչև մեկ ուրիշ գիծ վերջացնելիս է լինում դրա մեջ իր գրառումը։ Lamport's bakery ալգորիթմը փոխադարձ բացառելի ալգորիթմներից մեկն է, որը նախագծված է համընկնող գծերի մուտքը ծածկագրի կրիտիկական տեղամաս կանխելու համար՝ տվյալների աղավաղման ռիսկը մրցակցային ձևով վերացնելու նպատակով։

Ալգորիթմ

Համանմանություն

Lamport-ը նախատեսել է հացի խանութը դրա մուտքի մոտ համարակալող մեքենայի հետ մեկտեղ այնպես, որ յուրաքանչյուր հաճախորդի տրվի եզակի համար։ Համարները աճում են մեկով, երբ հաճախորդները մտնում են խանութ։ Ընդհանուր հաշվիչը ցույց է տալիս այն հաճախորդի համարը, որը այդ պահին սպասարկվում է։ Մնացած բոլոր հաճախորդները պետք է սպասեն հերթում մինչև հացթուխը վերջացնի ընթացիկ հաճախորդի սպասարկումը, որից հետո ցուցադրվում է հաջորդ համարը։ Երբ հաճախորդը ավարտում է գնումներ կատարելը և հեռացվում է իր համարից, գրագիրը ավելացնում է համար՝ թույլատրելով հաջորդ հաճախորդին սպասարկվել։ Այդ հաճախորդը պետք է դուրս բերի համարակալող մեքենայից մեկ ուրիշ համար, որպեսզի կրկին գնումներ կատարի։ Համանմանության համաձայն՝ "հաճախորդները" գծերն են, որ նույնացվում են i տառի հետ և ստացվում են գլոբալ փոփոխականներց։

Համակարգչի կառուցվածքային սահմանափակումների շնորհիվ Lamport-ի համանմանությունը չնչին ձևափոխության կարիք ունի։ Դա անհրաժեշտ է, որ մեկից ավելի գծեր կարողանան ստանալ միևնույն համարը, երբ դրանք պահանջում են այն. դա չի կարող խուսափելի լինել։ Ուստի ենթադրվում է, որ գծի նույնարկիչ i-ն նույնպես առաջնային նույնարկիչ է։ i-ի ցածր արժեքը նշանակում է ավելի բարձր առաջնայնություն, և բարձր առաջնայնությամբ գծերը առաջինը կմտնեն կրիտիկական տեղամաս։

Կրիտիկական տեղամաս

Կրիտիկական տեղամասը ծածակագրի մի մասն է, որը պահանջում է բացառիկ մուտք դեպի ռեսուրսներ և կարող է կատարվել տվյալ պահին միայն մի գծի կողմից։ Հացի խանութի համամասնության մեջ դա այն է, երբ հաճախորդն առևտուր է անում հացթուխի հետ, և մնացած հաճախորդները պետք է սպասեն։

Երբ գիծը ցանկանում է մուտք գործել կրիտիկական տեղամաս, այն ենթարկվում է ստուգման, թե արդյոք պատրաստ է այդքանը կատարել։ Այն պետք է ստուգի բոլոր մնացած գծերի համարները վսահ լինելու համար, որ այն ամենափոքրն է։ Այլ գծի ավելի փոքր համար ունենալու դեպքում ամենափոքր i-ով գիծը առաջինը կմտնի կրիտիկական հատված։

Այդ համեմատության կեղծ կոդը կգրվի հետևյալ տեսքով.

(a, b) < (c, d)

որը հավասար է՝

(a < c) or ((a == c) and (b < d))

Հենց որ գիծը ավարտում է իր կրիտիկական աշխատանքը, այն ազատվում է իր համարից և մտնում է ոչ կրիտիկական հատված։

Ոչ կրիտիկական տեղամաս

Ոչ կրիտիկական հատվածը ծածկագրի մի մասն է, որը բացառիկ մուտքի կարիք չունի։ Այն հանդիսանում է որոշ գծերի հատուկ հաշվարկում, որը չի խառնվում այլ գծերի՝ ռեսուրսների և ձևակերպումների հետ։

Այս մասը համանման է այն գործողություններին, որոնք տեղի են ունենում են գնումներից հետո, ինչպես օրինակ մանրադրամի հետ տեղադրումը դրամապանակի մեջ։

Ալգորիթմի իրագործումը

Սահմանումներ

Lamport-ի բնագրում փոփոխականների մուտքագրումը հայտնի է որպես ընտրություն, և կիրառվում են հետևյալ պայմանները.

• [i] բառերի ընտրությունը և [i] թիվը i պրոցեսորի հիշողության մեջ է և նախապես զրո է
• [i] թվի արժեքների դասակարգումը սահմանված չէ
• Պրոցեսորը կարող է ձախողվել ցանկացած ժամանակ։ Մենք ենթադրում ենք, որ երբ այն ձախողվում է, անմիջապես գնում է իր ոչ կրիտիկական հատված և դադարեցվում։ Այդ ժամանակ առաջանում է մի ժամանակաշրջան, երբ պրոցեսորի հիշողությունից ընթերցումը տալիս է կամայական արժեքներ։ Վերջ ի վերջո պրոցեսորի հիշողությունից ցանկացած ընթերցում պետք է տա զրո արժեք։

Կեղծ ծածկագիր

// գլոբալ փոփոխականների հռչակումը և սկզբնական արժեքները
Մուտքագրում։ array [1..NUM_THREADS] of bool = {false};
Թիվ։ array [1..NUM_THREADS] of integer = {0};

1 lock(integer i) {
2 Entering[i] = true;
3 Number[i] = 1 + max(Number[1], ..., Number[NUM_THREADS]);
4 Entering[i] = false;
5 for (j = 1; j <= NUM_THREADS; j++) {
6 // Սպասել մինչև j գիծը ստանա իր համարը։
7 while (Entering[j]) { /* nothing */ }
8 // Սպասել մինչև ավելի փոքր համարներով կամ նույն համարով, բայց
9 // ավելի բարձր առաջնայնությամբ գծերը վերջացնեն իրենց աշխատանքը։
10 while ((Number[j] != 0) && ((Number[j], j) < (Number[i], i))) {
11 /*nothing */
12 }
13 }
14 }
15 //կրիտիկական հատված
16 unlock(integer i) {
17 Number[i] = 0;
18 }
19
20 Thread(integer i) {
21 while (true) {
22 lock(i);
23 // Կրիտիկական հատվածը գալիս է այստեղ...
24 unlock(i);
25 // ոչ կրիտիկական հատված...
26 }
27 }

Այս օրինակում բոլոր գծերը կատարում են միևնույն "գլխավոր" գործողությունը, Գիծ։ Իրական գործածության մեջ տարբեր գծեր հաճախ ունենում են տարբեր "գլխավոր" գործողություններ։

Գրառում։ Գիծը նույնպես ստուգում է ինքնիրեն մինչև կրիտիկական հատված մուտք գործելը, բայց դա չի առաջացնում որևէ ձգձգումներ մինչև որ հանգուցային իրավիճակները կգնահատվեն որպես սխալ։

Քննարկում

Յուրաքանչյուր գիծ գրում է միայն իր իր սեփական պահումը, միայն ընթերցումներն են մասնատված։ Հատկանշական է, որ այս ալգորիթմը կառուցված չէ "ատոմային" գործողության որոշ ցածր մակարդակի վերին աստիճանի համար, օրինակ՝ համեմատումը և փոխանակումը։ Նախնական ապացույցը ցույց է տալիս, որ միևնույն պահեստային բջջում գրառումների և ընթերցումների համընկման դեպքում միայն գրառումները պետք է ճիշտ լինեն։ Ընթերցելու գործողությունը կարող է վերադարձնել կամայական համար։ Հետևաբար այս ալգորիթմը կարող է օգտագործվել հիշողության վրա փոխադարձ բացառումներ կատարելու համար, քանի որ պարզունակ համաժամանակեցումները բացակայում են, օրինակ՝ պարզ SCSI սկավառակը բաժանված է երկու համակարգիչների միջև։ Փոփոխակնների մուտքագրման անհրաժեշտությունը չպետք է ակնհայտ լինի, քանի որ 7-ից 13 տողերի մոտ 'փականք' չկա։ Տես՝ UCDAVIS: Bakery ալգորիթմ` խորությամբ դիտարկման համար։

Երբ միակ պրոցեսորի/ամենաէական համակարգի համար կիրարկում ենք կեղծ ծածկագիր, ավելի հարմար է փոխարինել "do nothing" տեղամասը այն ծածկագրի հետ, որը տեղեկացնում է օպերացիոն համակարգին անմիջապես անցնել հաջորդ գծին։ Սա հաճախ դիտվում է որպես ընթացիկ գծերի զիջում։

Տես նաև

• Dekker-ի ալգորիթմ
• Eisenberg McGuire-ի ալգորիթմ
• Peterson-ի ալգորիթմ

Արտաքին հղումներ

• Bakery ալգորիթմի Wallace-ի փոփոխությունը, որը հաղթահարում է Javascript լեզվի սահմանափակումները
• Lamport's Bakery ալգորիթմ
• Այլ JavaScript գործարկումներ Արխիվացված 2010-03-11 Wayback Machine ըստ՝ a.in.the.k

Մեջբերումներ

• Նախնական ձևաթուղթ
• Իր հրատարակած էջում Lamport-ը ավելացրել է որոշ դիտողություններ ալգորիթմի վերաբերյալ։