2

I am trying to figure out an implementation for a solution to a problem I outlined in another Programmers.SE question. I need to find a solution for this problem in C# most likely using the collection in the System.Collections.Concurrent namespace.

My problem is a classic problem related to the Dining Philosophers Problem. I have a finite set of resources that need to be used by multiple threads. My current implementation of a solution involves a sort of signalling system to let other threads know when they may start using a resource. I have actually created a nice analogy.


Resources are seen as amusement park rides that can only fit a single rider at a time. Threads/tasks/units of work are seen as groups of people that wish to ride multiple different rides at the same time.

When a group of people enters the park they stop at the ticketing stand, each purchase a ticket to their respective ride, and each get in line for their respective lines, all simultaneously. Each of these groups of people will only start riding a ride once they are all at the front of the line, otherwise they will wait first in line at their respective rides until all of them are first in line.


This solution would work but the concurrent collection in C# make it hard to implement properly. (Going along with the analogy) As a result of each person in the group having to purchase tickets and get in line all simultaneously at some point I have to make multiple modifications to some concurrent collection atomically. In C# there is no mechanism to do this in System.Collections.Concurrent.

In C# I have the following data structures to represent the analogy above

ConcurrentDictionary<IResource, ConcurrentQueue<Guid>> ResourceWaitQueues { get; set; }
ConcurrentDictionary<ITask, ConcurrentDictionary<IResource, Guid>> TasksToDo { get; set; } 

[Step 1.a] When a new ITask is generated it is interrogated for the IResources that it requires to be ran. For each IResource it needs a new Guid is generated. A KeyValuePair is created for this ITask and inserted into TasksToDo.

[Step 1.b] The Guid created for each IResource the ITask needed is then inserted into the corresponding ConcurrentQueue<Guid> in the ResourcesWaitQueues object.

[DispatchThread] The dispatch thread (TPL Task) is started. This thread continually loops over the TasksToDo structure and checks to see if the current ITask's List<Guid> needed to run are at the front of the ConcurrentQueues in the ResourceWaitQueues. If so it is started, otherwise it is skipped.

[TaskRunningThread] When a ITask is found to be ready to run it is ran. Once complete the List<Guid> it hold are dequeued from their respective ConcurrentQueue in ResourceWaitQueues.


As you should notice the issue with this solution is that I must make multiple adds or removes to ConcurrentQueue and ConcurrentDictionary when a new ITask is generated or when an ITask has completed. If the DispatchThread or TaskRunningThread manages to interleave with each other then it is possible that Guid are never added or removed from their respective collections.

I'd like to think I am experienced enough to write my own concurrent collection to allow multiple atomic modifications, though I would much rather use out of the box, well developed classes.


So my question is, is there a way to solve this problem with the out of the box System.Collections.Concurrent collections?

1

You probably need some kind of locking when simultaneously accessing multiple queues. If you really want to stick to System.Collections.Concurrent, you can store a single token in any IProducerConsumerCollection. But it would be kind of silly.

I have combined concurrent collections and used ReaderWriterLockSlim. When performing a single operation on a single queue such as GetorAdd(), I would use EnterReadLock() relying on the collection's own thread safety and allowing other simple operations simultaneously. When performing a 'transaction' of operations on one or more collection's, I would use EnterWriteLock() signalling exclusive use of all concurrent collections.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.