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:

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

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

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:

  1. In out story the employee asks his boss for a project to work on.
  2. Not wanting to decide without approval of his manager the wimp manager asks his boss for new project for the employee.
  3. 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:

  1. Call the wimp boss with a new project.
  2. 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:

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]
public void RunDilbertDeadlock_RunMainWithSubThreads_DeadlockDiscovered()
{
ThreadTest.AddThreadAction(Run).Start();
}

And get the following output:

image

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.

image

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…

TOP