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.
    – Massimo
    Aug 25 '16 at 22:21

Your Answer

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

Browse other questions tagged or ask your own question.