Mutual blocking (deadlock) in Java and methods of dealing with it

When developing multi-threaded applications, a dilemma often arises: what is more important is the reliability or operability of the application. For example, we use synchronization for thread safety (thread safety), while in cases where the synchronization order is wrong, we can cause a deadlock. Also, we use thread pools and semaphores to limit the consumption of resources, while a mistake 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, try to get some other resources occupied by other processes, and none of the processes can occupy the resource they need and, accordingly, free it. This definition is too general, therefore it is difficult to understand, for a better understanding of it, we will consider the types of mutual blocking with examples.

Synchronization Order Mutual

Let's consider the following task: it is necessary to write a method that performs a transaction of transferring 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 recipient account. But, 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, under unfortunate 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 for this transaction 2 must access monitor A, occupied by transaction 1. One of the big problems with mutexes is that they are not easy to find when testing. Even in the situation described in the example, the threads may not block, that is, this situation will not be constantly reproduced, which greatly complicates the diagnosis. In general, the described problem of non-determinism is typical for multithreading (although this does not make it 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 problematic to reproduce during testing. This, of course, does not mean that the application does not need to be tested, just that you should not forget about code review either. What needs to be done so that this code does not lead to deadlock? This blocking is caused by the fact that the synchronization of accounts can occur in a different order. Respectively, 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 the accounts have some kind of unique identifier (for example, account number) numerical, lowercase, or some other with a natural concept of order (strings can be compared in lexicographic order, then we can consider ourselves lucky and we always we can first occupy the monitor of a smaller score, and then a 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 do not have such an identifier, then we will have to invent it ourselves. We can, as a first approximation, compare objects by hash code. Most likely they will be different. But what if they are still the same? Then you have to add another object for synchronization. This may look a bit 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)
				}
			}
		}
	}
}

Mutual blocking between objects

The blocking conditions described represent the easiest case of deadlock to diagnose. Often in multi-threaded applications, different objects try to access the same synchronized blocks. This can lead to deadlock. Consider the following example: a flight controller application. Planes inform the controller when they have arrived at their destination and request permission to land. The controller stores all the information about the aircraft flying in his direction, and can build 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 this code has an error 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 so. You probably already noticed that setLocationclass Planeand getMapclass methods Dispatcherare synchronized and call synchronized methods of other classes internally. This is generally bad practice. How this can be fixed is discussed in the next section. As a result, if the plane arrives at the site, at the same moment that someone decides to get a card, a deadlock can occur. getMapThat is, the methods, and will be called setLocation, which will occupy the instance monitors Dispatcherand Planerespectively. The method will then getMapcall plane.getLocation(specifically for an instancePlane, which is currently busy) that will wait for the monitor to become free for each of the Plane. At the same time setLocation, will be called in the method dispatcher.requestLanding, leaving the instance monitor Dispatcherbusy drawing the map. The result is a deadlock.

Open calls

In order to avoid situations like those 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 of the synchronized block. If using the principle of open calls to rewrite the methods setLocationand getMapthe possibility of deadlock will be eliminated. It will look like this, for example:

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 is a database connection pool. If some threads need access to two connections at the same time, and they get that access in a different order, this can lead to deadlock. Fundamentally, this kind of locks are no different from synchronization order locks, except that they occur 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 (of which we saw examples 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 multithreaded code are not easy to diagnose, and even after testing, one cannot be sure that there are no deadlock situations. Can we somehow play it safe from blocking? The answer is yes. Similar techniques are used in database engines, which often need to recover from deadlocks (related to the mechanism of transactions 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 by the methodtryLock(returns true if the monitor was occupied). Suppose we have a couple of objects that implement the 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 can be seen in this program, we occupy two monitors, while excluding the possibility of mutual blocking. Note that the block try- finallyis required because the classes from the packagejava.util.concurrent.locksdo not automatically release the monitor, and if an exception occurs during the execution of your task, the monitor will hang 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 locked, then the dump contains information about the monitor the thread is waiting for. Before dumping threads, the JVM looks at the graph of expected (busy) monitors, and if it finds cycles, it adds deadlock information, indicating the monitors and threads involved. A deadlock thread dump 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 feature of the JVM, it is necessary to place calls to the thread dump operation in various places in the program and test the application. The next step is to analyze the received logs. In cases where they indicate that a deadlock has occurred, the information from the dump will help to detect the conditions for its occurrence. In general, the situations shown in the deadlock examples should be avoided. In such cases, the application will most likely work stably. But don't forget about testing and code reviews. This will help identify problems if they do occur. In cases where you are developing a system for which it is critical to restore the deadlock field, you can use the method described in the "How to avoid deadlocks?" section. In this case, the method may also be useful.lockInterruptiblyinterface Lockfrom the package java.util.concurrent.locks. It allows you to interrupt the thread occupying the monitor with this method (and thus release the monitor).