Richard’s Weblog

February 21, 2014

Java deadlock, livelock and lock starvation examples

Filed under: Threading — Richard @ 11:55 pm
Tags: , , , ,

The following examples uses a bank account analogy, where we can deposit to, widthraw from and transfer money from one account to another. Three different implementations (bad ones) of the transfer operation are used to show how a Deadlock, a LiveLock or a LockStarvation could occur while working with multiple processes/threads.

Deadlock

I think the deadlock is the easiest one to understand. It happens when a process wait for another one who is using some needed resource (ie: file or database table row) to finish with it, while the other process also wait for the first process to release some other resource.

In the folowing example, two different threads attempts to transfer money between the two same accounts at the same time : 

package com.example.thread.deadlock._synchronized;

public class BankAccount {
	double balance;
	int id;
	
	BankAccount(int id, double balance) {
		this.id = id;
		this.balance = balance;
	}
	
	void withdraw(double amount) {
		// Wait to simulate io like database access ...
		try {Thread.sleep(10l);} catch (InterruptedException e) {}
		balance -= amount;
	}
	
	void deposit(double amount) {
		// Wait to simulate io like database access ...
		try {Thread.sleep(10l);} catch (InterruptedException e) {}
		balance += amount;
	}
	
	static void transfer(BankAccount from, BankAccount to, double amount) {
		synchronized(from) {
			from.withdraw(amount);
			synchronized(to) {
				to.deposit(amount);
			}
		}
	}
	
	public static void main(String[] args) {
		final BankAccount fooAccount = new BankAccount(1, 100d);
		final BankAccount barAccount = new BankAccount(2, 100d);
		
		new Thread() {
			public void run() {
				BankAccount.transfer(fooAccount, barAccount, 10d);
			}
		}.start();
		
		new Thread() {
			public void run() {
				BankAccount.transfer(barAccount, fooAccount, 10d);
			}
		}.start();
		
	}
}


Here is what happens. Thread1 wants to transfer 10 dollars from foo account to bar account. Almost at the same time, Thread2 wants to tranfer 10 dollars from the bar account to the foo account. Here how goes the execution of the code above :

  • Thread1 starts
  • Thread2 starts
  • Thread1 try to lock account foo. Nobody is locking foo so the lock is granted to thread 1.
  • Thread2 try to lock account bar. Nobody is locking bar so the lock is granted to thread 2.
  • Thread1 try to lock account bar. Since Thread2 is already olding the lock on the bar account, Thread1 is NOT granted the lock.
  • Thread2 try to lock account foo. Since Thread1 is already olding the lock on the foo account, Thread2 is NOT granted the lock.
  • Thread1 waits for Thread2 to release the lock on the bar account.
  • Thread2 waits for Thread1 to release the lock on the foo account.

The two threads will wait infinitely one after the other.
Just for fun, here is another version of the same deadlock behavior, but this time using the java.util.concurrent.locks package :

package com.example.thread.deadlock.lock;

import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;

public class BankAccount {
	double balance;
	final int id;
	final Lock lock = new ReentrantLock();
	
	BankAccount(int id, double balance) {
		this.id = id;
		this.balance = balance;
	}
	
	void withdraw(double amount) {
		// Wait to simulate io like database access ...
		try {Thread.sleep(10l);} catch (InterruptedException e) {}
		balance -= amount;
	}
	
	void deposit(double amount) {
		// Wait to simulate io like database access ...
		try {Thread.sleep(10l);} catch (InterruptedException e) {}
		balance += amount;
	}
	
	static void transfer(BankAccount from, BankAccount to, double amount) {
		from.lock.lock();
			from.withdraw(amount);
			to.lock.lock();
				to.deposit(amount);
			to.lock.unlock();
		from.lock.unlock();
	}
	
	public static void main(String[] args) {
		final BankAccount fooAccount = new BankAccount(1, 100d);
		final BankAccount barAccount = new BankAccount(2, 100d);
		
		new Thread() {
			public void run() {
				BankAccount.transfer(fooAccount, barAccount, 10d);
			}
		}.start();
		
		new Thread() {
			public void run() {
				BankAccount.transfer(barAccount, fooAccount, 10d);
			}
		}.start();
		
	}
}

