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.



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

TaskFactory Iterate Extensions

Async sample Philosopher creation appears below:

  var forks = (from i in Enumerable.Range(0, _philosophers.Length) select new AsyncSemaphore(1, 1)).ToArray();
  for (int i = 0; i < _philosophers.Length; i++)
  {
      Task.Factory.Iterate(RunPhilosopherAsync(forks, i));
  }

TaskFactory.Iterate is an extension function implemented in the TPL Samples. Main parts of the Iterate function appear below.

  public static Task Iterate(
      this TaskFactory factory,
      IEnumerable<object> source, object state, 
      CancellationToken cancellationToken, TaskCreationOptions creationOptions, TaskScheduler scheduler)
  {
  // Get an enumerator from the enumerable
  var enumerator = source.GetEnumerator();
  
  // Create the task to be returned to the caller.  And ensure
  // that when everything is done, the enumerator is cleaned up.
  var trs = new TaskCompletionSource<object>(state, creationOptions);
  trs.Task.ContinueWith(_ => enumerator.Dispose(), CancellationToken.None, TaskContinuationOptions.ExecuteSynchronously, TaskScheduler.Default);
  
  // This will be called every time more work can be done.
  Action<Task> recursiveBody = null;
  recursiveBody = antecedent =>
  {
      try
      {
          if (enumerator.MoveNext())
          {
              var nextItem = enumerator.Current;
                          
              // If we got a Task, continue from it to continue iterating
              if (nextItem is Task)
              {
                  var nextTask = (Task)nextItem;
                  nextTask.ContinueWith(recursiveBody).IgnoreExceptions();
              }
          }
  
          // Otherwise, we're done!
          else trs.TrySetResult(null);
      }
  ….
  };
  
  // Get things started by launching the first task
  factory.StartNew(() => recursiveBody(null), CancellationToken.None, TaskCreationOptions.None, scheduler).IgnoreExceptions();
              
  // Return the representative task to the user
  return trs.Task;

For now, I'll defer the discussion of the enumerator.MoveNext code and, instead, focus on what the other components are doing. TaskCompletionSource wraps a data structure around a Task allowing a developer to manipulate the return results of a Task. Creating a TaskCompletionSource also creates an internal Task class. In the example it was useful to wrap a Task that recursively consumes the iterator and spawning other Tasks; inside an outer Task being returned to code calling Iterate.

Trs.Task.ContinueWith attaches a Task that invokes the Dispose function to the Task being returned to the Iterate caller. Code passed to the ContinueWith method is called when the Task associated with ContinueWith function completes execution.

RecursiveBody is a block of code that is utilized in two places:

  • It's invoked when the nextTask completes execution.  The ContinueWith on the nextTask sets this up.
  • The StartNew at the end of the function immediately invokes the code.

In the example above TrySetResult completes the Task from within RecursiveBody and unravels the recursion. Moving to the main portion of the Async sample I'll now explain the Enumerator.

Yield

The main body of the Async sample appears below.

  private IEnumerable<Task> RunPhilosopherAsync(AsyncSemaphore[] forks, int index)
  {
  // Assign forks
  int fork1Id, fork2Id;
  GetForkIds(index, forks.Length, out fork1Id, out fork2Id, true);
  AsyncSemaphore fork1 = forks[fork1Id], fork2 = forks[fork2Id];
  
  // Think and Eat, repeatedly
  var rand = new Random(index);
  while (true)
  {
      // Think (Yellow)
      yield return _ui.StartNew(() => _philosophers[index].Fill = _think);
      yield return Task.Factory.StartNewDelayed(rand.Next(10) * TIMESCALE, () => { });
  
      // Wait for forks (Red)
      yield return fork1.Wait();
      yield return _ui.StartNew(() => _philosophers[index].Fill = _wait);
      yield return fork2.Wait();
  
      // Eat (Green)
      yield return _ui.StartNew(() => _philosophers[index].Fill = _eat);
      yield return Task.Factory.StartNewDelayed(rand.Next(10) * TIMESCALE, () => { });
  
      // Done with forks
      fork1.Release();
      fork2.Release();
  }

As you can see the function returns an IEnumerable class. Coupling the return value with the yield statement sort of instructs the compiler to do the following:

  • Treat the function like a collection
  • Make an item available in the collection each time the yield is invoked.
  • Block until the item returned by the yield statement is consumed by the code doing the iteration.

AsyncSemaphore works with the Iterator extension function. The Wait function appears below:

  ThrowIfDisposed();
  lock (_waitingTasks)
  {
      // If there's room, decrement the count and return a completed task
      if (_currentCount > 0)
      {
          _currentCount--;
          return CompletedTask.Default;
      }
      else
      {
          // Otherwise, cache a new task and return it
          var tcs = new TaskCompletionSource<object>();
          _waitingTasks.Enqueue(tcs);
          return tcs.Task;
      }
  }

The name of the function is a bit misleading. Wait does not block until a utensil is available. Instead it returns a Task that remains suspended until SetResult is called from the Release function in the AsnycSemaphone; setting the Task's result. The AsyncSemaphore Release method appears below:

  lock (_waitingTasks)
  {
      // Validate that there's room
      if (_currentCount == _maxCount) throw new SemaphoreFullException();
  
      // If there are any tasks waiting, allow one of them access
      if (_waitingTasks.Count > 0)
      {
          var tcs = _waitingTasks.Dequeue();
          tcs.SetResult(null);
      }
          // Otherwise, increment the available count
      else _currentCount++;
  }

Couple the activity of the AsyncSemaphore with the Iterate code in the previous section and you can see how the whole sample is just a collection of Tasks strung together with ContinueWith methods.

Conclusion

Prior articles covered Tasks and BlockingCollections. Using the Dining Philosopers sample shipping with the .NET Framework samples,this article demonstrated Parallel Computing constructs in the Task Parallel Library that coordinate access to shared state.

Related Articles





About the Author

Jeffrey Juday

Jeff is a software developer specializing in enterprise application integration solutions utilizing BizTalk, SharePoint, WCF, WF, and SQL Server. Jeff has been developing software with Microsoft tools for more than 15 years in a variety of industries including: military, manufacturing, financial services, management consulting, and computer security. Jeff is a Microsoft BizTalk MVP. Jeff spends his spare time with his wife Sherrill and daughter Alexandra.

Comments

  • There are no comments yet. Be the first to comment!

Leave a Comment
  • Your email address will not be published. All fields are required.

Top White Papers and Webcasts

  • Learn How A Global Entertainment Company Saw a 448% ROI Every business today uses software to manage systems, deliver products, and empower employees to do their jobs. But software inevitably breaks, and when it does, businesses lose money -- in the form of dissatisfied customers, missed SLAs or lost productivity. PagerDuty, an operations performance platform, solves this problem by helping operations engineers and developers more effectively manage and resolve incidents across a company's global operations. …

  • Live Event Date: December 18, 2014 @ 2:00 p.m. ET / 11:00 a.m. PT The Internet of Things (IoT) incorporates physical devices into business processes using predictive analytics. While it relies heavily on existing Internet technologies, it differs by including physical devices, specialized protocols, physical analytics, and a unique partner network. To capture the real business value of IoT, the industry must move beyond customized projects to general patterns and platforms. Check out this upcoming webcast …

Most Popular Programming Stories

More for Developers

RSS Feeds