Avoiding Deadlock

Table of contents:

Problem

Your threads are competing for exclusive access to the same resources. With no coordination between threads, youll end up with deadlock. Thread A will be blocking, waiting for a resource held by thread B, and thread B will be blocking, waiting for a resource held by thread A. Neither thread will ever be seen again.

Solution

Theres no simple mix-in solution to this problem. You need to come up with some rules for how your threads acquire locks, and make sure your code always abides by them.

Basically, you need to guarantee that all your threads acquire locks in the same order. Impose an ordering (formally or informally) on all the locks in your program and make sure that your threads always acquire locks in ascending numerical order.

Heres how it would work. The standard illustration of deadlock is the Dining Philosophers problem. A table of philosophers are sharing a plate of rice and some chopsticks, but there aren enough utensils to go around. When there are only two chopsticks, its easy to see the problem. If philosopher A is holding one chopstick (that is, has a lock on it), and philosopher B is holding the other, then nobody can eat.

In this scenario, youd designate the the lock on one chopstick as lock #1, and the lock on the other chopstick as lock #2. If you guarantee that no philosopher will pick up chopstick #2 unless they e already picked up the chopstick #1, deadlock is impossible. You can guarantee this by simply making all the philosophers implement the same behavior:

	require 	hread
	$chopstick1 = Mutex.new
	$chopstick2 = Mutex.new

	class Philosopher < Thread
	 def initialize(name)
	 super do
	 loop do
	 $chopstick1.synchronize do
	 puts "#{name} has picked up one chopstick."
	 $chopstick2.synchronize do
	 puts "#{name} has picked up two chopsticks and eaten a " +
	 "bite of tasty rice."
	 end
	 end
	 end
	 end
	 end
	end
	Philosopher.new(Moore)
	Philosopher.new(Anscombe)
	# Moore has picked up one chopstick.
	# Moore has picked up two chopsticks and eaten a bite of tasty rice.
	# Anscombe has picked up one chopstick.
	# Anscombe has picked up two chopsticks and eaten a bite of tasty rice.
	# Moore has picked up one chopstick.
	# Moore has picked up two chopsticks and eaten a bite of tasty rice.
	# …

Discussion

Its hard to come up with an ordering of resources that isn totally arbitrary. Why is chopstick #1 designated #1 and not #2? It just is. When youve got more than a few locks, its hard to remember the order.

But if you keep a list of the locks in the proper order, you can have Ruby handle the locking order for you. The lock_all method defined below takes an unordered list of locks, and makes sure they get locked in the "right" order, as defined in the global hash $lock_order:

	require 	hread
	pool_lock, lion_lock, penguin_lock, cabbage_lock = (1..4).collect { Mutex.new }
	locks = [pool_lock, lion_lock, penguin_lock, cabbage_lock]
	$lock_order = {}
	locks.each_with_index { |lock, i| $lock_order[lock] = i }

	def lock_all(*locks)
	 ordered_locks = locks.sort_by { |x| $lock_order[x] }
	 ordered_locks.each do |lock|
	 puts "Locking #{$lock_order[lock]}." if $DEBUG
	 lock.lock
	 end
	 begin
	 yield
	 ensure
	 ordered_locks.reverse_each do |lock|
	 puts "Unlocking #{$lock_order[lock]}." if $DEBUG
	 lock.unlock
	 end
	 end
	end

Now you can simply pass the locks you want to get into lock_all, without having to keep track of an arbitrary order:

	$DEBUG = true
	lock_all(penguin_lock, pool_lock) do
	 puts "Im putting the penguin in the pool."
	end
	# Locking 0.
	# Locking 2.
	# Im putting the penguin in the pool.
	# Unlocking 2.
	# Unlocking 0.

When lock_all encounters a mutex thats already locked, the thread blocks until the mutex becomes available. A less greedy alternative is to drop all of the mutexes already obtained and try again from the start. This makes deadlock less likely even when not all of the code respects the order of the locks.

There are two locking-related problems that you can solve by imposing a lock ordering. The first is resource starvation. In the context of the dining philosophers, this would mean that one philosopher continually puts down chopstick #1 and immediately takes it up again, preventing anyone else from eating.

The thread library prevents this problem by keeping a list of the threads that are waiting for a lock to be released. Once its released, Ruby wakes up the first thread in line. So threads get the lock in the order they asked for it, rather than it being a free-for-all. You can see this if you create a bunch of Philosopher objects using the example from the Solution. Even if there are 20 philosophers and only one pair of chopsticks, the philosophers will take turns using the chopsticks in the order they were created, not randomly depending on the whims of the Ruby interpreter.

The second problem is harder to solve: a thread can "deadlock" with itself. The following code looks unobjectionable (why shouldn you be able to lock what you already have?), but it creates a thread that sleeps forever:

	require 	hread
	$lock = Mutex.new
	Thread.new do
	 $lock.synchronize { $lock.synchronize { puts I synchronized twice! } }
	end

The first time you call lock.synchronize, everything works fine: the Mutex isn locked, and the thread gets a lock on it. The second time, the Mutex is locked, so the thread stops to wait until it gets unlocked.

The problem is, the thread B thats stopping to wait is the same thread as thread A, which has the lock. Thread A is supposed to wake up thread B once its done, but it never does, because it is thread B, and its asleep. A thread can wake itself up.

That looks like a contrived example, but its pretty easy to get there by accident. If you e synchronizing an object, as described in Recipe 20.4, theres a chance youll go too far and synchronize two methods that call each other. Calling one method will synchronize and call the other, which will synchronize and put the thread to sleep forever. Short of hacking Mutex to keep track of which thread has the lock, the only way to avoid this problem is to be careful.

Problem

Solution

Discussion

See Also