//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. [[http://en.wikipedia.org/wiki/Lamport's_bakery_algorithm|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 P<sub>i</sub> i P<sub>j</sub> otrzymają ten sam numer
oraz i < j, to P<sub>i</sub> 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(a<sub>0</sub>, ..., a<sub>n-1</sub>) jest taką liczbą k, że k>a<sub>i</sub> 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.

[[so:sync_implementacja_semaforow|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.

[[so:sync_impl_reg_kryt|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.