1 Jarosław Kuchta Semafory

2 Operacje podniesienie semafora opuszczenie semaforaOperacje są niepodzielne (atomowe), tzn. że żadna z tych operacji nie może zostać przerwana.

3 Rodzaje semaforów ogólny binarny ograniczony uogólniony

4 Semafor ogólny (definicja klasyczna Dijkstry)Zmienna całkowita S: podniesienie – V(S): S = S + 1; opuszczenie – P(S): while (S<=0); S = S – 1; Nie spełnia warunku niepodzielności

5 Semafor ogólny (definicja praktyczna BenAriego)Zmienna całkowita S: podniesienie – V(S): if (są procesy wstrzymane podczas opuszczania S) wznów jeden z nich; else S = S +1; opuszczenie – P(S): if (S>0) S = S – 1; wstrzymaj; Spełnia warunek niepodzielności

6 Konstrukcja semafora Opuszczenie Podniesienie Proces A Proces B P(S):V(S): S = 0 ktoś czeka S = S - 1 S = S + 1

7 Semafor binarny (definicja klasyczna)Zmienna logiczna S: podniesienie – VB(S): S = 1; opuszczenie – PB(S): while (S==1); S = 0;

8 Semafor binarny (definicja praktyczna)Zmienna logiczna S: podniesienie – VB(S): if (są procesy wstrzymane podczas opuszczania S) wznów jeden z nich; else S = 1; opuszczenie – PB(S): if (S==1) S = 0; wstrzymaj;

9 Semafor binarny a ogólnySemafor binarny NIE jest szczególnym przypadkiem semafora ogólnego. Semafor binarny nie pamięta liczby operacji podniesienia. Semafor binarny może zastąpić ogólny, gdy realizuje wzajemne wykluczanie. Podniesienie już podniesionego semafora binarnego jest błędem.

10 Semafor dwustronnie ograniczonyZmienna całkowita S z zakresu (0..N): podniesienie – V(S): if (S==N) wstrzymaj; else if (są procesy wstrzymane podczas opuszczania S) wznów jeden z nich; else S = S + 1; opuszczenie – P(S): if (S==0) S = S – 1;

11 Semafor uogólniony Operacje podniesienia i opuszczenia mają dodatkowy operand n podniesienie – V(S, n): if (są procesy wstrzymane podczas opuszczania S o m) { wznów jeden z nich; S = S – m + n; } else S = S + n; opuszczenie – P(S, n): if (S >= n) S = S – n; wstrzymaj;

12 Jednoczesne operacje semaforoweKoniunktywna PAND (S1, S2): if (S1 > 0 && S2 > 0) { S1 = S1 – 1; S2 = S2 – 1; } else wstrzymaj; Alternatywna POR (S1, S2): if (S1 > 0 || S2 > 0) { S1 = S1 – 1; S2 = S2 – 1; } else wstrzymaj;

13 Przykłady Producenci i konsumenci Czytelnicy i pisarzePięciu filozofów

14 1 producent i 1 konsument Semaphore Wolne = N; Semaphore Pełne = 0;Dane[] bufor = new Dane[N]; void Producent () { Dane dane; int i = 0; while (true) Produkuj (out dane); P(Wolne); bufor [i] = dane; i = (i + 1) % N; V(Pełne); } void Konsument () { Dane dane; int j = 0; while (true) P(Pełne); dane = bufor [j]; j = (j + 1) % N; V(Wolne); Konsumuj (dane); }

15 Wielu producentów i konsumentówSemaphore Wolne = N; Semaphore Pełne = 0; Dane[] bufor = new Dane[N]; int j = 0; int k = 0 BinarySemaphore i_S = 1; BinarySemaphore j_S = 1; void Producent () { Dane dane; while (true) Produkuj (out dane); P(Wolne); PB(i_S); bufor [i] = dane; i = (i+1) % N; VB(i_S); V(Pełne); } void Konsument () { Dane dane; while (true) P(Pełne); PB(j_S); dane = bufor [j]; j = (j+1) % N; VB(j_S); V(Wolne); Konsumuj (dane); }

16 Czytelnicy i pisarze int M; // liczba czytelnikówint P; // liczba pisarzy Semaphore Wolne = N; // liczba miejsc w czytelni BinarySemaphore W = 1; // wzajemne wykluczanie się pisarzy void Czytelnik () { while (true) Własne_Sprawy(); P(Wolne); Czytanie(); V(Wolne); } void Pisarz () { while (true) Własne_Sprawy(); PB(W); // Pisarz stopniowo zajmuje miejsca // w czytelni for (int j=0; j Pisanie(); VB(W); }

17 Pięciu filozofów (z możliwością zagłodzenia)BinarySemaphore[] Pałeczki = new BinarySemaphore[] {1, 1, 1, 1, 1}; void Filozof(int i) { while (true) Myślenie(); PB(Pałeczki, i); PB(Pałeczki, (i+1) % 5); Jedzenie(); VB(Pałeczki, i); VB(Pałeczki, (i+1) % 5); }

18 Pięciu filozofów (z lokajem)BinarySemaphore[] Pałeczki = new BinarySemaphore[] {1, 1, 1, 1, 1}; Semaphore Lokaj = 4; void Filozof(int i) { while (true) Myślenie(); P(Lokaj); PB(Pałeczki, i); PB(Pałeczki, (i+1) % 5); Jedzenie(); VB(Pałeczki, i); VB(Pałeczki, (i+1) % 5); V(Lokaj); }