Deadlock due to running out of runnable threads

[rocallahan]

Suppose I start K threads and spawn N > K tasks. Suppose each of those tasks calls Pool::scoped() to run scheduler callbacks that each spawn additional tasks in their scopes. It seems to me this can easily deadlock, since we could have all K threads stopped waiting in a Scope::join() with no threads able to run the scoped tasks that are being waited for. Right?

If so, then it's dangerous to call Scope::join() or Pool::scoped() from a Pool thread, and Scope::recurse() is always dangerous.

Maybe this could be fixed by making the waiting thread in a Scope::join() available to run pending tasks?

[reem]

I think that is an excellent idea, using the waiting thread as an additional worker should solve this problem.

However, implementing this is rather tricky... currently there is no way for a pool worker thread to break out of its work loop except by receiving a quit message.

My first instinct is to simply add another running strategy where the waiting thread can simply poll the WaitGroup attached to the Scope by checking the number of remaining jobs it is waiting on after running each job. The only edge case here is that the loop will not progress if there are no jobs waiting in the queue, but in that case we can simply proceed with waiting on the WaitGroup since another thread must be handling our job (since it must not be in the queue as the queue is empty).

The implementation of this final check must ensure that it cannot miss the WaitGroup notification from another thread, otherwise we can be stuck waiting for a notification on a completed WaitGroup that already came.

I can probably implement this sometime today or tomorrow, but feel free to take a stab at it yourself if you are interested.

[reem]

Upon further reflection there is one more case that is cause for concern: once the queue is empty new jobs can still be submitted by currently running jobs. We need to effectively select between the wait group completing and a new job being submitted to the pool - this will require some more refactoring.