1 Systemy Operacyjne Synchronizacjadr inż. Wiktor B. Daszczuk Instytut Informatyki Politechnika Warszawska

2 Wyścigi w systemie operacyjnymIPC - komunikacja między procesami (ang. Inter-Process Communication) W SO wykonujące się procesy często współdzielą obszary wspólnej pamięci, pliki lub inne zasoby. Należy unikać tzw. wyścigów. Def. 1 Warunkami wyścigu (ang. race conditions) nazywamy sytuację, w której dwa lub więcej procesów wykonuje operację na zasobach współdzielonych, a ostateczny wynik tej operacji jest zależny od przeplotu operacji składowych i może być niejednoznaczny (niezgodny ze specyfikacją).

3 Przykład wyścigu Program P1 1. LOAD A 2. INC 3. STORE A Program P25. DEC 6. STORE A

4 Lekarstwo: niepodzielność ciągu operacjiProgram P1 1. LOAD A 2. INC 3. STORE A Program P2 4. LOAD A 5. DEC 6. STORE A sekcje krytyczne

5 Nieskuteczne w wieloprocesorach !Blokowanie przerwań Program P1 DI 1. LOAD A 2. INC 3. STORE A EI Nieskuteczne w wieloprocesorach !

6 Instrukcja „badaj i modyfikuj” (Test-And-Set)Komórki pamięci Rejestr 2. Z R Z’ 1. Niepodzielnie !

7 Instrukcja „badaj i modyfikuj” (Intel) IKomórka pamięci Rejestr 2. Z R 3. 1. RR Rejestr roboczy

8 Instrukcja „badaj i modyfikuj” (Intel) IIKomórka pamięci Rejestr Z R Wynik - zamiana wartości Instrukcja LOCK XCHG

9 Blokowanie instrukcją „badaj i modyfikuj”B: MOV AL,1 LOCK.XCHG AL,G TEST AL JNZ B Odblokowanie MOV G,0 Zmienna globalna G

10 Sekcja krytyczna Def. 2 Sekcja krytyczna - fragment programu, w którym występują instrukcje dostępu do zasobów współdzielonych. Instrukcje tworzące sekcje krytyczne muszą wykonywane w reżimie wzajemnego wykluczania (ang. mutual exclusion) ze względu na zasób współdzielony. W praktyce sekcja krytyczna musi być poprzedzona i zakończona operacjami realizującymi wzajemne wykluczanie.

11 Warunki konieczne implementacji SKDla prawidłowej implementacji sekcji krytycznych muszą być spełnione następujące 3 warunki, przy czym nie czynimy żadnych założeń dotyczących szybkości działania procesów, czy też liczby procesorów: 1. Wewnątrz SK może przebywać tylko jeden proces, 2. Jakikolwiek proces znajdujący się poza SK, nie może zablokować innego procesu pragnącego wejść do SK, 3. Każdy proces oczekujący na wejście do SK powinien otrzymać prawo dostępu w skończonym czasie, o ile procesy opuszczają SK w skończonym czasie (w praktyce: prawo dostępu w rozsądnym czasie).

12 Mechanizmy realizujące wzajemne wykluczaniePodejścia: 0. Blokowanie przerwań (nieskuteczne w wieloprocesorach). 1. Mechanizmy z aktywnym oczekiwaniem na wejście do SK, (a) instrukcja „Badaj i modyfikuj”, (d) algorytm Petersona. 2. Mechanizmy z zawieszaniem procesu oczekującego na wejście do SK. (a) semafory, (b) monitory, (c) komunikaty. Synchronizacja przez zmienne

13 Blokowanie przerwań ang. interrupt disablingkażdy proces wchodząc do SK blokuje przerwania, a wychodząc odblokowuje, zaleta: proces znajdujący się w SK może uaktualnić zawartość zasobów dzielonych bez obawy, że inny proces będzie interweniował. wada: jeżeli proces na wyjściu z SK nie odblokuje przerwań, to nastąpi upadek systemu; ponadto, w przypadku systemów wieloprocerowych technika nieskuteczna, technika blokowania przerwań może być stosowana w jądrze SO przy uaktualnianiu niektórych systemowych struktur danych, lecz nie może być wykorzystywana do realizacji wzajemnego wykluczania w przestrzeni użytkownika.

14 Algorytm Petersona I (aktywne oczekiwanie)T. Dekker (1965), R. Peterson ( prostsza wersja) Każdy proces przed wejściem do SK wywołuje enter_region z własnym numerem jako parametrem, zaś po wyjściu leave_region.

