Co to jest zakleszczenie w systemie operacyjnym: warunki i algorytm wykrywania

Wypróbuj Nasz Instrument Do Eliminowania Problemów





Głównym celem systemu operacyjnego jest zapewnienie właściwej komunikacji między zasobami sprzętowymi i programowymi, a także udostępnianie wspólnych usług programom. Gdy proces systemu operacyjnego chce uzyskać dostęp do dowolnego zasobu, najpierw wysyła żądanie do określonego zasobu, do którego chce uzyskać dostęp, następnie wykorzystuje ten zasób i ostatecznie zwalnia zasób po użyciu. Przypuśćmy, że wiele procesów próbuje uzyskać dostęp do jednego zasobu w tym samym czasie, trudno jest zapewnić jeden zasób wszystkim procesom na raz, w takiej sytuacji pojawia się koncepcja zwana zakleszczeniem. Dlatego w tym artykule opisano, jak dochodzi do zakleszczenia i jak przezwyciężyć tę sytuację.

Co to jest impas w systemie operacyjnym?

Definicja: Dead-Lock to sytuacja, w której co najmniej dwa procesory czekają na wystąpienie jakiegoś zdarzenia, ale takie zdarzenia, które się nie zdarzają, są stanem zakleszczenia i mówi się, że procesory są w stanie zakleszczenia. Na przykład załóżmy scenariusz czasu rzeczywistego, w którym na drodze jednokierunkowej jeżdżą dwa samochody A i B, którymi kieruje dwóch indywidualnych kierowców. Teraz pojawia się sytuacja, w której kierowca samochodu A mówi, że poruszanie się na północ jest właściwym kierunkiem, podczas gdy kierowca samochodu B mówi, że poruszanie się w kierunku południowym jest poprawne. Ale żaden z nich nie cofa się, aby pozwolić innemu samochodowi jechać do przodu, ten stan nazywa się stanem impasu.




Przykład samochodu

przykład samochodu

Dla lepszego zrozumienia rozważmy inny przykład, w którym istnieją dwa zasoby R1, R2 i dwa procesy P1 i P2, gdzie R1 jest przypisane do P1, a R2 do P2. Teraz, jeśli P1 chce uzyskać dostęp do R2, jak już wiemy, R2 jest trzymany przez P2, a teraz P2 chce uzyskać dostęp do R1, czyli P1 wykonuje tylko wtedy, gdy uzyskuje dostęp do R2, również P2 wykonuje tylko wtedy, gdy uzyska dostęp do R1, ta sytuacja jest stanem zakleszczenia.



Przykład procesora

przykład procesora

Warunki Dead-Lock

Poniżej przedstawiono cztery ważne warunki zakleszczenia, które mają wystąpić, jeśli wszystkie warunki występują jednocześnie, istnieją pewne szanse na wystąpienie impasu.

Wzajemne wykluczenie

Oznacza to, że każdy zasób, z którego korzystamy, musi być używany w sposób wzajemnie wykluczający się. Gdy tylko jeden proces używa tylko jednego zasobu w danym momencie. Na przykład trwa proces drukowania i nagle inny proces próbuje przerwać proces drukowania. A więc tutaj w sytuacji wzajemnego wykluczenia, dopiero po zakończeniu zadania drukowania, przetwarzane jest tylko następne zadanie. Wzajemne wykluczenie można wyeliminować przez jednoczesne udostępnianie zasobów, co praktycznie nie jest możliwe.

Wzajemne wykluczenie

wzajemne wykluczenie

Brak pierwszeństwa

Według dotyczący pierwokupu oparte na algorytmach, jeśli istnieje priorytetowe zadanie próbujące przerwać bieżące zadanie. Algorytm wywłaszczający, który przechowuje bieżące zadanie i najpierw wykonuje zadanie priorytetowe, a następnie wraca do pierwszego zadania. Sytuacja wyjaśniona zgodnie z powyższym przykładem, w której proces przechowuje zasób tak długo, jak długo jest wykonywany, czyli P1 może zwolnić R1 dopiero po wykonaniu, podobnie P2 zwolnić R2 dopiero po wykonaniu. Jeśli nie ma pierwszeństwa, może wystąpić zakleszczenie.


Przykład bez wywłaszczania

przykład bez wywłaszczania

Trzymaj i czekaj

Proces zatrzymuje pewne zasoby i oczekuje na dodatkowe zasoby, ale zasoby te są pozyskiwane przez inny proces. Z powyższego przykładu, P1 trzyma R1 i czeka na R2, gdzie R2 jest pozyskiwany przez P2, a P2 trzyma R2 i czeka na R1, gdzie R1 jest pozyskiwany przez P1, może wystąpić w systemie blokada sytuacji wstrzymania i oczekiwania.

Przykład wstrzymania i czekania

przykład wstrzymania i czekania

Czekaj okólnie

Mówi się, że zestaw procesów jest zakleszczony, jeśli jeden proces oczekuje na zasób, który jest przydzielony do innego procesu, a ten proces oczekuje na zasób, jest to podobne do wyjaśnionego powyżej przykładu, w którym jest w formie pętli. Gdzie P1 czeka na R2, a R2 jest przydzielony dla P2, a P2 czeka na R1, a R1 przydzielony do P1, co jest cykliczną formą oczekiwania, jeśli warunek ten spełnia zakleszczenie.

Przykład okrągłego oczekiwania

przykład okrągłego oczekiwania

