Work Stealing Deques

Work Stealing Deques

Work stealing is a scheduling strategy where each worker owns a double ended queue, or deque, of tasks. A worker that runs out of its own work steals a task from another worker rather than sitting idle. It is the engine behind many fork join frameworks.

Each worker pushes and pops new tasks from one end of its own deque, the local end. This end behaves like a stack and stays cache friendly because the worker touches only recently created tasks. When a worker is empty, it becomes a thief and takes a task from the opposite end of a victim deque.

• Local end The owner pushes and pops here like a stack, with no contention.
• Steal end Thieves take from the far end, away from the owner.
• Separation Owner and thief usually touch different ends, reducing conflicts.

Stealing from the opposite end is deliberate. The far end holds the oldest tasks, which tend to be larger units of work near the top of a recursive split. Stealing big chunks means a thief gains plenty of work from a single, infrequent steal.

This design keeps contention low because the owner and thieves operate on opposite ends most of the time. A lock or atomic operation is needed only when the deque is nearly empty and an owner and thief might reach for the same task.

Key idea

Work stealing gives each worker a deque it uses like a stack, while idle workers steal large old tasks from the far end, balancing load with little contention.