15 Algorytm Petersona II #define FALSE 0 #define TRUE 1 #define N 2int turn; int interested[N]; /* initially 0 */ enter_region(int process) /* process nr 0 or 1 */ { int other; other = 1 - process; interested[process] = TRUE; turn = process; while((turn == process)&&(interested[other] == TRUE)); } leave_region(int process) interested[process]=FALSE;

16 Algorytm Petersona IIIWady: 1. Aktywne oczekiwanie 2. Postać zależy od liczby procesów, bardzo komplikuje się ze zwiększaniem liczby procesów

17 Wady rozwiązań opartych na aktywnym oczekiwaniustrata czasu procesora, możliwość blokady systemu przy wielopriorytetowym sposobie szeregowania procesów, tzw. zjawisko inwersji priorytetów.

18 Semafory P passeren proberen V vrygeven verhogen

19 Semafor I 1968 - E. W. Dijkstra wprowadza pojęcie semaforaDef. 3 – typ danych Współdzielona zmienna s o wartościach całkowitych nieujemnych, na której są dostępne dwie niepodzielne operacje: zwiększenia o 1 V(s), up(s), s.signal - wykonana zawsze zmniejszenia o 1 P(s), down(s), s.wait - wykonana gdy rezultat nieujemny

20 Semafor II Def. 3a – programistycznaWspółdzielona zmienna s o wartościach całkowitych nieujemnych, na której są dostępne dwie niepodzielne operacje: P - zmniejszenie o 1 jeżeli możliwe, w przeciwnym wypadku operacja lub proces opóźniany V - zwiększenie o 1 lub wznowienie zawieszonego procesu

21 Semafor binarny Semafor ogólnyPróba zwiększenia powyżej 1 jest ignorowana Semafor ogólny Przyjmuje wszystkie wartości nieujemne

22 Semafory: realizacja type semaphore=class(wp:integer);var wart:integer; kolejka:queue; procedure V; begin if kolejka.empty then wart:=wart+1 else begin usuń jeden z procesów z kolejka i wstaw do kolejki gotowych end end; wart:=wp; init kolejka end. procedure P; begin if wart > 0 then wart:=wart-1 else begin wstaw proces do kolejka; zablokuj proces end end;

23 ? Semafory: bufor type buffer=class (n:integer) ;var mutex:bin_semaphore; b:array[0..n-1]of item; pełny,pusty:semaphore; wolny,zajęty:0..n-1; procedure get (var e:item); begin P (mutex); P (pusty); e:=b[zajęty]; zajęty:=(zajęty+1)mod n; V(pełny); V(mutex) end; wolny:=0; zajęty:=0; init mutex(1), pełny(n), pusty(0) end. P(pusty); P(mutex); procedure put (e:item); begin P(mutex); P(pełny); b[wolny]:=e; wolny:=(wolny+1)mod n; V(pusty); V(mutex) end; ? P(pełny); P(mutex);

24 Zakleszczenie Def. 4 Zakleszczenie to stan, w którym występują procesy (programy, wątki, ...), które oczekują na zdarzenie (zdarzenia) które nie może wystąpić.

25 Problem 5 filozofów RIP ? ? pięciu filozofów przy stole z rozstawionymi pięcioma talerzami i pięcioma widelcami pomiędzy talerzami każdy z filozofów tylko je i myśli, do jedzenia potrzebuje talerza i dwóch widelców widelec jest zasobem współdzielonym przez sąsiadujących filozofów

26 I rozwiązanie: ustalona kolejność1P 2L 2L 2P 1L 1P Co najmniej jeden bierze najpierw prawy, co najmniej jeden bierze najpierw lewy 2L 1P 2L 1P

27 II rozwiązanie: lokaje (uogólnienie I)Max 4 Max 4

28 III rozwiązanie: dwa lub żadenFilozof bierze dwa widelce jeżeli oba są wolne !

29 Przykładowy scenariuszRIP Zjawisko: zagłodzenie

30 Zagłodzenie Def. 5 Zagłodzenie to stan, w którym występują procesy (programy, wątki, ...), które oczekują na zdarzenie (zdarzenia) które może wystąpić, ale wciąż nie następuje.

31 5 filozofów: semafory (II)var philosophers:class; var fork:array[0..4]of semaphore; left_b,right_b:semaphore; procedure odłóż (i:0..4); begin select true  begin V(fork[i]); V(left_b); V(fork[i+]); V(right_b) end; V(fork[i+]); V(right_b); V(fork[i]); V(left_b) end endselect init left_b(4), right_b(4); for i:=0 to 4 do init fork[i](1) end. procedure weź (i:0..4); begin select true  begin P(left_b); P(fork[i]); P(right_b); P(fork[i+]) end; P(right_b); P(fork[i+]); P(left_b); P(fork[i]) end endselect

