1

SYNCHRONIZACJA

SYNCHRONIZACJA

PROCESÓW

PROCESÓW

Jerzy Peja

Politechnika Szczeci ska

Wydział Informatyki

ul. ołnierska 49, 71-210 Szczecin

2

Agenda

Tło

Instrukcje atomowe i ich przeplot
Problem sekcji krytycznej
Algorytmy wzajemnego wykluczania (alg. Petersona i Lamporta)
Synchronizacja sprz towa
Semafory
Klasyczne problemy synchronizacji
Regiony krytyczne
Monitory

2

3

Tło. Problem producent - konsument

Współbie ny dost p do dzielonych danych mo e prowadzi do

utraty spójno ci danych.
Proces współpracuj cy mo e wpływa na inne procesy w systemie

lub podlega ich oddziaływaniom, np. przez dzielenie danych.
Utrzymywanie spójno ci danych wymaga mechanizmu, który

zagwarantuje uporz dkowane wykonywanie współpracuj cych

procesów.
Rozwi zanie z wykorzystaniem pami ci dzielonej zastosowane do

problemu ograniczonego bufora działa w przypadku, gdy co

najwy ej N-1 danych zapisanych jest w tym samym czasie.

Rozwi zanie, w którym wykorzystane s wszystkie elementy

bufora nie jest proste.

Załó my, e zmodyfikujemy kod rozwi zania problemu

wprowadzaj c now zmienn counter, zainicjowana warto ci 0 i

zwi kszana za ka dym razem, gdy nowy element dodawany jest do

bufora.

4

Ograniczony bufor

Dane dzielone

#define BUFFER_SIZE 10
typedef struct {

. . .

} item;
item buffer[BUFFER_SIZE];
int in = 0;
int out = 0;
int counter = 0;

3

5

Ograniczony bufor

Proces producenta

item nextProduced;

while (1) {

while (counter == BUFFER_SIZE)

; /* nic nie rób */

buffer[in] = nextProduced;
in = (in + 1) % BUFFER_SIZE;
counter++;

}

6

Ograniczony bufor

Proces konsumenta

item nextConsumed;

while (1) {

while (counter == 0)

; /* nic nie rób */

nextConsumed = buffer[out];
out = (out + 1) % BUFFER_SIZE;
counter--;

}

4

7

Ograniczony bufor

Wyra enia

counter++;

counter--;

musz by wykonywane w sposób niepodzielny (atomiczny).

Operacje niepodzielne (operacje atomowe) oznaczaj , e

operacja ko czy si w cało ci bez jej przerwania.

8

Ograniczony bufor

Instrukcja “

counter++” mo e by przetłumaczone na j zyk

maszynowy np. do takiej postaci::

register1 = counter
register1 = register1 + 1

counter = register1

Z kolei instrukcja “

counter--” np. do takiej postaci:

register2 = counter

register2 = register2 – 1

counter = register2

5

9

Ograniczony bufor

Je li zarówno producent, jak i konsument spróbuj

współbie nie zaktualizowa bufor, to instrukcje

wykonywane na poziomie j zyka asembler mog by

przeplatane.

Przeplatanie zale y od tego w jaki sposób szeregowany jest

proces producenta i konsumenta.

10

Ograniczony bufor

Załó my, e pocz tkowo

counter ma warto 5. Przykładem

przeplotu instrukcji mo e by nast puj cy ci g wykona kodu

producenta i konsumenta:

producent:

register1 = counter (register1 = 5)

producent:

register1 = register1 + 1 (register1 = 6)

konsument:

register2 = counter (register2 = 5)

konsument:

register2 = register2 – 1 (register2 = 4)

producent:

counter = register1 (counter = 6)

konsument:

counter = register2 (counter = 4)

Warto ci

counter mo e by albo 4 albo 6, podczas, gdy

poprawnym wynikiem powinna by warto 5.

6

11

Ograniczony bufor (c.d.)

Warto

counter zale y od przeplatania kodu. Tutaj

otrzymujemy 4:

{counter = 4}

counter = register

2

wykonuje

konsument

T

5

{counter = 6}

counter = register

1

wykonuje

producent

T

4

{register

2

=4}

register

2

= register

2

– 1

wykonuje

konsument

T

3

{register

2

=5}

register

2

=counter

wykonuje

konsument

T

2

{register

1

=6}

register

1

= register

1

+1

wykonuje

producent

T

1

{register

1

=5}

register

1

=counter

wykonuje

producent

T

0

12

Ograniczony bufor (c.d.)

Zmiana kolejno ci w chwilach T

4

i T

5

daje warto 6:

{counter = 6}

counter = register

1

wykonuje

producent

T

5

{counter = 4}

counter = register

2

wykonuje

konsument

T

4

{register

2

=4}

register

2

= register

2

- 1

wykonuje

konsument

T

3

{register

2

=5}

register

2

=count

wykonuje

konsument

T

2

{register

1

=6}

register

1

= register

1

+1

wykonuje

producent

T

1

{register

1

=5}

register

1

=count

wykonuje

producent

T

0

7

13

Warunek wy cigu (ang. race condition)

Warunek wy cigu: Sytuacja, w której kilka procesów ma

dost p do danych dzielonych i współbie nie nimi

manipuluje. Ko cowa warto współdzielonych danych

zale y od tego, który proces zako czy si jako ostatni.

Aby zapobiec warunkom wy cigu, procesy współbie ne

musz by

synchronizowane.

14

Problem sekcji krytycznej (ang. the critical-

section problem)

We my N procesów rywalizuj cych o dost p do wspólnych

(dzielonych) danych.
Ka dy proces ma segment kodu, nazywany sekcja krytyczn , w

obr bie której realizowany jest dost p do danych dzielonych.
Problem – nale y zapewni , aby w momencie, gdy jeden z

procesów wykonuje si w swojej sekcji krytycznej, to aden inny

proces nie jest uprawniony do wykonywania si w swojej sekcji

krytycznej.

8

15

Rozwi zanie problemu sekcji krytycznej

1.

Wzajemne wykluczanie (ang. mutual exclusion). Je li proces P

i

wykonuje si w swojej sekcji krytycznej, to adne inne procesy

nie mog by wykonywane w ich sekcjach krytycznych.

2.

Post p. Je li aden proces nie wykonuje si w swojej sekcji

krytycznej oraz istniej procesy, które chc wej do swoich sekcji

krytycznych, to wybór procesu, który powinien wej do sekcji

krytycznej jako nast pny nie powinien by odwlekany w

niesko czono .

3.

Ograniczone oczekiwanie. Musi istnie warto graniczna liczby

wej innych procesów do ich sekcji krytycznej po tym, gdy dany

proces zgłosił ch wej cia do swojej sekcji krytycznej i zanim

uzyskał na to pozwolenie.

Zakłada si , e ka dy proces wykonuje si z niezerow pr dko ci .
Nie przyjmuje si adnych zało e , dotycz cych relatywnej

pr dko ci N procesów.

16

Sformułowanie zadania i szkic rozwi zania

Tylko dwa procesy, P

0

i P

1

Ogólna struktura procesu P

i

(i = 0, 1)

do {

sekcja wej ciowa

sekcja krytyczna

sekcja wyj ciowa

reszta

}

while (1);

Procesy mog dzieli pewne wspólne zmienne po to , aby

synchronizowa swoje działanie.

9

17

Algorytm 1

Zmienne dzielone:

shared int turn;

pocz tkowo

turn = 0; j = 1 - i

turn = i

