Solving the Dining Philosopher’s Problem with .NET Framework 4.0 Task Parallel Library

Introduction

Task Parallel Library (TPL) is a set of new .NET Framework 4.0 Parallel Computing classes for easing the pain of building applications that leverage today’s multi-core machines. Prior articles introduced the Task class, Understanding Tasks in .NET Framework 4.0 Task Parallel Library and Introducing the .NET Framework 4.0 Task Parallel Library BlockingCollection.
There is more, however, to TPL than Tasks and BlockingCollections. For example, there are patterns for composing Tasks implemented using other data structures and there data structures for synchronizing access to shared state. Using the Dining Philosophers example from the Framework samples, I’m going to explain how TPL data structures can be employed to organize Tasks and synchronize shared state.

Dining Philosophers?

Synchronizing access to shared state is one of the things that makes Parallel Computing so hard. Race conditions occur when separate threads don’t synchronize access to a shared place in memory. The shared memory may be a single variable or a collection of data structures. For example, a variable containing the number of items in an array should be in sync with the physical number of array items.

To ensure proper synchronization parallel solutions “lock” a critical section of code. Locking, however introduces a new problem, the deadlock. Deadlocks occur when, for example, two threads have locked a piece of memory the other thread needs to continue execution. To avoid a deadlock, a program will often implement an algorithm that exercises special care to avoid or detect a deadlock.

The Dining Philosophers problem shows how a seemingly simple set of conditions can lead to deadlocks. Main elements of the problem are as follows:

  1. A group of Philosophers are sitting at a table alternating between eating and thinking.
  2. To the left and right of each Philosopher are eating utensils.
  3. In order to eat a Philosopher must pick up a pair of utensils.

As you may have guessed a deadlock occurs if all the Philosophers grab the first available utensils without regard to what their neighbor is doing.

Sample Code Overview

Dining Philosophers TPL sample attempts to solve the problem using a variety of techniques and data structures built into TPL. The sample solves the problem using the following set of approaches.

  • SyncWithWaitAll utilizes Tasks alongside a WaitHandle. Each Philosopher runs on a separate Thread. Work is simulated using Thread.Sleep.
  • SyncWithOrderedForks solves the problem using the new in .NET Framework 4.0 SemphoreSlim data structure. Each Philosopher runs on a separate Thread. Work is simulated using Thread.Sleep.
  • Async composes a solution using Tasks, Iterators, and Continuations. This is a complicated example that showcases different ways to compose and link Tasks and leverage TaskCompletionSource classes. I’ll focus most of the article on this example.

Each of the samples follows a similar pattern:

  • A For loop creates 5 Philosophers as a Thread or initial Task.
  • Each Philosopher is associated with a ball.
  • Balls alternate between yellow (thinking), red (waiting), and green (eating).
  • In a WPF application user interface code must be executed on the User Interface thread. So changing colors is followed by code that blocks execution for a random amount of time.

With an understanding of the problem and an idea of what the sample is doing, attention now turns to code.

SyncWithWaitAll and SyncWithOrderedForks

These examples are very similar so I’m going to explain them together and point out where they differ.

Both samples start new Tasks using code like the example below.

  var forks = (from i in Enumerable.Range(0, _philosophers.Length) select new SemaphoreSlim(1, 1)).ToArray();
  for (int i = 0; i < _philosophers.Length; i++)
  {
      int index = i;
      Task.Factory.StartNew(() => RunPhilosopherSyncWithOrderedForks(forks, index), TaskCreationOptions.LongRunning);
  }

The TaskCreationOptions.LongRunning indicates that a Task will be running for a long time and “advises” TPL to create it as a separate thread. Utensils (forks) are implemented as Semaphores. SemaphoreSlim is a lighter weight version of the Semaphore class.

It’s important to note that many of the monitors a developer may have used in other .NET version may have been reimplimented in another similarly named class with equivalent functionality, but more efficient underlying plumbing.

Code capturing actions by each Philosopher appears below.

  // Assign forks
  int fork1Id, fork2Id;
  GetForkIds(index, forks.Length, out fork1Id, out fork2Id, false);
  Semaphore fork1 = forks[fork1Id], fork2 = forks[fork2Id];

  // Think and Eat, repeatedly
  var rand = new Random(index);
  while (true)
  {
      // Think (Yellow)
      _ui.StartNew(() => _philosophers[index].Fill = _think).Wait();
      Thread.Sleep(rand.Next(10) * TIMESCALE);

      // Wait for forks (Red)
      _ui.StartNew(() => _philosophers[index].Fill = _wait).Wait();
      WaitHandle.WaitAll(new[] { fork1, fork2 });

      // Eat (Green)
      _ui.StartNew(() => _philosophers[index].Fill = _eat).Wait();
      Thread.Sleep(rand.Next(10) * TIMESCALE);

      // Done with forks
      fork1.Release();
      fork2.Release();
  }

_ui.StartNew followed by “Wait” executes the color change on the user interface thread. WaitHandle.WaitAll blocks until both utensils are released. The other sample performs 2 successive waits on the SemaphoreSlim class.

That covers the more straightforward examples, the last example utilized some newer data structures and patterns. So I’m going to break the last example down into solution layers.

More by Author

Must Read