Algorytm piekarniany

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj
Algorytm piekarniany
Rodzaj wzajemne wykluczanie
Złożoność
Pamięciowa \Theta(n)

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.

Implementacja[edytuj | edytuj kod]

Pseudokod[edytuj | edytuj kod]

 // 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, zakończą się:
     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 sekcję krytyczną...
     odblokuj(i);
     // Miejsce na sekcję lokalną...
   }
 }

Opis działania[edytuj | edytuj kod]

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ą.

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ść).