32 Operacja + i+ =df (i+1) mod 5

33 Koncepcja monitora ? procedure put (e:item) begin P(mutex); P(pełny);b[wolny]:=e; wolny:=wolny+1; V(pusty); V(mutex) end; procedure put (e:item) beginP P(pełny); b[wolny]:=e; wolny:=wolny+1; V(pusty); endV; ?

34 Monitor ZASADY C.A.R. Hoare (1974) Per Brinh Hansen (1975)Edsger W. Dijkstra (1974) type m=monitor (...); var c1,c2,...:condition; ... procedure P1 (...); begin if nie może then ci.wait; zrób co trzeba; if not cj.empty then cj.signal end; procedure P2 (...); if nie może then cj.wait end; begin ... end. ZASADY 1. Klasa 2. Sekcja krytyczna w metodach 3. Zawieszanie ze zwolnieniem sekcji krytycznej 4. Zasada bezpośredniego wznowienia (H,D) lub stan pobudzony (BH)

35 Monitor: implementacja buforatype buf=monitor (n:integer); var pełny,pusty:condition; b:array[0..n-1]of item; ile:0..n; wolny,zajęty:0..n-1; procedure wstaw (e:item); begin if ile=n then pełny.wait; ile:=ile+1; b[wolny]:=e; wolny:=(wolny+1)mod n; if not pusty.empty then pusty.signal end; procedure wyjmij (var e:item); begin if ile=0 then pusty.wait; ile:=ile-1; e:=b[zajęty]; zajęty:=(zajęty+1)mod n; if not pełny.empty then pełny.signal end; ile:=0; wolny:=0; zajęty:=0 end.

36 Monitor: implementacja semaforatype sem=monitor (wp:integer); var s:condition; wart:integer; procedure P; begin if wart=0 then s.wait; wart:=wart-1; end; procedure V; begin wart:=wart+1; if not s.empty then s.signal end; wart:=wp end.

37 Monitor: 5 filozofów (rozwiązanie III)var philosophers:monitor; var fork:array[0..4]of boolean; s:array[0..4]of condition; procedure weź (i:0..4); begin if not (fork[i] and fork[i+]) then s[i].wait; fork[i]:=false; fork[i+]:=false end; procedure odłóż (i:0..4); begin fork[i]:=true; fork[i+]:=true; if fork[i] then s[i].signal; if fork[i++] and fork[i+] then s[i+].signal; end; for i:=0 to 4 do fork[i]:=true end.

38 Operacje +, ++,  i+ =df (i+1) mod 5 i++ =df (i+2) mod 5

39 Zasady implementacji monitora1 type m=monitor (...); var ci,cj: condition; ... procedure P1 (...); beginP if nie może then ci.wait; zrób co trzeba; if not cj.empty then cj.signal endV; begin ... end. 1 var m:bin_semaphore 2 2 var ci,cj:bin_semaphore; ile_ci,ile_cj:integer 3 3 P(m) 4 4 ile_ci:=ile_ci+1; V(m); P(ci); ile_ci:=ile_ci-1 5 5 ile_cj=0 6 6 V(cj); P(m) 7 7 V(m) 8 init m(1), ci(0), cj(0); ile_ci:=0; ile_cj:=0; 8

40 Monitor: realizacja w -jądrze Itype monitor=class; var aktywny:process; gotowe:queue; procedure endV (pr:process); var pr0:process; begin if gotowe.pusta then aktywny:=NULL else begin gotowe.wyjmij(pr0) aktywny:=pr0 end end; procedure beginP (pr:process); begin if aktywny  NULL then gotowe.wstaw(pr) else aktywny:=pr end; cdn...

41 Monitor: realizacja w -jądrze IIprocedure wait (pr:process); var pr0:process; begin if gotowe.pusta then aktywny:=NULL else begin gotowe.wyjmij(pr0) aktywny:=pr0 end end; {wait=endV} procedure transfer (pr,pr0:process); begin gotowe.usuń(pr0); gotowe.wstaw(pr); aktywny:=pr0 end; begin {monitor} aktywny:=NULL; init gotowe end. cdn...

42 Monitor: realizacja w -jądrze IIItype condition=class (m:monitor); zawieszone:queue; procedure signal (pr:process); var pr0:process; begin if not zawieszone.pusta then begin zawieszone.wyjmij(pr0) m.transfer(pr,pr0) end end; begin {condition} init zawieszone end. procedure wait (pr:process); begin zawieszone.wstaw(pr); m.wait(pr) end;