LiveLock

A LiveLock looks like a deadlock in the sense that two (or more) processes are blocking each others. But with the livelock, each process is waiting “actively”, trying to resolve the problem on its own (like reverting back its work and retry). A live lock occurs when the combination of these processes’s efforts to resolve the problem makes it impossible for them to ever terminate.
Let’s take the example of the bank account again. Suppose another erroneous implementation of two simultaneous transfer operation. Here again, two threads tries to transfer money from one account to another one at the same time. But this time, instead of waiting for a lock to be released when a required account is locked, a thread will juste revert its work if any, and retry the whole operation in loop until successful :

package com.example.thread.livelock;

import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;

public class BankAccount {
	double balance;
	int id;
	Lock lock = new ReentrantLock();

	BankAccount(int id, double balance) {
		this.id = id;
		this.balance = balance;
	}

	boolean withdraw(double amount) {
		if (this.lock.tryLock()) {
			// Wait to simulate io like database access ...
			try {Thread.sleep(10l);} catch (InterruptedException e) {}
			balance -= amount;
			return true;
		}
		return false;
	}

	boolean deposit(double amount) {
		if (this.lock.tryLock()) {
			// Wait to simulate io like database access ...
			try {Thread.sleep(10l);} catch (InterruptedException e) {}
			balance += amount;
			return true;
		}
		return false;
	}

	public boolean tryTransfer(BankAccount destinationAccount, double amount) {
		if (this.withdraw(amount)) {
			if (destinationAccount.deposit(amount)) {
				return true;
			} else {
				// destination account busy, refund source account.
				this.deposit(amount);
			}
		}

		return false;
	}

	public static void main(String[] args) {
		final BankAccount fooAccount = new BankAccount(1, 500d);
		final BankAccount barAccount = new BankAccount(2, 500d);

		new Thread(new Transaction(fooAccount, barAccount, 10d), "transaction-1").start();
		new Thread(new Transaction(barAccount, fooAccount, 10d), "transaction-2").start();

	}

}
class Transaction implements Runnable {
	private BankAccount sourceAccount, destinationAccount;
	private double amount;

	Transaction(BankAccount sourceAccount, BankAccount destinationAccount, double amount) {
		this.sourceAccount = sourceAccount;
		this.destinationAccount = destinationAccount;
		this.amount = amount;
	}

	public void run() {
		while (!sourceAccount.tryTransfer(destinationAccount, amount))
			continue;
		System.out.printf("%s completed ", Thread.currentThread().getName());
	}

}

The result of this execution is somewhat similar to the one of the deadlock example, but this time the CPU is working harder.
Typically the program will execute like this :

  • transaction-1 withdraw 10$ from account “1″
  • transaction-2 withdraw 10$ from account “2″
  • transaction-1 failed to deposit in account “2″ because “transaction-2″ already old the lock on that account. Account “1″ refunded
  • transaction-2 failed to deposit in account “1″ because “transaction-1″ already old the lock on that account. Account “2″ refunded
  • transaction-1 withdraw 10.000000 from account “1″
  • transaction-2 withdraw 10.000000 from account “2″
  • transaction-1 failed to deposit in account “2″ because “transaction-2″ already old the lock on that account. Account “1″ refunded
  • transaction-2 failed to deposit in account “1″ because “transaction-1″ already old the lock on that account. Account “2″ refunded
  • and so on …

Lock Starvation

Lock starvation is all about thread priority. It occurs when a thread, having lesser priority than other ones, is constantly waiting for a lock, never able to take it because other thread(s) with higher priority are constanly aquiring the lock. Suppose our bank account example. The bank adds a feature that constantly watch one’s account balance and send an email if that balance goes below zero (a monitor thread). But in this implementation, the monitor thread is of a higher priority than the transaction threads. Because of this, the transaction threads can take a very long time(say ever) to execute. See the example :

