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.
|
1 |
<span class="kwrd">public</span> <span class="kwrd">class</span> Philosopher<br />{<br /> <span class="kwrd">private</span> ChopStick rightChopstick, leftChopstick;<br /> <span class="kwrd">private</span> <span class="kwrd">int</span> timeToThink;<br /> <span class="kwrd">private</span> <span class="kwrd">string</span> name;<br /><br /> <span class="kwrd">public</span> Philosopher(<span class="kwrd">string</span> name, ChopStick rightChopstick, ChopStick leftChopstick, <span class="kwrd">int</span> timeToThink)<br /> {<br /> <span class="kwrd">this</span>.name = name;<br /> <span class="kwrd">this</span>.rightChopstick = rightChopstick;<br /> <span class="kwrd">this</span>.leftChopstick = leftChopstick;<br /> <span class="kwrd">this</span>.timeToThink = timeToThink;<br /> IsAlive = <span class="kwrd">true</span>;<br /> }<br /><br /> <span class="kwrd">public</span> <span class="kwrd">string</span> Name { get { <span class="kwrd">return</span> name; } }<br /> <span class="kwrd">public</span> <span class="kwrd">bool</span> IsAlive { get; set; }<br /><br /> <span class="kwrd">public</span> <span class="kwrd">void</span> Run()<br /> {<br /> <span class="kwrd">while</span> (IsAlive)<br /> {<br /> Think();<br /> TryToEat();<br /> }<br /> }<br /><br /> <span class="kwrd">public</span> <span class="kwrd">void</span> Think()<br /> {<br /> Console.WriteLine(<span class="str">"{0} is thinking"</span>, name);<br /> Thread.Sleep(timeToThink);<br /> Console.WriteLine(<span class="str">"{0} done thinking"</span>, name);<br /> }<br /><br /> <span class="kwrd">public</span> <span class="kwrd">void</span> TryToEat()<br /> {<br /> <span class="kwrd">lock</span> (rightChopstick)<br /> {<br /> Console.WriteLine(<span class="str">"{0} grabbed right Chopstick"</span>, name);<br /> <span class="kwrd">lock</span> (leftChopstick)<br /> {<br /> Console.WriteLine(<span class="str">"{0} grabbed Left chopstick"</span>, name);<br /> Console.WriteLine(<span class="str">"{0} is eating"</span>, name);<br /> }<br /> }<br /><br /> Console.WriteLine(<span class="str">"{0} has finished eating"</span>, name);<br /> }<br />} |
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:
|
1 |
[TestFixture]<br /><span class="kwrd">public</span> <span class="kwrd">class</span> DiningPhiloRacer<br />{<br /> [Test]<br /> <span class="kwrd">public</span> <span class="kwrd">void</span> DiningPhilosefers_Run_FindDeadlock()<br /> {<br /> var c1 = <span class="kwrd">new</span> ChopStick();<br /> var c2 = <span class="kwrd">new</span> ChopStick();<br /> var c3 = <span class="kwrd">new</span> ChopStick();<br /><br /> ThreadTest<br /> .AddThreadAction(() => <span class="kwrd">new</span> Philosopher(<span class="str">"Plato"</span>, c1, c2, 0).TryToEat())<br /> .AddThreadAction(() => <span class="kwrd">new</span> Philosopher(<span class="str">"Konfucius"</span>, c2, c3, 0).TryToEat())<br /> .AddThreadAction(() => <span class="kwrd">new</span> Philosopher(<span class="str">"Socrates"</span>, c3, c1, 0).TryToEat())<br /> .Start();<br /> }<br />} |
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 hisher 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
