Czy ktoś może wyjaśnić przykładami (kodem), jaka jest różnica między impasem a blokowaniem aktywnym ?
multithreading
pthreads
deadlock
livelock
Macindows
źródło
źródło
Odpowiedzi:
Zaczerpnięte z http://en.wikipedia.org/wiki/Deadlock :
źródło
Livelock
Główną różnicą między blokadą aktywności i zakleszczeniem jest to, że wątki nie będą blokowane, zamiast tego będą próbowały reagować na siebie w sposób ciągły.
Na tym obrazie oba kręgi (wątki lub procesy) będą próbowały dać sobie nawzajem miejsce, poruszając się w lewo i prawo. Ale nie mogą już iść dalej.
źródło
Cała treść i przykłady są tutaj
Systemy operacyjne: elementy wewnętrzne i zasady projektowania
William Stallings
8º Edition
Zakleszczenie : sytuacja, w której dwa lub więcej procesów nie jest w stanie kontynuować, ponieważ każdy z nich czeka na coś innego.
Rozważmy na przykład dwa procesy P1 i P2 oraz dwa zasoby R1 i R2. Załóżmy, że każdy proces potrzebuje dostępu do obu zasobów, aby wykonać część swojej funkcji. Następnie można mieć następującą sytuację: system operacyjny przypisuje R1 do P2, a R2 do P1. Każdy proces czeka na jeden z dwóch zasobów. Żadne z nich nie zwolni zasobu, który już posiada, dopóki nie zdobędzie drugiego zasobu i nie wykona funkcji wymagającej obu zasobów. Oba procesy są zakleszczone
Livelock : sytuacja, w której dwa lub więcej procesów stale zmienia swoje stany w odpowiedzi na zmiany w innych procesach bez wykonywania żadnej użytecznej pracy:
Głód : sytuacja, w której program uruchamiający jest pomijany w nieskończoność przez program planujący; chociaż jest w stanie kontynuować, nigdy nie jest wybrany.
Załóżmy, że każdy z trzech procesów (P1, P2, P3) wymaga okresowego dostępu do zasobu R. Rozważ sytuację, w której P1 jest w posiadaniu zasobu, a zarówno P2, jak i P3 są opóźnione, czekając na ten zasób. Kiedy P1 opuści sekcję krytyczną, P2 lub P3 powinny mieć dostęp do R. Załóżmy, że system operacyjny zapewnia dostęp do P3 i że P1 ponownie wymaga dostępu, zanim P3 zakończy sekcję krytyczną. Jeśli system operacyjny przyznaje dostęp do P1 po zakończeniu P3, a następnie naprzemiennie udziela dostępu do P1 i P3, wówczas P2 może zostać w nieskończoność pozbawiony dostępu do zasobu, nawet jeśli nie ma sytuacji zakleszczenia.
DODATEK A - TEMATY W KONKURENCJI
Przykład zakleszczenia
Jeśli oba procesy ustawią swoje flagi na true, zanim którekolwiek z nich wykona instrukcję while, wówczas każdy pomyśli, że drugi wszedł do swojej krytycznej sekcji, powodując impas.
Przykład Livelock
[...] rozważ następującą sekwencję zdarzeń:
Sekwencję tę można przedłużyć w nieskończoność i żaden proces nie może wejść do swojej krytycznej sekcji. Ściśle mówiąc, nie jest to impas , ponieważ każda zmiana względnej prędkości dwóch procesów przerwie ten cykl i pozwoli wejść do sekcji krytycznej. Ten stan jest określany jako livelock . Przypomnij sobie, że impas występuje, gdy zestaw procesów chce wejść do swoich krytycznych sekcji, ale żaden proces nie może się powieść. Dzięki livelock możliwe są sekwencje wykonania, które się powiodły, ale można również opisać jedną lub więcej sekwencji wykonania, w których żaden proces nigdy nie wchodzi w krytyczną sekcję.
Już nie treści z książki.
A co ze spinlockami?
Spinlock to technika pozwalająca uniknąć kosztów mechanizmu blokady systemu operacyjnego. Zazwyczaj robiłbyś:
Problem zaczyna się pojawiać, gdy
beginLock()
kosztuje znacznie więcej niżdoSomething()
. W bardzo przesadnych słowach wyobraź sobie, co się dzieje, gdybeginLock
kosztuje 1 sekundę, aledoSomething
kosztuje tylko 1 milisekundę.W takim przypadku, jeśli czekałeś 1 milisekundę, unikniesz przeszkód przez 1 sekundę.
Dlaczego
beginLock
to kosztuje tak dużo? Jeśli blokada jest bezpłatna, nie kosztuje dużo (patrz https://stackoverflow.com/a/49712993/5397116 ), ale jeśli blokada nie jest wolna, system operacyjny „zamrozi” Twój wątek, skonfiguruj mechanizm, który Cię obudzi kiedy zamek zostanie zwolniony, a następnie obudzę cię ponownie w przyszłości.Wszystko to jest znacznie droższe niż niektóre pętle sprawdzające zamek. Dlatego czasami lepiej jest zrobić „spinlock”.
Na przykład:
Jeśli twoja implementacja nie jest ostrożna, możesz spaść na livelock, wydając cały procesor na mechanizm blokujący.
Zobacz także:
https://preshing.com/20120226/roll-your-own-lightweight-mutex/
Czy moja implementacja blokady wirowania jest prawidłowa i optymalna?
Podsumowanie :
Zakleszczenie : sytuacja, w której nikt nie postępuje, nic nie robi (spanie, czekanie itp.). Zużycie procesora będzie niskie;
Livelock : sytuacja, w której nikt nie postępuje, ale procesor jest wydawany na mechanizm blokujący, a nie na twoje obliczenia;
Głód: sytuacja, w której jeden proces nigdy nie ma szans na ucieczkę; przez czysty pech lub przez część jego własności (na przykład niski priorytet);
Spinlock : technika unikania kosztów oczekiwania na uwolnienie blokady.
źródło
DEADLOCK Deadlock to stan, w którym zadanie czeka w nieskończoność na warunki, których nigdy nie można spełnić - zadanie twierdzi, że ma wyłączną kontrolę nad zasobami współdzielonymi - zadanie wstrzymuje zasoby podczas oczekiwania na zwolnienie innych zasobów - zadań nie można zmuszać do rozróżnienia zasobów - cykliczne oczekiwanie warunek istnieje
LIVELOCK Warunki Livelock mogą powstać, gdy dwa lub więcej zadań zależy od i używa jakiegoś zasobu, powodując warunek cyklicznej zależności, w którym zadania te działają nieprzerwanie, blokując w ten sposób wszystkie zadania o niższym priorytecie (te zadania o niższym priorytecie doświadczają stanu głodowego)
źródło
Być może te dwa przykłady ilustrują różnicę między impasem a blokadą na żywo:
Przykład Java dla impasu:
Przykładowe dane wyjściowe:
Przykład Java dla blokady na żywo:
Przykładowe dane wyjściowe:
Oba przykłady zmuszają wątki do zdobywania zamków w różnych porządkach. Podczas gdy impas czeka na drugi zamek, blokada blokady tak naprawdę nie czeka - desperacko próbuje zdobyć zamek bez szansy na jego zdobycie. Każda próba zużywa cykle procesora.
źródło
Wyobraź sobie, że masz wątek A i wątek B. Oba są
synchronised
na tym samym obiekcie, a wewnątrz tego bloku znajduje się zmienna globalna, którą aktualizują;Tak więc, gdy nawlec wchodzi w
while
pętlę i posiada blokadę, to robi to, co musi zrobić i ustawićcommonVar
siętrue
. Następnie przełóż B przychodzi, wchodzi wwhile
pętlę, a ponieważcommonVar
jesttrue
teraz, że jest w stanie utrzymać blokadę. Robi to, wykonujesynchronised
blok icommonVar
wraca dofalse
. Teraz wątek A ponownie otrzymuje nowe okno procesora, miał właśnie opuścićwhile
pętlę, ale wątek B właśnie go ustawiłfalse
, więc cykl się powtarza. Wątki coś robią (więc nie są blokowane w tradycyjnym sensie), ale praktycznie za nic.Warto też wspomnieć, że livelock niekoniecznie musi się tutaj pojawiać. Zakładam, że program planujący faworyzuje drugi wątek po
synchronised
zakończeniu wykonywania bloku. Myślę, że przez większość czasu jest to trudny do przebicia oczekiwanie i zależy od wielu rzeczy, które dzieją się pod maską.źródło