so:sync [mgr Wiki]

[[so:sync]]
mgr Wiki

Pytanie: “Porównaj mechanizmy synchronizacji procesów: synchronizację programową, semafory, mechanizmy strukturalne”

# Synchronizacja procesów

Proces współpracujący może wpływać na inne procesy w systemie lub podlegać ich oddziaływaniom. Procesy współpracujące mogą bezpośrednio dzielić logiczną przestrzeń adresową (tzn. zarówno kod, jak i dane) albo zezwala się im na dzielenie danych tylko za pośrednictwem plików. Pierwszą możliwość osiąga się za pomocą procesów lekkich czyli wątków. Współbieżny dostęp do danych dzielonych może powodować ich niespójność. Mechanizmy zapewniające synchronizację procesów:

Problem sekcji krytycznej polega na skonstruowaniu protokołu który mógłby posłużyć do organizowania współpracy procesów. Każdy proces musi prosić o pozwolenie na wejście do swojej sekcji krytycznej. Fragment kodu realizującego taką prośbę nazywa się sekcją wejściową (ang. entry section). Po sekcji krytycznej może występować sekcja wyjściowa (ang. exit section). Pozostały kod nazywa się resztą (ang. remainder section).

Rozwiązanie problemu sekcji krytycznej musi spełniać następujące trzy warunki:

- Wzajemne wykluczanie: Jeśli proces P, działa w swojej sekcji krytycznej, to żaden inny proces nie działa w sekcji krytycznej.
- Postęp: Jeśli żaden proces nie działa w sekcji krytycznej oraz istnieją procesy, które chcą wejść do sekcji krytycznych, to tylko procesy nie wykonujące swoich reszt mogą kandydować jako następne do wejścia do sekcji krytycznych i wybór ten nie może być odwlekany w nieskończoność.
- Ograniczone czekanie: Musi istnieć wartość graniczna liczby innych procesów do ich sekcji krytycznych po tym, gdy dany proces zgłosił chęć wejścia do swojej sekcji krytycznej i zanim uzyskał na to pozwolenie.

Zakładamy, że każdy proces jest wykonywany z szybkością niezerową Natomiast nie musimy niczego zakładać o względnej szybkości każdego z procesów.

    repeat
      sekcja wejściowa
      sekcja krytyczna
      sekcja wyjściowa
      reszta
    until false;

### Rozwiązania programowe

#### Algorytm dla dwóch procesów

Procesy mają dwie wspólne zmienne:

    var znacznik: array [0..1] of boolean;
           numer: 0..1;

Na początku znacznik[0] = znacznik[1] = false, a wartość zmiennej numer jest nieistotna (ale wynosi 0 lub 1).

    repeat
      znacznik[i] := true;
      numer:=j;
      while (znacznik(j) and numer =j) do nic;

      sekcja krytyczna

      znacznik[i] :=false;
      reszta
    until false;

#### Rozwiązania wieloprocesowe

Jest to tzw. algorytm piekarni (ang. bakery algorithm) wzorowany na algorytmie planowania praktykowanym w piekarniach, lodziarniach, sklepach mięsnych, urzędach rejestracji samochodów i innych miejscach, w których chaos wymaga uporządkowania. Algorytm ten opracowano dla środowisk rozproszonych, lecz w tym miejscu skoncentrujemy się tylko na tych jego aspektach, które dotyczą środowiska scentralizowanego. Przy wejściu do sklepu każdy klient dostaje numerek. Obsługę rozpoczyna się od klienta z najmniejszym numerem. Niestety, algorytm piekarni nie gwarantuje, że dwa procesy (klienci) nie dostaną tego samego numeru. W przypadku takiej kolizji jako pierwszy zostanie obsłużony proces o wcześniejszej nazwie. Tak więc, jeśli Pi i Pj otrzymają ten sam numer oraz i < j, to Pi będzie obsłużony najpierw. Ponieważ nazwy procesów są jednoznaczne i całkowicie uporządkowane, algorytm jest w pełni deterministyczny.

W algorytmie są używane następujące wspólne struktury danych:

     var wybrane: array [0..n - 1] of boolean;
           numer: array [0..n - 1] of integer;

Na początku elementy tych struktur danych przyjmują odpowiednio wartości false i 0.

Zdefiniujemy, dla wygody, następującą notację:

- (a, b) < (c, d), jeśli a < c lub jeśli a = c i b<d;
- max(a0, ..., an-1) jest taką liczbą k, że k>ai dla i = 0,...,n- 1

    // i - numer procesu
    repeat
      wybrane[i] := true;
      numer[i] := max(numer[0], numer[1],..., numer[n - 1]) + 1;
      wybrane[i]=false;

      for j:=0 to n - 1
      do begin
        // czekaj aż j-ty proces dostanie numerek
        while wybrane[j] do nic;

        // czekaj aż procesy z niższymi numerkami lub z wcześniejszą nazwą skończą swoje działanie
        while numer[j] <> 0 and (numer[j],j) < (numer[i], i) do nic;
      end;

      sekcja krytyczna

      numer[i] := 0;
      reszta
    until false;

