Algorithm to resolve general dependencies

Question

Imagine if you have a bunch of methods (Java in this case) that depends on each other.

• methodY depends on methodA, methodB, methodC
• methodX depends on methodA, methodB
• methodB depends on methodA, methodF
• methodT doesnt depends on anything
• methodU depends on methodW
• and so on

If methodA depends on methodB that means methodB has to be executed first before methodA is executed.

Assume you do not need to worry about cyclic dependencies.

Each method is run by a Thread, there is a fixed size thread pool.

If there are no cyclic dependencies, is it possible for all of them to run eventually ?
How do I queue the threads so all of them would run eventually ?

For example this wouldn't work
methodA depends on methodB, methodC depends on methodB, thread pool size is 2. If I queue methodA and methodC, they would hang around indefinitely because both are waiting for methodB but pool is already full.

Answer 1

when you think about it, separate threads and methods. methods are what the threads are executing.

you should have (in this case) 2 threads that can execute any method. they will pick a method that all of it's dependencies have been executed, and run it.

repeat this until methods queue is empty.

btw, if you are allowed to start executing a method when all of it's dependencies are done (i mean, if you are allowed to leave it in the queue) then the logic is the most trivial.