Deadlock in Java and methods to combat it

When developing multi-threaded applications, a dilemma often arises: what is more important is the reliability or performance of the application. For example, we use synchronization for thread safety, and in cases where the synchronization order is incorrect, we can cause deadlocks. We also use thread pools and semaphores to limit resource consumption, and an error in this design can lead to deadlock due to lack of resources. In this article we will talk about how to avoid deadlock, as well as other problems in the performance of the application. We will also look at how an application can be written in such a way as to be able to recover in cases of deadlock. Deadlock is a situation in which two or more processes occupying some resources are trying to acquire some other resources occupied by other processes and none of the processes can occupy the resource they need and, accordingly, release the occupied one. This definition is too general and therefore difficult to understand; for a better understanding, we will look at the types of deadlocks using examples.

Synchronization Order Mutual Locking

Consider the following task: you need to write a method that carries out a transaction to transfer a certain amount of money from one account to another. The solution might look like this:

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

At first glance, this code is synchronized quite normally; we have an atomic operation of checking and changing the state of the source account and changing the destination account. However, with this synchronization strategy, a deadlock situation may occur. Let's look at an example of how this happens. It is necessary to make two transactions: transfer x money from account A to account B, and transfer y money from account B to account A. Often this situation will not cause a deadlock, however, in an unfortunate set of circumstances, transaction 1 will occupy account monitor A, transaction 2 will occupy account monitor B. The result is a deadlock: transaction 1 waits for transaction 2 to release account monitor B, but transaction 2 must access monitor A, which is occupied by transaction 1. One of the big problems with deadlocks is that they are not easy to find in testing. Even in the situation described in the example, threads may not block, that is, this situation will not be constantly reproduced, which significantly complicates diagnostics. In general, the described problem of non-determinism is typical for multithreading (although this does not make it any easier). Therefore, code review plays an important role in improving the quality of multi-threaded applications, since it allows you to identify errors that are difficult to reproduce during testing. This, of course, does not mean that the application does not need to be tested; we just shouldn’t forget about code review. What should I do to prevent this code from causing a deadlock? This blocking is caused by the fact that account synchronization can occur in a different order. Accordingly, if you introduce some order on the accounts (this is some rule that allows you to say that account A is less than account B), then the problem will be eliminated. How to do it? Firstly, if accounts have some kind of unique identifier (for example, an account number) numerical, lowercase, or some other with a natural concept of order (strings can be compared in lexicographical order, then we can consider ourselves lucky, and we will always We can first occupy the monitor of the smaller account, and then the larger one (or 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)}
			}
		}
	} 
}

The second option, if we don’t have such an identifier, we’ll have to come up with it ourselves. We can, to a first approximation, compare objects by hash code. Most likely they will be different. But what if they turn out to be the same? Then you will have to add another object for synchronization. It may look a little sophisticated, but what can you do? And besides, the third object will be used quite rarely. The result will look like this:

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

Deadlock between objects

The described blocking conditions represent the easiest case of deadlock to diagnose. Often in multi-threaded applications, different objects try to access the same synchronized blocks. This may cause deadlock. Consider the following example: a flight dispatcher application. Airplanes tell the controller when they have arrived at their destination and request permission to land. The controller stores all the information about aircraft flying in his direction and can plot their position on the 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;
	}
}

Understanding that there is a bug in this code that can lead to deadlock is more difficult than in the previous one. At first glance, it does not have re-syncs, but this is not the case. You've probably already noticed that setLocationclass Planeand getMapclass methods Dispatcherare synchronized and call synchronized methods of other classes within themselves. This is generally bad practice. How this can be corrected will be discussed in the next section. As a result, if the plane arrives at the location, the moment someone decides to get the card, a deadlock can occur. That is, the getMapand methods will be called, setLocationwhich will occupy the instance monitors Dispatcherand Planerespectively. The method will then getMapcall plane.getLocation(specifically on the instance Planethat is currently busy) which will wait for the monitor to become free for each of the instances Plane. At the same time, the method setLocationwill be called dispatcher.requestLanding, while the instance monitor Dispatcherremains busy drawing the map. The result is a deadlock.

Open calls

In order to avoid situations like the one described in the previous section, it is recommended to use public calls to methods of other objects. That is, call methods of other objects outside the synchronized block. If methods are rewritten using the principle of open calls setLocation, getMapthe possibility of deadlock will be eliminated. It will look, for example, like this:

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

Resource deadlock

Deadlocks can also occur when trying to access some resources that only one thread can use at a time. An example would be a database connection pool. If some threads need to access two connections at the same time and they access them in different orders, this can lead to deadlock. Fundamentally, this kind of locking is no different from synchronization order locking, except that it occurs not when trying to execute some code, but when trying to access resources.

How to avoid deadlocks?

Of course, if the code is written without any errors (examples of which we saw in the previous sections), then there will be no deadlocks in it. But who can guarantee that his code is written without errors? Of course, testing helps to identify a significant part of the errors, but as we have seen earlier, errors in multi-threaded code are not easy to diagnose and even after testing you cannot be sure that there are no deadlock situations. Can we somehow protect ourselves from blocking? The answer is yes. Similar techniques are used in database engines, which often need to recover from deadlocks (associated with the transaction mechanism in the database). The interface Lockand its implementations available in the package java.util.concurrent.locksallow you to try to occupy the monitor associated with an instance of this class using the method tryLock(returns true if it was possible to occupy the monitor). Suppose we have a pair of objects that implement an interface Lockand we need to occupy their monitors in such a way as to avoid mutual blocking. You can implement it like this:

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

As you can see in this program, we occupy two monitors, while eliminating the possibility of mutual blocking. Please note that the block try- finallyis necessary because the classes in the package java.util.concurrent.locksdo not automatically release the monitor, and if some exception occurs during the execution of your task, the monitor will be stuck in a locked state. How to diagnose deadlocks? The JVM allows you to diagnose deadlocks by displaying them in thread dumps. Such dumps include information about what state the thread is in. If it is blocked, the dump contains information about the monitor that the thread is waiting for to be released. Before dumping threads, the JVM looks at the graph of waiting (busy) monitors, and if it finds cycles, it adds deadlock information, indicating the participating monitors and threads. A dump of deadlocked threads looks like this:

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)

The above dump clearly shows that two threads working with the database have blocked each other. In order to diagnose deadlocks using this JVM feature, it is necessary to place calls to the thread dump operation in various places in the program and test the application. Next, you should analyze the resulting logs. If they indicate that a deadlock has occurred, the information from the dump will help to detect the conditions under which it occurred. In general, you should avoid situations like those in the deadlock examples. In such cases, the application will most likely work stably. But don't forget about testing and code review. This will help identify problems if they do occur. In cases where you are developing a system for which recovery of the deadlock field is critical, you can use the method described in the section “How to avoid deadlocks?”. In this case, the lockInterruptiblyinterface method Lockfrom the java.util.concurrent.locks. It allows you to interrupt the thread that has occupied the monitor using this method (and thus free the monitor).