Algorytm wykrywania martwego zamka

Przypadki, w których przydzielamy zasoby do procesów, a system operacyjny ponownie sprawdza, czy w systemie wystąpił zakleszczenie lub nie przy użyciu 2 głównych algorytmów wykrywania zakleszczeń, są to:

  • Pojedyncza instancja
  • Wiele instancji typu zasobu

Pojedyncza instancja

Pojedyncza instancja to sytuacja, w której system ma pojedyncze wystąpienia wszystkich zasobów. Jest również znany jako oczekiwanie na algorytm grafu lub wykres alokacji zasobów. Wykres alokacji zasobów składa się z zestawu procesów i zestawu zasobów, które są reprezentowane jako dwa różne wierzchołki. Zasoby na wykresie alokacji zasobów są modyfikowane i są reprezentowane jako formularz oczekiwania na wykres. Gdzie oczekiwanie na formę wykresu ma tylko procesy, które są reprezentowane jako wierzchołki, jak pokazano poniżej, gdzie,

  • Wykres alokacji zasobów: Procesy P1, P2, P3 i zasoby R1, R2, R3 są przedstawione na wykresie alokacji zasobów.
  • Czekaj na wykres: tylko procesy P1, P2, P3 są wymienione w oczekiwaniu na wykres.
  • Jeśli istnieje warunek cyklu, to jeśli występuje ciągły przepływ procesu w jednym kierunku, oznacza to, że warunek cyklu kończy się i czeka, aż wykres znajdzie się w stanie zakleszczenia.

Przykład 1: Poniższy przykład pokazuje, że nie ma stanu zakleszczenia, ponieważ nie obserwuje się ciągłego przepływu w oczekiwaniu na wykres.

Przykład pojedynczej instancji 1

pojedyncza instancja przykład1

Przykład 2: Wystąpił stan zakleszczenia, ponieważ istnieje ciągły przepływ cyklu od P1 do P4.

Pojedyncza instancja - przykład2

pojedyncza instancja przykład2

Jeżeli w systemie bardzo często dochodzi do zakleszczenia, często stosowany jest algorytm wykrywania. Jeśli algorytm wykrywania będzie używany w większym stopniu, będzie więcej narzutów i dłuższy czas obliczeniowy. Dlatego, aby temu zaradzić, wywołujemy algorytm, podając równy czas, w ten sposób waga wykresu jest używana do wykrywania zakleszczenia.

Wiele wystąpień typu zasobu

Wiele wystąpień typu zasobu to sytuacja, w której system ma wiele wystąpień wszystkich zasobów, jest to również znane jako algorytm bankierów. Zgodnie z algorytmem Bankierów, gdy tylko proces uzyska wszystkie wymagane zasoby, zwalnia swoje zasoby.

Rozważmy następujący przykład, załóżmy, że istnieją 3 procesy P0, P1, P2 i typ zasobów A, B, C, gdzie A może być procesor , B może być drukarką, a C może być klawiaturą. Cyfry „0” w kolumnie oznaczają dostępność zasobów.

Przypadek (i): Załóżmy, że jeśli przyjmiemy, że żądanie warunku to „000”, który jest obecny w P0 i P2, powinniśmy sprawdzić, które żądanie jest spełnione, procesy P0 zwalniają procesy po ich przydzieleniu, a następnie kolejne procesy P2 zwalniają po przydzieleniu. W ten sposób w sekwencji jeden po drugim proces uwalnia kolejno P0, P2, P3, P1, P4. Ostatecznie otrzymujemy dostępne zasoby jako P7, P2, P6. Dostępna sekwencja to stan, w którym nie ma zakleszczenia.

Bankers-Algorithm-Example1

algorytm-bankierów przykład1

Domy (ii): Załóżmy, że jeśli P2 wynosi 001 zamiast 000, zastosuj teraz algorytm bankiera, aby sprawdzić stan zakleszczenia, w którym jedyny P0 jest wykonywany spośród wszystkich 5 procesów. Stąd P1, P2, P3, P4 są w stanie zakleszczenia, z wyjątkiem P0.

Przykład bankierów 2

bankierzy przykład2

Zastosowania impasu

Zastosowania impasu można wyjaśnić na przykładzie wyników egzaminów online w czasie rzeczywistym, gdzie kilku studentów próbuje uzyskać dostęp do witryny internetowej uczelni w momencie zwolnienia. Można zauważyć, że czasami strona internetowa nie ładuje się jednocześnie dla wielu użytkowników, jest to stan zakleszczenia. Można to obejść za pomocą dowolnego algorytmu.

Zalety

Zalety impasu są

  • W unikaniu zakleszczenia nie obserwuje się żadnego pierwszeństwa
  • Bez opóźnień w procesie

Niedogodności

Wadą impasu jest

  • Zasób, który ma zostać użyty, musi być wcześniej znany
  • Zablokowanie procesu przez długi czas
  • Straty z tytułu wywłaszczenia są dziedziczone.

W tym artykule omówiono, w jaki sposób dochodzi do zakleszczenia, gdy istnieją dwa lub więcej procesów i trzy warunki, które są przyczyną wystąpienia impasu, oraz dwa typy algorytmów, mianowicie algorytm współdzielenia zasobów, który wykrywa, że ​​istnieje stan zakleszczenia oraz algorytm bankierów, który jest algorytmem unikania zakleszczenia. Oto pytanie „Co się stanie, jeśli impas zostanie zignorowany?”.