Developers familiar with parallel programming are also familiar with a wide range of potential problems that can occur when practicing the art. One of the most well-known issues is “deadlock,” where two or more operations are waiting on each other to complete in a manner such that none of them will be able to complete.
I’ve received a few times now a question along the lines of the following: “previously I was using synchronous blocking mechanisms, and I had to be careful to avoid deadlocks… now that I’m moving to more asynchronous mechanisms, do I still need to worry about deadlocks?” In short: yes.
There are four conditions, known as the Coffman conditions, that are necessary for a deadlock to occur. Remove any one of these, and a deadlock can’t happen:
- Mutual exclusion. There’s a resource that only one entity can use at a time.
- Hold and wait. An entity is holding one resource while waiting for another.
- No preemption. An entity gets to decide when it releases its hold on a resource.
- Circular wait. There must be a cycle of waits, such that entity 1 is waiting on a resource held by entity 2; entity 2 is waiting on a resource held by entity 3; …; and entity N is waiting on a resource held by entity 1.
Note that in these conditions, I’ve used the word “wait” several times, but I’ve not specified how that wait must be implemented. It actually doesn’t matter. Whether the “wait” blocks a thread or asynchronously schedules a continuation or callback, the same rules apply.
We can easily see this in action with a simple repro:
static void SimpleTaskTaskDeadlock()
{
var bothTasksCreated = new TaskCompletionSource<bool>();
Task t2 = null;
Task t1 = Task.Run(async delegate
{
await bothTasksCreated.Task;
Console.WriteLine(“t1 waiting for t2…”);
await t2; // instead of a synchronous t2.Wait()
Console.WriteLine(“… t1 done.”);
});
t2 = Task.Run(async delegate
{
await bothTasksCreated.Task;
Console.WriteLine(“t2 waiting for t1…”);
await t1; // instead of a synchronous t1.Wait()
Console.WriteLine(“… t2 done.”);
});
bothTasksCreated.SetResult(true);
}
In this example, we’re creating two tasks, each of which asynchronously waits for the other to complete. Obviously that can never happen, and if you run this, you’ll indeed find that the “done” messages are never output.
Just as the same kinds of issues exist regardless of whether waiting synchronously or asynchronously, so too do the same solutions exist. To see this, let’s look at one of the classic example problems in computer science: Dining Philosophers. Formulated by Edsger Dijkstra and then Tony Hoare, the dining philosophers problem involves five philosophers sitting around a circular table, with a bowl containing an unlimited amount of spaghetti in front of each of them. Between each philosopher is a fork. As spaghetti is slippery, you can only eat it with two forks. The philosophers each alternate between thinking and eating, and when they want to eat, they need to pick up both the forks to their left and right, eat, and put the forks back down. The question of the problem: how do you avoid getting into a situation where none of the philosophers are able to eat? If, for example, each philosopher immediately decided to eat, and each philosopher picked up their left fork, all of the philosophers would be holding only one fork, and none would be able to get the second fork necessary to eat. They might all just sit there waiting for the philosopher to their right to put down a fork so they can eat. Deadlock!
Here’s one implementation of this using async/await. We’re using SemaphoreSlim instances to represent our forks. To pick up a fork, a philosopher acquires the semaphore (asynchronously waiting via WaitAsync for it to be available), and to put down the fork, the philosopher releases the semaphore.
static Task DiningPhilosophersAsync()
{
const int timescale = 10, meals = Int32.MaxValue;
var philosophers = new[] { “Plato”, “Nietzsche”, “Locke”, “Hobbes”, “Descartes” };
var forks = philosophers.Select(_ => new SemaphoreSlim(1, 1)).ToList();
return Task.WhenAll(philosophers.Select((name,id) =>
{
var myForks = new int[] { id, (id + 1) % philosophers.Length };
return Task.Run(async delegate
{
var rand = new Random();
// Think and eat, repeatedly
for (int meal = 0; meal < meals; meal++)
{
// Think
Console.WriteLine(“{0} thinking…”, name);
await Task.Delay(rand.Next(10) * timescale);
// Pick up forks
await forks[myForks[0]].WaitAsync();
Console.WriteLine(“t{0} waiting for 2nd fork…”, name);
await forks[myForks[1]].WaitAsync();
// Eat
Console.WriteLine(“tt{0} eating…”, name);
await Task.Delay(rand.Next(10) * timescale);
// Put down forks
forks[myForks[0]].Release();
forks[myForks[1]].Release();
}
});
}));
}
Note that I’ve not done anything in this implementation to avoid deadlock, and sure enough, when I run it, I frequently get the following output (we’re dealing with concurrency and races here, so we’re not guaranteed to get this output every time):
Hobbes thinking…
Locke thinking…
Plato thinking…
Nietzsche thinking…
Descartes thinking…
Nietzsche waiting for 2nd fork…
Locke waiting for 2nd fork…
Hobbes waiting for 2nd fork…
Plato waiting for 2nd fork…
Descartes waiting for 2nd fork…
To prevent this deadlock from occurring, I can eliminate one of the four Coffman conditions, just as I would have if I was using synchronous waiting rather than asynchronous waiting. For this particular example, the easiest condition to eliminate is #4, the circular wait, and I can do so via “lock ordering”. The idea behind lock ordering (sometimes referred to as a lock hierarchy) is to always ensure that locks are taken in the same order. In the above code example, the philosophers will try to acquire the following locks:
- Plato: 0 then 1
- Nietzshe: 1 then 2
- Locke: 2 then 3
- Hobbes: 3 then 4
- Descartes: 4 then 0
Note that most of the philosophers are acquiring the lower numbered lock first and then the higher numbered lock… except for that pesky Descartes, who’s acquiring the higher numbered lock first and then the lower numbered lock. If we fix that so that the lower numbered lock is always acquired first, we eliminate the possibility of a cycle, and thus we eliminate the possibility of deadlock. To implement that, let’s add one line to sort the forks of each philosopher:
static Task DiningPhilosophersAsync()
{
const int timescale = 10, meals = Int32.MaxValue;
var philosophers = new[] { “Plato”, “Nietzsche”, “Locke”, “Hobbes”, “Descartes” };
var forks = philosophers.Select(_ => new SemaphoreSlim(1, 1)).ToList();
return Task.WhenAll(philosophers.Select((name,id) =>
{
var myForks = new int[] { id, (id + 1) % philosophers.Length };
return Task.Run(async delegate
{
Array.Sort(myForks);
var rand = new Random();// Think and eat, repeatedly
for (int meal = 0; meal < meals; meal++)
{
// Think
Console.WriteLine(“{0} thinking…”, name);
await Task.Delay(rand.Next(10) * timescale);
// Pick up forks
await forks[myForks[0]].WaitAsync();
Console.WriteLine(“t{0} waiting for 2nd fork…”, name);
await forks[myForks[1]].WaitAsync();
// Eat
Console.WriteLine(“tt{0} eating…”, name);
await Task.Delay(rand.Next(10) * timescale);
// Put down forks
forks[myForks[0]].Release();
forks[myForks[1]].Release();
}
});
}));
}
Now, all of the philosophers will pick up their left fork first and then their right fork, except for Descartes, who will pick up his right fork first and then his left fork. Our philosophers can now think and eat to their hearts content.
Don’t let this deadlock discussion scare you. Using async/await doesn’t make deadlocks any more likely than they were before; you still need the same conditions you always previously needed in order to end up with these kinds of situations. In fact, there are often mitigating factors when using async/await that make deadlocks less likely. One such factor is that async/await are often used from a UI thread, such that all work ends up being serviced by that one thread. Let’s assume we only have one thread to serve all of our philosophers’ eating needs. If we only have one thread, then the individual waits on both of a philosopher’s forks will, in effect, be atomic, because no other philosopher could run concurrently so as to pick up forks at the same time (and because the Task return from WaitAsync will complete synchronously, since no one else was holding the semaphore, such that the await on that Task doesn’t suspend). This eliminates condition #2, hold and wait, and thus avoids deadlock. So, if all of this code was running on the UI thread (e.g. I hadn’t used Task.Run and I’d invoked this from the UI thread of my app), this wouldn’t have deadlocked in the first place, even without the sorting of the array. I can get that same serialized behavior in my console app by using a ConcurrentExclusiveSchedulerPair to ensure that all of the work done by the philosophers is serialized:
static Task DiningPhilosophersAsync()
{
const int timescale = 10, meals = Int32.MaxValue;
var philosophers = new[] { “Plato”, “Nietzsche”, “Locke”, “Hobbes”, “Descartes” };
var forks = philosophers.Select(_ => new SemaphoreSlim(1, 1)).ToList();
var tf = new TaskFactory(new ConcurrentExclusiveSchedulerPair().ExclusiveScheduler);
return Task.WhenAll(philosophers.Select((name,id) =>
{
var myForks = new int[] { id, (id + 1) % philosophers.Length };
return tf.StartNew(async delegate
{
var rand = new Random();
// Think and Eat, repeatedly
for (int meal = 0; meal < meals; meal++)
{
// Think
Console.WriteLine(“{0} thinking…”, name);
await Task.Delay(rand.Next(10) * timescale);
// Pick up forks
await forks[myForks[0]].WaitAsync();
Console.WriteLine(“t{0} waiting for 2nd fork…”, name);
await forks[myForks[1]].WaitAsync();
// Eat
Console.WriteLine(“tt{0} eating…”, name);
await Task.Delay(rand.Next(10) * timescale);
// Put down forks
forks[myForks[0]].Release();
forks[myForks[1]].Release();
}
}).Unwrap();
}));
}
0 comments