Skip to content

Work stealing

Category: Scheduling · Status: stub

One line: Each worker thread keeps its own queue of tasks, and an idle worker takes tasks from a busy worker's queue, balancing the load without one central queue.

Also called: work-stealing scheduler.

How it connects

flowchart LR
  n_async_runtime["Async runtime (executor and reactor)"]
  n_fork_join["Fork-join"]
  n_parallel_iterators["Parallel iterators and streams"]
  n_scheduling_policy["Scheduling policy"]
  n_work_stealing["Work stealing"]
  n_async_runtime -->|uses| n_work_stealing
  n_fork_join -->|uses| n_work_stealing
  n_parallel_iterators -->|uses| n_work_stealing
  n_work_stealing -->|is a| n_scheduling_policy
  classDef center stroke-width:3px
  class n_work_stealing center
  classDef outside stroke-dasharray: 4 3
  class n_async_runtime,n_fork_join,n_parallel_iterators,n_scheduling_policy outside

In each language
Rust Tokio's multi-thread scheduler ↗ and Rayon's join ↗ both use work stealing
Java ForkJoinPool ↗, and Executors.newWorkStealingPool ↗
C# The default TaskScheduler ↗ gives thread-pool threads local work queues, and an idle thread steals from another's

Where to read more