title: Implementing a Generic Task Scheduler with Nested-Parallelism and Task Dependency support in C++
body: <p>I want to create a generic task scheduler that supports nested parallelism with dependencies, that is, to be able to create and enqueue (child) tasks from inside other (parent) tasks and at the same time the parent task execution be dependent on the child task result. Unfortunately I am having trouble figuring out how to implement this. I am stuck on the following simple case:
  Lets assume that we have 2 worker threads and we create/enqueue 2 parent tasks. Each task will start executing on a separate thread. Now each task spawns 2 child tasks and waits for them to finish before returning. But because there are no other available threads (because the two worker threads are blocked waiting the child tasks to finish)  the child tasks will never be executed. As a result the parent tasks will never return. </p>
  
  <ul>
  <li>One solution I can think of is to just execute all the children tasks serially on the same thread. But this is not efficient because one of the parent tasks and its children might finish very fast and then one thread will be sitting there doing nothing.</li>
  <li>Another solution is to spawn a new thread for every child task. But this might lead to a huge amount of threads and it is not a good idea.</li>
  <li>Another solution would be to enqueue the new children tasks if and only if there threads available. If there aren't then execute the child tasks serially on the same thread with the parent task. This one looks somehow efficient but I am not quit sure if it is correct or how can be implemented.</li>
  </ul>
  
  <p>Is there a standard way/pattern used for the above problem? I also tried to read Intel's TBB documentation on the task scheduler but it is still unclear how TBB is implementing this.</p>