Intel Threading Building Blocks

Fair Scheduling

Most general-purpose operating systems use a scheduler based on the idea of fair scheduling. You might be asking yourself, “With a name like fair scheduling, how could it be bad?”

It’s bad because fair, when speaking of thread scheduling, means balancing time. Thread schedulers typically distribute time slices in a round-robin fashion. The distribution is called fair because each logical thread gets an equal share of time. Thread schedulers are typically fair because it is the safest strategy to undertake without understanding the higher-level organization of a program.

Preempting a thread in the name of fairness is often done out of concern that some very large tasks will dominate others. But Threading Building Blocks takes care of the difference in task loads by monitoring processors and starting new tasks on idle processors. It also offers some assurance that tasks are “right-sized,” thanks to recursive splitting. This works very well in combination with the dynamic load balancing that Threading Building Blocks implements through task stealing.

In short, Threading Building Blocks does not need the inefficiencies of so-called fair scheduling. Preempting a task, in the name of fairness, would generally slow the completion of the overall task. It is better to let tasks complete.

In task-based programming, the task scheduler does have some of the higher-level information that is unavailable to the operating system, so the Threading Building Blocks task scheduler can sacrifice ...