### Semafory

Rozwiązania problemu sekcji krytycznej zaprezentowane wcześniej nie są łatwe do uogólnienia w bardziej złożonych zagadnieniach. Do omijania tej trudności służy narzędzie synchronizacji nazwane semaforem (ang. semaphore). Semafor S jest zmienną całkowitą, która - oprócz nadania wartości początkowej -jest dostępna tylko za pomocą dwu standardowych, niepodzielnych operacji: czekaj (ang. wait) i sygnalizuj (ang. signal). Klasyczne definicje operacji czekaj i sygnalizuj są następujące:

       czekaj (S): while S < O do nic;
                         S:=S-1;
          sygnalizuj(S): S:= S + 1;

Zmiany wartości całkowitych semafora muszą być wykonywane za po mocą operacji czekaj i sygnalizuj w sposób niepodzielny. Oznacza to, że gdy jeden proces modyfikuje wartość semafora, wówczas żaden inny proces nie może jednocześnie wartości tej zmieniać. Ponadto w przypadku operacji czekaj(S) nie może wystąpić przerwanie podczas sprawdzania wartości zmiennej całkowitej S (S < 0) i jej ewentualnego zmieniania (S := S - 1).

#### Sposób użycia

Semafory znajdują zastosowanie w rozwiązywaniu problemu sekcji krytycznej z udziałem n procesów. Wspólny semafor mutex (ang. mutual exclusion -wzajemne wykluczanie) jest dzielony przez n procesów. Na początku mutex ma wartość 1. Każdy proces P, jest zorganizowany tak jak na rys. \ref{rys_6_11}.

     repeat
       czekaj(mutex)

       sekcja krytyczna

       sygnalizuj(mutex);
       reszta
     until false;

Semaforów możemy również używać do rozwiązywania różnych problemów synchronizacji. Rozważmy na przykład dwa współbieżnie wykonywane procesy: P1 z instrukcjami i S1 i P2 instrukcją S2. Załóżmy, że chcemy, aby instrukcja S2 została wykonana dopiero wtedy, gdy zakończy się wykonanie instrukcji S1. Schemat ten można czytelnie zrealizować, pozwalając procesom P1 i P2 na dzielenie wspólnej zmiennej synch, z początkową wartością 0, i dołączając do procesu P1 instrukcje sygnalizuj(synch) oraz instrukcje czekaj(synch) do procesu P2. Ponieważ początkowa wartość zmiennej synch wynosi 0, więc proces P2 wykona instrukcję S2 dopiero po wywołaniu przez proces P1 instrukcji sygnalizuj(synch), umieszczonej po instrukcji S1.

Sposób implementacji semaforów ...

### Konstrukcje strukturalne

Pomimo że semafory stanowią wygodny i efektywny mechanizm synchronizowania procesów, niewłaściwe ich użycie może powodować błędy koordynacji czasowej, trudne do wykrycia z tego powodu, że zależą od pewnych szczególnych - nie zawsze występujących - ciągów wykonywanych instrukcji. Do radzenia sobie z prostymi błędami programistycznymi (zmiana kolejności instrukcji wait/signal, pominięcie wait/signal, nadmiarowe wait/signal) zaproponowano wiele konstrukcji językowych.

Przedstawiając obie konstrukcje założymy, że proces składa się z zestawu danych lokalnych i sekwencyjnego programu, który na nich operuje. Do danych lokalnych można mieć dostęp tylko za pomocą programu sekwencyjnego należącego do tego procesu, do którego należą one same. Żaden proces nie może więc bezpośrednio sięgać po dane lokalne innego procesu. Niemniej jednak procesy mogą dzielić dane globalne.

#### Region krytyczny

W konstrukcji regionu krytycznego, służącej do organizowania synchronizacji w języku wysokiego poziomu, wymaga się, aby zmienną v typu T, która będzie używana wspólnie przez wiele procesów, deklarowano, jak niżej:

    var v: shared T

Zmienna v będzie dostępna tylko w obrębie instrukcji region o następującej postaci:

        region v when B do S;

Konstrukcja ta oznacza, że podczas wykonywania instrukcji S żaden inny proces nie ma dostępu do zmiennej v. Dostęp do regionu krytycznego zależy od wyrażenia boolowskiego B. Gdy proces próbuje wejść w obszar sekcji krytycznej, wówczas oblicza się wyrażenie boolowskie B. Jeśli wyrażenie jest prawdziwe, to instrukcja S będzie wykonana. Jeśli jest fałszywe, to proces nie ubiega się o wyłączny dostęp i ulega opóźnianiu do czasu, aż wyrażenie B stanie się prawdziwe oraz żaden inny proces nie będzie przebywał w regionie związanym ze zmienną v. Jeśli więc dwie instrukcje:

    region v when true do Sl;
    region v when true do S2;

są wykonywane współbieżnie w różnych procesach sekwencyjnych, to wynik będzie równoważny sekwencyjnemu wykonaniu “S1 przed S2” lub “S2 przed S1”.

