Rozumiem, co to jest livelock, ale zastanawiałem się, czy ktoś ma dobry przykład oparty na kodzie? I kodem oparte, ja nie znaczy „dwie osoby próbują ominąć siebie w korytarzu”. Jeśli jeszcze raz to przeczytam, stracę lunch.
concurrency
livelock
Alex Miller
źródło
źródło
Odpowiedzi:
Oto bardzo prosty przykład livelocka w Javie, w którym mąż i żona próbują zjeść zupę, ale mają między sobą tylko jedną łyżkę. Każdy z małżonków jest zbyt uprzejmy i podaje łyżkę, jeśli drugi jeszcze nie jadł.
źródło
getOwner
metoda również nie musi być synchronizowana? Z efektywnej Java „ synchronizacja nie ma żadnego efektu, chyba że zarówno odczyt, jak i zapis ”.Thread.join()
raczej używać niżThread.sleep()
, ponieważ chce poczekać, aż małżonek zacznie jeść?getOwner
Metoda musi być zsynchronizowane, ponieważ nawet jeślisetOwner
jest zsynchronizowany, to nie gwarantuje nić korzystaniagetOwner
(lub uzyskiwania dostępu do polaowner
bezpośrednio) będzie zobaczyć zmiany dokonane przez innego wątku wykonującegosetOwner
. Ten film wyjaśnia to bardzo dokładnie: youtube.com/watch?v=WTVooKLLVT8synchronized
słowa kluczowego dlasetOwner
metody, ponieważ czytanie i pisanie jest niepodzielną akcją dla zmiennej referencyjnej.Odkładając na bok niepoważne komentarze, jednym z przykładów, o którym wiadomo, że pojawia się, jest kod, który próbuje wykryć i poradzić sobie z sytuacjami zakleszczenia. Jeśli dwa wątki wykryją zakleszczenie i spróbują „odsunąć się” dla siebie nawzajem, bez ostrzeżenia skończą z utknięciem w pętli, zawsze „odsuwając się na bok” i nigdy nie udając się ruszyć do przodu.
Przez „odsunięcie się” mam na myśli, że zwolniliby blokadę i spróbowaliby pozwolić drugiemu go zdobyć. Możemy sobie wyobrazić sytuację z dwoma wątkami robiącymi to (pseudokod):
Pomijając warunki wyścigu, mamy tutaj sytuację, w której oba wątki, jeśli wejdą w tym samym czasie, zakończą bieg w wewnętrznej pętli bez kontynuowania. Oczywiście jest to uproszczony przykład. Naiwnym rozwiązaniem byłoby wprowadzenie pewnego rodzaju przypadkowości w czasie oczekiwania wątków.
Właściwym rozwiązaniem jest zawsze przestrzeganie hierarchii blokad . Wybierz kolejność, w której zdobędziesz zamki i trzymaj się tego. Na przykład, jeśli oba wątki zawsze uzyskują lock1 przed lock2, nie ma możliwości zakleszczenia.
źródło
Ponieważ nie ma odpowiedzi oznaczonej jako zaakceptowana, próbowałem utworzyć przykład blokady na żywo;
Oryginalny program został napisany przeze mnie w kwietniu 2012 roku, aby nauczyć się różnych koncepcji wielowątkowości. Tym razem zmodyfikowałem go, aby utworzyć zakleszczenie, stan wyścigu, blokadę żywą itp.
Więc najpierw zrozummy stwierdzenie problemu;
Problem z twórcą plików cookie
Jest kilka pojemników na składniki: ChocoPowederContainer , WheatPowderContainer . CookieMaker wymaga pewnej ilości proszku z pojemników składników upiec Cookie . Jeśli producent ciasteczek stwierdzi, że pojemnik jest pusty, szuka innego pojemnika, aby zaoszczędzić czas. I czeka, aż Filler wypełni wymagany pojemnik. Jest wypełniacz który regularnie sprawdza pojemnik i uzupełnia pewną ilość, jeśli pojemnik tego potrzebuje.
Sprawdź cały kod na github ;
Pozwólcie, że krótko wyjaśnię wdrożenie.
Spójrzmy na kod:
CookieMaker.java
IngredientContainer.java
Wszystko działa dobrze do Fillera nie napełni pojemników. Ale jeśli zapomnę uruchomić wypełniacz lub wypełniacz nieoczekiwanie opuścił, wątki podrzędne zmieniają swoje stany, aby umożliwić innemu producentowi przejście i sprawdzenie pojemnika.
Stworzyłem również demona ThreadTracer, który śledzi stany wątków i zakleszczenia. To jest wyjście z konsoli;
Zauważysz, że pod-wątki i zmieniają się ich stany i czekają.
źródło
Rzeczywisty (aczkolwiek bez dokładnego kodu) przykład to dwa konkurujące ze sobą procesy blokujące na żywo w celu skorygowania zakleszczenia serwera SQL, przy czym każdy proces używa tego samego algorytmu oczekiwania na ponowienie podczas ponawiania. Chociaż jest to szczęście związane z synchronizacją, widziałem, że dzieje się to na oddzielnych maszynach o podobnej charakterystyce wydajności w odpowiedzi na wiadomość dodaną do tematu EMS (np. Zapisywanie aktualizacji pojedynczego wykresu obiektu więcej niż raz) i brak możliwości sterowania kolejność zamka.
Dobrym rozwiązaniem w tym przypadku byłoby posiadanie konkurujących konsumentów (zapobieganie zduplikowanemu przetwarzaniu jak najwyżej w łańcuchu poprzez podzielenie pracy na niepowiązane ze sobą obiekty).
Mniej pożądanym rozwiązaniem (ok, brudny hack) jest przełamanie pecha czasowego (rodzaj różnic sił w przetwarzaniu) z wyprzedzeniem lub przełamanie go po impasie za pomocą różnych algorytmów lub elementu losowości. Może to nadal powodować problemy, ponieważ jest możliwe, że kolejność przyjmowania blokad jest „lepka” dla każdego procesu, a to zajmuje pewien minimalny czas, który nie jest uwzględniany w ponownej próbie oczekiwania.
Jeszcze innym rozwiązaniem (przynajmniej dla SQL Server) jest wypróbowanie innego poziomu izolacji (np. Migawki).
źródło
Zakodowałem przykład 2 osób przechodzących na korytarzu. Dwie nici będą się unikać, gdy tylko zorientują się, że ich kierunki są takie same.
źródło
Wersja C # kodu jelbourn:
źródło
Jednym z przykładów może być użycie czasowego tryLock, aby uzyskać więcej niż jedną blokadę, a jeśli nie możesz uzyskać ich wszystkich, wycofaj się i spróbuj ponownie.
Mogę sobie wyobrazić, że taki kod byłby problematyczny, ponieważ wiele wątków koliduje i czeka na uzyskanie zestawu blokad. Ale nie jestem pewien, czy jest to dla mnie bardzo przekonujące jako prosty przykład.
źródło
tryLockAll()
z zamkamilocks
w tej samej kolejności, nie ma żywej blokady.Wersja kodu jelbourn w Pythonie:
źródło
Modyfikuję odpowiedź @jelbourn. Kiedy jeden z nich zauważy, że drugi jest głodny, powinien puścić łyżkę i poczekać, aż inny powiadomi, aby zdarzyło się bydło.
źródło
źródło