This post describes a known deadlock problem and how Typemock Racer can be used to discover deadlocks in .NET code.
You can read more about Typemock Racer at ISerializable Blog.
Overview
The well known computer science problem called Dining philosophers was invented by E. W. Dijkstra:
A number of philosophers (usually five but it could work with any number larger than two) sitting around a table thinking about philosophical problems. Each philosopher has a bowl of rice and two chopsticks he can use to eat it.
Every now and then a philosopher gets hungry and grabs his two chopsticks so he can eats.
So far so good - However to complicate things the philosophers share their chopsticks.
Each philosopher's right chopstick is shared with his neighbor on the right and his left chopstick is shared with his neighbor on the left.
The problem
what happens if Plato would pick his right chopstick but when he tries to grab his left chopstick it is already taken by his colleague?
Obviously being Plato he is patient enough to wait till his fellow thinker finish his snack and put his chopsticks down. however to insure that he does get to eat in the near future Plato keeps the chopstick he managed to get till he can grab the other chopstick.
This behavior can cause a deadlock if each philosopher takes the chopstick to his right at the same time.
The program
As we can see from the story each philosopher does the following actions:
- Think for a while
- Take the chopstick to your right
- Take the chopstick to your left
- Eat
- Put down the chopstick in your left hand
- Put down the chopstick in your right hand
As you can already see we can implement this behavior using locks - each chopstick is an object that the philosopher tries to lock.
My implementation uses three classes:
1. Philosopher - to contain the bulk of our problem logic
2. Chopstick - I could use simple object instead but I like to properly define my classes
3. Table - to contain the overall problem domain
Philosopher class has left and right chopsticks and two functions: Think and TryToEat.
As you can see from the code below TryToEat use lock to acquire the chopsticks and then eat and exit.
public class Philosopher
{
private ChopStick rightChopstick, leftChopstick;
private int timeToThink;
private string name;
public Philosopher(string name, ChopStick rightChopstick, ChopStick leftChopstick, int timeToThink)
{
this.name = name;
this.rightChopstick = rightChopstick;
this.leftChopstick = leftChopstick;
this.timeToThink = timeToThink;
IsAlive = true;
}
public string Name { get { return name; } }
public bool IsAlive { get; set; }
public void Run()
{
while (IsAlive)
{
Think();
TryToEat();
}
}
public void Think()
{
Console.WriteLine("{0} is thinking", name);
Thread.Sleep(timeToThink);
Console.WriteLine("{0} done thinking", name);
}
public void TryToEat()
{
lock (rightChopstick)
{
Console.WriteLine("{0} grabbed right Chopstick", name);
lock (leftChopstick)
{
Console.WriteLine("{0} grabbed Left chopstick", name);
Console.WriteLine("{0} is eating", name);
}
}
Console.WriteLine("{0} has finished eating", name);
}
}
Remark:
in the real program I would have used Thread.Sleep to simulate the time it takes the philosopher to eat but for the example purpose I can do without it.
Typemock Racer
As we can tell the deadlock would happen in TryToEat function and so we can write the following test to check it:
[TestFixture]
public class DiningPhiloRacer
{
[Test]
public void DiningPhilosefers_Run_FindDeadlock()
{
var c1 = new ChopStick();
var c2 = new ChopStick();
var c3 = new ChopStick();
ThreadTest
.AddThreadAction(() => new Philosopher("Plato", c1, c2, 0).TryToEat())
.AddThreadAction(() => new Philosopher("Konfucius", c2, c3, 0).TryToEat())
.AddThreadAction(() => new Philosopher("Socrates", c3, c1, 0).TryToEat())
.Start();
}
}
Running the test is as simple as clicking a mouse button - and presto deadlock found.
Under the deadlock message we can see the scenario that caused the deadlock and with stack trace (blue rectangle) and if that's not enough the user is given an attribute (yellow rectangle) he can use in his\her test to quickly reproduce the scenario that caused the deadlock.
That's it for now
Stay tuned for other uses and tips from the Racer team
