Systemy operacyjne /
Współbieżność: blokady i zagłodzenia
System komputerowy składa się ze skończonej liczby zasobów, o które ubiega się
pewna liczba procesów. Jeżeli pewien proces zamówi zasób, a zasób nie jest
dostępny, to proces przechodzi w stan zawieszenia Z,
Sytuację, w której oczekujące procesy nigdy nie zmienią swego stanu, ponieważ
zamówione przez nie zasoby są przetrzymywane przez inne procesy, nazywamy
blokadą (ang. deadlock).
Założenia odnośnie rozpatrywanego modelu
całość zasobów dzieli się na kilka grup, z których każda zawiera pewną liczbę
identycznych egzemplarzy,
proces powinien zamówić zasób przed jego użyciem i zwolnić go po
wykorzystaniu,
proces może żądać tyle zasobów, ile ich potrzebuje do wykonania zadania,
przy czym nie potrzebuje ich więcej niż jest dostępne w systemie.
Kolejne kroki podczas korzystania z zasobu
1.
zamówienie, jeśli nie może być spełnione, to proces Z,
2.
korzystanie z zasobu (np. czytanie z pliku),
3.
zwolnienie zasobu.
Systemy operacyjne /
Definicja blokady
Zbiór procesów pozostaje w stanie blokady, jeżeli każdy proces z tego zbioru czeka
na zdarzenie, które może być spowodowane tylko przez inny proces z tego samego
zbioru.
Najczęściej zdarzenia te dotyczą przydzielania i zwalniania zasobów, takich jak:
zasoby fizyczne (drukarki, miejsce w pamięci, cykle procesora),
zasoby logiczne (pliki, semafory).
Systemy operacyjne /
Przykład z alokacją pamięci
dwa procesy żądają przydziału pamięci,
liczba dostępnej pamięci: 200kB,
proces A:
o żądanie przydziału 80kB,
o żądanie przydziału 60kB,
proces B:
o żądanie przydziału 70kB,
o żądanie przydziału 80kB,
proces B:
o receive( A, M2),
o send( A, M1),
Przykład z przekazywaniem komunikatów
proces A:
o receive( B, M1),
o send( B, M2),
Systemy operacyjne /
Warunki konieczne istnienia blokady
Sytuacja blokady może powstać wtedy i tylko wtedy, gdy w systemie są jednocześnie
spełnione cztery warunki (WKB):
1.
wzajemne wykluczanie
Przynajmniej jeden zasób musi być niepodzielny, tzn. że zasobu tego może
używać w danym czasie tylko jeden proces. Jeżeli inny proces zamawia dany
zasób, to jest zawieszany do czasu, aż zasób zostanie zwolniony.
2.
przetrzymywanie i oczekiwanie
Musi istnieć proces mający przydzielony co najmniej jeden zasób i oczekujący
na przydział dodatkowego zasobu, który jest przetrzymywany przez inny
proces.
3. Brak wywłaszczeń
Zasoby nie podlegają wywłaszczaniu, tzn., że zasób może zostać zwolniony
tylko z inicjatywy przetrzymującego go procesu, po zakończeniu działania tego
procesu.
4.
Czekanie cykliczne
Musi istnieć zbiór {Po,P1,...,Pn} czekających procesów (w stanie Z)
takich, że
Po czeka na zasób przetrzymywany przez proces P1
P1 czeka na zasób przetrzymywany przez proces P2
..
Pn czeka na zasób przetrzymywany przez proces Po
warunek czekania cyklicznego 4. implikuje warunek 2., więc warunki te nie są
zupełnie niezależne. Rozpatrywanie ich z osobna jest jednak wygodne.
Graf przydziału zasobów
... zobacz całą notatkę
Komentarze użytkowników (0)