# Trade off between concurrency and stagnation in a Dining Philosophers problem analogue?

I am currently facing a problem in the application I am developing that I think is the same as, or an analogue of, the Dining Philosophers Problem.

In my application I have a list of N resources. I also have a queue of tasks that need a number from 1 to N of these resources to run (which are continually generated at unknown intervals). What I would like to do is run as many of these tasks as I can in parallel while not letting a task sit stagnant for too long.

``````Available resources: A, B, C
---------------------------------------------------------------------------------------
[T=4] Task 4 requires resource(s): A, C    Takes 4 time to complete <-- Last in queue
[T=3] Task 3 requires resource(s): A       Takes 1 time to complete
[T=2] Task 2 requires resource(s): C       Takes 1 time to complete
[T=1] Task 1 requires resource(s): A, B, C Takes 1 time to complete
[T=0] Task 0 requires resource(s): B       Takes 6 time to complete <-- First in queue
``````

Say that I start processing incoming tasks. At `T=0` I see `Task 0` and start it because the needed resource is open. At `T=0` I see `Task 1` but cannot start it because all of its resources are not open to run it. At `T=2` I see `Task 2` and start it because the needed resource is open. At `T=3` I see `Task 3` and start it because the needed resource is open. At `T=4` I see `Task 4` and start it because resource `A` and `C` are free because `Task 2` and `Task 3` completed quickly.

In this case `Task 1` has become stagnant because of the specific timing and resource needs of the tasks that have entered the queue. While I have ran tasks as quickly as possible I have now allowed tasks to become stagnant.

The reverse of this strategy where I wait for all resources for each task to become available in order of tasks also fails because I could be running tasks in parallel while waiting for resources to become available.

Is there a solution/strategy to this problem where I get a good trade off between concurrency and task stagnation?

Is my belief in this trade off even real or am I just outlining the worst case scenarios for a known optimal/most used solution?

• Have a look at the LMAX Disruptor. See also martinfowler.com/articles/lmax.html Aug 25 '16 at 15:48
• It seems to me like asking "which is the maximum y of this F(x) ?" but with a "black box" function and, obviously, no infinite space and time to see all the function results. So I can suggest to search for local solutions : choose a period of time to collect the resources, and then dispatch and use them. You can also adjust the period, longer or shorter, according to your metrics and goals. Aug 25 '16 at 22:21