algorytm.org

Algorytm Lamport'a

Baza Wiedzy
wersja offline serwisu przeznaczona na urządzenia z systemem Android
Darowizny
darowiznaWspomóż rozwój serwisu
Nagłówki RSS
Artykuły
Implementacje
Komentarze
Forum
Bookmarki






Sonda
Implementacji w jakim języku programowania poszukujesz?

Algorytm Lamport'a
Ocena użytkowników:***** / 8
SłabyŚwietny 
Wpisany przez Tomasz Lubiński, 26 lipca 2005 20:54

Algorytm ten wykorzystuje się do rozwiązania problemu wzajemnego wykluczania. Z zagadnieniem tym mamy do czynienia na przykład, gdy dwa równolegle wykonywane procesy korzystają ze wspólnej pamięci. Przeprowadźmy symulację działania dwóch równolegle wykonywanych programów, z których jeden zwiększa wartość współdzielonej zmiennej w o 2, a drugi o 3 (wartość początkowa w to 0). Najpierw obydwa procesy pobierają wartość zmiennej w po czym pierwszy zwiększa jej wartość o 2 (0+2=2), a drugi o 3 (0+3=3). Po wykonaniu operacji procesy odsyłają wyniki. Jeżeli proces pierwszy zapisze swój wynik szybciej do zmiennej współdzielonej końcowym wynikiem będzie 3, jeżeli wolniej niż proces drugi w wyniku otrzymamy 2. W przypadku, gdy procesy wykonają obliczenia w sposób, który wykluczy jednoczesny dostęp do zmiennej współdzielonej wynik będzie prawidłowy.

Zapiszmy teraz problem wzajemnego wykluczania w sposób formalny:
Dany jest zbiór procesów sekwencyjnych komunikujących się przez wspólną pamięć. Każdy z procesów zawiera sekcję krytycznę, w której następuje dostęp do wspólnej pamięci. Procesy te są procesami cyklicznymi. Zakłada sie ponadto:
  • zapis i odczyt wspólnych danych jest operacją niepodzielną, a próba jednoczesnych zapisów lub odczytów realizowana jest sekwencyjnie w nieznanej kolejności
  • sekcje krytyczne nie mają priorytetu,
  • względne prędkości wykonywania procesów są nieznane,
  • proces może zostać zawieszony poza sekcją krytyczna,
  • procesy realizujące instrukcje poza sekcją krytyczną nie mogą uniemożliwiać innym procesom wejścia do sekcji krytycznej,
  • procesy powinny uzyskać dostęp do sekcji krytycznej w skończonym czasie.


Założenia dotyczące algorytmu są następujące:
Algorytm pozwala rozwiązać problem wzajemnego wykluczania dla n procesów.
Do komunikacji między równolegle wykonującymi się procesami służą 2 współdzielone zmienne tablicowe:
  num[1..n] - która dla każdego procesu ubiegającego się o wejście do sekcji krytycznej ma nadaną wartość, która określa miejsce procesu w kolejce do sekcji, (np. num[j]=3 oraz num[j-1]=4, oznacza tyle, że proces j-ty ma pierwszeństwo w dostępie do sekcji krytycznej przed procesem j-1),
  choosing[1..n] - wartość 1 dla choosing[j] oznacza, że j-ty proces nadaje sobie kolejny numer w kolejce procesów chcących uzyskać dostęp do sekcji krytycznej. Wartość 0 oznacza, że nie ubiega się w danej chwili o przyznanie numeru w kolejce do sekcji (albo ma już nadany taki numer, albo w ogóle nie chce wejść do sekcji krytycznej).
Algorytm Lamporta'a ma następującą postać (zmienna i przyjmuje wartość będącą numerem procesu, czyli w procesie pierwszym 1, w procesie drugim 2, ...):
procedure process_i;
var //zmienne lokalne procesu
test, k, mine, other, temp: integer;
begin
  while true do
   begin
   {część prgramu przed sekcją krytyczną}
   choosing[i]:=1;
   for k:=1 to n do
    if k<>i then
     begin
     temp:=num[k];
     mine:=max(mine, temp);
     end;
   mine:=mine+1;
   num[i]:=mine;
   choosing[i]:=0;
   for k:=1 to n do
    if k<>i then
     begin
     repeat
      test:=choosing[k];
     until test=0
     repeat
      other:=num[k];
     until other=0 or (mine,i)<(other,k)
     end;
   {sekcja krytyczna}
   num[i]:=0;
   {pozostała część programu}
   end;
end;


Proces, który chce wejść do sekcji krytycznej, na początku musi przyznać sobie numer w kolejce procesów czekających na wejście do tej sekcji. W tym celu ustawia zmienną choosing[i] na wartość 1, ktora informuje inne procesy, że ustala on właśnie swój numer w kolejce. Następnie w pętli for, szuka maksymalnej wartości zmiennej num[], spośród wszystkich pozostałych procesów. Po znalezieniu tej wartości zwiększa ją o jeden i przypisuje sobie numer w kolejce, w zmiennej współdzielonej num[i]. Następnie zdejmuje flagę informując, w ten sposób inne procesy, o tym, że znalazł już swój numer w kolejce procesów czekających na wejście do sekcji krytycznej (choosing[i] na wartość 0).
Teraz w drugiej pętli for kolejno dla wszystkich procesów (z wyjątkiem siebie samego) proces czeka na procesy, które nadają sobie numer w kolejce (pierwsza pętla repeat), oraz na procesy, które znajdują się przed nim (druga pętla repeat). Wyjaśnienia wymaga tutaj druga pętla repeat. Kończy ona swoje wykonywanie w przypadku, gdy proces nie chce wejść do sekcji krytycznej lub w kolejce procesów znajduje się za naszym procesem. Porównanie (mine,i)<(other,k) czytać należy jako prawdziwe gdy: (mine<other bez względu na wartość i oraz k), lub gdy (mine=other oraz i<k). Tą konstrukcję należy użyć, gdyż nie możemy zagwarantować, żę dwa różne procesy nie przyznadzą sobie równych wartości w tablicy num[].
Po wyjściu z sekcji krytycznej proces ustawia wartość zmiennej współdzielonej num[i], na wartość 0, ustępując tym samym miejsce procesom czekającym w kolejce.
Problemem, podczas implementacji algorytmu, może być kwestia przekroczenia zakresu w tablicy num[]. Może stać się tak, gdy do kolejki procesów czekających na wejście do sekcji krytycznej ciągle dołączają nowe, które przyznają sobie kolejne numery w kolejce. By rozwiązać ten problem, można co jakiś czas "wyrzucać" procesy przed algorytm, zerować wartość zmiennej num[] i wpuszczać je ponownie. Można również zastosować odmienne podejście: jeżeli w tablicy num[] są przydzielone już liczby np. od 100 do maksimum zakresu, to należy kolejnemu procesowi przydzielić numer 1 i traktować tą wartość tak jakby była ona największa.

Implementacje
AutorJęzyk
programowania
KomentarzOtwórzPobierzOcena
Tomasz LubińskiC/C++Linux
.cpp
.cpp
***** / 1
 
Dodaj własną implementację tego algorytmu
  • Zaloguj się na stronie
Plik:
Język
programowania:
Komentarz:
  By móc dodać implementacje zaloguj się na stronie

Poprawiony: 11 czerwca 2011 19:10
Komentarze
photo
+2 # łukaszek 2010-10-10 13:44
Dzięki za ten kod - polecam
Odpowiedz | Odpowiedz z cytatem | Cytować
Dodaj komentarz