Algorytm piekarniany

Z Wikipedii

Algorytm piekarniany 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 operuje na dwóch tablicach n-elementowych

int numerek[N];
 bool pobiera_numerek[N];

Implementacja algorytmu

void task_i(int i)
{
  const int id = i;
  while(1)
  {
   // sekcja lokalna
   pobiera_numerek[id] = true;
   numerek[i] = max(numerek) + 1;
   pobiera_numerek[id] = false; 
   for(k = 0; (k < N) && (k != id); k++)
   {
    if(numerek[k] == 0 ||
     numerek[id] == numerek[k] ||
     numerek[id] == numerek[k] && id < k)
       break;
   }
   // sekcja krytyczna
   numerek[id] = 0;
  }
 }

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

Istnieje jednak zasadnicza różnica między systemem przydzielania numerów porządkowych w urzędach a tym algorytmem. W algorytmie tym 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 seksji 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ść).