Zakleszczenie w Javie i metody jego zwalczania

Podczas tworzenia aplikacji wielowątkowych często pojawia się dylemat: ważniejsza jest niezawodność czy wydajność aplikacji. Na przykład synchronizację stosujemy dla bezpieczeństwa wątków, a w przypadkach, gdy kolejność synchronizacji jest nieprawidłowa, możemy spowodować zakleszczenia. Używamy również pul wątków i semaforów, aby ograniczyć zużycie zasobów, a błąd w tym projekcie może prowadzić do impasu z powodu braku zasobów. W tym artykule porozmawiamy o tym, jak uniknąć zakleszczenia, a także innych problemów w działaniu aplikacji. Przyjrzymy się również, jak można napisać aplikację tak, aby móc odzyskać siły w przypadku zakleszczenia. Zakleszczenie to sytuacja, w której dwa lub więcej procesów zajmujących pewne zasoby próbują przejąć inne zasoby zajmowane przez inne procesy i żaden z procesów nie jest w stanie zająć potrzebnego im zasobu i w związku z tym zwolnić zajętego. Definicja ta jest zbyt ogólna i dlatego trudna do zrozumienia; dla lepszego zrozumienia przyjrzymy się rodzajom zakleszczeń na przykładach.

Wzajemne blokowanie kolejności synchronizacji

Rozważ następujące zadanie: musisz napisać metodę przeprowadzającą transakcję, aby przelać określoną kwotę pieniędzy z jednego konta na drugie. Rozwiązanie może wyglądać następująco:

public void transferMoney(Account fromAccount, Account toAccount, Amount amount) throws InsufficientFundsException {
	synchronized (fromAccount) {
		synchronized (toAccount) {
			if (fromAccount.getBalance().compareTo(amount) < 0)
				throw new InsufficientFundsException();
			else {
				fromAccount.debit(amount);
				toAccount.credit(amount);
			}
		}
	}
}

Na pierwszy rzut oka kod ten jest synchronizowany całkiem normalnie, mamy do czynienia z atomową operacją sprawdzania i zmiany stanu konta źródłowego oraz zmiany konta docelowego. Jednakże w przypadku tej strategii synchronizacji może wystąpić sytuacja zakleszczenia. Spójrzmy na przykład, jak to się dzieje. Należy dokonać dwóch transakcji: przelać x pieniądze z konta A na konto B i przelać y pieniędzy z konta B na konto A. Często taka sytuacja nie spowoduje zakleszczenia, jednak w niefortunnych okolicznościach transakcja 1 zajmie monitor konta A, transakcja 2 zajmie monitor konta B. Rezultatem jest zakleszczenie: transakcja 1 czeka, aż transakcja 2 zwolni monitor konta B, ale transakcja 2 musi uzyskać dostęp do monitora A, który jest zajęty przez transakcję 1. Jednym z głównych problemów związanych z zakleszczeniami jest to, że niełatwo je znaleźć podczas testów. Nawet w sytuacji opisanej w przykładzie wątki mogą się nie blokować, czyli sytuacja ta nie będzie stale odtwarzana, co znacznie komplikuje diagnostykę. Generalnie opisywany problem niedeterminizmu jest typowy dla wielowątkowości (choć to wcale nie ułatwia). Dlatego przegląd kodu odgrywa ważną rolę w poprawie jakości aplikacji wielowątkowych, ponieważ pozwala zidentyfikować błędy, które są trudne do odtworzenia podczas testowania. Nie oznacza to oczywiście, że aplikacji nie trzeba testować – po prostu nie należy zapominać o przeglądzie kodu. Co powinienem zrobić, aby zapobiec powodowaniu zakleszczenia przez ten kod? Blokada ta wynika z faktu, że synchronizacja kont może nastąpić w innej kolejności. Odpowiednio, jeśli wprowadzisz jakiś porządek na rachunkach (jest to pewna reguła, która pozwala powiedzieć, że konto A jest mniejsze niż konto B), to problem zostanie wyeliminowany. Jak to zrobić? Po pierwsze, jeśli konta mają jakiś unikalny identyfikator (na przykład numer konta) numeryczny, mały lub inny z naturalną koncepcją porządku (ciągi można porównywać w porządku leksykograficznym, to możemy uważać się za szczęściarzy i będziemy zawsze Możemy najpierw zająć monitor mniejszego konta, a następnie większego (lub odwrotnie).

private void doTransfer(final Account fromAcct, final Account toAcct, final DollarAmount amount) throws InsufficientFundsException {
	if (fromAcct.getBalance().compareTo(amount) < 0)
		throw new InsufficientFundsException();
	else {
		fromAcct.debit(amount);
		toAcct.credit(amount);
	}
}
public void transferMoney(final Account fromAcct, final Account toAcct, final DollarAmount amount) throws InsufficientFundsException {
	int fromId= fromAcct.getId();
	int toId = fromAcct.getId();
	if (fromId < toId) {
		synchronized (fromAcct) {
			synchronized (toAcct) {
				doTransfer(fromAcct, toAcct, amount)}
			}
		}
	} else  {
		synchronized (toAcct) {
			synchronized (fromAcct) {
				doTransfer(fromAcct, toAcct, amount)}
			}
		}
	}
}

