Algorytm piekarniany

Algorytm piekarniany – algorytm Leslie Lamporta rozwiązujący wykluczanie się w sekcji krytycznej dla dowolnej N liczby procesów. Algorytm działa na podobnej zasadzie jak automaty do wydawania numerków w bankach i urzędach. Proces o najwyższym indeksie wykona swoją sekcję krytyczną najpóźniej.

Algorytm piekarniany

Rodzaj	wzajemne wykluczanie
Złożoność
Pamięciowa	$\Theta (n)$

Implementacja

Pseudokod

  // ''deklaracja i nadanie początkowych wartości zmiennych globalnych''
  Wpisywanie: '''array''' [1..N] '''of''' '''bool''' = {false};
  Numer: '''array''' [1..N] '''of''' '''integer''' = {0};
  
  blokuj(integer i) {
    Wpisywanie[i] = true;
    Numer[i] = 1 + max(Numer[1], ..., Numer[N]);
    Wpisywanie[i] = false;
    '''for''' (j = 1; j <= N; j++) {
      // ''Czekaj, aż proces j dostanie swój numer'':
      '''while''' (Wpisywanie[j])
        { /* Nie rób nic. */ }
      // ''Czekaj na wszystkie procesy z numerami mniejszymi, bądź równymi,''
      // ''ale z wyższym priorytetem, aż się zakończą'':
      '''while''' ((Numer[j] != 0) && ((Numer[j], j) < (Numer[i], i)))
        { /* Nie rób nic. */ }
    }
  }
  
  odblokuj(integer i) {
    Numer[i] = 0;
  }
  
  Proces(integer i) {
    '''while''' (true) {
      blokuj(i);
      // ''Miejsce na [[sekcja krytyczna|sekcję krytyczną]]...''
      odblokuj(i);
      // ''Miejsce na sekcję lokalną...''
    }
  }

Opis działania

Wywołanie algorytmu (sygnalizacja wejścia do sekcji krytycznej), powoduje zaznaczenia faktu pobierania numeru w tablicy Wpisywanie, wybranie numeru z tabeli Numer a następnie odznaczenie akcji w tablicy Wpisywanie. Odblokowanie numeru realizowane jest przez wyzerowanie odpowiedniej wartości w tablicy Numer. W algorytmie przyjmuje się, że komputer może zapisać dowolną liczbę naturalną atomowo.

Istnieje jednak zasadnicza różnica między systemem przydzielania numerów porządkowych w urzędach a tym algorytmem. Tutaj istnieje szansa, że dwa procesy otrzymają ten sam numerek. Gwarantowane jest jednak niejednoczesne udostępnienie im zasobu, gdyż kolejność wejścia do sekcji krytycznej regulowana jest także przez numer procesu. Można powiedzieć, że procesy wchodzą do sekcji krytycznej w porządku leksykograficznym par (numerek, i).

Wadą tego algorytmu jest aktywne czekanie (proces oczekuje na udostępnienie zasobu wykonując pętlę sprawdzającą jego dostępność).