In a work-stealing scheduler, each worker keeps its tasks in a double-ended queue: the owner pushes and pops at one end (LIFO for itself) while thieves take from the other end (FIFO with respect to the owner's pushes). Why is it arranged that way rather than both ends behaving the same?

middleshould knowfreq 33%

answer

own end = stack: hot data, bounded depth
far end = oldest = biggest subtree
one steal should buy a lot of work
opposite ends ⇒ no shared cache line
only the last element races → one CAS

basics

~20 s

LIFO locally keeps execution depth-first: the newest task's data is still cache-hot and memory stays bounded. Thieves take the oldest task because, near the root of the computation, it is the largest subtree — so one steal buys a lot of work. Using opposite ends also keeps owner and thief off the same memory, so the local path needs almost no synchronization.

solid answer

~60 s

Three reasons, all of them structural.

Locality and space. Taking your newest task first makes each worker run its own subtree depth-first, like the sequential program would. The data that task touches is what you just touched, so it is cache-warm, and the number of live unfinished tasks stays bounded by the recursion depth instead of exploding breadth-first.

Steal value. Tasks pushed earliest sit closest to the root of the task tree, so they represent the largest remaining subtrees. A thief that takes the oldest task acquires a big chunk of work and will not need to steal again soon. Since a steal is the expensive operation, you want each one to be worth as much as possible.

Contention. Owner and thieves operate on opposite ends, so their cache lines and their compare-and-swaps do not collide except when the deque holds a single element. That is what allows lock-free deque protocols (Chase-Lev is the canonical one) to make the owner's push and pop a plain store or load plus a fence, with an atomic only in the last-element race.

Three reasons, all of them structural. **Locality and space.** Taking your newest task first makes each worker run its own subtree depth-first, like the sequential program would. The data that task touches is what you just touched, so it is cache-warm, and the number of live unfinished tasks stays bounded by the recursion depth instead of exploding breadth-first. **Steal value.** Tasks pushed earliest sit closest to the root of the task tree, so they represent the *largest* remaining subtrees. A thief that takes the oldest task acquires a big chunk of work and will not need to steal again soon. Since a steal is the expensive operation, you want each one to be worth as much as possible. **Contention.** Owner and thieves operate on opposite ends, so their cache lines and their compare-and-swaps do not collide except when the deque holds a single element. That is what allows lock-free deque protocols (Chase-Lev is the canonical one) to make the owner's push and pop a plain store or load plus a fence, with an atomic only in the last-element race.

code

text · 9 lines

text

thieves steal here            owner pushes/pops here
              |                                |
              v                                v
  [ oldest task ][ ... ][ ... ][ ... ][ newest task ]
     biggest subtree                    hottest cache

  owner:  push(t): deque[bottom++] = t          (plain store + fence)
          pop():   take deque[--bottom]         (CAS only if 1 left)
  thief:  steal(): CAS top -> take deque[top]

go deeper

for a junior

Recall the two facts: run your own newest task (its data is still in cache) and let thieves take your oldest one (it is the biggest job).

for a middle

Give all three reasons — locality, bounded outstanding-task memory, and steal value — and note that opposite ends keep owner and thief from contending.

for a senior

Add the implementation consequence: the owner's fast path avoids atomics because the only real race is the last element, which one CAS settles; and name the fairness cost you inherit.

for a principal

Discuss where the assumptions fail — flat equal-sized workloads, latency-sensitive external submissions — and why production runtimes mix a FIFO submission path with LIFO internal forks.

The structure

A work-stealing worker's task container is a deque — a queue you can access from both ends. The owner uses one end as a stack: it pushes a newly spawned task there, and when it needs work it pops from that same end, so it gets the most recently created task (LIFO). Thieves go to the far end and take the oldest task the owner pushed (FIFO from the owner's point of view). The asymmetry is not an accident; each half of it buys something specific.

Why the owner runs LIFO

Consider a recursive parallel computation: a task splits into two subtasks, each of which splits again. If a worker always takes its newest task, it descends into the tree exactly like the equivalent single-threaded recursive program would.

