SYSTEMY OPERACYJNE

Wykład 6

Synchronizowanie procesów

• Podstawy
• Problem sekcji krytycznej
• Sprzętowe środki synchronizacji
• Semafory
• Klasyczne problemy synchronizacji
• Regiony Krytyczne
• Monitory
• Transakcje niepodzielne

• Podstawy
  • współbieżny dostęp procesów współpracujących do danych dzielonych (np. bezpośrednie dzielenie przestrzeni adresowej przez procesy lekkie czyli wątki) może powodować ich niespójność.
  • podtrzymywanie spójności danych wymaga istnienia mechanizmów zapewniających właściwą kolejność wykonywania kodów programów współpracujących
  • rozwiązanie problemu ograniczonego buforowania z użyciem wspólnej pamięci pozwala na pomieszczenie w buforze co najwyżej n-1 jednostek w tym samym czasie; usunięcie tej wady (modyfikacja kody producenta - konsumenta) nie jest łatwa
    • procedury kody producenta - konsumenta (rozdz. 4) pozwalały na pomieszczenie w buforze w tym samym czasie co najwyżej n-1 jednostek
    • załóżmy, że modyfikujemy ten kod przez dodanie zmiennej całkowitej licznik, z zawartością początkową 0, zwiększaną / zmniejszaną przy każdym dołączaniu / usuwaniu do bufora nowej jednostki
  • proces producenta
    

    repeat
    	...
    	produkuj jednostkę w nastp
    	...
    	while licznik = n do nic;
    	bufor[we] := nastp;
    	we := we + 1 mod n;
    	licznik := licznik + 1;
    until false;
            

• proces producenta
  

  repeat
  	while licznik = 0 do nic;
  	nastk := bufor[wy];
  	wy := wy + 1 mod n;
  	licznik := licznik - 1;
     	...
  	konsumowanie jednostki z nastk
  	...
  until false;
  
        
  

• obie procedury są poprawne, jeśli są rozpatrywane z osobna; mogą nie działać, gdy będą wykonywane współbieżnie:
  • załóżmy, że bieżąca wartość zmiennej licznik=5, oraz że producent i konsument wykonują współbieżnie instrukcje 

    licznik:=licznik+1   i   licznik:=licznik-1

  • zauważmy, że instrukcje te mogą być przetłumaczone na język maszynowy jako następujące ciągi instrukcji:

    rejestr1 := licznik;	rejestr2 := licznik;
    rejestr1 := rejestr1 + 1;	rejestr2 := rejestr2 - 1;
    licznik := rejestr1;	licznik := rejestr2;

  •  współbieżne wykonywanie tych instrukcji jest równoważne wykonaniu sekwencyjnemu, w którym rozkazy maszynowe mogą się przeplatać, np.:

    T0	producent	wykonaj	rejestr1 := licznik	{rejestr1 = 5}
    T1	producent	wykonaj	rejestr1 := rejestr1 + 1	{rejestr1 = 6}
    T2	konsument	wykonaj	rejestr2 := licznik	{rejestr2 = 5}
    T3	konsument	wykonaj	rejestr2 := rejestr2 - 1	{rejestr2 = 4}
    T4	producent	wykonaj	licznik := rejestr1	{licznik = 6}
    T5	konsument	wykonaj	licznik := rejestr2	{licznik = 4}

• otrzymujemy niepoprawny stan licznik = 4

• przyczyna: oba procesy manipulują zmienną współbieżnie

• konieczna jest jakaś forma synchronizacji obu procesów

• Problem sekcji krytycznej

  • n procesów współzawodniczy w dostępie do wspólnych danych

  • każdy proces ma segment kodu zwany sekcją krytyczną, w którym może zmieniać wspólne dane

  • PROBLEM: skonstruować protokół taki, że gdy jeden proces wykonuje sekcję krytyczną, wówczas żaden inny nie jest dopuszczony do wykonywania swojej sekcji krytycznej

  • struktura procesu P_i :

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

Ogólna struktura typowego procesu P_i .

• rozwiązanie problemu sekcji krytycznej musi spełnić trzy warunki:

  1. Wzajemne wykluczanie: Jeśli proces P_i działa w swojej sekcji krytycznej, to żaden inny proces nie działa w sekcji krytycznej.

  2. 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 odwlekany w nieskończoność.

  3. Ograniczone czekanie: Musi istnieć wartość graniczna liczby wejść 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ą

  • nie zakładamy niczego o względnej szybkości każdego z n procesów

• rozwiązanie dla dwu procesów:

  • tylko dwa procesy P₀ i P₁

  • dla wygody założymy, że j=1-i

   

  #1: Algorytm 1

  • pozwolimy procesom dzielić wspólną zmienną numer

    • var numer: (0..1)

    początkowo numer=0

    • numer=i => P_i może wejść do swojej sekcji krytycznej

  • struktura procesu P_i w algorytmie

    repeat
    	while numer <> i do nic;
    	    sekcja krytyczna
    	numer := j;
       	reszta
    until false;
    
    

Struktura procesu P_i w algorytmie 1

• algorytm spełnia warunki wzajemnego wykluczania, jednak nie spełnia warunków postępu (narzuca naprzemienne wykonywanie przez procesu sekcji krytycznej)

---

• #1: Algorytm 2

  • wadą algorytmu 1 jest, że pamięta tylko, któremu procesowi wolno wejść do sekcji krytycznej

  • dzielone zmienne

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

      początkowo znacznik[0]=znacznik[1]=false

    • znacznik[i]=true => P_i jest gotowy, aby wejść do swojej sekcji krytycznej

  • proces P_i  

    repeat
    	znacznik[i] := true;
    	while znacznik[j] do nic;
                sekcja krytyczna
    	znacznik[i] := false;
       	reszta
    until false;
    
    

Struktura procesu P_i w algorytmie 2

• rozwiązanie spełnia warunek wzajemnego wykluczania, ale nie spełnia warunku postępu

• aby to zilustrować rozważmy następujący ciąg wykonań:

T0:	P0 ustala znacznik[0] = true
T1:	P1 ustala znacznik[1] = true

po których procesy P₀ i P₁ zapętlają się na zawsze w swoich instrukcjach while

• algorytm ten jest bardzo uzależniony od dokładnych następstw czasowych obu procesów
• przedstawiona sekwencja może się zdarzyć w środowisku kilku procesów działających współbieżnie lub jeśli jakieś przerwanie (np. od czasomierza) wystąpi bezpośrednio po wykonaniu kroku T₀ i procesor zostanie przełączony z jednego procesu do drugiego

---

#3 Algorytm 3

• łączy ze sobą zmienne dzielone zawarte w algorytmie 1 i 2

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

  • numer: 0..1

    początkowo znacznik[0]=znacznik[1]=false

    a wartość zmiennej numer jest nieistotna

• proces P_i  

  repeat
  	znacznik[i] := true;
  	numer := j;
          while (znacznik[j]and numer=j) do nic;
              sekcja krytyczna
  	znacznik[i] := false;
     	reszta
  until false;
  
  

Struktura procesu P_i w algorytmie 3

• to rozwiązanie spełnia wszystkie trzy wymagania rozwiązania problemu sekcji krytycznej dla dwu procesów

• Sprzętowe środki synchronizacji