Konstrukcja regionu krytycznego strzeże przed pewnymi prostymi błędami związanymi z rozwiązywaniem problemu sekcji krytycznej za pomocą semaforów, które mogą być popełniane przez programistę. Wypada dodać, że nie wyklucza ona z całą pewnością wszystkich błędów synchronizacji, niemniej jednak zmniejsza ich liczbę. Jeśli wystąpi błąd logiczny w programie, to odtworzenie konkretnego ciągu zdarzeń może nie być łatwe.

Sposób implementacji regionu krytycznego ...

#### Monitory

Jeśli ktoś dysponuje bardziej “zjadliwym” materiałem na temat monitorów, to zapraszam do podzielenia się.

Innego rodzaju konstrukcją stosowaną w językach wysokiego poziomu do synchronizacji jest typ monitor. Charakterystyczną cechą monitora jest zbiór operacji zdefiniowanych przez programistę. Reprezentacja typu monitor zawiera deklaracje zmiennych, których wartości określają stan obiektu tego typu, oraz treści procedur lub funkcji realizujących działania na tym obiekcie. Składnia monitora przybiera postać

    type nazwa-monitora = monitor
      deklaracje zmiennych

      procedure entry Pl (...); begin ... end;

      procedure entry P2 (...); begin ... end;

      procedure entry Pn (...); begin ... end;

      begin
        kod inicjujący
      end.

Reprezentacji typu monitor nie mogą używać bezpośrednio dowolne procesy. Procedura zdefiniowana wewnątrz monitora może korzystać tylko ze zmiennych zadeklarowanych w nim lokalnie i ze swoich parametrów formalnych. I podobnie, zmienne lokalne w monitorze są dostępne tylko za pośrednictwem tych lokalnych procedur.

Konstrukcja monitora gwarantuje, że w jego wnętrzu w danym czasie może być aktywny tylko jeden proces. W związku z tym programista nie musi kodować barier synchronizacyjnych w sposób jawny. Jednakże konstrukcja monitora w postaci zdefiniowanej do tej pory nie jest wystarczająco ogólna do modelowania pewnych schematów synchronizacji. Aby tak się stało, potrzebujemy dodatkowego mechanizmu - jest nim konstrukcja pod nazwą warunek (ang. condition). Jeśli programista chce zapisać przykrojony na miarę własnych potrzeb schemat synchronizacji, to może zdefiniować jedną lub kilka zmiennych typu condition:

    var x, y. condition;

Jedynymi operacjami, które mogą dotyczyć zmiennej typu condition, są czekaj i sygnalizuj. Operacja

    x.czekaj

oznacza, że proces ją wywołujący zostaje zawieszony do czasu, aż inny proces wywoła operację

    x.sygnalizuj;

Operacja x.sygnalizuj wznawia dokładnie jeden z zawieszonych procesów. Jeśli żaden proces nie jest zawieszony, to operacja sygnalizuj nie ma żadnych skutków, tzn. stan zmiennej x jest taki, jak gdyby operacji tej nie wykonano wcale. Warto porównać to z operacją sygnalizuj dotyczącą semaforów, która zawsze oddziałuje na stan semafora.

Załóżmy teraz, że w chwili, w której proces P wywołuje operację x.sygnalizuj, istnieje zawieszony proces Q, związany z warunkiem x. W tej sytuacji, jeśli zawieszonemu procesowi Q udzieli się zezwolenia na wznowienie działania, to sygnalizujący to proces P będzie musiał poczekać. W przeciwnym razie zarówno P, jak i Q stałyby się jednocześnie aktywne wewnątrz monitora. Zauważmy jednak, że teoretycznie każdy z dwu procesów mógłby kontynuować działanie. Istnieją dwie możliwości:

- P zaczeka, aż Q opuści monitor, albo zaczeka na inny warunek.
- Q zaczeka, aż P opuści monitor, albo zaczeka na inny warunek.

Można znaleźć argumenty przemawiające zarówno za przypadkiem l, jak i 2. Ponieważ proces P działa już w obrębie monitora, wybór przypadku 2 wydaje się rozsądniejszy. Jeśli jednakże pozwolimy procesowi P kontynuować pracę, to warunek “logiczny”, w oczekiwaniu na który Q pozostawał wstrzymany, może nie być już spełniony wtedy, gdy Q zostanie wznowiony. Za wybraniem przypadku l opowiedział się Hoare, głównie z tego powodu, że przypadek ten można przełożyć na prostsze i bardziej eleganckie reguły przy dowodzeniu. W języku Concurrent Pascal przyjęto rozwiązanie kompromisowe. Gdy proces P wykonuje operację sygnalizuj, wówczas opuszcza monitor natychmiast, dzięki czemu proces Q jest niezwłocznie wznawiany. Taki schemat jest mniej uniwersalny niż zaproponowany przez Hoare’a, ponieważ proces nie może zasygnalizować więcej niż jeden raz podczas jednego wywołania procedury.

so/sync.txt · Last modified: 2006/05/22 23:50 by 213.134.172.237