P

i

mo e wej do swojej sekcji krytycznej

Proces P

i

do {

while (turn != i) ;

sekcja krytyczna

turn = j;

reszta

}

while (1);

Spełniony warunek wzajemnego wykluczania, ale

brak post pu.

18

Algorytm 1

Post p. Je li aden proces nie wykonuje swojej sekcji krytycznej

oraz istniej procesy, które chc wej do sekcji krytycznych, to

tylko procesy nie wykonuj ce swoich reszt mog kandydowa do

wej cia jako jako nast pne do sekcji krytycznych; wybór ten nie

mo e by odwlekany w niesko czono .
Je li

turn = 0 i T

1

chce wej do swojej sekcji krytycznej, ale T

0

nie chce, to T

1

tak e nie mo e wej .

Ten algorytm nie przechowuje wystarczaj co du o informacji o

stanie ka dego z w tków.

Pami ta jedynie to, który w tek powinien wej jako kolejny do

swojej sekcji krytycznej.

10

19

Algorytm 2

Zmienne dzielone:

shared boolean flag[2];

pocz tkowo

flag [0] = flag [1] = false.

flag [i] = true

P

i

gotowy do wej cia do swojej sekcji

krtycznej

Proces P

i

do {

flag[i] := true;

while (flag[j]) ;

sekcja krytyczna

flag [i] = false;

reszta

} while (1);

Spełniony warunek wzajemnego wykluczenia, ale

nie jest spełniony warunek post pu.

20

Algorithm 2

Warunek wzajemnego wykluczania jest spełniony.
Post p

. Je li aden proces nie wykonuje si w swojej sekcji

krytycznej oraz istniej procesy, które chc wej do swoich sekcji

krytycznych, to wybór procesu, który powinien wej do sekcji

krytycznej jako nast pny nie powinien by odwlekany w

niesko czono .
T

0

ustawia flag[0] na

true

. Nast pnie nast puje przeł czenie

kontekstu i CPU ma T

1

.

T

1

ustawia flag[1] na

true

.

aden z procesów nie mo e wej do swojej sekcji krytycznej.

11

21

Algorytm 3 (algorytm Petersona)

Poł czone zmienne współdzielone algorytmu 1 i 2.
Proces P

i

Spełnione wszystkie trzy wymagania; rozwi zanie

problemu sekcji krytycznej dla dwóch procesów.

22

Algorytm Lamporta (tzw. algorytm piekarni)

Przed wej ciem do swojej sekcji krytycznej proces

otrzymuje numer. Posiadacz najmniejszego numeru

wchodzi do sekcji krytycznej.
Je li procesy P

i

i P

j

otrzymaj ten sam numer, a i < j,

to P

i

jest obsługiwany jako pierwszy; w przeciwnym

przypadku pierwszy obsługiwany jest proces P

j

.

Schemat numerowania zawsze generuje numery w

porz dku narastaj cym, np. 1,2,3,3,3,3,4,5...

Sekcja krytyczna dla n procesów

12

23

Algorytm piekarni (algorytm Lamporta)

Notacja <

≡ porz dek leksykograficzny (bilet #, ID #

procesu)

(a,b) < (c,d), je li a < c lub je li a = c i b < d
max (a

0

,…, a

n-1

) jest numerem k takim, e k

≥ a

i

dla i = 0,

…, n – 1

Dane dzielone

shared boolean choosing[n];
shared int number[n];
local int k;

Struktury danych s inicjowane odpowiednio warto ciami

false i 0.

24

Algorytm piekarni – struktura procesu P

i

!

"

!

# $

!

$ % $

!

&

'

#

(

''

!

) # * *

!

$

