algorytm.org

Algorytm Peterson'a dla n procesów

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 Peterson'a dla n procesów
Ocena użytkowników:***** / 7
SłabyŚwietny 
Wpisany przez Tomasz Lubiński, 26 lipca 2005 21:15

Najszybszym sposobem wymieniania danych pomiędzy procesami jest współdzielenie przez nie pewnego obszaru pamięci. W ten sposób dane umieszczone przez nadawcę są natychmiast dostępne dla odbiorcy. Jednak by zapewnić, prawidłowe odczytywanie i zapisywanie współdzielonych danych należy wprowadzić mechanizmy, które ograniczą do nich dostęp tak by w jednym momencie operacje na danych wykonywał wyłącznie jeden proces.
Jest to jeden z przykładów problemu wzajemnego wykluczania, który rozwiązać możemy przy pomocy poniżej podanego algorytmu. Najpierw jednak zapiszmy 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 się 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:
flag[1..n] - która dla każdego procesu przyjmuje n-1 możliwych wartości, informujące na którym z etapów dochodzenia do sekcji krytycznej znajduje się proces, (flag[j]=k, oznacza, że j-ty proces znajduje się na k-tym etapie),
turn[1..n-1] - określa, który z procesów znajduje się na danym etapie, (turn[k]=j, oznacza, że na k-tym etapie znajduje się j-ty proces).
Algorytm Peterson'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
k, l, other, whose: integer;
begin
while true do
 begin
 {część prgramu przed sekcją krytyczną}
 for k:=1 to n-1 do
  begin
   flag[i]:=k;
   turn[k]:=i;
   repeat
    whose:=turn[k];
    if whosei then break;
    for l:=1 to n do
     begin
      if li then other:=flag[l];
      if other>=k then break;
     end;
   until other<k;
  end;
 {sekcja krytyczna}
 flag[i]:=0;
 {pozostała część programu}
 end;
end;
Algorytm ten rozwiązuje problem wzajemnego wykluczania dla n procesów. Wejście do sekcji krytycznej odbywa się tutaj w n-1 etapach (główna pętla for).
Najpierw proces ustawia flagę na wartość etapu, w którym się znajduje (flag[i]:=k), następnie zmiennej określającej, który z procesów znajduje się na danym etapie przypisuje swoją wartość (turn[k]:=i). Dalej sprawdza, jaki proces znajduje się w tym samym etapie (pierwsza instrukcja if), Jeżeli nie jest to on, następuje przejście do kolejnego etapu (instrukcja break, powoduje wykonanie kolejnej iteracji w głównej pętli for). W przeciwnym wypadku pozostaje on w pętli repeat ... until, tak długo jak któryś z procesów znajduje się na dalszym etapie jak on sam - warunek until w połączeniu z zagnieżdżoną pętlą for i instrukcjami if.
Po wyjściu z sekcji krytycznej proces zdejmuje falgę (ustawia wartość zmiennej współdzielonej flag[i], na wartość 0), ustępując tym samym miejsce czekającym procesom.

Implementacje
AutorJęzyk
programowania
KomentarzOtwórzPobierzOcena
Tomasz LubińskiC/C++Linux
.cpp
.cpp
***** / 4
 
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: 15 sierpnia 2012 18:12
Dodaj komentarz