Dlaczego stan niebezpieczny nie zawsze powoduje impas?

Czytałem Systemy operacyjne Galvina i natrafiłem na poniższy wiersz,

Jednak nie wszystkie niebezpieczne stany są w impasie. Niebezpieczny stan może doprowadzić do impasu

Czy ktoś może wyjaśnić, jak impas! = Stan niebezpieczny ? Tutaj też złapałem tę samą linię

Jeśli bezpieczna sekwencja nie istnieje, system znajduje się w niebezpiecznym stanie, co MOŻE doprowadzić do impasu. (Wszystkie bezpieczne stany są wolne od impasu, ale nie wszystkie niebezpieczne stany prowadzą do impasu).

Zakleszczenie oznacza coś konkretnego: istnieją dwa (lub więcej) procesy, które są obecnie blokowane, czekając na siebie.

W niebezpiecznym stanie możesz również znaleźć się w sytuacji, w której może dojść do impasu w przyszłości, ale tak się jeszcze nie stało, ponieważ jeden lub oba procesy faktycznie nie zaczęły czekać.

Rozważ następujący przykład:

Process A                  Process B
lock X                     lock Y           # state is "unsafe"
                           unlock Y
lock Y                                      # state is back to "safe" (no deadlock this time.  We got lucky.)

Bardziej interesujący przykład znajduje się w sekcji 7.5.1 podanego linku :

Rozważ system z 12 napędami taśmowymi z:

Process       Max Need       Current
P0:             10              5
P2:              9              3

To jest niebezpieczny stan. Ale nie jesteśmy w impasie. Są tylko 4 wolne dyski, tak, na przykład, jeśli P0 robi poprosić o dodatkowe 5 i P2 robi żądanie dodatkowy 1, będziemy impasu, ale to jeszcze nie zdarzyło. I P0 może nie żądać więcej dysków, ale zamiast tego może zwolnić dyski, które już posiada. Max needJest ponad wszystkich możliwych wykonań programu, a to może nie być jednym z wykonań, gdzie musimy wszystkie 10 dysków w P0.

Tylko po to, żeby wyjaśnić, co mówiła Wędrująca Logika.

Powiedzmy, że mam dwa wątki, które potrzebują dostępu do X i Y, i nie mam synchronizacji ani mechanizmu naprawiającego zakleszczenie. Jest to niebezpieczne, ponieważ jeden może zablokować X i drugi Y, a następnie żaden nie może kontynuować. Ale nie ma gwarancji.

Thread 1                    Thread 2
Lock X                      
Lock Y
OS Interrupts Thread 1 and passes control to Thread 2
                            Unable to lock needed resources.
OS Interrupts Thread 2 and passes control to Thread 1
Unlock X                    
Unlock Y                    
                            Lock Y
                            Lock X
 ....

Ten scenariusz nie zakończył się impasem, ale mógł mieć. Ze względu na sposób działania wątkowania nie ma ustalonego przepływu. System operacyjny kontroluje wątki, więc może wystąpić coś takiego:

Thread 1                    Thread 2
Lock X        
OS Interrupts Thread 1 and passes control to Thread 2
                            Lock Y              
DEADLOCK Thread 1 needs Y, Thread 2 needs X. Neither knows to back down and simply waits.

Stan bezpieczny na pewno nie jest zakleszczony, ale jeśli nie możesz spełnić wszystkich wymagań, aby zapobiec zakleszczeniu, może to nastąpić. Na przykład, jeśli dwa wątki mogą wpaść w impas, gdy zaczynają wątek A, to wątek B, ale gdy zaczynają się przeciwnie (B, A), będą działać dobrze - załóżmy, że B jest ładniejszy;) Stan systemu jest niebezpieczny, ale przy szczęśliwej sekwencji początkowej będzie działać. Bez impasu, ale jest to możliwe. Jeśli również zsynchronizujesz je ręcznie - zaczniesz w odpowiedniej kolejności - jest to niebezpieczne - z jakiegoś powodu mogą nie zostać wystrzelone tak, jak lubisz - system nadal jest niebezpieczny (z powodu możliwego impasu), ale jest małe prawdopodobieństwo tego. W przypadku niektórych zdarzeń zewnętrznych, takich jak zamrażanie wątków lub przerwanie po kontynuowaniu, zakończy się niepowodzeniem.

Musisz zdać sobie sprawę - stan bezpieczny jest warunkiem wystarczającym, aby uniknąć impasu, ale niebezpieczny jest tylko warunkiem koniecznym. Trudno jest teraz napisać kod, ale mogę go wyszukać. Zetknąłem się z kodem w Adzie, który ponad 99/100 razy działał idealnie przez kilka tygodni (a potem przestał działać z powodu restartu serwera, a nie zakleszczenia), ale raz na jakiś czas zawieszał się po kilku sekundach do stanu zakleszczenia.

Dodajmy prosty przykład w porównaniu do dzielenia: jeśli twoja funkcja dzieli c / d i zwraca wynik, bez sprawdzania, czy d jest równe 0, może wystąpić błąd dzielenia przez zero, więc kod jest niebezpieczny (zamierzone takie samo nazewnictwo), ale do robisz taki podział, wszystko jest w porządku, ale po analizie teoretycznej kod jest niebezpieczny i może popaść w niezdefiniowane zachowanie, które nie będzie właściwie obsługiwane.

Oto moje rozumienie tego (proszę mnie poprawić, jeśli się mylę): (A) Jeśli impas oznacza, że ​​istnieje cykl (jeden z niezbędnych warunków) (B) Cykl jest obowiązkowym warunkiem impasu (zarówno dla pojedynczego, jak i dla wielu zasoby instancji)

Możemy więc teraz udowodnić, że istnieje cykl, który może nie doprowadzić do impasu. Widać tutaj cykl, co oznacza, że ​​znaleziono niebezpieczny stan, ale może to nie prowadzić do impasu, ponieważ zasób R2 biorący udział w cyklu może przerwać uruchom cykl, gdy tylko proces P3 zakończy się i zwolni (pamiętaj, że P3 nie jest zależny ani nie czeka na żadne inne zasoby).

Trywialny stan niebezpieczny: Wątek 1 przyjmuje blokadę A, następnie blokadę B, a następnie odblokowuje obie. Wątek 2 przyjmuje blokadę B, następnie blokadę A, a następnie odblokowuje obie.

Doprowadzi to do impasu tylko wtedy, gdy Wątek 2 przejdzie w blokadę B tylko między Wątkiem 1, przyjmując blokadę A i próbując przejąć blokadę B, lub Wątek 1 przejdzie w blokadę A tylko między Wątkiem 2, przyjmując blokadę B i próbując przejąć blokadę A.

Jeśli Wątek 1 i Wątek 2 wykonają to losowo raz na godzinę, istnieje mikrosekundowa przerwa, która faktycznie doprowadziłaby do impasu. może to trwać bardzo długo w rękach klientów, aż w końcu przypadkowo znajdziesz impas.

Przejdź przez ulicę z zamkniętymi oczami. To niebezpieczne. Ale nie zawsze giniesz.