package com.example.thread.lockstarvation;

public class BankAccount {
	private double balance;
	int id;

	BankAccount(int id, double balance) {
		this.id = id;
		this.balance = balance;
	}
	
	synchronized double getBalance() {
		// Wait to simulate io like database access ...
		try {Thread.sleep(100l);} catch (InterruptedException e) {}
		return balance;
	}
	
	synchronized void withdraw(double amount) {
		balance -= amount;
	}

	synchronized void deposit(double amount) {
		balance += amount;
	}

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

	public static void main(String[] args) {
		final BankAccount fooAccount = new BankAccount(1, 500d);
		final BankAccount barAccount = new BankAccount(2, 500d);
		
		Thread balanceMonitorThread1 = new Thread(new BalanceMonitor(fooAccount), "BalanceMonitor");
		Thread transactionThread1 = new Thread(new Transaction(fooAccount, barAccount, 250d), "Transaction-1");
		Thread transactionThread2 = new Thread(new Transaction(fooAccount, barAccount, 250d), "Transaction-2");
		
		balanceMonitorThread1.setPriority(Thread.MAX_PRIORITY);
		transactionThread1.setPriority(Thread.MIN_PRIORITY);
		transactionThread2.setPriority(Thread.MIN_PRIORITY);
		
		// Start the monitor
		balanceMonitorThread1.start();
		
		// And later, transaction threads tries to execute.
		try {Thread.sleep(100l);} catch (InterruptedException e) {}
		transactionThread1.start();
		transactionThread2.start();

	}

}
class BalanceMonitor implements Runnable {
	private BankAccount account;
	BalanceMonitor(BankAccount account) { this.account = account;}
	boolean alreadyNotified = false;
	
	@Override
	public void run() {
		System.out.format("%s started execution%n", Thread.currentThread().getName());
		while (true) {
			if(account.getBalance() <= 0) {
				// send email, or sms, clouds of smoke ...
				break;
			}
		}
		System.out.format("%s : account has gone too low, email sent, exiting.", Thread.currentThread().getName());
	}
	
}
class Transaction implements Runnable {
	private BankAccount sourceAccount, destinationAccount;
	private double amount;

	Transaction(BankAccount sourceAccount, BankAccount destinationAccount, double amount) {
		this.sourceAccount = sourceAccount;
		this.destinationAccount = destinationAccount;
		this.amount = amount;
	}

	public void run() {
		System.out.format("%s started execution%n", Thread.currentThread().getName());
		sourceAccount.transfer(destinationAccount, amount);
		System.out.printf("%s completed execution%n", Thread.currentThread().getName());
	}

}

In that example, a balance monitor is started on account foo. This balance monitor should stop when the balance it monitors falls under zero. An then, two transaction threads are started, each one taking 250$ from the foo account, wich started at 500$. That should normally leaves the account with 0$, wich should trigger the monitor to send email and terminates.
If you try to execute this program, chances are that it will end successfully, but with abnormal execution time. This is because the transfer transactions have a hard time aquiring the lock on the foo account : the monitor almost always have it.
The execution could be seen as this :

  • BalanceMonitor lock account foo
  • Transaction 1 tries to acquire lock on account foo. Cannot, because balance monitor hold it. Waiting …
  • BalanceMonitor read balance
  • BalanceMonitor unlock acccount
  • BalanceMonitor lock account foo
  • Transaction 1 retry to aquire lock, Cannot, BalanceMonitor still holding it.
  • BalanceMonitor read balance
  • BalanceMonitor unlock acccount
  • BalanceMonitor lock account foo
  • Transaction 1 retry to aquire lock, Cannot, BalanceMonitor still holding it.
  • BalanceMonitor read balance
  • BalanceMonitor unlock acccount
  • And so on a lot of time until Transaction 1 and Transaction 2 finally execute

Conlusion

If you have to work with lots of threads, better drink a lot of coffee :)

About these ads

Leave a Comment »

No comments yet.

RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

The Rubric Theme. Create a free website or blog at WordPress.com.

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: