Impasse em Java e métodos para combatê-lo

Ao desenvolver aplicações multithread, muitas vezes surge um dilema: o que é mais importante é a confiabilidade ou o desempenho da aplicação. Por exemplo, usamos sincronização para segurança de thread e, nos casos em que a ordem de sincronização está incorreta, podemos causar conflitos. Também usamos pools de threads e semáforos para limitar o consumo de recursos, e um erro nesse design pode levar a um impasse por falta de recursos. Neste artigo falaremos sobre como evitar deadlocks, bem como outros problemas no desempenho da aplicação. Veremos também como uma aplicação pode ser escrita de forma a ser capaz de se recuperar em casos de deadlock. Deadlock é uma situação em que dois ou mais processos que ocupam alguns recursos estão tentando adquirir alguns outros recursos ocupados por outros processos e nenhum dos processos consegue ocupar o recurso de que necessitam e, consequentemente, liberar o ocupado. Esta definição é muito geral e, portanto, difícil de entender; para uma melhor compreensão, examinaremos os tipos de impasses usando exemplos.

Bloqueio mútuo de ordem de sincronização

Considere a seguinte tarefa: você precisa escrever um método que realize uma transação para transferir uma certa quantia de dinheiro de uma conta para outra. A solução pode ser assim:

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);
			}
		}
	}
}

À primeira vista, esse código é sincronizado normalmente; temos uma operação atômica de verificação e alteração do estado da conta de origem e alteração da conta de destino. Contudo, com esta estratégia de sincronização, pode ocorrer uma situação de impasse. Vejamos um exemplo de como isso acontece. É necessário fazer duas transações: transferir x dinheiro da conta A para a conta B e transferir y dinheiro da conta B para a conta A. Muitas vezes esta situação não causará um impasse, no entanto, num conjunto infeliz de circunstâncias, a transacção 1 ocupará o monitor de conta A, a transacção 2 ocupará o monitor de conta B. O resultado é um impasse: a transacção 1 espera que a transacção 2 liberte o monitor de conta B, mas a transação 2 deve acessar o monitor A, que é ocupado pela transação 1. Um dos grandes problemas dos deadlocks é que eles não são fáceis de encontrar nos testes. Mesmo na situação descrita no exemplo, os threads podem não bloquear, ou seja, esta situação não será reproduzida constantemente, o que dificulta significativamente o diagnóstico. Em geral, o problema descrito de não determinismo é típico de multithreading (embora isso não torne tudo mais fácil). Portanto, a revisão de código desempenha um papel importante na melhoria da qualidade de aplicações multithread, pois permite identificar erros difíceis de reproduzir durante os testes. Isto, claro, não significa que a aplicação não precise ser testada; apenas não devemos esquecer da revisão de código. O que devo fazer para evitar que esse código cause um impasse? Esse bloqueio é causado pelo fato de que a sincronização da conta pode ocorrer em uma ordem diferente. Assim, se você introduzir alguma ordem nas contas (esta é uma regra que permite dizer que a conta A é menor que a conta B), o problema será eliminado. Como fazer isso? Em primeiro lugar, se as contas tiverem algum tipo de identificador único (por exemplo, um número de conta) numérico, minúsculo ou algum outro com um conceito natural de ordem (as strings podem ser comparadas em ordem lexicográfica, então podemos nos considerar sortudos, e iremos sempre Podemos ocupar primeiro o monitor da conta menor e depois a maior (ou vice-versa).

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)}
			}
		}
	}
}

A segunda opção, se não tivermos esse identificador, teremos que inventá-lo nós mesmos. Podemos, numa primeira aproximação, comparar objetos por código hash. Muito provavelmente eles serão diferentes. Mas e se eles forem iguais? Então você terá que adicionar outro objeto para sincronização. Pode parecer um pouco sofisticado, mas o que você pode fazer? Além disso, o terceiro objeto raramente será usado. O resultado ficará assim:

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)
				}
			}
		}
	}
}

Impasse entre objetos

As condições de bloqueio descritas representam o caso de impasse mais fácil de diagnosticar. Freqüentemente, em aplicativos multithread, objetos diferentes tentam acessar os mesmos blocos sincronizados. Isso pode causar impasse. Considere o seguinte exemplo: um aplicativo de despachante de voo. Os aviões informam ao controlador quando chegam ao destino e solicitam permissão para pousar. O controlador armazena todas as informações sobre aeronaves voando em sua direção e pode traçar sua posição no mapa.

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;
	}
}

Entender que existe um bug neste código que pode levar ao deadlock é mais difícil do que no anterior. À primeira vista, não possui ressincronizações, mas não é o caso. Você provavelmente já percebeu que setLocationclasses Planee métodos getMapde classe Dispatchersão sincronizados e chamam métodos sincronizados de outras classes dentro de si. Geralmente, isso é uma má prática. Como isso pode ser corrigido será discutido na próxima seção. Com isso, se o avião chegar ao local, no momento em que alguém decidir pegar o cartão, pode ocorrer um impasse. Ou seja, serão chamados os métodos getMape setLocation, que ocuparão os monitores da instância Dispatchere Planerespectivamente. O método irá então getMapchamar plane.getLocation(especificamente na instância Planeque está ocupada no momento), que aguardará até que o monitor fique livre para cada uma das instâncias Plane. Ao mesmo tempo, o método setLocationserá chamado dispatcher.requestLanding, enquanto o monitor da instância Dispatcherpermanece ocupado desenhando o mapa. O resultado é um impasse.

Chamadas abertas

Para evitar situações como a descrita na seção anterior, recomenda-se utilizar chamadas públicas a métodos de outros objetos. Ou seja, chame métodos de outros objetos fora do bloco sincronizado. Se os métodos forem reescritos usando o princípio das chamadas abertas setLocation, getMapa possibilidade de deadlock será eliminada. Ficará, por exemplo, assim:

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;
}

Impasse de recursos

Deadlocks também podem ocorrer ao tentar acessar alguns recursos que apenas um thread pode usar por vez. Um exemplo seria um pool de conexões de banco de dados. Se alguns threads precisarem acessar duas conexões ao mesmo tempo e as acessarem em ordens diferentes, isso poderá levar a um deadlock. Fundamentalmente, esse tipo de bloqueio não é diferente do bloqueio por ordem de sincronização, exceto que ocorre não ao tentar executar algum código, mas ao tentar acessar recursos.

Como evitar impasses?

É claro que, se o código for escrito sem erros (exemplos dos quais vimos nas seções anteriores), não haverá conflitos nele. Mas quem pode garantir que seu código seja escrito sem erros? É claro que os testes ajudam a identificar uma parte significativa dos erros, mas como vimos anteriormente, erros em código multithread não são fáceis de diagnosticar e mesmo após testar não se pode ter certeza de que não há situações de deadlock. Podemos de alguma forma nos proteger do bloqueio? A resposta é sim. Técnicas semelhantes são usadas em mecanismos de banco de dados, que muitas vezes precisam se recuperar de deadlocks (associados ao mecanismo de transação no banco de dados). A interface Locke suas implementações disponíveis no pacote java.util.concurrent.lockspermitem tentar ocupar o monitor associado a uma instância desta classe utilizando o método tryLock(retorna verdadeiro se foi possível ocupar o monitor). Suponha que temos um par de objetos que implementam uma interface Locke precisamos ocupar seus monitores de forma a evitar o bloqueio mútuo. Você pode implementá-lo assim:

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();
			}
		}
	}
}

Como você pode ver neste programa, ocupamos dois monitores, eliminando a possibilidade de bloqueio mútuo. Observe que o bloqueio try- finallyé necessário porque as classes do pacote java.util.concurrent.locksnão liberam o monitor automaticamente e, se ocorrer alguma exceção durante a execução de sua tarefa, o monitor ficará travado em estado bloqueado. Como diagnosticar impasses? A JVM permite diagnosticar deadlocks exibindo-os em dumps de thread. Esses dumps incluem informações sobre o estado do thread. Se estiver bloqueado, o dump contém informações sobre o monitor que o thread está aguardando para ser liberado. Antes de descartar threads, a JVM analisa o gráfico de monitores em espera (ocupados) e, se encontrar ciclos, adiciona informações de deadlock, indicando os monitores e threads participantes. Um despejo de threads em conflito é assim:

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)

O dump acima mostra claramente que dois threads que trabalham com o banco de dados bloquearam um ao outro. Para diagnosticar deadlocks usando esse recurso da JVM, é necessário fazer chamadas para a operação de dump de thread em vários locais do programa e testar a aplicação. A seguir, você deve analisar os logs resultantes. Se indicarem que ocorreu um impasse, as informações do dump ajudarão a detectar as condições sob as quais ocorreu. Em geral, você deve evitar situações como as dos exemplos de impasse. Nesses casos, o aplicativo provavelmente funcionará de forma estável. Mas não se esqueça dos testes e da revisão do código. Isso ajudará a identificar problemas, caso eles ocorram. Nos casos em que você está desenvolvendo um sistema para o qual a recuperação do campo de deadlock é crítica, você pode utilizar o método descrito na seção “Como evitar deadlocks?”. Nesse caso, o método lockInterruptiblyde interface Lockdo arquivo java.util.concurrent.locks. Ele permite interromper o thread que ocupou o monitor usando este método (e assim liberar o monitor).