The woes of multithreaded design - How to find deadlock using Typemock Racer

I came across an article on Dr’ Dobb’s I’d like to share called The woes of multithreaded design. The amazing thing is that although the article was published at 1997 (11 years ago) the problem described in it is still relevant today.

The article explains basic multithreading concepts (in Java) such as threads, thread safety and so on.

Towards the end of the article there is a description of the following problem:

The Players

There are four "players" in this story:

Employee – Assigned work by his boss.
Marketer – Gives new projects to the boss.
Wimp Manager – Manages both Marketer and Employee but doesn’t decide anything without consulting his boss first.
Manager – Uber boss of the weak manager.

If we take the java code and convert it into C# it would look something like:

<span class="kwrd">public</span> <span class="kwrd">class</span> Employee<br />{<br />    <span class="kwrd">private</span> Manager boss;<br />    <span class="kwrd">public</span> <span class="kwrd">virtual</span> <span class="kwrd">void</span> Work()<br />    {<br />        boss.AssignProject();<br />    }<br /><br />    <span class="kwrd">public</span> Manager Boss<br />    {<br />        get { <span class="kwrd">return</span> boss; }<br />        set { boss = <span class="kwrd">value</span>; }<br />    }<br />}<br /><br /><span class="kwrd">public</span> <span class="kwrd">class</span> Marketer : Employee<br />{<br />    <span class="kwrd">public</span> <span class="kwrd">override</span> <span class="kwrd">void</span> Work()<br />    {<br />        Boss.ReceiveProject();<br />    }<br />}<br /><br /><span class="kwrd">public</span> <span class="kwrd">class</span> WimpManager : Manager<br />{<br />    <span class="kwrd">private</span> <span class="kwrd">object</span> wimpManagerSync = <span class="kwrd">new</span> <span class="kwrd">object</span>();<br /><br />    <span class="kwrd">public</span> <span class="kwrd">override</span> <span class="kwrd">void</span> ReceiveProject()<br />    {<br />        <span class="kwrd">lock</span> (wimpManagerSync)<br />        {<br />            Boss.ReceiveProject();<br />        }<br />    }<br /><br />    <span class="kwrd">public</span> <span class="kwrd">override</span> <span class="kwrd">void</span> AssignProject()<br />    {<br />        <span class="kwrd">lock</span> (wimpManagerSync)<br />        {<br />            Boss.AssignProject();<br />        }<br />    }<br />}<br /><br /><span class="kwrd">public</span> <span class="kwrd">class</span> Manager : Employee<br />{<br />    <span class="kwrd">private</span> <span class="kwrd">bool</span> hasProject;<br />    <span class="kwrd">private</span> AutoResetEvent waitHandle = <span class="kwrd">new</span> AutoResetEvent(<span class="kwrd">false</span>);<br />    <span class="kwrd">private</span> <span class="kwrd">object</span> managerSync = <span class="kwrd">new</span> <span class="kwrd">object</span>();<br /><br />    <span class="kwrd">public</span> <span class="kwrd">virtual</span> <span class="kwrd">void</span> ReceiveProject()<br />    {<br />        <span class="kwrd">lock</span> (managerSync)<br />        {<br />            <span class="rem">// add project to project queue</span><br />            hasProject = <span class="kwrd">true</span>;<br />        }<br />     <br />        waitHandle.Set();<br />    }<br /><br />    <span class="kwrd">public</span> <span class="kwrd">virtual</span> <span class="kwrd">void</span> AssignProject()<br />    {<br />        <span class="kwrd">bool</span> haveNewProject;<br /><br />        <span class="kwrd">lock</span> (managerSync)<br />        {<br />            haveNewProject = hasProject;<br />        }<br /><br />        <span class="kwrd">if</span> (haveNewProject == <span class="kwrd">false</span>)<br />        {<br />            waitHandle.WaitOne();<br />        }<br /><br />        <span class="kwrd">lock</span> (managerSync)<br />        {<br />            <span class="rem">// remove project to project queue</span><br />            hasProject = <span class="kwrd">false</span>;<br />        }<br />    }<br />}

public class Employee { private Manager boss; public virtual void Work() { boss.AssignProject(); } public Manager Boss { get { return boss; } set { boss = value; } } } public class Marketer : Employee { public override void Work() { Boss.ReceiveProject(); } } public class WimpManager : Manager { private object wimpManagerSync = new object(); public override void ReceiveProject() { lock (wimpManagerSync) { Boss.ReceiveProject(); } } public override void AssignProject() { lock (wimpManagerSync) { Boss.AssignProject(); } } } public class Manager : Employee { private bool hasProject; private AutoResetEvent waitHandle = new AutoResetEvent(false); private object managerSync = new object(); public virtual void ReceiveProject() { lock (managerSync) { // add project to project queue hasProject = true; } waitHandle.Set(); } public virtual void AssignProject() { bool haveNewProject; lock (managerSync) { haveNewProject = hasProject; } if (haveNewProject == false) { waitHandle.WaitOne(); } lock (managerSync) { // remove project to project queue hasProject = false; } } }

The Story

Because we’re dealing with a multi threaded problem we have two threads of execution that occur "simultaneously".

The employee thread:

In out story the employee asks his boss for a project to work on.
Not wanting to decide without approval of his manager the wimp manager asks his boss for new project for the employee.
If such project exist the boss assigns it to the wimp boss which in turn assigns it to the employee.
Otherwise the boss waits till marketing suggest a new project.

The Marketer Thread:

Call the wimp boss with a new project.
The wimp boss tells his boss that a new project just been requested by marketing.

The only thing still missing is the code that runs the story:

<span class="kwrd">public</span> <span class="kwrd">void</span> Run()<br />{<br />    <span class="rem">// Create an organization to get work done</span><br />    Manager wimp = <span class="kwrd">new</span> WimpManager();<br />    Manager boss = <span class="kwrd">new</span> Manager();<br />    Employee dilbert = <span class="kwrd">new</span> Employee();<br />    Employee catbert = <span class="kwrd">new</span> Marketer();<br /><br />    wimp.Boss = boss;<br />    dilbert.Boss = wimp;<br />    catbert.Boss = wimp;<br /><br />    <span class="rem">// Build the threads in which projects will be done</span><br />    Thread dilbertThread = <span class="kwrd">new</span> Thread(dilbert.Work);<br />    Thread catbertThread = <span class="kwrd">new</span> Thread(catbert.Work);<br /><br />    <span class="rem">// Run the project threads</span><br />    dilbertThread.Start();<br />    catbertThread.Start();<br />}

public void Run() { // Create an organization to get work done Manager wimp = new WimpManager(); Manager boss = new Manager(); Employee dilbert = new Employee(); Employee catbert = new Marketer(); wimp.Boss = boss; dilbert.Boss = wimp; catbert.Boss = wimp; // Build the threads in which projects will be done Thread dilbertThread = new Thread(dilbert.Work); Thread catbertThread = new Thread(catbert.Work); // Run the project threads dilbertThread.Start(); catbertThread.Start(); }

In case you haven’t noticed yet there is a deadlock lurking in the code.

Running Typemock Racer

In order to find the deadlock we can write simple NUnit test using Racer:

[Test]<br /><span class="kwrd">public</span> <span class="kwrd">void</span> RunDilbertDeadlock_RunMainWithSubThreads_DeadlockDiscovered()<br />{<br />    ThreadTest.AddThreadAction(Run).Start();<br />}

1	[Test]<br /><span class="kwrd">public</span> <span class="kwrd">void</span> RunDilbertDeadlock_RunMainWithSubThreads_DeadlockDiscovered()<br />{<br /> ThreadTest.AddThreadAction(Run).Start();<br />}

And get the following output:

Reading the output we can see that the following actions took place:

the employee thread was started by out main thread.
- Locked resource #1(wimpManagerSync) at WimpManager.AssignProject
- Locked resource #2 (ManagerSync) at Manager.AssignProject
- Released resource #2 (ManagerSync) at Manager.AssignProject
- Wait for signal at Manager.AssignProject
The Marketer Started by the main thread
- Tried to lock resource #1 which we can see that is being held by the employee.

The deadlock happened because the marketer cannot reach the Manager and to notify him of a new project while the manager is waiting for a new project from the marketer. This deadlock was created because of the wimp manager locks before each action – the RecieveProject action cannot start before the AssignProject action is finished.

How can we solve this problem?

The solution for this problem is quite simple, all we have to do is to remove the Wimp manager from our code. By removing this object we remove the deadlock that happens if both marketer and employee need to access the boss.

Try it and see what happens…

Tags:tutorials

The woes of multithreaded design – How to find deadlock using Typemock Racer

The Players

The Story

Running Typemock Racer

How can we solve this problem?

Products

Help

Company

Community

Contact

Typemock Store (US toll FREE 866–895–4680). Copyright © 2006 Typemock Inc. All rights reserved. Terms of Use.

Choose the product type: