Algoritmul de panificație al lui Lamport este un algoritm pentru partajarea resurselor partajate între mai multe fire prin excludere reciprocă . Publicat de informaticianul Leslie Lamport în 1974 [1] .
O situație comună în informatică este atunci când mai multe fire au nevoie de acces la aceleași resurse. Dacă două sau mai multe fire de execuție încearcă să scrie în aceeași locație de memorie sau dacă un fir de execuție încearcă să citească ceva care nu a fost încă scris de un alt fir de execuție, poate apărea coruperea datelor. Algoritmul Bakery de la Lamport este unul dintre numeroșii algoritmi de excludere reciprocă proiectați pentru a împiedica firele paralele să locuiască concomitent în secțiuni critice de cod pentru a elimina riscul coruperii datelor.
Lamport sugerează să luați în considerare o brutărie cu o mașină de numerotație la intrare. Fiecărui client care vine i se acordă un număr cu unu mai mult decât precedentul. Contorul total arată numărul clientului deservit în prezent. Toți ceilalți clienți așteaptă până când termină servirea clientului actual și tabloul de bord arată următorul număr. După ce clientul face o achiziție și își predă numărul, angajatul mărește cu unul numerele permise pentru dispozitivul de la intrarea în emitere. Dacă clientul care a făcut achiziția dorește să cumpere din nou ceva, va trebui să ia din nou numărul de la intrare și să stea la coada generală.
Fie cumpărători fluxurile care au primit numerele i din variabila globală.
Din cauza limitărilor arhitecturii computerului, momentul emiterii numerelor ar trebui să fie ușor modificat, deoarece apare o situație de ambiguitate dacă doi sau mai mulți cumpărători (fluxuri) doresc să primească un număr cu numărul n deodată . Dacă există mai multe fire care au primit numărul n la intrarea în secțiunea critică, firul cu numărul i mai mic va avea o prioritate mai mare la servire (intrarea în secțiunea critică).
O secțiune critică este o bucată de cod care necesită acces exclusiv la resurse și poate fi executată doar de un fir la un moment dat.
Când un thread dorește să intre într-o secțiune critică, trebuie să verifice dacă poate face acest lucru acum. Firul trebuie să verifice numerele n primite de alte fire și să se asigure că are un număr mai mic. Dacă două sau mai multe fire au același n , firul cu cel mai mic i intră în secțiunea critică .
În pseudocod, această comparație pentru fluxurile a și b poate fi scrisă ca:
(n a , i a ) < (n b , i b ),care este echivalent cu:
(n a < n b ) sau ((n a == n b ) și (i a < i b ))Când un fir își termină munca în secțiunea critică, eliberează numărul n și intră în secțiunea necritică.
O secțiune non-critică este o bucată de cod care nu are resurse care necesită acces exclusiv. Acesta este un cod pe care mai multe fire de execuție îl pot executa în paralel fără a interfera unul cu celălalt.
Pentru a reveni la analogie, aceasta face parte din acțiunile care au loc după efectuarea achiziției. De exemplu, returnarea modificărilor într-un portofel.
În articolul original al lui Lamport, procesului și variabilei de numerotare (introducerea, alegerea) se aplică următoarele condiții:
În exemplul de mai jos, toate firele execută aceeași funcție „principală” Thread . În aplicațiile reale, firele diferite au adesea funcții „master” diferite. Ca și în articolul original, aici firele se verifică înainte de a intra în secțiunea critică. Deoarece condiția buclei va returna false , verificarea nu provoacă o întârziere semnificativă de execuție.
// Declararea și inițializarea valorilor variabilelor globale Introducerea : matrice [ 1. . NUM_THREADS ] de bool = { false }; Număr : matrice [ 1. . NUM_THREADS ] de întreg = { 0 }; blocare ( întreg i ) { Introducând [ i ] = adevărat ; Număr [ i ] = 1 + max ( Număr [ 1 ], ..., Număr [ NUM_THREADS ]); Introducerea [ i ] = fals ; pentru ( întreg j = 1 ; j <= NUM_THREADS ; j ++ ) { // Așteptați ca firul j să primească numărul său: în timp ce ( Introducând [ j ]) { /* nu faci nimic */ } // Așteptați până când toate firele cu un număr mai mic sau cu același număr, // dar cu o prioritate mai mare, își vor termina munca: în timp ce (( Numărul [ j ] != 0 ) && (( Numărul [ j ], j ) < ( Numărul [ i ], i ))) { /* nu face nimic */ } } } deblocare ( întreg i ) { număr [ i ] = 0 ; } Fir ( întreg i ) { în timp ce ( adevărat ) { blocare ( i ); // Executați secțiunea critică... debloca ( i ); // Executați secțiunea non-critică... } } Exemplu de cod Java Tichet AtomicIntegerArray = AtomicIntegerArray nou ( fire ); // bilet pentru fire în linie, n - numărul de fire // Fiecare element „ticket” este inițializat la 0 AtomicIntegerArray introducerea = new AtomicIntegerArray ( fire ); // 1 când firul intră în linie // Fiecare element de „intrare” este inițializat la 0 public void lock ( int pid ) // ID-ul firului { intrând . set ( pid , 1 ); int max = 0 ; pentru ( int i = 0 ; i < fire ; i ++ ) { int curent = bilet . obține ( i ); dacă ( curent > max ) { max = curent ; } } bilet . set ( pid , 1 + max ); intrând . set ( pid , 0 ); pentru ( int i = 0 ; i < bilet . lungime (); ++ i ) { dacă ( i != pid ) { în timp ce ( intrând . get ( i ) == 1 ) { Thread . randament (); } // Așteptați ca firul i să-și primească numărul while ( bilet . get ( i ) != 0 && ( bilet . get ( i ) < bilet . get ( pid ) || ( bilet . obține ( i ) == bilet . obține ( pid ) && i < pid ))) { Thread . randament (); } } } // Executați secțiunea critică } deblocare public void ( int pid ) { bilet . set ( pid , 0 ); }Fiecare thread scrie în propria memorie, doar o operație de citire poate fi efectuată pe memoria partajată. Interesant este că algoritmul nu utilizează operații atomice, cum ar fi compararea cu schimbul . Dovada originală arată că pentru suprapunerea citirilor și scrierilor în aceeași celulă, numai scrierea trebuie să fie validă. Operația de citire poate returna o valoare arbitrară. Prin urmare, acest algoritm poate fi folosit pentru a implementa mutexuri pentru memorie care nu are primitive de sincronizare. De exemplu, pentru un simplu disc SCSI folosit de două computere în același timp.
Necesitatea matricei Entering poate să nu fie evidentă, deoarece nu există blocări pe liniile 7 - 13 ale pseudocodului. Cu toate acestea, să presupunem că eliminăm acea matrice și două fire de execuție calculează aceeași valoare Number[i] . Apoi, dacă firul cu prioritate mai mare a fost preemptat înainte de a calcula Number[i] , firul cu prioritate inferioară va vedea că primul proces are Number[i] = 0 și va intra în secțiunea critică. Apoi, primul proces cu prioritate mai mare va ignora numărul de potrivire Number[i] și va intra, de asemenea, în secțiunea critică. Ca rezultat, două procese vor executa simultan secțiunea critică. Este necesară introducerea pentru a efectua operația pe linia 6 ca atomică. Procesul i nu va vedea niciodată Number[j] = 0 când procesul j este pe cale să ia același număr ca i .
Când implementați pseudocod pe un sistem cu o singură sarcină sau multitasking , cel mai bine este să înlocuiți cuvintele „nu face nimic” cu o notificare către sistem pentru a trece imediat la următorul thread. Această primitivă este adesea numită randament .
Algoritmul de panificație al lui Lamport presupune utilizarea unui model de memorie secvenţial consistent . Puține, dacă există, limbi sau procesoare multi-core implementează un astfel de model de memorie. Prin urmare, implementarea corectă a algoritmului necesită de obicei inserarea de gărzi pentru a preveni reordonarea [2] .