Systemy operacyjne / Współbie Ŝ no ść : blokady i zagłodzenia 1 Współbie Ŝ no ść : blokady i zagłodzenia Systemy operacyjne / Współbie Ŝ no ść : blokady i zagłodzenia 2 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 Systemy operacyjne / Współbie Ŝ no ść : blokady i zagłodzenia 3 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. 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 / Współbie Ŝ no ść : blokady i zagłodzenia 4 Systemy operacyjne / Współbie Ŝ no ść : blokady i zagłodzenia 5 Systemy operacyjne / Współbie Ŝ no ść : blokady i zagłodzenia 6 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, Przykład z przekazywaniem komunikatów • proces A:
(…)
… przekroczyć ogólnej liczby zasobów w systemie,
2. kiedy P zamawia zbiór Za, wtedy system musi określić, czy ich
przydzielenie pozostawi system w stanie bezpiecznym. Jeśli tak, to Za
zostaną przydzielone; w przeciwnym razie P→ Z, aŜ inne P nie
zwolnią wystarczającej ilości Za
• w implementacji algorytmu bankiera występuje kilka struktur danych,
struktury te przechowują stan przydziału zasobów.
Niech:
n będzie liczbą procesów w systemie,
m będzie liczbą typów zasobów.
20
Systemy operacyjne / WspółbieŜność: blokady i zagłodzenia
21
Wprowadza się następujące struktury danych:
Dostępne
Maksymalne
Przydzielone
Potrzebne
Przyjmijmy, Ŝe wiersze w tablicach:
Przydzielone i Potrzebne moŜemy uwaŜać za wektory i odwoływać się do
nich odpowiednio Przydzielone[i] oraz Potrzebne[i].
Wektor o długości m, określający liczbę…
… mu się ten Za i przydziela
Systemy operacyjne / WspółbieŜność: blokady i zagłodzenia
procesowi aktualnie zamawiającemu. Jeśli Za nie jest ani dostępny,
ani przetrzymywany przez inny czekający proces, to P→ Z.
Protokół ten często stosuje się do zasobów, których stan moŜna łatwo
przechować i później odtworzyć, jak np. rejestry procesora, czy
obszary pamięci. Na ogół nie moŜna go stosować do takich zasobów,
jak drukarki…
…. Gwarantowało
16
Systemy operacyjne / WspółbieŜność: blokady i zagłodzenia
17
to niespełnienie przynajmniej jednego z WKB, wobec czego blokada nie
mogła wystąpić. Wadą tych algorytmów jest słabe wykorzystanie
urządzeń i ograniczona przepustowość systemu.
• liczbę dostępnych i przydzielonych zasobów,
• maksymalne zapotrzebowanie P.
Stan jest bezpieczny, jeśli istnieje porządek, w którym system operacyjny
moŜe…
... zobacz całą notatkę
Komentarze użytkowników (0)