• Rozwiązanie wieloprocesorowe

  • problem sekcji krytycznej dla n procesów

  • rozwiązanie tzw. algorytm piekarni

    • przed wejściem do swojej sekcji krytycznej, proces otrzymuje numerek; obsługa rozpoczyna się od procesu posiadacza najmniejszego numerka

    • przed wejściem do swojej sekcji krytycznej, proces otrzymuje numerek; obsługa rozpoczyna się od procesu posiadacza najmniejszego numerka

    • jeżeli procesy Pi oraz Pj otrzymują ten sam numer, to jeżeli i<j to Pi będzie obsłużony najpierw (tzn. proces o wcześniejszej nazwie);

    • schemat generujący numery tworzy je w rosnącym porządku: 1,2,3,3,3,4;

  • używana notacja:

    • (a,b) < (c,d) jeżeli a < c, lub jeżeli a = c i b < d;

    • max (a0, ..., an-1) jest taką liczbą k, że k >= ai dla i=0, ..., n-1; gdzie leksykograficzny porządek (bilet #, identyfikator procesu #)
  • w algorytmie używane są następujące 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

• struktura procesu Pi w algorytmie piekarni

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            while wybrane[j] do nic;            while numer[j]<>0                and (numer[j],i) < (numer[i],i) do nic;     end;

sekcja krytyczna

numer[i]:=0;

reszta

until false;

•  aby udowodnić, że algorytm piekarni jest poprawny, trzeba najpierw pokazać, że jeżeli proces Pi znajduje się w swojej sekcji krytycznej, a proces Pk (k<>i) ma już wybrany swój numer[k]<>0 to (numer[i],i)<(numer[k],k);
• jeśli tak jest, to załóżmy, że proces Pi jest w sekcji krytycznej, a Pk próbuje wejść do swojej sekcji krytycznej, gdy Pk przejdzie do wykonania drugiej instrukcji while przy j=i, wówczas sprawdzi, że:
  • numer[i]<>0 oraz
  • (numer[i],i)<(numer[k],k)

  będzie zatem dopóty wykonywać tę pętlę, dopóki Pi nie wyjdzie ze swojej sekcji krytycznej;

 

• Sprzętowe środki synchronizacji
  • właściwości sprzętu mogą pomóc w rozwiązaniu problemu sekcji krytycznej;
  • w środowisku jednoprocesorowym problem sekcji krytycznej daje się łatwo rozwiązać jeżeli można zakazać występowania przerwań podczas modyfikowania zmiennej dzielonej;
  • to rozwiązanie jest nieprzydatne w środowisku wieloprocesorowym: wymaga przekazywania komunikatów do wszystkich procesorów i opóźnia wejście do sekcji krytycznej
  • specjalne rozkazy sprzętowe typu Testuj-i-Ustal pozwalające w sposób niepodzielny sprawdzić i zmienić zawartość słowa

         function Testuj-i-Ustal(var cel:boolean):boolean;
                  begin
                      Testuj-i-Ustal:=cel;
                       cel:=true;
                 end;

• ważną cechą tego rozkazu jest jest jego niepodzielne wykonanie, którego nie można przerwać;
• jeśli zatem dwa takie rozkazy są wykonywane jednocześnie (każdy na innym procesorze), to będą wykonywane sekwencyjnie w dowolnym porządku;

• wzajemne wykluczanie z Testuj-i-Ustal
  • zmienna dzielona var zamek:boolean początkowo false;
  • proces Pi

repeat

while Testuj-i-Ustal(zamek) do nic;

 sekcja krytyczna

zamek:=false;

reszta

until false

• Semafory

• semafor S - zmienna całkowita

• jest dostępna tylko za pomocą dwu standardowych niepodzielnych operacji: czekaj i  sygnalizuj:

               czekaj(S):          while S<= 0 do nic;
                                        S:=S-1;

               sygnalizuj(S): S:=S+1;

• niepodzielność operacji oznacza, że:

  • gdy jeden proces modyfikuje wartość semafora wówczas inny proces nie może jednocześnie tej wartości zmieniać

  • ponadto w przypadku operacji czekaj(S) nie może nastąpić przerwanie podczas sprawdzania wartości zmiennej całkowitej S (S<=0) i jej ewentualne zmienianie (S:=S-1)

• Sposób użycia semaforów

1. do rozwiązania problemu sekcji krytycznej z udziałem n procesów

• dzielone zmienne: wspólny semafor mutex (ang. mutal exclusion - wzajemne wykluczanie) - var mutex: semaphore (początkowo mutex=1)
• proces Pi

repeat

czekaj(mutex);

 sekcja krytyczna

sygnalizuj(mutex);

reszta

until false

2. do rozwiązywania różnych problemów synchronizacji, np. dwa procesy współbieżne P1 z instrukcją S1 i P2 z instrukcją S2 chcemy, aby S2 została wykonana dopiero gdy zakończy się wykonanie 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, dołączając do procesu P1 instrucje
  S1; sygnalizuj(synch);
  oraz instrukcje
  czekaj(synch); S2;
  do procesu P2. Ponieważ początkowa wartość zmiennej synch wynosi 0, więc proces P1 instrukcji sygnalizuj(synch), umieszczonej po instrukcji S1

• Implementacja

• problem poprzednich rozwiązań: konieczność aktywnego czekania (wykonywanie instrukcji pętli w sekcji wejściowej) przez procesy usiłujące wejść do sekcji krytycznej
• aby ominąć tą konieczność można zmodyfikować semaforowe operacje czekaj i sygnalizuj
  • semafor jako rekord:
    
    type semaphore=record
                                   wartość:integer;
                                    L:list of proces;
                               end;
  • dwie dodatkowe operacje (f. systemowe)
    
    blokuj: zawiesza proces, który go wywołuje;
    obudź(P): wznawia działanie zablokowanego procesu
    
• operacje semaforowe można zdefiniować teraz tak:
  
  czekaj(S):      S.wartość:=S.wartość-1;
                        if S.wartość<0
                              then begin
                                           dołącz dany proces do S.L;
                                            blokuj;
                                      end;
  
  sygnalizuj(S): S.wartość:=S.wartość-1;
                        if S.wartość<0
                              then begin
                                           usuń jakiś proces P z S.L;
                                            obudź(P);
                                       end;
  
• decydujący aspekt poprawnego działania: niepodzielność wykonania operacji czekaj i sygnalizuj na tym samym semaforze w tym samym czasie
  • w środowisku jednoprocesorowym można zabronić wykonywania przerwań podczas wykonywania tych samych operacj

• Zakleszczenia i głodzenie

• zakleszczenie - dwa lub więcej procesów czeka w nieskończoność na zdarzenie, które może być spowodowane tylko przez jeden z czekających procesów
• załóżmy, że mamy dwa procesy P0 i P1, z których każdy ma dosyęp do dwu semaforów S i Q ustawionych na 1:
  
           P0                                          P1
      czekaj(S);                                 czakaj(Q);
      czekaj(Q);                                 czekaj(S);
           .                                                .
           .                                                .
      sygnalizuj(S);                             sygnalizuj(Q);
      sygnalizuj(Q);                            sygnalizuj(S);
  
• blokowanie nieskończone czyli głodzenie: procesy czekają w nieskończoność pod semaforem (np. jeśli przy dodawaniu i usuwaniu procesów z listy związanej z semaforem użyto porządku LIFO)

• Semafory binarne

• poprzednio opisana konstrukcja semafora to tzw. semafor zliczający - jego wartości całkowite mogą przebiegać dowolny przedział;
• semafor binarny - wartość całkowita to tylko 0 i 1; łatwiejsza implementacja
• implementacja semafora zliczającego S przy użyciu semaforów binarnych
  • struktury danych:
    
          var S1:semafor-binarny;
                 S2:semafor-binarny;
                 C: integer;
    
  • inicjalizacja
    S1 = 1, S2 = 0 , C = początkowa wartość semafora S
• operacja czekaj
  
         czekaj(S1);
         C:=C-1;
         if C < 0
               then begin
                            sygnalizuj(S1);
                            czekaj(S2);
                       end
            sygnalizuj(S1);
  
• operacja sygnalizuj
  
           czekaj(S1);
           C:= C + 1;
           if C <= 0
               then sygnalizuj(S2);
               else sygnalizuj(S1);

• Klasyczne problemy synchronizacji

• Problem ograniczonego buforowania
  • operujemy na puli n buforów
  • semafor mutex umożliwia wzajemne wykluczanie dostępu do puli buforów i ma wartość początkową 1;
  • semafory pusty i pełny zawierają odpowiednio liczbę pustych i pełnych buforów z wartościami początkowymi n i 0 odpowiednio
    • proces producenta
      
          repeat
                ...
              produkowanie jednostki w nastp
                ...
             czekaj(pusty);
             czekaj(mutex);
               ...
             dodanie jednostki nastp do bufora bufor
              ...
            sygnalizuj(mutex);
            sygnalizuj(pełny);
         until false;
      
    • proces konsumenta
      
         repeat
                czekaj(pełny);
                czekaj(mutex);
                     ...
                wyjmowanie jednostki z bufora bufor do nastk    
                    ...
               sygnalizuj(mutex);
               sygnalizuj(pełny);
                   ...
              konsumowanie jednostki z nastk
         until false;
              
• Problem czytelników i pisarzy
  • pierwszy problem czytelników i pisarzy: żaden nie powinien czekać, chyba że właśnie pisarz otrzymał pozwolenie na używanie obiektu dzielonego
  • zmienna dzielona
    
       var mutex, pis: semaphore;
              liczba-czyt: integer;
    
  • proces pisarza
    
       czekaj(pis);
            ...
         tu następuje pisanie
           ...
      sygnalizuj(pis);
    
  • proces czytelnika
    
        czytaj(mutex);
            liczba-czyt:=liczba-czyt - 1;
            if liczba-czyt = 1 thenczekaj(pis);
       sygnalizuj(mutex);
           ...
          tu następuje czytanie
          ...
      czekaj(mutex);
         liczba-czyt:=liczba-czyt - 1;
         if liczba-czyt = 0 then sygnalizuj(pis);
      sygnalizuj(mutex);
    
  • zauważmy, że jeśli na pisarza przebywającego w sekcji krytycznej oczekuje n czytelników, to jeden czytelnik stoi w kolejce do semafora pis oraz n-1 czytelników ustawia się w kolejce do semafora mutex. Gdy pisarz wykona operację, sygnalizuj(pis), to można wznowić działanie czekających czytelników lub pojedynczego pisarza
• Problem obiadujących filozofów

  

  • zmienne dzielone
    • każda pałeczka jest semaforem
         var pałeczka: array[0..4] of semaphore;
    • początkowo wszystkie elementy tablicy = 1
  • struktura i-tego filozofa
    
         repeat
              czekaj(pałeczka[i]);
              czekaj(pałeczka[i +1 mod 5]);
                   ...
                 jedzenie
                  ...
             sygnalizuj(pałeczka[i]);
             sygnalizuj(pałeczka[i + 1 mod 5]);
                 ...
               myślenie
                ...
          until false;
    
    • możliwość powstania zakleszczenia: np. wszyscy filozofowie podnieśli jednocześnie pałeczkę ze swojej lewej strony

• Regiony krytyczne

   

  • niewłaściwe użycie semaforów może prowadzić do rozmaitych błędów
  • zaproponowano konstrukcje synchronizujące wysokiego poziomu; jedną z nich jest rejon krytyczny (critical region)
  • zmienna dzielona v typu T

  var v: sharred T

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

  region v when B do S;

  • gdzie B jest wyrażeniem boolowskim

  • 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
    - jeśli B jest fałszywe, to proces nie ubiega się o wyłączny dostęp i ulega opóźnieniu do czasu aż B stanie się prawdziwe oraz żaden inny proces nie będzie przebywał w regionie związanym ze zmienna v

     

• Przykład: schemat ograniczonego buforowania

  • obszar bufora i jego wskaźniki (zmienne dzielone)

var bufor: shared record
           pula: array[0..n-1] of jednostka;
           licznik, we, wy: integer;
           end;

• proces produkujący umieszcza nazwę jednostki nast w buforze dzielonym

region bufor when licznik < n
   do begin
         pula[we]:=nastp;
         we:=we+1 mod n;
         licznik:=licznik + 1;
      end;

• proces konsumujący usuwa jednostkę z bufora dzielonego i zapamiętuje ją w nastk za pomocą instrukcji:

region bufor when licznik > 0
    do begin
          nastk:=pula[wy];
          wy:=wy+1 mod n;
          licznik:=licznik-1;
       end;

• Implementacja warunkowego regionu krytycznego
  • z każdą zmienną dzieloną kojarzy się następujące zmienne:

var mutex, pierwsza-zwłoka, druga-zwłoka: semaphore;
    pierwszt-licznik, drugi-licznik: integer;

- początkowo mutex=1, pozostałe semafory mają wartość 0

Za wyłączność dostępu do sekcji krytycznej odpowiada zmienna mutex. Jeśli proces nie może wejść do sekcji krytycznej z powodu fałszywości warunku boolowskiego B, to najpierw czeka pod semaforem pierwsza-zwłoka. Proces czekający pod semaforem pierwsza-zwłoka jest w końcu przenoszony do semafora druga-zwłoka, co poprzedza udzielenie mu zezwolenia na ponowne obliczenie boolowskiego B. Za pomocą zmiennych pierwszy-licznik i drugi-licznik pamięta się odpowiednio ile procesów oczekuje pod semaforami pierwsza-zwłoka i druga-zwłoka.

Jeśli jakiś proces opuszcza sekcję krytyczną, to może zmienić wartość jakiegoś warunku boolowskiego B, wzbraniającego innemu procesowi wejścia do sekcji krytycznej. Biorąc to pod uwagę, należy przejrzeć kolejkę procesów czekających pod semaforami pierwsza-zwłoka i dryga-zwłoka (w tej kolejności) i pozwolić, by każdy proces przetestował wyrażenie boolowskie. Proces testujący to wyrażenie może odkryć, że jego obecna wartość jest równa true. Wówczas proces wchodzi do sekcji krytycznej. W przeciwnym razie proces musi nadal czekać pod semaforami pierwsza-zwłoka i druga-zwłoka, jak opisaliśmy poprzednio.

• jeśli jakiś proces opuszcza sekcję krytyczną, to może zmienić wartość jakiegoś warunku boolowskiego B, wzbraniającego innemu procesowi wejście do sekcji

• należy więc przejrzeć kolejkę procesów czekających pod semaforami pierwsza-zwłoka i dryga-zwłoka i pozwolić, aby każdy proces przetestował wyrażenie boolowskie

• proces testujący może odkryć, że jego obecna wartość jest równa true, wówczas proces wchodzi do sekcji krytycznej

• w przeciwnym razie proces musi nadal czekać pod semaforem

• mając więc daną zmienną x, instrukcję:

region x when B do S;

czekaj(mutex);
while not B
  do begin
     pierwszy-licznik:=pierwszy-licznik + 1;
     if drugi-licznik > 0
       then sygnalizuj(druga-zwłoka)
       else sygnalizuj(mutex);
     czekaj (pierwsza-zwłoka);
     pierwszy-licznik:=pierwszy-licznik - 1;
     drugi-licznik:=drugi-licznik + 1;
     if pierwszy-licznik > 0
       then sygnalizuj(pierwsza-zwłoka)
       else sygnalizuj(drugi-licznik);
     czekaj(druga-zwłoka);
     drugi-licznik:=drugi-licznik - 1;
  end;
S;
if pierwszy-licznik > 0
  then sygnalizuj(pierwsza-zwłoka)
  else if drygi-licznik > 0
         then sygnalizuj(druga-zwłoka)
         else sygnalizuj(mutex);

• Monitory

  • inną konstrukcją stosowaną w językach wysokiego poziomu do synchronizacji jest typ monitor
  • cechą monitora jest zbiór operacji zdefiniowanych przez programistę

  type nazwa-monitora=monitor deklaracje zmiennych procedure entry P1(...); begi ... 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
  • 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ć tylko jeden proces

  

  • do modelowania pewnych schematów synchronizacji potrzebny jest dodatkowy mechanizm - konstrukcja pod nazwą warunek (condition):
    var x, y: condition;
  • jedyne operacje na zmiennej typu condition to: czekaj i sygnalizuj
  • operacja x.czekaj oznacza, że proces ja 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żeli żaden nie jest zawieszony to operacja nie ma żadnych skutków

• Problem obiadujących filozofów:

  Rozwiązanie z użyciem monitora

  

  • będziemy rozróżniać trzy stany, w których może znajdować się filozof
    
    var stan: array [0..4] of (myśli, głodny, je);
    
  • filozof o numerze i może nadać wartość zmiennej stan[i]=je tylko wtedy, gdy jego dwóch sąsiadów nie pożywia się, tzn.
    
    stan[i+4 mod 5] <> je and stan[i+1 mod 5] <> je
    
  • należy zadeklarować tablicę warunków
    
    var sam: array[o..4] of condition;
    
    za pomocą których nękani głodem filozofowie będą mogli opóźniać swoje zamiary, jeśli nie będzie możliwości otrzymania kompletu pałeczek

  type obiadujący-filozofowie=monitor var stan: array[1..4] of (myśli, głodny, je); var sam: array[0..4] of condition; procedure entry podnieś(i: 0..4); begin stan[i]:=głodny; test(i); if stan[i]<>je then sam[i].czekaj; end; procedure entry połóż(i: 0..4); begin stan[i]:=myśli; test(i+4 mod 5); test(i+1 mod 5); end; procedure entry test(k: 0..4); begin if stan[k+4 mod 5]<>je and stan[k]=głodny and stan[k+1 mod 5]<>je then begin stan[k]=je; sam[k].sygnalizuj; end; end; begin for i:=0 to 4 do stan[i]:=myśli; end.

  •  i-ty filozof musi wywoływać operacje podnieś i połóż w następującej kolejności:

  obiad-f.podnieś(i); ... jedzenie ... obiad-f.połóż;

• Transakcje niepodzielne

•  transakcja - zbiór instrukcji (operacji) które wykonują logicznie spójną funkcję (program) i które muszą być wykonane niepodzielnie, tzn. albo wszystkie operacje zostaną wykonane albo żadna nie będzie wykonana.

• niepodzielność musi być zachowana pomimo ewentualnych awarii systemu komputerowego

• należy zapewnić niepodzielność wykonywania transakcji w środowisku gdzie awaria systemu spowoduje utratę informacji w pamięci ulotnej

  • wycofanie transakcji - dane zmienione przez zaniechanie transakcji muszą być odtworzone do stanu przed rozpoczęciem transakcji

• techniki baz danych a SO-e

• cechy urządzeń stosowanych do przechowywania danych, z których korzystają transakcje

  • Pamięć ulotna (ang. volatile storage): Informacje przechowywane w pamięci ulotnej na ogół nie są w stanie przetrwać awarii systemu. Przykładem tego rodzaju pamięci są: pamięć operacyjna (główna) oraz pamięć podręczna. Dostęp do pamięci ulotnych jest najszybszy, zarówno z powodu swoistych ich szybkości jak i dlatego, że dowolną jednostkę danych uzyskuje się z pamięci ulotnej w sposób bezpośredni.

  • Pamięć nieulotna (ang. nonvolatile storage): Informacje przechowywane w pamięci nieulotnej zwykle potrafią przetrwać awarie systemu. Przykładami nośników takiej pamięci są dyski i taśmy magnetyczne. Dyski są bardziej niezawodne niż pamięć operacyjna, lecz mniej niezawodne niż taśmy magnetyczne. Jednak zarówno dyski, jak i taśmy magnetyczne są narażone na uszkodzenia, które mogą powodować utratę informacji. Obecnie wytwarzane pamięci nieulotne są wolniejsze od pamięci ulotnych o kilka rzędów wielkości, ponieważ dyski i taśmy magnetyczne są urządzeniami elektromechanicznymi, w których dostęp do danych wymaga ruchu.

  • Pamięć trwała (ang. stable storage): Informacje przechowywane w pamięci trwałej nie giną nigdy ("nigdy" należy tu potraktować z pewnym dystansem, gdyż teoretycznie taka 100 %-wa gwarancja nie jest możliwa). Do implementacji przybliżenia takiej pamięci należy zastosować zwielokrotnienie informacji w kilku nieulotnych pamięciach podręcznych (zazwyczaj dyskach), niezależnie od siebie na wypadek awarii, oraz uaktualnić te informacje w sposób kontrolowany

   

  • skoncentrujemy się na zapewnieniu niepodzielności transakcji w środowisku, w którym awaria powoduje utratę informacji w pamięci ulotnej

• odtwarzanie za pomocą rejestru

  • rejestrowanie z wyprzedzeniem - wszystkie zmiany wykonywane przez transakcję w danych, do których ona ma dostęp są rejestrowane w pamięci trwałej, w strukturze danych nazywanej rejestrem (dziennikiem).

  • każdy rekord rejestru opisuje jedną operację pisania w transakcji i ma pola:

    • nazwa transakcji

    • nazwa jednostki danych, stara wartość, nowa wartość

  • rejestr posiada rekord <T_i, rozpoczęcie> 

    • każda operacja pisz w transakcji jest poprzedzona zapisaniem odpowiedniego rekordu

    • gdy dochodzi do zatwierdzenia transakcji, wówczas w rejestrze zapisuje się rekord <T_i , zatwierdzenie>, a w wypadku przeciwnym < T_i , anulowano>

  • algorytm rekonstrukcji korzysta z dwóch procedur

    • wycofaj ( T_i ) - odtwarza wszystkie dane uaktualnione przez transakcję T_i , nadając im stare wartości; procedura jest aktywowana gdy rejestr zawiera rekord <T_i, rozpoczęcie> lecz nie zawiera <T_i , zatwierdzenie>

    • przywróć ( T_i ) - nadaje nowe wartości wszystkim danym uaktualnionym przez T_i ; jest aktywizowana gdy rejestr zawiera oba rekordy <T_i, rozpoczęcie> i <T_i , zatwierdzenie>

• punkty kontrolne

  1. Wszystkie rekordy aktualnie pozostające w pamięci ulotnej (zazwyczaj w pamięci operacyjnej) mają  

      być zapisane w pamięci trwałej

  2. Wszystkie zmienione dane pozostające w pamięci ulotnej mają być umieszczone w pamięci trwałej

  3. W przechowywanym w pamięci trwałej rejestrze transakcji należy zapisać rekord <punkt kontrolny>

  • po wystąpieniu awarii procedura rekonstrukcji przegląda rejestr w celu odnalezienia ostatniej transakcji T_i , której wykonanie rozpoczęto przed wykonaniem ostatniego punktu kontrolnego

    • wsteczne przeszukiwanie rejestru w celu napotkania pierwszego rekordu < punkt kontrolny>

    • odnalezienie pierwszego rekordu <T_i , rozpoczęcie> występującego po nim

  • operacje przywróć i wycofaj wystarczy wykonać tylko dla T_i i wszystkich transakcji rozpoczętych po niej

• współbieżne transakcje niepodzielne

  • szeregowalność - transakcje są wykonywane sekwencyjnie (jedna po drugiej) i każda z nich jest wykonywana w sekcji krytycznej

  • przykład seryjnego planu wykonywania niepodzielnych transakcji, w których T₀ poprzedza T₁ 

  T0	T1
  czytaj(A)
  pisz(A)
  czytaj(B)
  pisz(B)
  	czytaj(A)
  	pisz(A)
  	czytaj(B)
  	pisz(B)

 Plan 1, czyli plan szeregowy, w którym transakcja T₀ poprzedza transakcję T₁ 

• jeśli zezwolimy na przeplatanie się instrukcji wchodzących w skład dwóch transakcji, to wynikowy plan przestaje być szeregowym; czy szeregowy plan musi pociągać za sobą błąd w ostatecznym wyniku?

• zdefiniujmy pojęcie operacji konfliktowych: operacje O_i oraz O_j należące odpowiednio do T_i i T_j pozostają w konflikcie, jeżeli mają dostęp do tych samych obiektów danych i co najmniej jedna z nich jest operacją pisania

• przeanalizujmy nieszeregowy plan 2 

T0	T1
czytaj(A)
pisz(A)
	czytaj(A)
	pisz(A)
czytaj(B)
pisz(B)
	czytaj(B)
	pisz(B)

 

Plan 2: szeregowalne zaplanowanie współbieżne

• jeśli zezwolimy na przeplatanie się instrukcji wchodzących w skład transakcji, to wynikowy plan przestaje być szeregowy; czy nieszeregowy plan musi pociągać za sobą błąd w ostatecznym wyniku?

• zdefiniujmy pojęcie operacji konfliktowych: operacje O_i oraz O_j należące odpowiednio do T_i i T_j pozostają w konflikcie, jeśli mają dostęp do tych samych obiektów danych i co najmniej jedna z nich jest operacją pisania

• przeanalizujmy nieszeregowy plan 2:

T0	T1
czytaj(A)
pisz(A)
	czytaj(A)
	pisz(A)
czytaj(B)
pisz(B)
	czytaj(B)
	pisz(B)

. . . . . - operacje konfliktowe

. . . . . - operacje niekonfliktowe

• jeżeli sąsiednie operacje O_i i O_j w planie P są operacjami w różnych transakcjach, i te operacje nie są w konflikcie, to wolno nam zamienić porządek tych operacji, co daje nowy plan P'

• można oczekiwać, że plan P będzie równoważny planowi P' (kolejność operacji O_i i O_j jest bez znaczenia)

• tak więc operację Pisz(A) należącą do T₁ można zamienić z Czytaj(B) należącą do T₀ 

• kontynuując zamienianie bezkonfliktowych operacji uzyskujemy w efekcie plan 1, czyli plan szeregowy.

• plany te więc są równoważne; mówimy, że plan P jest szeregowalny z uwzględnieniem konfliktów

• protokół blokowania

  • jeden ze sposobów zapewnienia szeregowalności polega na skojarzeniu z każdym obiektem danych zamka i wymaganiu, aby w każdej teansakcji przestrzegano protokołu blokowania

  • dane mogą być blokowane w następujących trybach:

    • tryb wspólny: jeśli transakcja T_i zajmuje obiekt danych w trybie wspólnym, to może ona czytać ten obiekt, lecz nie może go zapisywać.

    • tryb wyłączny: jeśli transakcja T_i zajmuje obiekt danych w trybie wyłącznym, to może ona czytać ten obiekt, jak i go zapisywać.

  • wymaga się, aby każda transakcja zamawiająca zamek blokujący obiekt danych Q w odpowiednim trybie stosownie od rodzaju operacji, które będzie ona na Q wykonywać

  • aby uzyskać dostęp do obiektu Q, transakcja musi go najpierw zablokować

• protokół blokowania dwufazowego

• • faza wzrostu: transakcja może zablokować zasób, lecz nie wolno jej zwolnić żadnych z już zablokowanych zasobów

• • faza zmniejszania: transakcja może zwolnić zasób, lecz nie wolno jej już blokować nowych zasobów

  • ten protokół zapewnia szeregowalność pod względem konfliktów, nie chroni jednak przed zakleszczeniami

• protokoły korzystające ze znaczników czasu
  • schemat uporządkowania według znacznika czasu - inna metoda określania kolejności transakcji polegająca na ich uporządkowaniu z góry:
    • z każdą transakcją T_i w systemie kojarzymy niepowtarzalny i stały znacznik czasu ZC(T_i)
    • jeżeli transakcji przypisano znacznik ZC(T_i) i w późniejszym czasie pojawi się nowa transakcja T_j, to ZC(T_i) < ZC(T_j)
  • w celu implementacji tego schematu z każdym obiektem danych Q kojarzymy dwa znaczniki czasu
    • znacznik czasu - P(Q), określający największy znacznik czasu transakcji, która pomyślnie wykonała operację pisz(Q)
    • znacznik czasu - C(Q), określający największy znacznik czasu transakcji, która pomyślnie wykonała operację czytaj(Q)

• Załóżmy, że transakcja T_i wydaje polecenie czytaj(Q)

  • Jeśli ZC(T_i) < znacznik_czasu_P(Q), to z tego wynika, że transakcja T_i chce czytać wartość Q, która już została zmieniona. Dlatego operacja czytaj zostaje odrzucona, a transakcja T_i - wycofana.

  • Jeśli ZC(T_i) >= znacznik_czasu_P(Q), to wykonuje się operację czytaj oraz określa znacznik_czasu_C(Q) jako maksimum z wartości znacznik_czasu_C(Q) i ZC(T_i).

• Załóżmy, że transakcja T_i wydaje polecenie pisz(Q)

  • Jeśli ZC(T_i) < znacznik_czasu_C(Q), to z tego wynika, że wytwarzana przez transakcję T_i wartość Q, była potrzebna wcześniej i przyjmuje się że transakcja T_i nigdy nie wytworzyła tej wartości. Wobec tego rezygnuje się z operacji pisz i wycofuje transakcję T_i .

  • Jeśli ZC(T_i) >= znacznik_czasu_P(Q), to z tego wynika, że transakcja T_i usiłuje zapisać przestarzałą wartość Q. Dlatego odrzuca się tę operację pisz i wycofuje transakcję (T_i).

• rozpatrzmy plan3; zakładamy, że transakcjom przypisuje się znacznik czasu tuż przed ich pierwszymi instrukcjami, zatem ZC(T₂) < ZC(T₃); rozpatrzony ciąg wykonywań może być wytworzony protokół blokowania dwufazowego

T2	T3
czytaj(B)
	czytaj(B)
	pisz(B)
czytaj(A)
	czytaj(A)
	pisz(A)

Plan 3: zaplanowanie możliwe przy użyciu protokołu ze znacznikami czasu

• protokół zapewnia szeregowalność z uwzględnieniem konfliktów, wolną od zakleszczeń

<<< THE END >>>