ExtendedSource checked

Work Stealing

Balances parallel work by letting idle workers take tasks from busy workers.

Explore relationships Open constellationBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category: Scheduling
Difficulty: Intermediate
Family: Parallel Scheduling
Tier: Extended
Status: Verified
Review: Source Checked
Sources: 1
Formulas: 0
Relationships: 1
Code example: Ready
Visualization: Ready

Overview

Work Stealing gives each worker a local task deque and lets idle workers steal tasks from others when they run out.

Core Concepts

task orderingwork distributiondependency timingparallel schedulingready queuetask priorityresource allocation

Quick facts

Complexity

Runtime and memory behavior at a glance.

Best

O(1)

Average

O(t)

Worst

O(t)

Space

O(w + t)

When to Use

Use Work Stealing when you need to keep local queues for workers.
Use it for parallel runtimes with inputs like worker queues.
Use it when tasks, priorities, deadlines, or resource limits drive execution order.
Use it when the Parallel Scheduling tradeoff is acceptable for the problem size.

When Not to Use

Avoid it when fairness, latency, and throughput requirements conflict but are not prioritized.
Avoid it when the required output is not balanced task execution.

What It Does

Keeps local queues for workers
Moves tasks from busy workers to idle workers

Use Cases

Parallel runtimes
Task schedulers
Fork-join workloads

Inputs

Worker queues
Tasks or jobs

Outputs

Balanced task execution

Pseudocode

1.Give each worker its own deque
2.Workers push and pop local tasks
3.When a worker becomes idle, choose another worker
4.Steal a task from that worker's deque
5.Continue until all queues are empty

Canonical Example

Input: tasks = A(4ms), B(2ms), C(1ms)
Output: execution order and completion times
Explanation: Work Stealing: The scheduler chooses which task should run next according to its rule.

Implementation Notes

Keep the input contract explicit: Worker queues; Tasks or jobs.
Use this step as the implementation spine: Give each worker its own deque.
Then preserve the next state change: Workers push and pop local tasks.
Record arrival time, remaining work, and completion time so schedule metrics can be checked.

Common Pitfalls

Work Stealing reduces central contention and works well for irregular parallel work.
Ignoring starvation, preemption cost, or inaccurate duration estimates.
Returning balanced task execution without handling empty, invalid, or boundary inputs.

Interactive Mechanism Walkthrough

Graph Frontier & Edge Relaxation

Show idle workers stealing tasks from busy queues.

Step 1 of 5: Give each worker its own deque

worker-deques

Notes

Work Stealing operates in O(t) time and O(w + t) space within the Parallel Scheduling family. Often compared with Priority Scheduling and Critical Path Method.