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?
2