43 Graf stanów - semafor siP(si),wsi>0 neutralny zawieszo- ny na si P(si),wsi=0 V(si) V(si)

44 Graf stanów - monitor endV aktywny w mon. beginP, r.k. wolny poza mon.zawiesz. na ci ci.wait ci.signal ci.signal gotowy w mon. beginP, r.k. zaj. cx.wait, endV cx.wait, endV

45 Monitor Brinh Hansena 1. zamiast warunków condition - kolejki queue2. zamiast bezpośredniego wznowienia - wznawiany proces z priorytetowym stanie pobudzony 3. proces wznawiający może tyko opuścić monitor

46 Graf stanów - monitor Brinh HansenaendV aktywny w mon. beginP, r.k. wolny poza mon. zawiesz. na qi qi.wait endV gotowy w mon. beginP, r.k. zaj. cx.wait, endV (brak pob.) pobudzony qi.continue cx.wait, endV

47 Komunikaty I (ang. message passing)Oparte na dwóch wywołaniach systemowych (prymitywach): send( destination, message ) receive( source, message ) Synchronizacja bazuje na fakcie, że komunikat nie może zostać odebrany zanim zostanie wysłany. Komunikaty są kompletowane i przekazywane przez system przesyłania komunikatów (ang. Message Passing System), często zawarty w systemie operacyjnym.

48 Komunikaty II Def. 6 Synchroniczność komunikacji:prymityw synchroniczny (blokujący) - blokuje nadawcę/odbiorcę do zakończenia przesyłania i zaakceptowania komunikatu prymityw asynchroniczny (nieblokujący) - pozwala nadawcy/odbiorcy biec dalej również przy niegotowości drugiej strony, zakończenie komunikowane przez wyjątek lub ustawienie flagi (aktywne oczekiwanie)

49 Komunikaty III Adresowanie:bezpośrednie, każdy proces posiada unikatowy adres. Można stosować poniższy mechanizm spotkań: pośrednie poprzez skrzynkę (port, kolejkę, ...) pośredniczącą pełniącą funkcję bufora pośredniczącego. Argumentem wywołań send i receive jest adres skrzynki a nie adres konkretnego procesu.

50 Komunikaty: spotkaniaSpotkanie: para synchronicznych (blokujących) komunikatów: właściwy komunikat i potwierdzenie zawierające odpowiedź.

51 Komunikaty: algorytm producent/konsument IZałożenia wstępne: wiadomości są tego samego rozmiaru, wiadomości wysłane lecz nie odebrane są buforowane automatycznie przez system przesyłania komunikatów, użyto N wiadomości, analogicznie do N miejsc współdzielonego bufora, komunikaty są traktowane jako medium transportowe dla informacji, tzn. mogą być wypełnione bądź puste, algorytm rozpoczyna wysłanie przez konsumenta N pustych komunikatów do producenta, aby producent mógł wysłać nową informację do konsumenta, musi mieć dostępny pusty komunikat odebrany od konsumenta - liczba komunikatów w obiegu między producentem a konsumentem jest stała i niezależna od szybkości produkcji czy konsumpcji informacji.

52 Komunikaty: algorytm producent/konsument IIconst N=100; procedure producer; var item:integer; m:message; begin repeat produce_item( item ); receive( m ); build_message( m, item ); send ( m ) until false end; procedure consumer; var i,item:integer; m:message; begin for i = 0 to N-1 do send( producer, m ); repeat receive( m ); extract_item( m, item ); send( m ); until false end.

53 Problem pisarzy i czytelnikówvar writers_readers:class; var mutex,db: bin_semaphore; rc:integer; procedure writer; begin think_up_data; P(db); write_data_base; V(db) end; procedure reader; begin P(mutex); rc := rc + 1; if rc = 1 then P(db); V(mutex); read_data_base; rc := rc - 1; if rc = 0 then V(db); use_data_read; end; begin init mutex(1), db(1); rc := 0 end.

54 Problem śpiącego fryzjeravar barbers=class (n:integer) const CHAIRS=n; var customers,barbers: semaphore; mutex:bin_semaphore; waiting:integer; procedure barber; begin P(customers); P(mutex); waiting := waiting - 1; V(barbers); V(mutex); cut_hair end; Problem śpiącego fryzjera procedure customer; begin P(mutex); if waiting < CHAIRS then begin waiting := waiting + 1; V(customers); V(mutex); P(barbers); get_haircut end else V(mutex) end; begin init customers(0), barbers(0), mutex(1); wainitng := 0 end.