Waking a sleeping parent task

[Charles_Tucker]

I've been merrilly hacking away at the TBB work-stealing scheduler, trying to implement some different scheduling heuristics, and I've run into an oddity. I don't understand how a sleeping worker thread, with a parent execution waiting on its stack (blocking-style), ever gets awakened in the event that it can unwind its stack.

An example. Suppose I have a parent task A, two children B and C, and two threads. Thread 1 picks up A, which spawns and waits for B and C. Thread 1 picks up B and begins executing, thread 2 picks up C. C takes so long to complete that thread 1 finishes B, spins for a while, and ends up sleeping at the arena Gate, waiting for someone to call mark_pool_full(). Later, thread 2 completes task C, does the atomic decrement on A's ref_count, finds no work to do, and also sleeps...

...except that this doesn't appear to happen in the original scheduler, just mine. Is there some other mechanism that wakes thread 1 that I'm not seeing? The code immediately following the atomic decrement to the parent (somewhere in the middle of wait_for_all) seems to only apply in the case of continuation-passing code (where the continuation task needs to be spawned), but I don't see the case associated with blocking-style. What am I missing?

[Dmitry_Vyukov]

Quoting - Charles Tucker

I've been merrilly hacking away at the TBB work-stealing scheduler, trying to implement some different scheduling heuristics, and I've run into an oddity. I don't understand how a sleeping worker thread, with a parent execution waiting on its stack (blocking-style), ever gets awakened in the event that it can unwind its stack.

An example. Suppose I have a parent task A, two children B and C, and two threads. Thread 1 picks up A, which spawns and waits for B and C. Thread 1 picks up B and begins executing, thread 2 picks up C. C takes so long to complete that thread 1 finishes B, spins for a while, and ends up sleeping at the arena Gate, waiting for someone to call mark_pool_full(). Later, thread 2 completes task C, does the atomic decrement on A's ref_count, finds no work to do, and also sleeps...

The last time I was looking at the sources threads do NOT block at all provided that there are some tasks on the stack.
Only worker threads with no tasks on the stack block. There must be something like "if (depth == 0 && ...) block();

[Charles_Tucker]

Quoting - Dmitriy Vyukov

The last time I was looking at the sources threads do NOT block at all provided that there are some tasks on the stack.
Only worker threads with no tasks on the stack block. There must be something like "if (depth == 0 && ...) block();

Good point - one of the things that I changed was that my scheduler decisions don't pay attention to depth, so I haven't been considering it / checking for it. I have also not looked at the latest development builds thoroughly yet (i.e. the ones with TBB_TASK_DEQUE-related code), but at first glace they also have to deal with a similar problem. I'll investigate deeper.