2. Deadlock

Deadlock

A deadlock is where both threads get stuck waiting on acquiring a lock that the other thread is currently holding. e.g. thread A holds lock X and thread B holds lock Y; thread A requires lock Y to proceed and thread B requires lock X to proceed.

A deadlock can occur if the following conditions are true:

• Mutual Exclusion: existence of critical sections
• Hold and Wait: a thread is currently holding a lock and seeking to acquire others
• No preemption: a lock is only released when the holding thread releases it
• Circular wait: there exists a cycle of threads waiting on each other for locks

Link to original

An example of a deadlock situation is:

public static void transfer(BankAccount from, BankAccount to, double amount) {
	synchronized(from) {
		synchronized(to) {
			from.withdraw(amount);
			to.deposit(amount);
		}
	}
}

A simple solution would be to always order the lock acquisition:

public static void transfer(BankAccount from, BankAccount to, double amount) {
	var first = first.getID() < second.getId() ? to : from;
	var second = first.getID() < second.getId() ? from : to;
	
	synchronized(first) {
		synchronized(second) {
			from.withdraw(amount);
			to.deposit(amount);
		}
	}
}

Dining Philosophers Problem

There are give philosophers sitting at a table. They alternate between thinking and eating. Each thinks for a random period of time until they feel hungry then they attempt to eat until they are full.

Each philosopher requires two forks to eat, but there are only five forks on the table, in the positions as shown below:

As soon as an adjacent fork is available, a philosopher will pick it up. They cannot eat until they have two forks; one in each hand.

Philosophers are selfish and greedy and do not coordinate their actions. An eating philosopher will eat until they are ready to stop and think again. They will also immediately grab a fork, even if they can’t use it yet because it’s the only one they have.

We can solve this issue by making the final philosopher try to pick up their right fork first. This helps avoid a circular wait conditions where all of the philosophers are waiting on the philosopher to the right of them.