TBB uses an approximation of Cilk-style
scheduling (work LIFO; steal FIFO).It has good locality and load
balancing properties while making certain space guarantees. It enables
clean nesting of software components, analogous to the way serial code
composes by nested subroutine calls.
FIFO has terrible locality and often has no space guarantees, which
often leads to complex throttling mechanisms. Nonetheless FIFO
scheduling definitely has its uses, notably for soft real-time.
Finding a rationale marriage ofCilk-style and FIFO scheduling remains
an open problem. If done rigorously it's a worthyfor aPh.D. thesis.
The "two roots" idea suggests that perhaps said marriage could be
accomplished by some kind of epoch mechanism, where each task belongs
to an epoch and older epochs are given precedence. There's a long way
between a notion and a practical system.
There are two kinds of user algorithms.
First is a 'Cilk-style' computational algorithms ('HPC'). They doesn't require nor won't benefit from 'fair' processing. Even worser, they will degrade and will require more memory.
Second is a kind of general-purpose algorithms (games, client/server software). Sometimes they just require fair (at least to some degree) processing. Otherwise they can basically deadlock.
So, I think, the first decision one have to made is how to cope with those kinds of user algorithms. For example TBB can postulate that it doesn't support second kind at all. Or TBB can have 2 modes of operation, i.e. user will have to setup proper type of scheduler at the beginning of program. Or TBB can support 2 kind simultaneously, for example on per task basis, i.e. those tasks are HPC, and those are general-purpose. Or just provide some single compromise scheduler.
I'm curious what .NET TPL team will decide on this problem:
I hope they will publish some results. Btw, I see some interesting words in comments, like PRIO, SIZE and AGE.