Pat w OperaSystem tingowy: Co to jest czekanie cykliczne (przykłady)

Czym jest Deadlock?

Deadlock jest sytuacją, która ma miejsce w system operacyjny Kiedy proces przechodzi w stan oczekiwania, ponieważ inny oczekujący proces zajmuje żądany zasób. Zakleszczenie to częsty problem w wieloprocesorowości, gdzie kilka procesów współdzieli określony typ wzajemnie wykluczającego się zasobu, znany jako blokada programowa lub blokada programowa.

Gdy wystąpi impas, żaden z zaangażowanych procesów nie może kontynuować pracy, więc praca zostaje wstrzymana do momentu interwencji systemu operacyjnego.

Przykład impasu

• Przykładem ze świata rzeczywistego byłby ruch odbywający się tylko w jednym kierunku.
• W tym przypadku most jest uważany za zasób.
• Kiedy więc dojdzie do impasu, można go rozwiązać poprzez cofnięcie jednego samochodu (przejęcie zasobów i wycofanie).
• W przypadku wystąpienia impasu może zaistnieć konieczność cofnięcia kilku samochodów.
• Więc głód jest możliwy.

Przykład impasu

Co to jest czekanie cykliczne?

Jeden proces czeka na zasób, który jest w posiadaniu drugiego procesu, który również czeka na zasób w posiadaniu trzeciego procesu i tak dalej. Proces ten trwa, aż ostatni proces zacznie czekać na zasób w posiadaniu pierwszego procesu. W ten sposób powstaje łańcuch cykliczny.

Na przykład procesowi A przydzielany jest zasób B, gdy żąda on zasobu A. W ten sam sposób procesowi B przydzielany jest zasób A, gdy żąda on zasobu B. Powoduje to powstanie pętli oczekiwania.

Przykład oczekiwania cyklicznego

Na przykład komputer ma trzy dyski USB i trzy procesy. Każdy z tych trzech procesów obsługuje jeden z dysków USB. Zatem, gdy każdy proces żąda kolejnego dysku, wszystkie trzy procesy dochodzą do impasu, ponieważ każdy z nich czeka na zwolnienie dysku USB, gdy jest on jeszcze w użyciu. W rezultacie powstaje cykliczny łańcuch.

Przykład oczekiwania cyklicznego

Wykrywanie blokad w systemie operacyjnym

Wystąpienie impasu może zostać wykryte przez harmonogram zasobów. Harmonogram zasobów pomaga systemowi operacyjnemu utrzymać track wszystkich zasobów przydzielonych różnym procesom. Po wykryciu impasu można go rozwiązać poprzez wywłaszczenie zasobów, wycofanie procesu lub zakończenie jednego lub kilku procesów, w których wystąpił impas.

Zapobieganie blokadom w systemie operacyjnym

Ważne jest, aby zapobiec impasowi, zanim do niego dojdzie. System sprawdza każdą transakcję przed jej wykonaniem, aby upewnić się, że nie doprowadzi ona do impasu. Nawet drobna operacja, która mogłaby spowodować impas w przyszłości, nigdy nie jest dopuszczana do wykonania.

Zapobieganie blokadom to zbiór metod mających na celu zapewnienie, że przynajmniej jeden z czterech niezbędnych warunków nie będzie mógł zostać spełniony.

Brak uprzedzenia

Zasób może zostać zwolniony wyłącznie dobrowolnie przez proces, który go przechowuje, po zakończeniu przez ten proces swojego zadania.

• Jeżeli proces posiadający pewne zasoby zażąda innego zasobu, którego nie można mu natychmiast przydzielić, wówczas wszystkie zasoby zostaną zwolnione.
• Wywłaszczone zasoby są dodawane do listy zasobów, na które proces czeka.
• Proces zostanie uruchomiony ponownie dopiero wtedy, gdy będzie można odzyskać zarówno stare zasoby, jak i nowe, o które wnioskowano.

Wzajemne wykluczenie