Opcja druga, jeśli nie mamy takiego identyfikatora, będziemy musieli wymyślić sami. W pierwszym przybliżeniu możemy porównywać obiekty według kodu skrótu. Najprawdopodobniej będą inne. Ale co, jeśli okażą się takie same? Następnie będziesz musiał dodać kolejny obiekt do synchronizacji. Może to wyglądać na nieco wyrafinowane, ale co możesz zrobić? A poza tym trzeci obiekt będzie używany dość rzadko. Wynik będzie wyglądał następująco:

private static final Object tieLock = new Object();
private void doTransfer(final Account fromAcct, final Account toAcct, final DollarAmount amount) throws InsufficientFundsException {
	if (fromAcct.getBalance().compareTo(amount) < 0)
		throw new InsufficientFundsException();
	else {
		fromAcct.debit(amount);
		toAcct.credit(amount);
	}
}
public void transferMoney(final Account fromAcct, final Account toAcct, final DollarAmount amount) throws InsufficientFundsException {
	int fromHash = System.identityHashCode(fromAcct);
	int toHash = System.identityHashCode(toAcct);
	if (fromHash < toHash) {
		synchronized (fromAcct) {
			synchronized (toAcct) {
				doTransfer(fromAcct, toAcct, amount);
			}
		}
	} else if (fromHash > toHash) {
		synchronized (toAcct) {
			synchronized (fromAcct) {
				doTransfer(fromAcct, toAcct, amount);
			}
		}
	} else {
		synchronized (tieLock) {
			synchronized (fromAcct) {
				synchronized (toAcct) {
					doTransfer(fromAcct, toAcct, amount)
				}
			}
		}
	}
}

Zakleszczenie między obiektami

Opisane stany blokowania stanowią najłatwiejszy do zdiagnozowania przypadek zakleszczenia. Często w aplikacjach wielowątkowych różne obiekty próbują uzyskać dostęp do tych samych zsynchronizowanych bloków. Może to spowodować zakleszczenie. Rozważmy następujący przykład: aplikację dyspozytora lotniczego. Samoloty informują kontrolera o dotarciu do celu i proszą o pozwolenie na lądowanie. Kontroler przechowuje wszystkie informacje o samolotach lecących w jego kierunku i może nanieść ich położenie na mapę.

class Plane {
	private Point location, destination;
	private final Dispatcher dispatcher;

	public Plane(Dispatcher dispatcher) {
		this.dispatcher = dispatcher;
	}
	public synchronized Point getLocation() {
		return location;
	}
	public synchronized void setLocation(Point location) {
		this.location = location;
		if (location.equals(destination))
		dispatcher.requestLanding(this);
	}
}

class Dispatcher {
	private final Set<Plane> planes;
	private final Set<Plane> planesPendingLanding;

