Algoritmul Bakerului

De la Wikipedia, enciclopedia liberă.
Salt la navigare Salt la căutare

Algoritmul baker este una dintre metodele de excludere reciprocă care găsesc aplicații practice în programarea paralelă pentru a serializa execuția secțiunilor critice prin mai multe procese sau fire simultane.

Algoritmul își datorează numele inventatorului său Leslie Lamport , care a propus analogia cu modelul real al unei brutării ocupate, unde clienții smulg un număr înainte de a face coadă pentru a-și aștepta rândul. Clienții brutarului reprezintă sarcini care așteaptă rândul lor să efectueze secțiunea critică .

Sistem

Următoarea este o descriere schematică a algoritmului în pseudocod C ++ :

 // declararea variabilelor globale comune
bool alege [N] = {false}; // N constantă
numărul int [N] = {0};

int i; // indexul firului care rulează
// ...
pentru (;;) {
    alege [i] = adevărat;
    număr [i] = 1 + max (număr [0], număr [1], ..., număr [N - 1]);
    alege [i] = false;
    pentru (j = 0; j <N; ++ j) {
        while (alege [j]);
        in timp ce (
            (număr [j]! = 0) &&
            (
             (număr [j] <număr [i]) ||
             ((număr [j] == număr [i]) && (j <i))
            )
        );
    }
    // <secțiune critică>
    număr [i] = 0;
    // <secțiune non-critică>
}

Operațiune

Indiferent de orice afinitate cu situațiile din lumea reală, este posibil ca mai multe fire să primească același număr de schimbare. Pentru a depăși această circumstanță, indexul firului este introdus ca al doilea argument de comparație. Dacă mai multe fire primesc același număr de schimbare, este o idee bună să acordăm prioritate firului cu cel mai mic indice. Rețineți că indexul fiecărui fir trebuie să fie unic: poate fi atribuit la momentul creării sau transmis ca parametru . În exemplul schematic de mai sus, constanta N reprezintă numărul maxim de fire concurente. După primirea indexului său unic, fiecare fir scrie doar în sloturile sale ( sceglie[i] și numero[i] ). Serializarea este asigurată de cele două iterații consecutive. Aceste bucle sunt repetate de fiecare fir pentru toate firele, inclusiv cel care rulează și firele inactive. Numai atunci când nu mai există fire cu prioritate mai mare este posibil accesul la secțiunea critică.

Considerații

Algoritmul brutarului asigură că numai un fir la un moment dat poate accesa secțiunea critică, indiferent de ordinea comutatoarelor de context și de alte detalii de planificare. Cu toate acestea, există principalul dezavantaj care este tipic pentru toți algoritmii de coordonare descentralizați, adică nu sunt coordonați de programator : sarcinile de așteptare continuă să utilizeze procesorul într-un ciclu de așteptare activ numit așteptare ocupată , încetinind astfel celelalte fire din sistem.

Bibliografie

Elemente conexe

Informatică Portal IT : accesați intrările Wikipedia care se ocupă cu IT