Wzajemne wykluczenie to pełna forma Mutex. Jest to specjalny typ binarny semafor Służy do kontrolowania dostępu do współdzielonego zasobu. Zawiera mechanizm dziedziczenia priorytetów, aby uniknąć problemów z rozszerzoną inwersją priorytetów i utrzymuje zadania o wyższym priorytecie zablokowane na najkrótszy możliwy czas.

Współdzielone zasoby, takie jak pliki tylko do odczytu, nigdy nie prowadzą do blokad, ale zasoby takie jak drukarki i napędy taśmowe wymagają wyłącznego dostępu przez pojedynczy proces.

Trzymaj i czekaj

W takiej sytuacji należy powstrzymać procesy przed zajmowaniem jednego lub większej liczby zasobów i równoczesnym oczekiwaniem na zajęcie jednego lub większej liczby innych zasobów.

Okrągłe czekanie

Ta metoda wymusza całkowite uporządkowanie wszystkich typów zasobów. Zapobieganie cyklicznemu oczekiwaniu wymaga również, aby każdy proces żądał zasobów w rosnącej kolejności enumeracji.

Unikanie zakleszczenia Algorithms

Lepiej jest uniknąć impasu niż podejmować działania po jego wystąpieniu. Unikanie impasu wymaga dodatkowych informacji, takich jak sposób wykorzystania zasobów. Unikanie impasu to użyteczny model, w którym każdy proces deklaruje maksymalną liczbę zasobów każdego typu, których może potrzebować.

Unikanie Algorithms

Algorytm zapobiegający blokadom dynamicznie ocenia stan alokacji zasobów, dzięki czemu nigdy nie może wystąpić sytuacja cyklicznego oczekiwania.

Dla pojedynczego wystąpienia typu zasobu:

• Użyj wykresu alokacji zasobów.
• Cykl na wykresie jest konieczny i wystarczający do wystąpienia impasu.

W przypadku wielu wystąpień typu zasobu:

• Cykl jest konieczny, ale niewystarczający do wystąpienia impasu.
• Użyj Algorytm bankiera.

Różnica między głodem a impasem

Oto kilka ważnych różnic między impasiem a głodowaniem:

Deadlock	Głód
Sytuacja impasu występuje, gdy jeden z procesów zostaje zablokowany.	Zagłodzenie to sytuacja, w której wszystkie procesy o niskim priorytecie zostają zablokowane, podczas gdy procesy o wysokim priorytecie są wykonywane.
Blokada jest procesem nieskończonym.	Głodzenie się to długie oczekiwanie, ale nie proces nieskończony.
Każdemu impasowi towarzyszy głód.	Nie każde głodowanie musi oznaczać impas.
Do impasu dochodzi w wyniku wzajemnego wykluczania, oczekiwania i przytrzymania, braku wywłaszczenia oraz cyklicznego oczekiwania występującego jednocześnie.	Dzieje się tak ze względu na brak kontroli nad priorytetami i złe zarządzanie zasobami.

Zalety Deadlocka

Oto zalety stosowania metody obsługi blokad:

• Taka sytuacja sprawdza się w przypadku procesów, które wykonują pojedynczą serię czynności.
• Do wystąpienia impasu nie jest potrzebne żadne wywłaszczenie.
• Jest to wygodna metoda, gdy jest stosowana do zasobów, których stan można łatwo zapisać i przywrócić.
• Możliwe jest egzekwowanie tego poprzez sprawdzanie w czasie kompilacji.
• Nie ma potrzeby wykonywania obliczeń w czasie rzeczywistym, ponieważ problem rozwiązano już na etapie projektu systemu.

Wady Deadlocka

Oto wady stosowania metody obsługi blokad:

• Opóźnia rozpoczęcie procesu.
• Procesy muszą z wyprzedzeniem znać swoje przyszłe zapotrzebowanie na zasoby.
• Wyprzedza częściej niż to konieczne.
• Nie zezwala na przyrostowe żądania zasobów.
• Wiąże się to ze stratami wynikającymi z pierwszeństwa.

FAQ