	public Dispatcher() {
		planes = new HashSet<Plane>();
		planesPendingLanding = new HashSet<Plane>();
	}
	public synchronized void requestLanding(Plane plane) {
		planesPendingLanding.add(plane);
	}
	public synchronized Image getMap() {
		Image image = new Image();
		for (Plane plane : planes)
			image.drawMarker(plane.getLocation());
		return image;
	}
}

Zrozumienie, że w tym kodzie jest błąd, który może prowadzić do zakleszczenia, jest trudniejsze niż w poprzednim. Na pierwszy rzut oka nie ma resynchronizacji, ale tak nie jest. Prawdopodobnie już zauważyłeś, że setLocationklasa Planei metody getMapklas Dispatchersą zsynchronizowane i wywołują w sobie zsynchronizowane metody innych klas. Jest to ogólnie zła praktyka. Sposób, w jaki można to naprawić, zostanie omówiony w następnej sekcji. W rezultacie, jeśli samolot dotrze na miejsce, w momencie, gdy ktoś zdecyduje się sięgnąć po kartę, może nastąpić impas. Oznacza to, że zostaną wywołane metody getMapi , setLocationktóre zajmą odpowiednio monitory instancji Dispatcheri Plane. Następnie metoda zostanie getMapwywołana plane.getLocation(szczególnie na instancji Plane, która jest aktualnie zajęta), która będzie czekać, aż monitor stanie się wolny dla każdej instancji Plane. Jednocześnie setLocationzostanie wywołana metoda dispatcher.requestLanding, podczas gdy monitor instancji Dispatcherbędzie zajęty rysowaniem mapy. Rezultatem jest impas.

Otwórz połączenia

Aby uniknąć sytuacji takich jak ta opisana w poprzednim podrozdziale, zaleca się stosowanie publicznych wywołań metod innych obiektów. Oznacza to, że należy wywoływać metody innych obiektów poza blokiem synchronizowanym. Jeśli metody zostaną przepisane w oparciu o zasadę otwartych wywołań setLocation, getMapwyeliminowana zostanie możliwość zakleszczenia. Będzie to wyglądać na przykład tak:

public void setLocation(Point location) {
	boolean reachedDestination;
	synchronized(this){
		this.location = location;
		reachedDestination = location.equals(destination);
	}
	if (reachedDestination)
		dispatcher.requestLanding(this);
}
………………………………………………………………………………
public Image getMap() {
	Set<Plane> copy;
	synchronized(this){
		copy = new HashSet<Plane>( planes);
	}
	Image image = new Image();
	for (Plane plane : copy)
		image.drawMarker(plane.getLocation());
	return image;
}

Zakleszczenie zasobów

Zakleszczenia mogą również wystąpić podczas próby uzyskania dostępu do zasobów, z których w danym momencie może korzystać tylko jeden wątek. Przykładem może być pula połączeń z bazą danych. Jeśli niektóre wątki muszą uzyskać dostęp do dwóch połączeń jednocześnie i uzyskują do nich dostęp w różnej kolejności, może to prowadzić do zakleszczenia. Zasadniczo ten rodzaj blokowania nie różni się od blokowania kolejności synchronizacji, z tą różnicą, że występuje nie podczas próby wykonania jakiegoś kodu, ale podczas próby uzyskania dostępu do zasobów.

Jak uniknąć impasu?

Oczywiście, jeśli kod zostanie napisany bez błędów (przykłady, które widzieliśmy w poprzednich sekcjach), to nie będzie w nim żadnych zakleszczeń. Ale kto może zagwarantować, że jego kod zostanie napisany bez błędów? Oczywiście testowanie pomaga zidentyfikować znaczną część błędów, ale jak widzieliśmy wcześniej, błędy w kodzie wielowątkowym nie są łatwe do zdiagnozowania i nawet po przetestowaniu nie można być pewnym, że nie wystąpią sytuacje zakleszczenia. Czy możemy się jakoś zabezpieczyć przed blokowaniem? Odpowiedź brzmi tak. Podobne techniki stosowane są w silnikach baz danych, które często wymagają wyjścia z zakleszczeń (związanych z mechanizmem transakcyjnym w bazie danych). Interfejs Locki jego implementacje dostępne w pakiecie java.util.concurrent.lockspozwalają na próbę zajęcia monitora powiązanego z instancją tej klasy za pomocą metody tryLock(zwraca wartość true, jeśli udało się zająć monitor). Załóżmy, że mamy parę obiektów implementujących interfejs Locki musimy zająć ich monitory w taki sposób, aby uniknąć wzajemnego blokowania. Możesz to zaimplementować w ten sposób:

public void twoLocks(Lock A,  Lock B){
	while(true){
		if(A.tryLock()){
			if(B.tryLock())
			{
				try{
					//do something
				} finally{
					B.unlock();
					A.unlock();
				}
			} else{
				A.unlock();
			}
		}
	}
}

Jak widać w tym programie zajmujemy dwa monitory, eliminując jednocześnie możliwość wzajemnego blokowania się. Należy pamiętać, że blokada try- finallyjest konieczna, ponieważ klasy w pakiecie java.util.concurrent.locksnie zwalniają automatycznie monitora i jeśli podczas wykonywania zadania wystąpi jakiś wyjątek, monitor utknie w stanie zablokowanym. Jak diagnozować zakleszczenia? JVM umożliwia diagnozowanie zakleszczeń poprzez wyświetlanie ich w zrzutach wątków. Takie zrzuty zawierają informacje o stanie, w jakim znajduje się wątek. Jeśli jest zablokowany, zrzut zawiera informacje o monitorze, na który wątek oczekuje na zwolnienie. Przed zrzuceniem wątków maszyna JVM sprawdza wykres oczekujących (zajętych) monitorów i jeśli znajdzie cykle, dodaje informację o zakleszczeniu, wskazując uczestniczące monitory i wątki. Zrzut zablokowanych wątków wygląda następująco:

Found one Java-level deadlock:
=============================
"ApplicationServerThread":
waiting to lock monitor 0x0f0d80cc (a MyDBConnection),
which is held by "ApplicationServerThread"
"ApplicationServerThread":
waiting to lock monitor 0x0f0d8fed (a MyDBCallableStatement),
which is held by "ApplicationServerThread"
Java stack information for the threads listed above:
"ApplicationServerThread":
at MyDBConnection.remove_statement
- waiting to lock <0x6f50f730> (a MyDBConnection)
at MyDBStatement.close
- locked <0x604ffbb0> (a MyDBCallableStatement)
...
"ApplicationServerThread":
at MyDBCallableStatement.sendBatch
- waiting to lock <0x604ffbb0> (a MyDBCallableStatement)
at MyDBConnection.commit
- locked <0x6f50f730> (a MyDBConnection)

Powyższy zrzut wyraźnie pokazuje, że dwa wątki pracujące z bazą danych zablokowały się wzajemnie. Aby zdiagnozować zakleszczenia przy pomocy tej funkcjonalności JVM, konieczne jest umieszczenie wywołań operacji zrzutu wątku w różnych miejscach programu i przetestowanie aplikacji. Następnie należy przeanalizować powstałe logi. Jeśli wskażą, że doszło do zakleszczenia, informacje ze zrzutu pomogą wykryć warunki, w jakich do niego doszło. Ogólnie rzecz biorąc, należy unikać sytuacji takich jak te w przykładach impasu. W takich przypadkach aplikacja najprawdopodobniej będzie działać stabilnie. Ale nie zapomnij o testowaniu i przeglądzie kodu. Pomoże to zidentyfikować problemy, jeśli wystąpią. W przypadkach, gdy tworzysz system, dla którego odtworzenie pola zakleszczenia jest krytyczne, możesz skorzystać z metody opisanej w sekcji „Jak uniknąć zakleszczenia?”. W tym przypadku metoda lockInterruptiblyinterfejsu Lockz java.util.concurrent.locks. Umożliwia przerwanie w ten sposób wątku, który zajmował monitor (i tym samym uwolnienie monitora).