(

!

$

!

#

13

25

Algorytm piekarni

Nale y pokaza , e je li P

i

jest w swojej sekcji krytycznej P

k

(k <>

I) ma ju przydzielony swój numer number[k] <> 0, to (number[i],

i) < (number[k], k).

Wzajemne wykluczanie

.

Załó my, e P

i

jest w swojej sekcji krytycznej

P

k

próbuje wej do swojej sekcji krytycznej.

Gdy P

k

wykonuje drugie wyra enie dla j = i, to

•

number[i] <> 0

•

(number[i],i) < (number[k],k)

Z tego powodu kontynuuje oczekiwanie w p tli, dopóki P

i

nie opu ci

swoj sekcje krytyczna.

Ograniczone oczekiwanie i post p

Procesy wchodz do swoich sekcji zgodnie z reguł FCFS.

26

Synchronizacja sprz towa Test-and-Set

Testuj i modyfikuj zawarto słowa w sposób niepodzielny

(atomowy).

boolean TestAndSet(boolean &target) {

boolean rv = target;
target = true;

return rv;

}

14

27

Procesor Intel-32

W architekturze IA-32 (Intel) tego typu operacje realizowane s na

poziomie maszynowym przez rozkazy:

bt, bts, btr, btc,

poprzedzone ewentualnie prefiksem lock.

BT Bit test
BTS Bit test and set
BTR Bit test and reset
BTC Bit test and complement

28

Wzajemne wykluczanie z u yciem instrukcji

Test-and-Set

Dane dzielone:

boolean lock = false;

Proces P

i

do {

while (TestAndSet(lock)) ;

sekcja krytyczna

lock = false;

reszta

}

15

29

Synchronizacja sprz towa – instrukcja

exchange

Niepodzielna zamiana warto ci dwóch zmiennych.

void exchange(boolean &a, boolean &b) {

boolean temp = a;
a = b;
b = temp;

}

30

Procesor Intel-32

W architekturze IA-32 (Intel) operacja

exchange realizowana jest na

poziomie maszynowym przez rozkaz:

xchg, dotyczy jednak nie bitów a

zawarto ci całych rejestrów.
Pewnym ograniczeniem jest fakt, e jeden z operandów musi by w

rejestrze procesora, ale nie przeszkadza to np. w zastosowaniu tego.

rozkazu do rozwi zania problemu wzajemnego wykluczania.
Je li który z operandów rozkazu

xchg jest w pami ci, nast puje blokada

magistrali niezale nie od u ycia prefiksu lock.

16

31

Wzajemne wykluczanie z u yciem instrukcji

exchange

Dane dzielone (zainicjowane na

false):

!
!

Proces P

i

exchange

$

32

Semafory

Semafor (ang. semaphore) - pierwszy mechanizm

synchronizacyjny w j zykach wysokiego poziomu (Dijkstra,

1965):
Narz dzie synchronizacji niewymagaj ce aktywnego oczekiwania.
Semafor S – zmienna całkowita, na której mog by wykonywane

operacje jedynie za pomoc dwóch niepodzielnych (atomowych)

operacji:

+

+

≤ #

, -

+,,

+
+''

17

33

Semafory - uwagi

Podstawow wad przedstawionej poprzednio definicji semafora

jest to, e operacja

wait zawiera aktywne czekanie (busy

waiting), które marnuje cykle procesora.
Taki semafor nazywany jest

wiruj c blokad (spinlock).

34

Dwa typy semaforów

Semafory ogólny – warto całkowita, przybieraj ca

warto ci z pewnej nieograniczonej domeny.
Semafor binarny – warto całkowita, która mo e

przybiera tylko warto ci 0 i 1; prostszy w

implementacji.
Semafor ogólny mo na zaimplementowa jako semafor

binarny.

18

35

Implementacja semafora

S

jako semafora

binarnego

Struktury danych:

binary-semaphore S1, S2;
int C:

Inicjalizacja

S1 = 1
S2 = 0
C = wart.pocz tkowa semafora S

36

Implementacja semafora

S

Operacja wait

wait(S1);

C--;

if (C < 0) {

signal(S1);

wait(S2);

}

signal(S1);

Operacja signal

wait(S1);
C++;
if (C <= 0)

signal(S2);

else

signal(S1);

19

37

Implementacja semaforów

Ka dy operacja semaforowa musi by wykonania

automatycznie

i w sposób

niepodzielny

.

Powoduje to powstanie problemu sekcji krytycznej.
Dwa rozwi zania:

Mo na zablokowa przerwania podczas wykonywania operacji

wait (oznaczanej dalej tak e przez P - hol. passeren, proberen)

lub signal (oznaczanej tak e przez

V - hol. vrijmaken, verhogen).

Trudne do implementacji w przypadku systemów

wieloprocesorowych.

•

Instrukcje ró nych procesorów mog by przeplatane w dowolnej

kolejno ci.

•

Zablokowanie przerwa na jednym procesorze nie ma wpływu na
pozostałe procesory.

38

Implementacja semaforów (c.d.)

Rozwi zanie wieloprocesorowe:

Wykorzysta instrukcje sprz towe (

test-and-set lub swap)

pracuj ce na wspólnej pami ci.
Wykorzysta poprzednio omawiane algorytmu rozwi zania sekcji

krytycznej.

Rozwi zania te nie daj mo liwo ci wyeliminowania aktywnego

oczekiwania.

Aktywne oczekiwanie mo na by ewentualnie umie ci w

implementacji sekcji krytycznej operacji P i V (ale najlepiej jest

wyeliminowa je).
Je li sekcje kodowane s poprawnie, to s krótkie (~10 instrukcji)
Rozwi zanie bardziej efektywne ni u ycie aktywnego oczekiwania

na poziomie programu u ytkownika.

20

39

Semafory jako ogólny mechanizm

synchronizacji

Stosowanie semaforów binarnych

+ -

+ ..

/ +
+

0

1 +

40

Semafory bez

aktywnego oczekiwania

/ +

2

,,

2

( #

-

- /

1 +

2

''

2

( #

3 -

/

- /

Gdy wykonywana jest operacja

P

,

sprawdzana jest warto

semafora. Je li warto semafora

Jest ujemna, to proces dodawany

jest do listy procesów oczekuj cych

i

blokowany

(usypiany).

Gdy wykonywana jest operacja

V

,

to sprawdzane jest, czy warto

semafora <= 0.

Je li tak, to na li cie musi znajdowa

si jaki proces. Usu proces z listy

i wznów jego wykonywanie

21

41

Semafory bez

aktywnego oczekiwania

/ +

2

,,

2

( #

-

- /

1 +

2

''

2

( #

3 -

/

- /

W tej implementacji warto

semafora mo e by ujemna. Je li

jest ujemna, to warto

bezwzgl dna z warto ci semafora

oznacza liczb procesów na li cie

procesów oczekuj cych pod

semaforem..

Implementacja listy realizowana

jest w oparciu o pole wi zania

wyst puj ce w ka dy bloku kontrolnym

procesu (PCB). Ka dy semafor

zawiera warto całkowit i wska nik

do listy PCB.

Mo na stosowa dowolna strategi

obsługi kolejek, ale najcz ciej

wykorzystywana jest strategia FIFO.

42

Sekcja krytyczna dla n procesów

Dane dzielone:

Semaphore mutex; //pocz tkowo

mutex

= 1

Proces P

i

:

do {

wait(mutex);

sekcja krytyczna

signal(mutex);

reszta

} while (1);

22

43

Muteksy (ang.

mut

ual

ex

clusion) (1/2)

Pełni rol semaforów binarnych, wyst puj pojedynczo (nie w

tablicach).
Powinny by inicjowane za pomoc obiektu atrybutów. W

Linuksie maj statyczny przydział pami ci.

Rodzaje muteksów:

szybki (ang. fast)
sprawdzaj cy (ang. error checking)
rekurencyjny (ang. recursive)

Stany:

otwarty
zamkni ty

Warto ci domy lne: szybki i otwarty

44

Muteksy (ang. mutual exclusion) (1/2)

Muteks szybki – pami ta jedynie swój stan. Mo e by przyczyn

blokady w tku, który go utworzył, zamkn ł, a nast pnie próbował

zamkn ponownie (teoretycznie musiałby go uwolni inny w tek,

ale to wiadczyłoby o bł dzie w algorytmie).
Muteks sprawdzaj cy – pami ta, kto go zamkn ł (kto jest jego

wła cicielem przez czas zamkni cia). Mo e zapobiega bł dom:

nie pozwala po raz drugi zamkn si temu samemu w tkowi

(wła cicielowi);
nie pozwala otworzy si w tkowi nie b d cemu jego wła cicielem;
próba otwarcia muteksu otwartego powoduje sygnalizacj bł du;

Muteks rekurencyjny – „zamek zamykany na wiele spustów”,

posiada licznik operacji zamkni cia / otwarcia. Kolejnych

zamkni /otwar mo e dokonywa tylko wła ciciel (zmiana

wła ciciela – tylko przy pełnym otwarciu). Liczba spustów i

skutki jej przekroczenia – zale ne od implementacji.

23

45

Zmienne warunkowe

Zmienne warunkowe s mechanizmami synchronizacji, gdy

pojedynczy muteks nie jest wystarczaj cy. Musz by

wykorzystywane ł cznie z muteksami („same nie maj racji bytu”)
Zasadniczo zmienne warunkowe powinny by inicjowane

dynamicznie przez obiekty atrybutów (w Linuksie do niedawna

niezaimplementowane.

46

Implementacja semafora

Zdefiniujmy semafor jako rekord

typedef struct {

int value;

struct process *L;

} Semaphore;

Przyjmijmy, e wykonywane s dwie proste operacje:

block „zawiesza” proces, który wywołuje ta operacj .
wakeup(P) „budzi” i uaktywnia zablokowany proces P.

24

47

Implementacja

Definiujemy nast puj ce operacje

semaforowe:

wait

(

S

):

S.value--;
if (S.value < 0) {

dodaj proces do kolejki

S.L;

block;

}

signal

(

S

):

S.value++;
if (S.value <= 0) {

usu

proces P z kolejki

S.L;

wakeup(P);

}

48

Semafory jako ogólne narz dzie synchronizacji

Wykonaj B w P

j

tylko po wykonaniu A w P

i

U yjemy jako semafora zmiennej flag, zainicjowanej na 0
Kod:

P

i

P

j

A

wait

(

flag

)

signal

(

flag

)

B

25

49

Blokada (ang. deadlock) i zagłodzenie (ang.

starvation)

Blokada – dwa lub wi cej procesów oczekuj niesko czenie na

zdarzenie, które mo e by wywołane tylko przez jeden z

oczekuj cych procesów..
Niech S i Q b d dwoma semaforami, zainicjowanymi na 1

P

0

P

1

wait

(

S

);

wait

(

Q

);

wait

(

Q

);

wait

(

S

);

signal

(

S

);

signal

(

Q

);

signal

(

Q

)

signal

(

S

);

Zagłodzenie – niesko czone blokowanie. Proces mo e nie by

nigdy usuni ty spod semafora, na którym został zawieszony.

50

"Prawdziwe” semafory

W j zyku Java zaimplementowane s jedynie mechanizmy

synchronizacji, brak implementacji prawdziwych

semaforów.
Linux umo liwia prac z macierzami semaforów.

26

51

Semafory w systemie Linux

Mo liwo komunikacji mi dzyprocesowej została wprowadzona

wersji AT&T System V.2 systemu UNIX.
Mo liwo ci te maja jednakowy interfejs programisty i z tego

powodu okre lane s mianem IPC (ang. interprocess

communication) lub System V IPC.
Istniej tak e inne metody komunikowania si pomi dzy

procesami (np. ł cza - pipes).
Trzy mechanizmy System V IPC:

Semafory
Kolejki wiadomo ci
Wspólna pami

Dalej zajmiemy si jedynie semaforami.

52

Semafory w systemie Linux

Funkcje semaforowe:

4

(

. 5 6

7 $

7

$

$ %

7

$

7

$

7

-

7 $

!

8 7 - $

7

7

7 -

key

identyfikuje zasób,

za pomoc którego proces

mo e si do niego

odwoływa i kooperowa

Z innymi procesami.

Zwraca

int

, który słu y jako

identyfikator semafora.

Jego rola jest podobna jak

deskryptora pliku

key

umo liwia niepowi zanym

procesom na dost p do tego

samego semafora.

Procesy odwołuj si do

semaforów podaj c klucz (

key

).

27

53

Semafory w systemie Linux

Doł czane pliki nagłówkowe

4

(

5 6

4

(

. - 5 6

4

(

. - 5 6

4

(

. 5 6

Zwykle nie potrzebujemy tak silnych semaforów.
Dalej b dziemy u ywa semaforów binarnych zbudowanych

na bazie semaforów systemu Linux.

54

Semafory w systemie Linux

Implementowane funkcje semaforowe:

7

2

7

Tworzy semafor i zwraca jego ID. Procesy mog odwoływa si do

niego podaj c ten sam numer

sem_num

.

7

2

7

$

1

Ustawia warto semafora

sem_id

na

semVal

.

28

55

Semafory w systemie Linux

Implementowane funkcje semaforowe:

2

7

2

7

Usuwa identyfikator semafora. Nie usuwa semafora; inny proces

mo e nadal korzysta z semafora.

-

7 -

7

Wykonuje operacj

wait (inaczej P) na

sem_id

.

-

7 2

7

Wykonuje operacje

signal (inaczej V)

sem_id

.

56

Wywo

ł

anie systemowe

semget()

Funkcji semget() tworzy nowy zbiór semaforów lub udost pnia

zbiór ju istniej cy.
Wywołanie systemowe: semget();

7

$

$

9

:; !

< $

=

!>?

, /

@

5A

-

- <

$

<

!

<

< 5

, B

! <

!

-

C

:/D7 DE F G H &

! <

< $

! <

$

<

C

:/D7 F I DJ &

:/D7 DE F G H

!ł

-

-

$

! <

<

:/D7 F I DJ

ł

ł

! <

<

&

5

29

57

Semafory w systemie Linux

binSem.h

7

2

7

7

7

$ $ # K K K L

:/D7 DE F G H

58

Wywołanie systemowe semctl()

Funkcji

semctl() umo liwia sterowanie operacjami wykonywanymi na

zbiorze semaforów.

/

-

$

$

$

,

!

<

,

$

<

M -

?

, N

-

3

!

<

C

:/D7 +H G H & - !

?

7

-

!

!

=

5

C

:/D7 +F H &

=M - 7 -

7

=M @

- !

!

!

=

5

C

:/D7 E O :; &

! <

<

@

$

C

P F H 1 G J & - !

=M

$

C

P F H G JJ & - !

=

<

!

$

C

+F H 1 G J &

=M

=

-

-

2

$

C

+F H G JJ &

=

!

$

=

-

-

2

5

30

59

Semafory w systemie Linux

binSem.h

7

2

7

$

1

2

.8

=M

+F H 1 G J 8.

7

8!

.8 !

:/D7 +H G H * :/D7 +F H 8.

8

.8

!

P F H G JJ * +F H G JJ 8.

7

7

52

1

7 $ # $ +F H 1 G J$

7

,

#

60

Semafory w systemie Linux

binSem.h

2

7

2

7

2

.8

=M

+F H 1 G J 8.

7

8!

.8 !

:/D7 +H G H * :/D7 +F H 8.

8

.8

!

P F H G JJ * +F H G JJ 8.

7

7 $ # $ :/D7 E O :; $

7

,

-

$ QR

-

S Q

31

61

Wywo

ł

anie systemowe

semoop()

Funkcji semop() umo liwia wykonywanie operacji na zbiorze

semaforów
Wywołanie systemowe: semop();

/

-

-

$

!

8 - $

-

&

!

<

- ,

=

!?

<

!

!

$

< @

-

62

Struktura sembuf

!

7

.8

!

8.

7 -

.8 -

$

!

8.

7

.8

-

8.

Je li

sem_op

jest ujemna, wtedy proces wywołuj cy funkcj

semop() chce czeka , a warto semafora stanie si wi ksza ni

(lub taka sama jak) warto bezwzgl dna tego pola.
Je li

sem_op

jest dodatnia, to b dzie ona dodana do bie cej

warto ci semafora
Je li

sem_op

jest zerem, wtedy proces wywołuj cy funkcj

semop() chce czeka , a warto ci semafora stanie si zero.

32

63

Semafory w systemie Linux

binSem.h

-

7 -

7

!

7 !

7 !5 7

#

7 !5 7 -

, .8 / 8.

7 !5 7

+F O 7 T U ; V

-

7 $ *

7 !$

,

-

$ WX >@

-

7 -S Q

#

64

Semafory w systemie Linux

binSem.h

-

7 2

7

!

7 !

7 !5 7

#

7 !5 7 -

.8 1

8.

7 !5 7

+F O 7 T U ; V

-

7 $ *

7 !$

,

-

$ WX >@

-

7 2S Q

#

33

65

Semafory w systemie Linux

Przykład 1

4

(

!5 6

4

(

5 6

4

(

. - 5 6

4

(

. - 5 6

4

(

. 5 6

4

Q

! + 5

Q

7

66

Semafory w systemie Linux

Przykład 1

$

8

2

-

7

-7

YV Y

-

7

7

2

Z [ \

6

)

7

2

7 $

-

$ WX >@

S Q

"

F I :H 7 R G :JT E F

-7

YI Y

- Z

Wykonujemy

nast puj ce polecenia

>gcc ex1.c

> a.out 1 &

[1] 1082

> a.out

00XX00XX00XX0000

1083 finished

1082 finished

>

Wyj cie zawiera nieparzysta liczb X

Przeplatana nieparzyst liczba 0

Je li wywo-

łanie z linii

polece

zawiera

parametr,

to

Inicjowany

jest

semafor

34

67

Semafory w systemie Linux

Przykład 1

#

( # ''

)

-

7 -

7

"

F I :H 7 R G :JT E F

.8 -

@

8.

-

Q] Q$ -7

-

7

] [

- -

7

-

Q] Q$ -7

.8

8.

)

-

7 2

7

"

F I :H 7 R G :JT E F

-

7

] Z

- -

7

68

Semafory w systemie Linux

Przykład 1

-

QS ]

,

3

S Q$

-

6

- #

7

2

7

"

F I :H 7 +T DDF ++

Semafor usunie jedynie ten

proces, który otrzymał

parametr z linii polece .

35

69

Semafory w systemie Linux

Przykład 2

W tym przykładzie tworzony jest proces potomny.
Rodzic zanim utworzy proces potomny tworzy semafor i

inicjalizuje go..
Proces potomny i rodzic maj sekcje krytyczn .

Oba otwieraj w sekcji krytycznej ten sam plik.
Rodzic zapisuje do pliku dwa znaki P
Potomek zapisuje do pliku dwa zanki C

Ka da sekcja krytyczna wykonuje si w p tli. Jest ona powtarzana

10 razy zarówno przez rodzica, jak i potomka.

70

Semafory w systemie Linux

Przykład 2

4

Q! + 5 Q

7

$

8

2

-

7

-7

YD Y

R :JF 8

Q -Z 5 " Q

-

7

7

2

Z [ \

)

7

2

7 $

-

$ QR

-

S Q

"

F I :H 7 R G :JT E F

Rodzic tworzy

i inicjalizuje semafor

36

71

Semafory w systemie Linux

Przykład 2

#

#

( # ''

)

-

7 -

7

"

F I :H 7 R G :JT E F

.8 -

@

8.

-

$ Q Q

-

$ Q] Q$ -7

-

7

] [

- -

7

-

$ Q] Q$ -7

.8

8.

)

-

7 2

7

"

F I :H 7 R G :JT E F

-

7

] Z

- -

7

"

#

Kod potomka

Zapis do pliku

72

Semafory w systemie Linux

Przykład 2

-7

Y/Y

#

( # ''

)

-

7 -

7

"

F I :H 7 R G :JT E F

.8

8.

-

$ Q Q

-

$ Q] Q$ -7

-

7

] [

- -

7

-

$ Q] Q$ -7

.8

8.

)

-

7 2

7

"

F I :H 7 R G :JT E F

-

7

] Z

- -

7

Kod rodzica

Zpis do pliku

37

73

Semafory w systemie Linux

Przykład 2

U T JJ

-

QS ]

,

S Q$

-

7

2

7

"

F I :H 7 +T DDF ++

Rodzic usuwa

semafor po zako czeniu

procesu potownego

74

Semafory POSIX

Przykład – deklaracja semafora

4

(

-

5

6

7

Operacje na semaforze

4

(

-

5

6

7

7 8 $

-

$

2

7

7 8

7

7 8

7 -

7 8

7

2

7 8

$

8 2

7

7 8

38

75

Semafory POSIX

sem_init

inicjalizuje obiekt typu semafor wskazywany przez

sem

.

Pocz tkowa warto semafora ustawiana jest na

value

. Zmienna

pshared

wskazuje czy semafor jest lokalny wzgl dem bie cego

procesu (warto zero) lub dzielony z innymi procesami (warto

niezerowa).

sem_wait

zawiesza w tek wywołuj cy dopóki warto semafora

sem

ma warto niezerow . Je li to nast pi, to warto semafora

jest automatycznie zmniejszana.

sem_trywait

jest nieblokuj cym wariantem

sem_wait

. Je li

warto semafora jest niezerowa, to jego warto jest zmniejszana

od razu.

sem_post

automatycznie zwi ksza warto semafora (bez

blokowania).

sem_getvalue

umieszcza pod adresem

sval

aktualn warto

semafora

sem

.

sem_destroy

usuwa semafor

76

Semafory POSIX

.8 :

8.

.8 -

#

=

@

$ -

= -

8.

2

+ 7

7 8 $

-

$

2

7

$ -

$ 2

( #

-

Q+ 7

Q

.8 / -

8.

2

/

7 8

7

-

Q/Q

.8 1 -

8.

2

1

7 8

7 -

-

Q1 Q

39

77

Problem producenta-konsumenta z

jednoelementowym buforem

.8 !

5 , -

,

,

!

8.

4

^

--5 _

4

U :H F E + `

2

8-

2

8

2

8

2

8

!

.8

2

8.

7

.8

8.

7

-

-

7

7 -

-

7

7

.8

< 8.

+ 7

*

5 - $ #$

+ 7

*

5

$ #$ #

.8

@ <

8.

/

7

*

7 -

$ U T JJ$

-

$ U T JJ

/

7

*

7

$ U T JJ$

$ U T JJ

/

7

7-

$ U T JJ

/

7

7

$ U T JJ

"

#

78

Problem producenta-konsumenta (c.d.)

.8 @

-

8.

2

8-

2

8

$

# (U :H F E + ''

.8 -

8.

-

W -

] S Q$

.8

-

!

8.

/ *

5 -

5!

1 *

5

U T JJ

.8 @

8.

2

8

2

8

$

# (U :H F E + ''

.8

!

8.

/ *

5

5!

1 *

5 -

.8

8.

-

W

] S Q$

U T JJ

Pocz tkowo: empty = 1, full = 0.

40

79

Mechanizmy synchronizacji POSIX — zmienne

synchronizuj ce

Mechanizmy synchronizacji s cz ci standardu POSIX zwi zan

z obsług wielow tkowo ci.
Mechanizmy te powstały zatem na potrzeby synchronizacji

w tków i w takim kontek cie b d rozwa ane w dalszej cz ci

wykładu.
Rodzaje zmiennych synchronizuj cych:

muteks (zamek)

— umo liwiaj ca implementacj wzajemnego

wykluczania,

zmienna warunkowa

— umo liwia usypianie i budzenie w tków.

Zmienne synchronizuj ce musz by współdzielone przez

synchronizowane w tki.
Zanim zmienna zostanie wykorzystana do synchronizacji musi

zosta zainicjalizowana

80

Operacje na zmiennych synchronizuj cych

Zamki

s podobne do semaforów binarnych i u ywane s do

zapewnienie wzajemnego wykluczania.

Zmienne warunkowe

u ywane s wówczas, gdy stan przetwarzania

uniemo liwia w tkowi dalsze działanie i w tek musi wej w stan

oczekiwania
Zamek - umo liwia implementacj wzajemnego wykluczania.

Operacje:

lock — zaj cie (zaryglowanie) zamka
unlock — zwolnienie (odryglowanie) zamka
trylock — nieblokuj ca próba zaj cia zamka

Zmienna warunkowa - umo liwia usypianie i budzenie w tków.

Operacje:

wait — u pienie w tku,
signal — obudzenie jednego z u pionych w tków
broadcast — obudzenie wszystkich u pionych w tków

41

81

Zamek - podstawowe operacje

-

7

"7

-

7

"7 8

"$

-

7

"

7 8 !

7

! <

mutex – wska nik na zamek; obiekt_atrybutów – wska nik na

obiekt atrybutów mo e by NULL domy lnie
Zwraca: W Linuxie zawsze 0 (bo statyczny przydział pami ci)
Działanie: tworzy (inicjuje) zamek

82

Zamek - podstawowe operacje

-

7

"7

-

7

"7 8

"

zwraca: 0 (sukces) lub niezerowy kod bł du
działanie: zaj cie zamka; je li zamek był otwarty, to nast puje

jego zamkni cie i przyporz dkowanie mu wła ciciela; je li zamek

był zamkni ty, a zamkn go próbował w tek, nie b d cy jego

wła cicielem, to zawiesza dany w tek a do otwarcia w tku przez

wła ciciela.
Je eli próbował go zamkn ponownie wła ciciel, to:

blokada (ang. deadlock) w przypadku zamka szybkiego;
sygnał bł du w przypadku zamka sprawdzaj cego
zwi kszenie „licznika spustów” w przypadku zamka rekurencyjnego.

42

83

Zamek - podstawowe operacje

-

7

"7

-

7

"7 8

zwraca: 0 (sukces) lub niezerowy kod bł du
działanie: jak w przypadku pthread_mutex_lock, ale w sposób nie

blokuj cy w tku w przypadku niepowodzenia, tzn. zamiast

zawiesza w tek powoduje sygnalizacj bł du.

-

7

"7

-

7

"7 8

zwraca: jak wy ej
działanie: teoretycznie powinna likwidowa zamek i zwraca

systemowi zaj te zasoby. W Linuksie jedynie sprawdza, czy

zamek był otwarty (je li nie sygnalizuje bł du).

84

Zamek - podstawowe operacje

-

7

"7

-

7

"7 8

zwraca: jak wy ej
działanie: zwolnienie zamka (otwarcie zamka). Dokładniej:

je li pod zamkiem czekały jakie w tki, to jeden z nich (wybrany

losowo) zostaje uwolniony i przejmuje zamek na własno ,

zamykaj c go ponownie;
je eli aden w tek nie czekał, to zamek pozostaje otwarty i bez

wła ciciela;
w przypadku zamka sprawdzaj cego – otworzy mo e go tylko

wła ciciel.
w przypadku zamka rekurencyjnego – licznik zamkni zmniejszy

si o 1 (je li osi gnie 0 – zamek otwarty i bez wła ciciela).

43

85

Zmienna warunkowa – podstawowe operacje

Zmienna warunkowa jest obiektem typu pthread_cond_t
Zmienna warunkowa nie jest u ywana samodzielnie.

Ze wzgl du na ryzyko hazardu (ró nicy w działaniu w zale no ci od

kolejno ci operacji w przeplocie) pewne operacje na zmiennej

warunkowej musz by wykonywane sekcji krytycznej, chronionej

przez zamek.

Działanie zmiennej warunkowej kojarzone jest niekiedy z

semaforem. W operacjach semaforowych u ywa si czasami

takich samych nazw, czyli wait - opuszczanie oraz signal -

podnoszenie.

86

Zmienna warunkowa – podstawowe operacje

-

7

7

-

7

7 8

$

-

7

7 8 !

7

! <

zwraca: zawsze 0
działanie: uruchamia jeden z w tków (losowo wybrany), spo ród

czekaj cych pod dan zmienn warunkow (je eli aden nie

czeka, to funkcja nic nie robi)

-

7

7 !

-

7

7 8

zwraca: zawsze 0
działanie: jak wy ej, ale uwalnia wszystkie czekaj ce w tki

44

87

Zmienna warunkowa – podstawowe operacje

-

7

7

-

7

7 8

$

-

7

"7 8

zwraca: zawsze 0
działanie: wykonanie

NIEPODZIELNIE

dwie czynno ci: otwiera dany

zamek i zawiesza w tek pod dan zmienn warunkow ; aby funkcja

działała poprawnie, w tek ten powinien wcze niej zamkn dany zamek.

powrót z funkcji nast puje po (niedeterministycznym) uruchomieniu

w tku i powoduje automatyczne ponowne zamkni cie danego zamka.
Wywołanie funkcji pthread_cond_wait powoduje wej cie w tku w stan

oczekiwania na sygnał, który z kolei musi wysła inny w tek, wywołuj c

funkcj pthread_cond_signal lub pthread_cond_broadcast. Na czas

oczekiwania nast puje zwolnienie zamka, do którego wska nik

przekazywany jest jako drugi parametr funkcji pthread_cond_wait.
Jak mo na si domy la , funkcja ta wywoływana jest w sekcji

krytycznej.

88

Zmienna warunkowa – podstawowe operacje

-

7

7

-

7

7 8

zwraca: zawsze 0
działanie: obudzenie jednego z w tków u pionych na zmiennej

warunkowej
Obudzenie w tku nie musi oznacza natychmiastowego uzyskania

stanu gotowo ci.
W tek budzony musi jeszcze ponownie zaj zamek, który

zwolnił na czas oczekiwania. Je li zamek jest zaj ty musi

poczeka na jego zwolnienie.

45

89

Zasada funkcjonowania zmiennej warunkowej

Zasadnicza ró nica pomi dzy zmienna warunkow a semaforem

polega na tym, e

sygnał na zmiennej warunkowej budzi

oczekuj cy w tek lub jest ignorowany, je li aden w tek nie

oczekuje na tej zmiennej

.

Efekt operacji podnoszenia semafora jest natomiast

odzwierciedlany w stanie semafora i mo e by „skonsumowany”

przez pó niejsza operacj opuszczenia.
W przypadku zmiennej warunkowej istnieje zatem ryzyko hazardu

- je li w tek nie zd y usn na zmiennej warunkowej, mo na

straci sygnał, który miał go obudzi .

90

Zasada funkcjonowania zmiennej warunkowej

46

91

Klasyczne problemy synchronizacji

Problem ograniczonego bufora

Problem czytelników i pisarzy

Problem posilaj cych si filozofów.

92

Problem ograniczonego bufora

Dane dzielone

semaphore full, empty, mutex;

Pocz tkowo:

full = 0, empty = n, mutex = 1

47

93

Problem ograniczonego bufora dla procesu

producenta

do {

…

utwórz element w

nextp

…

wait(empty);

wait(mutex);

…

dodaj

nextp do bufora

…

signal(mutex);

signal(full);

} while (1);

94

Problem ograniczonego bufora dla procesu

konsumenta

do {

wait(full)
wait(mutex);

…

usu

element z bufora do

nextc

…

signal(mutex);
signal(empty);

…

konsumuj element w

nextc

…

} while (1);

48

95

Problem czytelników i pisarzy

Dwie grupy procesów:

czytelnicy i pisarze konkuruj o dost p do

wspólnego zasobu

- czytelni. Czytelnik odczytuje informacje

zgromadzone w czytelni i mo e to robi

razem z innymi

czytelnikami, natomiast pisarz zapisuje nowe informacje i musi

przebywa

sam w czytelni.

Mo liwe rozwi zania:

Czytelnik

powinien wej do czytelni

najszybciej jak to mo liwe.

Mo liwo zagłodzenia pisarzy!

Pisarz powinien wej do czytelni najszybciej jak to mo liwe.

Mo liwo

zagłodzenia czytelników!

Czytelnicy i pisarze wpuszczani s do czytelni na przemian, np. według

kolejno ci zgłosze , przy czym

pisarze wchodz pojedynczo, natomiast

wchodz cy

czytelnik mo e wpu ci do czytelni wszystkich czekaj cych

czytelników.

Brak zagłodzenia!

96

Dane dzielone

semaphore mutex, wrt;

Pocz tkowo

mutex = 1, wrt = 1, readcount = 0

Fragment kodu pisarza:

wait (wrt);

…

wykonywany jest zapis

…

signal(wrt);

Problem czytelników i pisarzy dla procesu

pisarza

49

97

Problem czytelników i pisarzy dla procesu

czytelnika

wait(mutex);
readcount++;
if (readcount == 1)

wait(rt);

signal(mutex);

…

wykonywany jest odczyt

…

wait(mutex);
readcount--;
if (readcount == 0)

signal(wrt);

signal(mutex):

98

Problem posilaj cych si filozofów

Pi ciu filozofów siedzi przy wspólnym okr głym stole i my li.

Co jaki czas filozofowie musz si posili . Przed ka dym
filozofem stoi talerz, a obok talerza widelec. Na rodku stołu stoi
półmisek z ryb .

Ryb nale y je dwoma widelcami, wi c filozof mo e zacz je
tylko wtedy, gdy b dzie miał obok siebie dwa wolne widelce.

Po spo yciu posiłku filozof odkłada oba widelce na stół i zatapia
si w my leniu.

50

99

Problem posilaj cych si filozofów

Dane dzielone

semaphore chopstick[5];

Pocz tkowo wszystkie dane zostały ustawione na 1

100

Problem posilaj cych si filozofów

i-ty filozof:

do {

wait(chopstick[i])
wait(chopstick[(i+1) % 5])

…

je

…

signal(chopstick[i]);
signal(chopstick[(i+1) % 5]);

…

my li

…

} while (1);

51

101

Problem posilaj cych si filozofów –

podsumowanie

Mo liwe rozwi zania:

Ka dy filozof czeka a jeden widelec (np. lewy) b dzie wolny i

podnosi go, a nast pnie czeka a b dzie wolny drugi widelec i te go

podnosi. Mo liwo zakleszczenia – ka dy filozof podniesie jeden

widelec.
Głodny filozof podnosi jednocze nie dwa widelce wtedy, gdy s

wolne. Mo liwo zagłodzenia – je li który z filozofów b dzie miał

„ arłocznych” s siadów, to nigdy dwa widelce obok jego talerza nie

b d wolne i nie b dzie mógł je , co oznacza, e zostanie

zagłodzony.
Nad procesem jedzenia filozofów czuwa lokaj, który dopuszcza do

rywalizacji o widelce tylko czterech filozofów naraz, a ci podnosz

widelce sekwencyjnie.

102

Problem pi cego fryzjera

Jeden proces fryzjera

i wiele procesów

klientów.
Współdzielone zasoby:

n krzeseł w poczekalni

i jedno krzesło fryzjera
Napisz program

koordynuj cy prac

fryzjera i klientów!

52

103

Regiony krytyczne

Mechanizmy synchronizacji wysokiego poziomu.
Zmienna dzielona

v typu T deklarowana jest nast puj co:

v: shared T

Zmienna

v dost pna jest tylko wewn trz instrukcji

region v when B do S

gdzie

B jest wyra eniem logicznym.

Podczas wykonywania si instrukcji

S aden inny proces nie

ma dostepu do zmiennej

v.

104

Regiony krytyczne

Regiony odwołuj ce si do dzielonych zmiennych

wykluczaj si wzajemnie w czasie.

Je li proces próbuje wykona instrukcje region, to pod

uwag brana jest warto wyra enia logicznego B. Je li B

jest prawdziwe, to instrukcja S jest wykonywana. Je li jest

nieprawdziwe, to wykonanie procesu jest odwlekane dot d,

dopóki B nie stanie si prawdziwe i w obr bie regionu

zwi zanego ze zmienna v nie b dzie znajdował si aden

inny proces.

53

105

Przykład – ograniczony bufor

Dane dzielone:

struct buffer {

int pool[n];
int count, in, out;

}

106

Ograniczony bufor procesu producenta

Proces producenta umieszcza

nextp w dzielonego bufora

buffer

region buffer when( count < n) {

pool[in] = nextp;
in:= (in+1) % n;
count++;

}

54

107

Ograniczony bufor procesu producenta

Proces konsumenta pobiera element z dzielonego bufora

buffer i i umieszcza go w nextc

region buffer when (count > 0) {

nextc = pool[out];

out = (out+1) % n;
count--;

}

108

Implementacja instrukcji region

x

when

B

do

S

Zwi z ka d zmienna dzielon x nast puj ce zmienne:

semaphore mutex, first-delay, second-delay;

int first-count, second-count;

Wzajemnie wykluczaj cy si dost p do sekcji krytyczna

zapewnia si dzi ki u yciu zmiennej

mutex.

Je li proces nie mo e wej do sekcji krytycznej, bo

wyra enie logiczne

B ma warto false, to pocz tkowo czeka

on na semafor

first-delay; do semafora second-delay

przesuwany jest w momencie, gdy posiada prawo ponownej

oceny warto ci wyra enia B.

55

109

Implementacja instrukcji region

x

when

B

do

S

Przechowuj informacje o liczbie procesów oczekuj cych

odpowiednio na semafor

first-delay i second-delay,

synchronizowana z

first-count i second-count.

Algorytm przyjmuje, e kolejka procesów oczekuj cych pod

semaforem jest uporz dkowana wg zasady FIFO.

Przypadku dowolnej innej zasady kolejkowania wymagane

mog by bardziej zło one mechanizmy implementacji.

110

Monitory

Mechanizmy synchronizacji wysokiego poziomu, które

pozwalaj na bezpieczne dzielenie abstrakcyjnych typów

danych pomi dzy współbie ne procesy.

monitor

monitor-name

{

deklaracje zmiennych dzielonych

procedure body

P1

(…) {

. . .

}

procedure body

P2

(…) {

. . .

}

procedure body

Pn

(…) {

. . .

}

{

kod inicjuj cy

}

}

56

111

Monitory

Aby zezwoli procesom na oczekiwanie wewnay\trz monitora,

zadeklarowa nale y zmienn

condition (warunek):

condition x, y;

Zmienna warunkowa mo e by u ywana z operacjami

wait i

signal.

Operacja

x.wait();

oznacza, e means proces wywołuj cy t operacj jest zawieszany

dot d, dopóki inny proxes nie wywoła operacji

x.signal();

Operacja

x.signal wznawia wykonywanie dokładnie jednego

procesu. Je li aden proces nie jest zawieszony, to wykonanie

operacji

signal nie ma adnego znaczenia.

112

Ilustracja idei monitora

57

113

Monitor ze zmiennymi warunkowymi

114

Przykład posilaj cych si filozofów

monitor dp
{

enum {thinking, hungry, eating} state[5];
condition self[5];
void pickup(int i)

// nast pny slajd

void putdown(int i)

// nast pny slajd

void test(int i)

// nast pny slajd

void init() {

for (int i = 0; i < 5; i++)

state[i] = thinking;

}

}

58

115

Posilaj cy si filozofowie

void dp::pickup(int i) {

state[i] = hungry;
test[i];
if (state[i] != eating)

self[i].wait();

}

void dp::putdown(int i) {

state[i] = thinking;
// sprawd

s siada po lewej i prawej

test((i+4) % 5);
test((i+1) % 5);

}

116

Posilaj cy si filozofowie

void dp::test(int i) {

if ( (state[(i + 4) % 5] != eating)

&& state[i] == hungry)

&& (state[(i + 1) % 5] != eating))

{

state[i] = eating;

self[i].signal();

}

}

59

117

Implementacja monitora przy u yciu

semaforów

Zmienne

semaphore mutex; // (initially = 1)

semaphore next; // (initially = 0)
int next-count = 0;

Ka da zewnetrzna procedura F zostanie zastapiona przez

instrukcje:

wait(mutex);

…

instrukcje procedury

F

;

…

if (next-count > 0)

signal(next)

else

signal(mutex);

Wewnatrz monitora zapewnione jest wzajemne

wykluczanie.

118

Monitory

Mechanizmy synchronizacji wysokiego poziomu, które

pozwalaj na bezpieczne dzielenie abstrakcyjnych typów

danych pomi dzy współbie ne procesy.

monitor

monitor-name

{

deklaracje zmiennych dzielonych

procedure body

P1

(…) {

. . .

}

procedure body

P2

(…) {

. . .

}

procedure body

Pn

(…) {

. . .

}

{

kod inicjuj cy

}

}

60

119

Monitory

Aby zezwoli procesom na oczekiwanie wewnay\trz monitora,

zadeklarowa nale y zmienn

condition (warunek):

condition x, y;

Zmienna warunkowa mo e by u ywana z operacjami

wait i

signal.

Operacja

x.wait();

oznacza, e means proces wywołuj cy t operacj jest zawieszany

dot d, dopóki inny proxes nie wywoła operacji

x.signal();

Operacja

x.signal wznawia wykonywanie dokładnie jednego

procesu. Je li aden proces nie jest zawieszony, to wykonanie

operacji

signal nie ma adnego znaczenia.

120

Ilustracja idei monitora

61

121

Monitor ze zmiennymi warunkowymi

122

Przykład posilaj cych si filozofów

monitor dp
{

enum {thinking, hungry, eating} state[5];
condition self[5];
void pickup(int i)

// nast pny slajd

void putdown(int i)

// nast pny slajd

void test(int i)

// nast pny slajd

void init() {

for (int i = 0; i < 5; i++)

state[i] = thinking;

}

}

62

123

Posilaj cy si filozofowie

void dp::pickup(int i) {

state[i] = hungry;
test[i];
if (state[i] != eating)

self[i].wait();

}

void dp::putdown(int i) {

state[i] = thinking;
// sprawd

s siada po lewej i prawej

test((i+4) % 5);
test((i+1) % 5);

}

124

Posilaj cy si filozofowie

void dp::test(int i) {

if ( (state[(i + 4) % 5] != eating)

&& state[i] == hungry)

&& (state[(i + 1) % 5] != eating))

{

state[i] = eating;

self[i].signal();

}

}

63

125

Implementacja monitora przy u yciu

semaforów

Zmienne

semaphore mutex; // (initially = 1)

semaphore next; // (initially = 0)
int next-count = 0;

Ka da zewnetrzna procedura F zostanie zastapiona przez

instrukcje:

wait(mutex);

…

instrukcje procedury

F

;

…

if (next-count > 0)

signal(next)

else

signal(mutex);

Wewnatrz monitora zapewnione jest wzajemne

wykluczanie.

126

Implementacja monitora

Dla ka dej zmiennej warunkowej

x mamy:

semaphore x-sem; // (initially = 0)
int x-count = 0;

Operacj

x.wait mo na zaimplementowa nast puj co:

x-count++;
if (next-count > 0)

signal(next);

else

signal(mutex);

wait(x-sem);
x-count--;

64

127

Implementacja monitora

Operacja

x.signal mo e by z kolei zaimplementowana

nast pujaco:

if (x-count > 0) {

next-count++;
signal(x-sem);
wait(next);
next-count--;

}

128

Implementacja monitora

Instrukcja warunkowego oczekiwania:

x.wait(c)

c – wyra enie całkowitoliczbowe obliczane w momencie, gdy

wykonywana jest operacja wait.
warto c (warto priorytetu) przechowywana ł cznie nazw

procesu, który jest zawieszany.
Gdy wykonywana jest operacja

x.signal, to proces jako nast pny

wznawiany jest proces o najmniejszej skojarzonej z nim warto ci

priorytetu.

Sprawdzenie dwóch warunków w celu ustanowienia poprawno ci

systemu:

Procesy u ytkownika musz zawsze odwoływa si do monitora we

wła ciwej kolejno ci.
Musi istnie pewno , e nie współpracuj ce procesy nie ignoruj

wzajemnie wykluczaj cych si wej , zapewnianych przez monitor

oraz, e nie b d próbowa dosta si do dzielonych zasobów

bezpio rednio z pomini ciem protokołu dost pu.

65

129

Synchronizacja w systemie Solaris

W celu kontrolowania dost pu do sekcji krytycznych w systemie Solaris

zaimplementowano:

zamki adaptacyjne, zmienne warunkowe,

semafory, blokady do czytania lub pisania oraz turnikety.

Zamek adaptacyjny (adaptive mutex) - stosowany do ochrony krytycznych

danych dla krótkich segmentów kodu.

•

W systemach jednoprocesorowych w tek wstrzymany przez zamek adaptacyjny

jest usypiany.

•

W systemach wieloprocesorowych w tek jest usypiany tylko wtedy, gdy

utrzymuj cy zamek jest nieaktywny, w przeciwnym razie zamek realizuje

aktywne czekanie (

wiruj c blokad )

Do synchronizacji dłu szych segmentów kodu u ywane s

zmienne

warunkowe i semafory - czekaj ce w tki s usypiane.
Blokady do czytania i pisania (readers-writers locks) stosuje si do ochrony

danych o cz stym dost pie, zwykle do czytania - mo liwo współbie nego

czytania przez wiele w tków (s kosztowne w realizacji).
Turnikety (turnstiles) słu do porz dkowania listy w tków czekaj cych na

pozyskanie zamka adaptacyjnego albo blokady do czytania lub pisania - s to

struktury kolejek zawieraj ce w ¹ tki zablokowane na zamku lub blokadzie.

130

Synchronizacja w MS Windows XP

W systemie jednoprocesorowym j dro si gaj c po jaki zasób globalny

maskuje czasowo przerwania.
W systemie wieloprocesorowym dost p do zasobów globalnych

chroniony jest za pomoc wiruj cych blokad.
Do synchronizacji w tków poza j drem słu obiekty dyspozytora.

U ywaj c obiektu dyspozytora w tek mo e korzysta z ró nych

mechanizmów synchronizacji: zamki (muteksy), semafory, zdarzenia, itd.
Zdarzenia (events) - mechanizm synchronizacji podobny do zmiennych

warunkowych (mog powiadamia w tek o spełnieniu danego warunku).

Obiekty dyspozytora mog znajdowa si w stanie sygnalizowania

(signaled) lub niesygnalizowania (nonsignaled).

Stan sygnalizowania oznacza, e obiekt jest dost pny i w tek nie zablokuje

si przy próbie jego pozyskania.
Stan niesygnalizowania wskazuje, e obiekt nie jest dost pny i przy próbie

jego pozyskania w tek zostanie zablokowany.
Istnieje zwi zek mi dzy stanem obiektu dyspozytora a stanem w tku:

sygnalizowany/niesygnalizowany obiekt - w tek w stanie

gotowo ci/czekania.

66

131

Synchronizacja w systemie Linux

J dro Linuxa jest niewywłaszczalne - proces wykonywany w trybie j dra

nie mo e zosta wywłaszczony przez proces o wy szym priorytecie,

dzi ki czemu nie pojawia si szkodliwa rywalizacja przy dost pie do

struktur danych j dra.
W trakcie wykonywania procesu w trybie j dra mog pojawia si

przerwania.

W przypadku krótkich sekcji krytycznych Linux wył cza przerwania na czas

trwania tych sekcji.
Dla dłu szych sekcji krytycznych Linux u ywa semaforów do ochrony

danych j dra.

W systemach wieloprocesorowych dzielone struktury danych j dra

chronione s za pomoc wiruj cych blokad.
Synchronizacja P-w tków
Interfejs Pthreads API dostarcza muteksów i zmiennych warunkowych

jako mechanizmów synchronizacji w tków standardu POSIX.
Wiele systemów implementuj cych P-w tki dostarcza ponadto

semaforów.

DZI KUJ PA STWU

DZI KUJ PA STWU

Je li s pytania, to z

Je li s pytania, to z

przyjemno ci na nie

przyjemno ci na nie

odpowiemy

odpowiemy