Wzajemne wykluczanie — przynajmniej jeden zasób musi być niepodzielny, czyli używanie egzemplarza tego zasobu przez jeden proces uniemożliwia używanie go przez inny proces do czasu zwolnienia.
Przetrzymywanie i oczekiwanie — proces, któremu przydzielono jakieś jednostki, oczekuje na dodatkowe jednostki blokowane przez inny proces.
Brak wywłaszczeń — jednostki zasobu zwalniane są tylko z inicjatywy odpowiednich procesów.
Cykl w oczekiwaniu — istnieje podzbiór {P1, ..., Pk} ⊆ P taki, że P1 czeka na jednostkę zasobu przetrzymywaną przez P2, P2 na jednostkę przetrzymywany przez P3, ..., Pk czeka na jednostkę przetrzymywany przez P1.
Proces Pi jest wstrzymany (zablokowany) w stanie systemu σ, jeśli wszystkie dopuszczalne zdarzenia w systemie mają miejsce w innych procesach niż Pi.
Proces Pi jest zakleszczony w stanie σ, jeśli jest wstrzymany w stanie σ i w każdym stanie osiągalnym ze stanu σ.
shared numer: Integer := i;
while numer ≠ i do ← sekcja wejściowa
nic;
sekcja krytycznai;
numer := j; ← sekcja wyjściowa
function test&set(var l: Boolean): Boolean;
begin
test&set := l;
l := true;
end;
procedure exchange(var a,b: Boolean);
var tmp: Boolean;
begin
tmp := a;
a := b;
b := tmp;
end;
shared zamek: Boolean := false;
while test&set(zamek) do ← sekcja wejściowa
nic; ← sekcja wejściowa
sekcja krytyczna;
zamek := false; ← sekcja wyjściowa
reszta;
shared zamek: Boolean := false;
local klucz: Boolean;
klucz := true; ← sekcja wejściowa
repeat exchange(zamek, klucz); ← sekcja wejściowa
until klucz = false; ← sekcja wejściowa
sekcja krytyczna;
zamek := false; ← sekcja wyjściowa
reszta;
// czyli wraz ze stronicowaniem jak myślę. //
Grafy przepływu procesów przedstawiają zależności czasowe wykonywania procesów. Wierzchołki tych grafów reprezentują chwile czasu, natomiast krawędzie zorientowane - procesy. Dwa wierzchołki są połączone krawędzią zorientowaną (łukiem) jeżeli istnieje proces, którego moment rozpoczęcia odpowiada pierwszemu wierzchołkowi, a moment zakończenia - drugiemu.
Graf przepływu procesów jest dobrze zagnieżdżony, jeżeli może być opisany przez funkcje P(a,b) i S(a,b) lub ich złożenie, gdzie P(a,b) i S(a,b) oznaczają odpowiednio wykonanie równoległe i szeregowe procesów a i b.
Przykład
Przedstawić graf przepływu procesów
odpowiadających wyznaczeniu wyrażenia
y := ( a + b )2–(c + d )(e – f)
Współbieżne wykonanie może być specyfikowane za pomocą operatora and, który łączy dwa wyrażenia wykonywane współbieżnie.
Zastosowanie notacji and do implementacji programu wyznaczającego wartość wyrażenia:
(a+b)2– (c+d)(e–f)
Wszystkie wyrażenia ujęte w nawiasy parbegin – parend są wykonywane współbieżnie
Załóżmy, że w systemie dostępna jest instrukcja typu testandset (a, b), która w sposób atomowy (niepodzielny) dokonuje odczytu zmiennej b, zapamiętania wartości tej zmiennej w zmiennej a oraz przypisania zmiennej b wartości true.
testandset(a, b) is equivalent to :
------------------
a := b;
b := True;
------------------
nottestandset(a, b) is equivalent to :
------------------
a := b;
b := False;
------------------
Semaforem nazywamy zmienną chronioną, na ogół będącą nieujemną zmienną typu integer, do której dostęp (zapis i odczyt) możliwy jest tylko poprzez wywołanie specjalnych funkcji (operacji) dostępu i inicjacji.
Wyróżnia się semafory:
binarne
przyjmujące tylko wartość 0 lub 1,
ogólne (licznikowe)
mogą przyjąć nieujemną wartość całkowitoliczbową.
// Z tego co myślę to jest z użyciem semafora //
Semafory binarne Sb mogą przyjmować tylko dwie wartości: 0 i 1.
Przez Pb i Vb oznaczone są operacje na semaforach binarnych odpowiadające operacjom P i V .
Definicja Pb jest taka sama jak P, natomiast definicja Vb różni się od V tylko tym, że Vb nie zmienia wartości semafora binarnego jeśli miał on wartość 1.
Opuszczanie semafora
Procedure P (var s:Binary_semaphore)
Begin
while not s do nic;
S:=false;
End;
Podnoszenie semafora
Procedure V (var s:Binary_semaphore)
Begin
S:=true;
End;
Niech następująca deklaracja zmiennej v typu T określa zmienną dzieloną przez wiele procesów.
var v: shared T;
Zmienna v będzie dostępna tylko w obrębie instrukcji region o następującej postaci:
region v do S;
Przez zakleszczenie (ang. deadlock) rozumieć będziemy formalnie stan systemu, w którym spełniany jest następujący warunek:
gdzie W jest zbiorem indeksów (lub zbiorem zadań)
Mówimy, że system jest w stanie zakleszczenia (w systemie wystąpił stan zakleszczenia), jeżeli istnieje niepusty zbiór W zadań, które żądają przydziału dodatkowych zasobów nieprzywłaszczalnych będących aktualnie w dyspozycji innych zadań tego zbioru.
Innymi słowy, system jest w stanie zakleszczenia, jeżeli istnieje niepusty zbiór W zadań, których żądania przydziału dodatkowych zasobów nieprzywłaszczalnych nie mogą być spełnione nawet jeśli wszystkie zadania nie należące do W zwolnią wszystkie zajmowane zasoby.
Jeżeli W≠∅, to zbiór ten nazywamy zbiorem zadań zakleszczonych.
Warunkami koniecznymi wystąpienia zakleszczenia są:
Wzajemne wykluczanie (ang. mutual exclusion condition),
W każdej chwili zasób może być przydzielony co najwyżej jednemu zadaniu.
Zachowywanie zasobu (ang. wait for condition),
Proces oczekujący na przydzielenie dodatkowych zasobów nie zwalnia zasobów będących aktualnie w jego dyspozycji.
Nieprzywłaszczalność (ang. non preemption condition),
Zasoby są nieprzywłaszczalne tzn. ich zwolnienie może być zainicjowane jedynie przez proces dysponujący w danej chwili zasobem.
Istnienie cyklu oczekiwań (ang. circular wait condition),
Występuje pewien cykl procesów z których każdy ubiega się o przydział dodatkowych zasobów będących w dyspozycji kolejnego procesu w cyklu.
Konstrukcje systemów immanentnie wolnych od zakleszczenia (construction of deadlock free systems)
Podejście to polega w ogólności na wyposażeniu systemu w taką liczbę zasobów, aby wszystkie możliwe żądania zasobowe były możliwe do zrealizowania. Przykładowo, uzyskuje się to, gdy liczba zasobów każdego rodzaju jest nie mniejsza od sumy wszystkich maksymalnych i możliwych jednocześnie żądań.
Detekcja zakleszczenia i odtwarzanie stanu wolnego od zakleszczenia (detection and recovery).
W podejściu detekcji i odtwarzania, stan systemu jest periodycznie sprawdzany i jeśli wykryty zostanie stan zakleszczenia, system podejmuje specjalne akcje w celu odtworzenia stanu wolnego do zakleszczenia.
Unikanie zakleszczenia (avoidance).
W podejściu tym zakłada sie znajomość maksymalnych żądań zasobowych. Każda potencjalna tranzycja stanu jest sprawdzana i jeśli jej wykonanie prowadziłoby do stanu niebezpiecznego, to żądanie zasobowe nie jest w danej chwili realizowane.
Zapobieganie zakleszczeniu (prevention)
W ogólności podejście to polega na wyeliminowaniu możliwości zajścia jednego z warunków koniecznych zakleszczenia.
Dany jest zbiór procesów sekwencyjnych komunikujących się przez wspólną pamięć. Każdy z procesów zawiera sekcję krytyczną, w której następuje dostęp do wspólnej pamięci. Procesy te są procesami cyklicznymi
Zakłada się ponadto:
1.Zapis i odczyt wspólnych danych jest operacją niepodzielną, a próba jednoczesnych zapisów lub odczytów
realizowana jest sekwencyjnie w nieznanej kolejności.
2.Sekcje krytyczne nie mają priorytetu.
3.Wzgledne prędkości wykonywania procesów są nieznane.
4.Proces może zostać zawieszony poza sekcją krytyczną.
5.Procesy realizujące instrukcje poza sekcją krytyczną nie mogą uniemożliwiać innym procesom
wejścia do sekcji krytycznej.
6. Procesy powinny uzyskać dostęp do sekcji krytycznej w skończonym czasie.
Przy tych założeniach należy zagwarantować, że w każdej chwili czasu najwyżej jeden proces
jest w sekcji krytycznej.
Opuszczanie semafora
Procedure P(var s: semaphore)
Begin
While s = 0 do nic;
S := s – 1;
End;
Podnoszenie semafora
Procedure V (var s: Semaphore)
Begin
S := s + 1
End;
Opuszczanie semafora
Procedure P (var s: Binary_Semaphore)
Begin
while not s do nic;
s := false;
end;
Podnoszenie semafora
Procedure V (var s: Binary_Semaphore)
Begin
S := true;
End;
Shared mutex: Semaphore := 1;
P(mutex); <- sekcja wejściowa
Sekcja krytyczna;
V(mutex); <- sekcja wyjściowa
Reszta;
Producent
Local i: Integer := 0;
Local elem: ElemT;
While . . . do Begin
Produkuj(elem)
P(wolne)
Buf[i] := elem;
I := (i+1) mod n;
V(zajety)
End;
Konsument
Local i: integer := 0;
Local elem: ElemT;
While … do Begin
P(zajety)
Elem := buf[i];
I := (i+1) mod n;
V(wolne);
Konsumuj(elem);
End:
Czytelnik
while ... do begin
P(mutex_r);
l_czyt := l_czyt + 1; if l_czyt = 1 then P(mutex_w);
V(mutex_r);
czytanie;
P(mutex_r);
l_czyt := l_czyt - 1; if l_czyt = 0 then V(mutex_w);
V(mutex_r);
end;
Pisarz
while ... do
P(mutex_w);
pisanie;
V(mutex_w);
end;
Filozof nr i (i = 0 ... 4)
while ... do begin
myślenie;
P(dopuść);
P(widelec[i]);
P(widelec[(i+1) mod 5]);
jedzenie;
V(widelec[i]);
V(widelec[(i+1) mod 5]);
V(dopuść);
end;
Klient
while ... do begin
P(mutex);
if l_czek < p then begin
l_czek := l_czek + 1; V(klient);
V(mutex);
P(fryzjer);
strzyżenie;
end
else V(mutex);
end;
Fryzjer
while ... do begin
P(klient);
P(fotel);
P(mutex);
l_czek := l_czek - 1;
V(fryzjer);
V(mutex);
strzyżenie;
V(fotel);
end;
Dane współdzielone
shared buf: Buffer;
Producent
local
elem: ElemType;
while ... do begin
produkuj(elem);
buf.wstaw(elem);
end;
Konsument
local
elem: ElemType;
while ... do begin
buf.pobierz(elem);
konsumuj(elem);
end;
• Dane współdzielone
shared czytelnia: Monitor;
• Czytelnik
czytelnia.wejście_czytelnika;
czytanie;
czytelnia.wyjście_czytelnika;
• Pisarz
czytelnia.wejście_pisarza;
pisanie;
czytelnia.wyjście_pisarza;
• Producent
local elem: ElemT;
while ... do
begin
produkuj(elem);
region buf when buf.licz < n do
begin
buf.pula[wej]:= elem;
buf.wej := (buf.wej+1) mod n;
buf.licz := buf.licz + 1;
end;
end;
• Konsument
local elem: ElemT;
while ... do
begin
region buf when buf.licz > 0 do
begin
elem := buf.pula[wyj];
buf.wyj := (buf.wyj+1) mod n;
buf.licz := buf.licz - 1;
end;
konsumuj(elem);
end;