Cache locality. The subtask you just created operates on the data the parent was working on — the array slice, the tree node, the arguments still in registers and L1. Running it now, rather than after ten thousand unrelated tasks, means most memory accesses hit warm cache. Breadth-first order guarantees the opposite: by the time you get to a task, its data has long since been evicted.
Bounded memory. Depth-first execution means the number of unfinished, outstanding tasks per worker is bounded roughly by the depth of the recursion, not the width of the tree. This is the practical form of the classic Cilk space bound: total space on P processors stays within a constant factor of P times the space the sequential program uses. A FIFO local order would materialize an entire level of the tree before executing any of it, and a computation that spawns millions of leaves would exhaust memory before it exhausted work.
Fewer scheduling decisions. In the common case the owner never touches a cross-thread structure at all; it just recurses.

Why thieves take the oldest task

Steals are the only expensive operation in the system, so the scheduler tries to make each one count.

The oldest task is the biggest. In a divide-and-conquer tree, tasks pushed early are near the root, so their subtrees are large; tasks pushed late are near the leaves and may be a handful of instructions. Stealing near the root gives the thief work it can chew on for a long time, so the steal rate stays low. Stealing a leaf would mean stealing again almost immediately — and the theoretical bounds on steal counts depend on this property.
It is the coldest task. The task the owner has not touched for the longest time is the one whose data is least likely to still be in the owner's cache, so migrating it destroys the least locality. Stealing the newest task would take precisely the one item the owner was about to run with hot data.

Why opposite ends

The two ends also give near-disjoint memory access patterns. The owner mutates a bottom index; thieves mutate a top index with atomic compare-and-swap. As long as the deque has two or more elements, the owner's push and pop touch a variable no thief is writing, which means:

the owner's fast path is a plain load/store plus a memory fence, not a locked read-modify-write;
the two ends usually sit on different cache lines, so the owner is not paying coherence traffic for other threads' steal attempts;
the only place a real race exists is the last remaining element, when owner and thief may both target it — that single case is resolved with one CAS, and if the owner loses, it simply reports empty and goes stealing itself.

This is what makes the design practical: correctness under concurrency is concentrated in a rare case rather than spread across every task boundary. (Chase-Lev deques additionally need release/acquire style ordering on the index updates; a naive port with no fences is a classic source of subtle bugs on weakly ordered hardware.)

The costs of the choice

The arrangement is tuned for throughput on tree-shaped work, and it has consequences you should be able to state:

Unfairness. A local LIFO order means a task at the far end of a worker's deque can wait a very long time if that worker keeps spawning new work and nobody steals. Completion order bears no relation to submission order.
It presumes tree-shaped work. If all tasks are independent and equal-sized (a flat batch), "oldest is biggest" is no longer true, and the LIFO/FIFO split buys locality and contention benefits but no steal-value benefit.
Some runtimes deliberately deviate. External submissions often go to a FIFO submission queue so client requests are not reordered arbitrarily, while internal forks keep the LIFO discipline. Some schedulers also let a worker check a stolen-from-me hint or run in FIFO mode for flat workloads.

## The structure A work-stealing worker's task container is a **deque** — a queue you can access from both ends. The owner uses one end as a stack: it *pushes* a newly spawned task there, and when it needs work it *pops* from that same end, so it gets the most recently created task (LIFO). Thieves go to the far end and take the *oldest* task the owner pushed (FIFO from the owner's point of view). The asymmetry is not an accident; each half of it buys something specific. ## Why the owner runs LIFO Consider a recursive parallel computation: a task splits into two subtasks, each of which splits again. If a worker always takes its newest task, it descends into the tree exactly like the equivalent single-threaded recursive program would. - **Cache locality.** The subtask you just created operates on the data the parent was working on — the array slice, the tree node, the arguments still in registers and L1. Running it now, rather than after ten thousand unrelated tasks, means most memory accesses hit warm cache. Breadth-first order guarantees the opposite: by the time you get to a task, its data has long since been evicted. - **Bounded memory.** Depth-first execution means the number of unfinished, outstanding tasks per worker is bounded roughly by the depth of the recursion, not the width of the tree. This is the practical form of the classic Cilk space bound: total space on P processors stays within a constant factor of P times the space the sequential program uses. A FIFO local order would materialize an entire level of the tree before executing any of it, and a computation that spawns millions of leaves would exhaust memory before it exhausted work. - **Fewer scheduling decisions.** In the common case the owner never touches a cross-thread structure at all; it just recurses. ## Why thieves take the oldest task Steals are the only expensive operation in the system, so the scheduler tries to make each one count. - **The oldest task is the biggest.** In a divide-and-conquer tree, tasks pushed early are near the root, so their subtrees are large; tasks pushed late are near the leaves and may be a handful of instructions. Stealing near the root gives the thief work it can chew on for a long time, so the steal rate stays low. Stealing a leaf would mean stealing again almost immediately — and the theoretical bounds on steal counts depend on this property. - **It is the coldest task.** The task the owner has not touched for the longest time is the one whose data is least likely to still be in the owner's cache, so migrating it destroys the least locality. Stealing the newest task would take precisely the one item the owner was about to run with hot data. ## Why opposite ends The two ends also give near-disjoint memory access patterns. The owner mutates a `bottom` index; thieves mutate a `top` index with atomic compare-and-swap. As long as the deque has two or more elements, the owner's push and pop touch a variable no thief is writing, which means: - the owner's fast path is a plain load/store plus a memory fence, not a locked read-modify-write; - the two ends usually sit on different cache lines, so the owner is not paying coherence traffic for other threads' steal attempts; - the *only* place a real race exists is the last remaining element, when owner and thief may both target it — that single case is resolved with one CAS, and if the owner loses, it simply reports empty and goes stealing itself. This is what makes the design practical: correctness under concurrency is concentrated in a rare case rather than spread across every task boundary. (Chase-Lev deques additionally need release/acquire style ordering on the index updates; a naive port with no fences is a classic source of subtle bugs on weakly ordered hardware.) ## The costs of the choice The arrangement is tuned for throughput on tree-shaped work, and it has consequences you should be able to state: - **Unfairness.** A local LIFO order means a task at the far end of a worker's deque can wait a very long time if that worker keeps spawning new work and nobody steals. Completion order bears no relation to submission order. - **It presumes tree-shaped work.** If all tasks are independent and equal-sized (a flat batch), "oldest is biggest" is no longer true, and the LIFO/FIFO split buys locality and contention benefits but no steal-value benefit. - **Some runtimes deliberately deviate.** External submissions often go to a FIFO submission queue so client requests are not reordered arbitrarily, while internal forks keep the LIFO discipline. Some schedulers also let a worker check a stolen-from-me hint or run in FIFO mode for flat workloads.

Where in this scheme can the owner and a thief actually conflict, and how is that resolved?
Only when the deque holds a single element and the owner's end and the thieves' end refer to the same slot. Implementations resolve it with one atomic compare-and-swap on the top index: exactly one of the two wins the element, and if the owner loses it treats its deque as empty and goes stealing. Concentrating the race in this one case is what lets every other push and pop stay non-atomic.
If all tasks are independent and roughly equal in size rather than a recursive tree, does the LIFO/FIFO asymmetry still help?
The contention and locality benefits remain — the owner still runs uncontended on cache-warm work and thieves still touch the other end — but the steal-value argument disappears, because the oldest task is no longer a larger subtree than the newest. For flat batches the practical wins come from chunking items into ranges so there is something worth stealing, and some runtimes switch external or flat workloads to FIFO order to preserve submission fairness.

A cook works from the top of their own to-do pad because the pot for that step is already on the stove; a helper walking by takes the sheet from the bottom, because that is the biggest job on the pad and the one nobody has started setting up for.

saying these in an interview costs you the question

Saying LIFO is chosen 'for fairness' — it is the opposite of fair, and locality/space are the real reasons
Claiming thieves take the newest task because it is hottest; that is the one task the owner most wants to keep
Thinking a breadth-first local order is equivalent, ignoring that it makes outstanding-task memory grow with the width of the tree
Assuming the deque needs a lock on every operation, missing that the fast path is deliberately non-atomic
Believing owner and thief can never touch the same element, forgetting the single-element case

In a work-stealing scheduler, each worker keeps its tasks in a double-ended queue: the owner pushes and pops at one end (LIFO for itself) while thieves take from the other end (FIFO with respect to the owner's pushes). Why is it arranged that way rather than both ends behaving the same?

§ answer

basics

solid answer

code

§ go deeper

▾level notes4 levels

▾deep dive~4 min

The structure

Why the owner runs LIFO

Why thieves take the oldest task

Why opposite ends

The costs of the choice

▾common follow-ups2 questions

▾analogy~20 s

▾red flags5 flags

§ context

▾related questions5 questions

▾related topics4 topics

The structure

Why the owner runs LIFO

Why thieves take the oldest task

Why opposite ends

The costs of the choice

answer

go deeper

context