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:
|
1 |
<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 />} |
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:
|
1 |
<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 />} |
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:
|
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…
