Hubbry Logo
Work stealingWork stealingMain
Open search
Work stealing
Community hub
Work stealing
logo
7 pages, 0 posts
0 subscribers
Be the first to start a discussion here.
Be the first to start a discussion here.
Work stealing
Work stealing
Work stealing
View on Wikipedia
from Wikipedia

In parallel computing, work stealing is a scheduling strategy for multithreaded computer programs. It solves the problem of executing a dynamically multithreaded computation, one that can "spawn" new threads of execution, on a statically multithreaded computer, with a fixed number of processors (or cores). It does so efficiently in terms of execution time, memory usage, and inter-processor communication.

In a work stealing scheduler, each processor in a computer system has a queue of work items (computational tasks, threads) to perform. Each work item consists of a series of instructions, to be executed sequentially, but in the course of its execution, a work item may also spawn new work items that can feasibly be executed in parallel with its other work. These new items are initially put on the queue of the processor executing the work item. When a processor runs out of work, it looks at the queues of the other processors and "steals" their work items. In effect, work stealing distributes the scheduling work over idle processors, and as long as all processors have work to do, no scheduling overhead occurs.[1]

Work stealing contrasts with work sharing, another popular scheduling approach for dynamic multithreading, where each work item is scheduled onto a processor when it is spawned. Compared to this approach, work stealing reduces the amount of process migration between processors, because no such migration occurs when all processors have work to do.[2]

The idea of work stealing goes back to the implementation of the Multilisp programming language and work on parallel functional programming languages in the 1980s.[2] It is employed in the scheduler for the Cilk programming language,[3] the Java fork/join framework,[4] the .NET Task Parallel Library,[5] and the Rust Tokio runtime.[6][7]

Execution model

[edit]

Work stealing is designed for a "strict" fork–join model of parallel computation, which means that a computation can be viewed as a directed acyclic graph with a single source (start of computation) and a single sink (end of computation). Each node in this graph represents either a fork or a join. Forks produce multiple logically parallel computations, variously called "threads"[2] or "strands".[8] Edges represent serial computation.[9][note 1]

As an example, consider the following trivial fork–join program in Cilk-like syntax: 

function f(a, b):
    c ← fork g(a)
    d ← h(b)
    join
    return c + d

function g(a):
    return a × 2

function h(a):
    b ← fork g(a)
    c ← a + 1
    join
    return b + c

The function call f(1, 2) gives rise to the following computation graph:

Graph representation of a fork–join computation.

In the graph, when two edges leave a node, the computations represented by the edge labels are logically parallel: they may be performed either in parallel, or sequentially. The computation may only proceed past a join node when the computations represented by its incoming edges are complete. The work of a scheduler, now, is to assign the computations (edges) to processors in a way that makes the entire computation run to completion in the correct order (as constrained by the join nodes), preferably as fast as possible.

Algorithm

[edit]

The randomized version of the work stealing algorithm presented by Blumofe and Leiserson maintains several threads of execution and schedules these onto processors. Each of the processors has a double-ended queue (deque) of threads. Call the ends of the deque "top" and "bottom".

Each processor that has a current thread to execute, executes the instructions in the thread one by one, until it encounters an instruction that causes one of four "special" behaviors:[2]: 10 

  • A spawn instruction causes a new thread to be created. The current thread is placed at the bottom of the deque, and the processor starts executing the new thread.
  • A stalling instruction is one that temporarily halts execution of its thread. The processor pops a thread off the bottom of its deque and starts executing that thread. If its deque is empty, it starts work stealing, explained below.
  • An instruction may cause a thread to die. The behavior in this case is the same as for an instruction that stalls.
  • An instruction may enable another thread. The other thread is pushed onto the bottom of the deque, but the processor continues execution of its current thread.

Initially, a computation consists of a single thread and is assigned to some processor, while the other processors start off idle. Any processor that becomes idle starts the actual process of work stealing, which means the following:

  • it picks another processor uniformly at random;
  • if the other processor's deque is non-empty, it pops the top-most thread off the deque and starts executing that;
  • else, repeat.

Child stealing vs. continuation stealing

[edit]

Note that, in the rule for spawn, Blumofe and Leiserson suggest that the "parent" thread execute its new thread, as if performing a function call (in the C-like program f(x); g(y);, the function call to f completes before the call to g is performed). This is called "continuation stealing", because the continuation of the function can be stolen while the spawned thread is executed, and is the scheduling algorithm used in Cilk Plus.[8] It is not the only way to implement work stealing; the alternative strategy is called "child stealing" and is easier to implement as a library, without compiler support.[8] Child stealing is used by Threading Building Blocks, Microsoft's Task Parallel Library and OpenMP, although the latter gives the programmer control over which strategy is used.[8]

Efficiency

[edit]

Several variants of work stealing have been proposed. The randomized variant due to Blumofe and Leiserson executes a parallel computation in expected time on processors; here, is the work, or the amount of time required to run the computation on a serial computer, and is the span, the amount of time required on an infinitely parallel machine.[note 2] This means that, in expectation, the time required is at most a constant factor times the theoretical minimum.[2] However, the running time (in particular, the number of steals executed) can be exponential in in the worst case.[10] A localized variant, in which a processor attempts to steal back its own work whenever it is free, has also been analyzed theoretically and practically.[11][12]

Space usage

[edit]

A computation scheduled by the Blumofe–Leiserson version of work stealing uses stack space, if were the stack usage of the same computation on a single processor,[2] fitting the authors' own earlier definition of space efficiency.[13] This bound requires continuation stealing; in a child stealing scheduler, it does not hold, as can be seen from the following example:[8] 

for i = 0 to n:
    fork f(i)
join

In a child-stealing implementation, all "forked" calls to f are put in a work queue that thus grows to size n, which can be made arbitrarily large.

Multiprogramming variant

[edit]

The work stealing algorithm as outlined earlier, and its analysis, assume a computing environment where a computation is scheduled onto a set of dedicated processors. In a multiprogramming (multi-tasking) environment, the algorithm must be modified to instead schedule computation tasks onto a pool of worker threads, which in turn are scheduled onto the actual processors by an operating system scheduler. At any given time, the OS scheduler will assign to the work stealing process some number PA ≤ P of the P processors in the computer, because other processes may be using the remaining processors. In this setting, work stealing with a pool of P worker threads has the problem that workers acting as thieves may cause livelock: they may block the execution of workers that would actually spawn useful tasks.[14][15]

A variant of work stealing has been devised for this situation, which executes a computation in expected time

where Pavg is the average number of processors allocated to the computation by the OS scheduler over the computation's running time.[16] The multiprogramming work-scheduler differs from the traditional version in two respects:

  • Its queues are non-blocking. While on dedicated processors, access to the queues can be synchronized using locks, this is not advisable in a multiprogramming environment since the operating system might preempt the worker thread holding the lock, blocking the progress of any other workers that try to access the same queue.
  • Before each attempt to steal work, a worker thread calls a "yield" system call that yields the processor on which it is scheduled to the OS, in order to prevent starvation.

Attempts to improve on the multiprogramming work stealer have focused on cache locality issues[12] and improved queue data structures.[17]

Alternatives

[edit]

Several scheduling algorithms for dynamically multithreaded computations compete with work stealing. Besides the traditional work sharing approach, there is a scheduler called parallel depth-first (PDF) that improves on the space bounds of work stealing,[18] as well giving better performance in some situations where the cores of a chip multiprocessor share a cache.[1]

Notes

[edit]

References

[edit]
Revisions and contributorsEdit on WikipediaRead on Wikipedia

Work stealing

View on Grokipedia
from Grokipedia
Work stealing is a scheduling strategy in designed to dynamically balance computational load across multiple processors by enabling idle processors to "steal" tasks from the private deques of busy processors, thereby reducing idle time and enhancing overall efficiency in executing multithreaded programs. Developed by Robert D. Blumofe and in 1999, this approach contrasts with work sharing, where tasks are pushed to a central queue, by minimizing thread migration and contention through localized operations on double-ended queues (deques). The algorithm for work stealing typically assigns each processor a private deque to manage ready threads or tasks. A processor executes tasks by popping them from the bottom of its own deque (treating it as a stack for local work) and, when idle, randomly selects another processor's deque to steal a task from the top, which acts as a queue to facilitate safe concurrent access without blocking. This asymmetric access—local push/pop from one end and remote steals from the other—ensures low contention and supports non-blocking implementations using atomic operations like . Originally proposed for fully strict multithreaded computations on MIMD-style parallel machines, work stealing has been extended to handle irregular parallelism and multiprogrammed environments. In terms of efficiency, work stealing provides strong theoretical guarantees: for a computation with total work T1T_1 (minimum serial time) and critical-path length T∞T_\infty (longest dependency chain), the expected execution time on PP processors is T1/P+O(T∞)T_1/P + O(T_\infty), achieving near-linear speedup when parallelism (T1/T∞T_1/T_\infty) exceeds PP. Space usage is bounded by O(S1P)O(S_1 P), where S1S_1 is the minimum serial space, and communication overhead remains low compared to alternatives. These bounds hold even under adversarial scheduling by the operating system kernel, making it robust for dynamic workloads. Work stealing has become a cornerstone of modern parallel programming frameworks due to its simplicity, scalability, and adaptability to fine-grained tasks. It powers the runtime of MIT Cilk, where it enables efficient execution of recursive divide-and-conquer algorithms. Intel's (TBB) employs work stealing in its task scheduler to dynamically balance workloads across cores in C++ applications. Similarly, the Java Fork/Join framework, introduced in Java 7, uses work stealing to manage recursive task decomposition, supporting high-throughput parallel processing in JVM-based systems. Variants continue to evolve, addressing challenges like cache efficiency and energy consumption in multicore and distributed settings.

Introduction

Definition and Motivation

Work stealing is a decentralized scheduling strategy employed in to achieve load balancing in multithreaded programs, wherein idle processors proactively "steal" tasks from the local double-ended queues (deques) of busy processors. This approach contrasts with centralized scheduling mechanisms by distributing the responsibility for load redistribution across processors, enabling adaptive handling of computational workloads without requiring prior knowledge of task granularities or execution times. The primary motivation for work stealing arises in environments with dynamic parallelism, where task sizes and creation patterns vary unpredictably, leading to potential load imbalances that static scheduling techniques cannot effectively mitigate. By allowing runtime adaptation, work stealing minimizes processor idle time and enhances overall throughput, particularly in applications exhibiting irregular parallelism such as recursive algorithms or data-driven computations. This dynamic redistribution proves essential for maintaining on multiprocessor systems, where uneven work distribution could otherwise result in significant performance degradation. Key benefits of work stealing include its inherent , achieved through task locality that preserves data access patterns and reduces recovery overhead in the event of processor failures; scalability to large numbers of processors due to its decentralized nature; and low synchronization overhead facilitated by lock-free deque operations. For instance, in divide-and-conquer algorithms like parallel mergesort, uneven subtree sizes can cause some processors to finish early while others remain burdened, but work stealing allows idle processors to extract subtasks from the deques of busy ones, thereby balancing the load and ensuring efficient completion.

Historical Development

Work stealing emerged in the 1990s as a load-balancing strategy for and multithreaded systems, addressing the challenges of dynamic workload distribution on multiprocessors. It was first formalized by Robert D. Blumofe and in their 1993 work on the Cilk at MIT, detailed in the paper "Space-Efficient Scheduling of Multithreaded Computations." This introduced a randomized work-stealing scheduler that ensures efficient execution of fully strict multithreaded computations by allowing idle processors to "steal" tasks from busy ones, while bounding space usage to linear in the computation's size. The approach was designed to minimize scheduling overhead and achieve near-optimal parallelism in systems like Cilk, which targeted fine-grained, dynamic parallelism for applications such as scientific and AI. Key theoretical advancements followed in 1999 with Blumofe and Leiserson's paper "Scheduling Multithreaded Computations by Work Stealing," published in the Journal of the ACM, which provided a rigorous proving the algorithm's efficiency: it spans the computation in expected time proportional to the critical path length plus logarithmic factors, with total work linear in the size. This work solidified work stealing's guarantees for fully strict programs, influencing subsequent scheduler designs. Practical adoption accelerated in the 2000s; Doug Lea's Java Fork/Join framework, proposed in 2000 and integrated into Java 7 in 2011 via JSR-166, adapted work stealing for recursive task decomposition, enabling scalable parallelism in managed environments. Similarly, Intel's (TBB) library, first released in 2007, incorporated work stealing in its task scheduler to support portable, high-performance parallelism in C++ applications. The technique evolved with extensions for robustness in shared-memory systems, notably the non-blocking work-stealing algorithm by Nimar S. Arora, Robert D. Blumofe, and C. Greg Plaxton in 1998, which eliminated locks using operations to support multiprogrammed multiprocessors and reduce contention. More recent innovations include formally verified implementations, such as the block-based work stealing (BWoS) design by Jiawei Wang et al. in 2023 at the on Operating Systems and (OSDI), which partitions per-core queues into blocks for improved and guarantees under high contention. Influential systems beyond Cilk include modern runtimes like the Go programming language's scheduler, which employs work stealing since Go 1.1 (2013), with significant improvements in Go 1.5, to balance goroutines across OS threads, and OpenCilk, an open-source extension of Cilk integrated with the compiler infrastructure since 2019 for optimized parallel code generation.

Core Concepts

Execution Model

In the work stealing execution model, a parallel computation is executed by multiple processors, each maintaining its own double-ended queue (deque) to hold ready tasks, typically in the form of threads or subtasks. When a processor spawns new tasks during execution, it pushes them onto the bottom of its local deque, following a last-in, first-out (LIFO) order for its own task consumption to prioritize recently created work. Conversely, when an idle processor attempts to steal work from another, it pops tasks from the top of the victim's deque, enforcing a first-in, first-out (FIFO) order to balance the load by taking older, potentially larger subtasks. This asymmetric access pattern—LIFO for owners and FIFO for thieves—facilitates efficient locality for the task creator while promoting parallelism through theft. Processors operate in one of two primary states: busy or idle. A busy processor repeatedly pops and executes tasks from the bottom (head) of its own deque until it becomes empty, at which point it transitions to idle. An idle processor randomly selects a victim processor and attempts to steal a task from the top (tail) of that victim's deque; if successful, it executes the stolen task and returns to the busy state, but if unsuccessful, it selects another victim at random and tries again, repeating the process until it finds a task to execute or the computation is complete. This random selection of victims helps distribute load evenly across processors without centralized coordination. Synchronization in the execution model relies on lock-free atomic operations, such as (CAS), to manage concurrent access to deques, avoiding the overhead and potential deadlocks associated with traditional locks. For instance, push and pop operations on a deque are implemented atomically to ensure that only one processor can modify the structure at a time, with failed attempts resolved through retries. The model is particularly suited to computations structured as recursive divide-and-conquer paradigms, where tasks spawn child subtasks upon encountering parallelism, adding them to the owner's deque bottom for immediate LIFO execution. This dynamic task creation ensures that thieves primarily acquire ready, independent subtasks from the deque tail, maintaining progress without violating dependencies in the computation graph. Such interactions enable scalable parallelism in shared-memory multiprocessors, with each processor acting autonomously in the runtime environment.

Task Representation and Deques

In work stealing, tasks are represented as closures or that encapsulate the remaining along with any dependencies, enabling dynamic parallelism. A closure typically includes a , arguments, and a frame for local state, while a captures the point in the program to resume after task execution. This structure supports operations such as spawn, which creates a task for concurrent execution without blocking the , and sync, which suspends the current task until all spawned children complete, ensuring dependency resolution before proceeding. The foundational for managing tasks is a (deque) assigned to each processor, allowing efficient local access and remote stealing. Deques are typically implemented as array-based structures with atomic pointers to the top and bottom indices, ensuring thread-safety in concurrent environments without locks. These pointers are updated using (CAS) operations to handle races between the owning processor and potential thieves. The owner processor performs operations exclusively on the bottom of the deque: it pushes newly spawned tasks to the bottom for sequential execution and pops from the bottom to execute the next local task. In contrast, a thief (an idle processor) attempts to steal a task from the top of another processor's deque, succeeding only if the deque is non-empty, again using CAS to atomically update the top pointer and claim the task. This asymmetric access—bottom for owner, top for thieves—maintains the LIFO order for the owner while providing FIFO-like stealing for load balancing. This design offers key advantages, as bottom-only access by the owner prevents thieves from interfering with the currently active task, preserving the illusion of sequential execution. Furthermore, the array-based deque with CAS ensures amortized O(1) for push, pop, and steal operations, supporting scalable parallelism across multiprocessors.

Algorithm

Standard Work-Stealing Procedure

In the standard work-stealing procedure, each processor maintains its own (deque) of ready tasks and operates in a loop to execute tasks until global termination. The core steps involve: (1) if the local deque is non-empty, the processor pops a task from the bottom of its deque and executes it; (2) if the local deque is empty, the processor selects a random other processor and attempts to steal a task from the top of that processor's deque; (3) if the steal succeeds, the processor executes the stolen task; and (4) the processor repeats this process until all tasks are completed. The procedure incorporates operations for spawning child tasks and synchronizing with them. When a processor spawns a child task during execution, it pushes the child task onto the bottom of its local deque. (sync) at a join point waits for all child tasks spawned since the last sync to complete, ensuring dependencies are resolved before proceeding. This is typically implemented using a join counter that tracks unfinished children; the worker continues executing tasks until the counter reaches zero. Implementations vary: stalling schedulers block the thread at sync until children complete, while greedy schedulers have the worker continue stealing tasks until the join condition is met, improving load balance. The following pseudocode outlines the detailed loop for a worker thread in the standard procedure, including spawn and sync mechanisms (simplified; actual implementations handle task frames and counters):

while (true) { if (local_deque not empty) { task = pop_bottom(local_deque); // Atomic pop from bottom execute(task); } else { victim = random_other_processor(); task = try_steal_top(victim_deque); // Atomic steal from top if (task != null) { execute(task); } else { // Idle; check for termination if (all_deques_empty() && no_active_tasks()) break; } } } spawn(child_task) { push_bottom(local_deque, child_task); // Push to bottom } sync() { // For greedy schedulers: continue the main loop, processing tasks until the task's join counter reaches zero // (all children completed) or termination // For stalling: block until children complete }

while (true) { if (local_deque not empty) { task = pop_bottom(local_deque); // Atomic pop from bottom execute(task); } else { victim = random_other_processor(); task = try_steal_top(victim_deque); // Atomic steal from top if (task != null) { execute(task); } else { // Idle; check for termination if (all_deques_empty() && no_active_tasks()) break; } } } spawn(child_task) { push_bottom(local_deque, child_task); // Push to bottom } sync() { // For greedy schedulers: continue the main loop, processing tasks until the task's join counter reaches zero // (all children completed) or termination // For stalling: block until children complete }

Global termination occurs when all processors' deques are empty and there are no active tasks in the computation. To handle concurrency, the procedure relies on atomic operations such as (CAS) for deque pops and steals, ensuring that races between a processor's local pops (from the bottom) and remote steals (from the top) are resolved safely without locks. This design allows multiple processors to access deques concurrently while maintaining consistency.

Child Stealing vs. Continuation Stealing

In child stealing, a spawning task pushes its ready child subtasks onto the owner's deque before executing its continuation, making the children immediately available for theft by other workers. This approach allows the owner to proceed with the remaining work after spawning, while thieves can access the explicit child tasks stored in the deque. Child stealing is commonly implemented in library-based systems, as it requires no special support to expose subtasks. In contrast, continuation stealing involves the owner executing the spawned child task while pushing a representation of its own —the remaining code after the spawn—onto the deque for potential theft. If a thief steals this , it executes the unfinished portion of the original task, effectively serializing the work across workers. This method relies on or runtime support to capture and resume continuations, often using techniques like stack allocation to avoid frequent dynamic task creation. The trade-offs between these approaches center on implementation complexity, space efficiency, and execution semantics. Child stealing simplifies library integration but can consume unbounded space proportional to the number of spawned tasks, potentially leading to O(n) memory usage for n tasks in unbalanced computations. It also requires dynamic task allocation, which may introduce overhead from locks or garbage collection. Continuation stealing, however, bounds space to O(P) for P processors by limiting enqueued items to active continuations, reducing memory pressure in deep or recursive parallelism, though it demands more invasive language support and may disrupt compiler optimizations if not integrated at the IR level. Additionally, continuation stealing preserves the original serial execution order in the absence of theft, aiding predictable behavior for features like reduction operations. Prominent systems exemplify these choices: child stealing is employed in Intel oneTBB and Parallel Patterns Library for straightforward , while continuation stealing underpins the Cilk runtime, enabling efficient scheduling of recursive divide-and-conquer algorithms with bounded overhead.

Analysis

Time and Work

Work stealing exhibits perfect work , as the total computational work performed across all processors equals the sequential work T1T_1, the minimum time required to execute the on a single processor; each instruction in the multithreaded is executed exactly once, incurring no redundant operations or overhead beyond necessary scheduling actions. The time efficiency of work stealing is characterized by an expected parallel execution time of O(T1/P+T∞)O(T_1 / P + T_\infty) on PP processors, where T∞T_\infty denotes the critical-path length, representing the longest chain of dependent tasks that limits parallelism. This bound provides linear relative to the available parallelism, with high probability (at least 1−ϵ1 - \epsilon) the execution time is T1/P+O(T∞+log⁡P+log⁡(1/ϵ))T_1 / P + O(T_\infty + \log P + \log(1/\epsilon)). In the worst case, the time can reach O(T1+P⋅T∞)O(T_1 + P \cdot T_\infty) due to potential imbalances, but the expected performance avoids this by minimizing idle time through dynamic load redistribution. The analysis relies on amortized techniques, including potential functions and delay-sequence arguments, to bound the overhead of steal operations; unsuccessful steal attempts are shown to have an amortized cost of O(1)O(1) per successful steal, ensuring that scheduling contention does not dominate the runtime. A key factor in achieving this efficiency is the randomized selection of victim processors for stealing, which probabilistically balances the load and reduces the likelihood of repeated failed attempts, as modeled by a balls-and-bins game that guarantees even distribution of work with high probability.

Space Usage

Work-stealing schedulers for fully strict multithreaded computations achieve a total space bound of O(P⋅S1)O(P \cdot S_1), where PP is the number of processors and S1S_1 is the minimum space required for a serial execution of the computation. This bound holds because each processor maintains at most S1S_1 live thread frames in its ready deque, owing to the parent-child structure of threads and the busy-leaves property that limits accumulation of unfinished subcomputations. Each task frame is stored exactly once across all deques and stacks at any time. Per-processor space usage is O(S1)O(S_1), as each deque stores a bounded number of frames corresponding to the local subcomputation depth, plus constant overhead for the deque structure itself. The stealing mechanism ensures balanced distribution, preventing any single deque from growing disproportionately even under varying task assignments, and keeps per-processor space independent of the total number of processors. To further optimize space, implementations often task frames (activation frames) during execution, memory for new threads instead of allocating fresh space, which maintains the overall bound of O(P⋅S1)O(P \cdot S_1) while reducing allocation costs. Child stealing variants minimize continuation storage by having the spawning processor immediately execute the parent and push only tasks to the deque, avoiding the need to hold continuation frames in the deque during child execution. A drawback of work stealing is the potential for temporary space peaks on individual processors during load imbalances, when tasks accumulate in a deque before thieves redistribute them; however, these peaks do not exceed the provable bound established by the analysis.

Variants

Multiprogramming Variant

The multiprogramming variant of work stealing adapts the standard to environments where multiple independent programs or jobs concurrently share a multiprocessor , such as time-shared servers or multitenant platforms. Each job maintains its own collection of per-thread deques for tasks, allowing intra-job stealing as in the conventional model, but extends this by permitting inter-job stealing when a processor exhausts its local job's work. This cross-job stealing helps maintain high processor utilization in dynamic, mixed workloads where jobs may have varying computational demands or undergo preemption by the operating . The approach relies on minimal kernel support to ensure fairness, avoiding the need for heavy time-slicing or centralized resource allocation. Key features include a global mechanism—often provided by the OS or runtime—for assigning processors to job pools and monitoring steal attempts across jobs. For instance, processors prioritize stealing from their assigned job's deques but fall back to other jobs if necessary, using priorities or demand estimates to favor high-load jobs and reduce contention from underloaded ones. In the Balanced Work Stealing (BWS) scheduler, this is achieved by dynamically controlling the number of active "thieves" per job: a monitoring system tracks steal success rates and puts low-success thieves to sleep, while a "watchdog" thread ensures at least one active thief per job to prevent deadlock. This balances load within and between jobs, adapting to OS-level preemption in scenarios. Implementations often integrate lightweight OS extensions, such as system calls for querying thread states and yielding cores directly to busy workers within the same job. The BWS system, built atop the Cilk++ runtime, requires only about 100 lines of Linux modifications to support these features, enabling fences or tickets to logically separate job queues without full isolation. Similarly, adaptive variants like demand-aware work stealing use runtime feedback on job progress to adjust stealing aggressiveness, employing per-job priority queues to throttle inter-job attempts in multi-core servers. These mechanisms ensure that stealing remains decentralized while accommodating multiprogrammed interference. This variant improves overall system utilization in mixed workloads by minimizing idle time and wasteful stealing attempts, outperforming naive work stealing under multiprogramming. For example, BWS boosts average throughput by 12.5% and cuts unfairness (measured as slowdown relative to dedicated execution) from 124% to 20% across benchmarks like and ray tracing. It also better handles preemption than single-job-focused schedulers, as controlled cross-job stealing redistributes work during OS context switches, leading to more predictable performance in shared environments without sacrificing scalability.

Hierarchical and Distributed Variants

Hierarchical work stealing extends the standard algorithm to multi-level architectures, such as those with clusters of processors or NUMA systems, by organizing tasks into nested deques that respect hardware topology. In this approach, processors are grouped into clusters, each maintaining local deques for intra-cluster stealing to minimize communication overhead and preserve cache locality. Group leaders manage additional global deques for inter-cluster stealing, where only larger tasks are transferred to reduce remote accesses. This structure ensures efficient load balancing by prioritizing local operations while allowing cross-cluster redistribution when necessary. The Qthreads library supports multi-threaded hierarchical scheduling for tasking runtimes. In Qthreads, stealing occurs first within local sockets or nodes to exploit locality, escalating to higher levels only if local work is exhausted, thus adapting to high-performance computing (HPC) environments with multi-socket nodes. This design has been shown to improve scalability in distributed-memory clusters by reducing inter-node communication. As of 2025, while languages like Chapel use Qthreads for task management, they assign tasks in a round-robin fashion without work stealing. Distributed variants adapt work stealing for networked environments, enabling remote deque access across nodes via . In these systems, idle processors request tasks from remote deques, often using protocols like MPI for communication, which introduces challenges from network latency and bandwidth constraints. To mitigate latency, techniques such as lazy stealing defer remote requests until local queues are critically empty, or task migration proactively moves work to balance loads without immediate stealing. Examples include extensions to MPI runtimes that integrate work stealing for hybrid MPI+ applications, allowing selective remote task execution based on runtime monitoring. Recent advancements, such as the integration of work stealing into the Celerity distributed (as of 2025), enable dynamic load balancing in large-scale distributed environments using synthetic benchmarks to demonstrate . In actor models, distributed work stealing schedules message-driven computations by stealing actors or tasks across distributed nodes, preserving locality through affinity-aware selection. Recent advancements address in these settings by incorporating checkpointing or replication during steals, ensuring recovery from node failures without full recomputation; for instance, task-level checkpointing in coordinated work-stealing frameworks supports fail-stop semantics in large-scale distributed systems. Key challenges in both hierarchical and distributed variants include amplified latency from cross-level or remote operations, which can degrade efficiency in unbalanced workloads. Solutions involve bounded steals, limiting the number or size of remote operations per cycle, and approximations like probabilistic victim selection to avoid contention hotspots, maintaining near-optimal load balance with reduced overhead. Seminal work on hierarchical schedulers, such as that by Quintin and Wagner, demonstrates up to 20% performance gains over flat stealing in heterogeneous platforms.

Alternatives

Work Sharing

Work sharing is a load-balancing technique in where processors with excess tasks actively donate them to a central shared queue, allowing idle processors to pull tasks for execution. This mechanism typically employs a FIFO (first-in, first-out) global queue to manage tasks, ensuring fair distribution as busy processors push subtasks onto the queue when their local workload exceeds a threshold, while idle ones dequeue and process them. Synchronization primitives, such as mutexes and condition variables, are used to coordinate access to the shared queue, preventing race conditions in multithreaded environments. Historically, work sharing has been employed in early parallel systems predating advanced dynamic scheduling methods, including implementations using the threads () standardized in 1995, where thread pools often employ shared queues for task distribution in producer-consumer patterns. This approach contrasts with the later development of work stealing, which uses hybrid LIFO/FIFO deques per processor for more decentralized management, as introduced in systems like Cilk in the . Work sharing's centralized model provided a straightforward way to handle dynamic workloads in shared-memory multiprocessors before the efficiency gains of stealing were demonstrated. While simpler to implement due to its centralized structure, work sharing suffers from higher contention on the shared queue as the number of processors increases, leading to scalability bottlenecks, and poorer locality compared to work stealing's decentralized per-processor deques, which minimize unnecessary task migrations. In contrast to stealing, which only incurs communication when processors others, work sharing proactively migrates tasks, potentially increasing overhead in balanced scenarios but offering better predictability at low loads. For instance, some implementations of task pools utilize a centralized shared queue for work sharing, distributing tasks dynamically but facing contention issues in large-scale parallelism, whereas others adopt work stealing to improve ; frameworks like Java's ForkJoinPool employ work stealing with local deques for improved load balance and reduced interference.

Global and Centralized Scheduling

In global and centralized scheduling, a master scheduler maintains a shared queue of tasks and assigns them to worker threads or processors based on aggregated load information from the system, enabling a unified view of utilization for balanced distribution. This top-down approach contrasts with decentralized methods by centralizing decision-making, often through a single point of control that monitors worker statuses and dispatches tasks to underutilized units, which can include mechanisms for priority-based or fairness-oriented allocation. Such schedulers are particularly suited for scenarios requiring predictable task ordering or , as the central entity can enforce policies like deadline awareness or quotas across all workers. Variants of centralized scheduling incorporate hybrid elements with work stealing for enhanced flexibility, where the master scheduler oversees a pool of per-worker deques and occasionally intervenes to redistribute tasks, blending global oversight with local autonomy to mitigate some contention issues. For instance, systems like Prompt I-Cilk maintain a centralized pool of deques that supports both work sharing and stealing, allowing the scheduler to push tasks proactively while permitting idle workers to steal from busy ones under central coordination. These hybrids aim to retain the predictability of centralized control while borrowing from stealing's adaptability, though they still rely on periodic with the master for load updates. In multiprogramming environments, such variants can briefly reference partitioned allocation strategies to handle multiple applications, but the core remains top-down assignment. Centralized scheduling offers advantages in predictability and ease of implementing global policies, such as uniform load balancing or priority enforcement, due to its complete system visibility, but it suffers from bottlenecks caused by frequent on the shared queue, leading to contention and reduced throughput as the number of processors grows. degrades beyond small-scale systems because every task submission and retrieval requires locking the central structure, imposing significant overhead in high-contention scenarios, unlike decentralized alternatives that localize most operations. Additionally, while fault-tolerant in theory through redundancy, centralized designs create single points of failure, contrasting with work stealing's inherent resilience where no scheduler dominates task flow. A classic example is the traditional thread pool implementation in Java's ExecutorService, such as , where tasks are enqueued centrally and workers block on the queue for assignment, providing straightforward management for I/O-bound or coarse-grained parallelism but exhibiting contention under fine-grained workloads. This approach ensures ordered execution but lacks the dynamic load balancing of stealing, making it less fault-tolerant in heterogeneous environments where worker failures do not propagate globally. For modern large-scale adaptations, approximate centralized scheduling employs protocols to disseminate load information among nodes periodically, simulating global awareness without a persistent master; this reduces costs while approximating optimal assignments, as seen in self-organized grids where exchanges enable workers to request tasks from high-load peers, scaling to hundreds of nodes with near-centralized efficiency.

Applications

Parallel Programming Frameworks

Work stealing has been integrated into several high-level parallel programming frameworks to enable efficient task scheduling and load balancing in multithreaded environments, abstracting away low-level details from developers. These frameworks typically employ work-stealing schedulers where idle threads opportunistically take tasks from busy threads' deques, promoting dynamic parallelism without explicit user intervention. OpenCilk, the open-source successor to Cilk Plus (deprecated in 2017), is an extension to C and C++ that provides spawn and sync primitives allowing programmers to express parallelism declaratively, with the underlying runtime using a work-stealing scheduler to manage task distribution across threads. The spawn keyword initiates a parallel child task, while sync ensures completion before proceeding, enabling a fork-join model where the scheduler balances load by allowing thieves to steal continuations from victims' deques. This approach, rooted in the original Cilk system, ensures low overhead for serial execution and scales efficiently on multicore processors. OpenCilk 3.0, released in May 2025, includes enhancements for better performance on modern hardware. The Java Fork/Join Framework, part of java.util.concurrent since Java 7, implements a similar model through ForkJoinPool and RecursiveTask subclasses, where tasks are forked into subtasks and joined upon completion, with work stealing occurring via double-ended queues (deques) per worker thread. Idle workers steal tasks from the tail of another thread's deque, reducing contention and improving throughput for divide-and-conquer algorithms like parallel sorting or merging. This design minimizes synchronization overhead and supports automatic parallelism for recursive computations. Intel Threading Building Blocks (TBB) incorporates work stealing in its task-based parallelism model, initialized via task_scheduler_init to control size and affinity, allowing developers to define tasks that the scheduler distributes using a randomized stealing protocol. Tasks are enqueued in a graph-like structure, and the runtime ensures load balancing by having idle arenas steal from others, supporting both coarse- and fine-grained parallelism in C++ applications. In language runtimes, Go's scheduler employs work stealing for goroutines, lightweight threads managed by the runtime, where each processor (P) maintains a local run queue, and idle Ps steal half the tasks from another P's queue to balance execution across OS threads (M). This hides deque operations from users, enabling seamless concurrency for I/O-bound and CPU-bound workloads via goroutines and channels. Similarly, Rust's crate facilitates through parallel iterators (e.g., par_iter()), leveraging a work-stealing inspired by Cilk to partition collections and redistribute work dynamically, abstracting thread management for safe, efficient parallel loops. These frameworks provide key features such as automatic load balancing, where work stealing mitigates imbalances without programmer tuning, and hide deque management entirely, allowing focus on algorithmic logic rather than scheduling details. Evolving from the Cilk-5 system in the 1990s, which introduced provably efficient work stealing for multithreaded C extensions, modern implementations continue this legacy in production languages and libraries.

Real-World Implementations

Work stealing has been integrated into the compiler infrastructure's runtime for efficient task scheduling during compiler optimizations, where idle threads randomly select another thread's queue to steal tasks and balance load across cores. This approach enhances parallelism in tasks like code generation and optimization passes, particularly for irregular workloads in compilation. Task stealing has been proposed to mitigate data skew in aggregations over Resilient Distributed Datasets (RDDs) in , where larger partitions are split into segment tasks that idle executors can steal, improving resource utilization in distributed . This mechanism dynamically redistributes work to prevent bottlenecks in skewed datasets, leading to more balanced execution across cluster nodes. In (HPC), Charm++ leverages work stealing through load balancers like PackStealLB for distributed simulations, enabling asynchronous task migration across nodes to handle irregular computational loads in applications such as and plasma simulations. This distributed variant ensures scalability on large supercomputers by allowing over-loaded chares to donate work to idle ones, reducing communication overhead. Work stealing delivers notable performance gains in irregular workloads, such as graph processing, where benchmarks on heterogeneous CPU-FPGA systems show speedups of 20-50% over static scheduling by dynamically balancing vertex traversals and edge computations. These improvements stem from reduced idle time and better adaptation to varying task granularities in algorithms like . Despite its benefits, implementing work stealing on (NUMA) architectures requires careful tuning to minimize remote memory accesses, as traditional stealers can incur high latency from cross-node thefts; locality-aware variants prioritize local queues before remote ones to optimize cache performance. Recent advancements include formal verifications ensuring properties like progress and , with a 2023 proof for block-based work stealing confirming its correctness under concurrent operations without races.

References

  1. https://dl.acm.org/doi/10.1145/324133.324234
  2. https://www.csd.uwo.ca/~mmorenom/CS433-CS9624/Resources/arora-blumofe-toc01.pdf
  3. https://www.lri.fr/~cecile/ENSEIGNEMENT/IPAR/Exposes/cilk1.pdf
  4. https://dl.acm.org/doi/pdf/10.1145/337449.337465
  5. https://www.intel.com/content/dam/develop/external/us/en/documents/gdma-2-165938.pdf
  6. https://docs.oracle.com/javase/tutorial/essential/concurrency/forkjoin.html
  7. https://epubs.siam.org/doi/10.1137/S0097539793259471
  8. https://gee.cs.oswego.edu/dl/papers/fj.pdf
  9. https://www.usenix.org/system/files/osdi23-wang-jiawei.pdf
  10. https://www.cs.cornell.edu/courses/cs612/2006sp/papers/blumofe94.pdf
  11. https://www.csd.uwo.ca/~mmorenom/CS433-CS9624/Resources/Scheduling_multithreaded_computations_by_work_stealing.pdf
  12. https://dl.acm.org/doi/10.1145/1073970.1073974
  13. https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n3872.pdf
  14. https://www4.cs.fau.de/Publications/2021/schmaus2021nowa.pdf
  15. https://dspace.mit.edu/bitstream/handle/1721.1/150176/trollback-aug-meng-eecs-2023-thesis.pdf?sequence=1&isAllowed=y
  16. https://pdfs.semanticscholar.org/3ee0/eec0553ca719f602b777f2b600a7aa5c31aa.pdf
  17. https://dspace.mit.edu/bitstream/handle/1721.1/149816/MIT-LCS-TR-677.pdf?sequence=1&isAllowed=y
  18. https://dl.acm.org/doi/10.1145/277851.277939
  19. http://istc-cc.cmu.edu/publications/papers/2012/BWS-Eurosys12.pdf
  20. https://www.cs.sjtu.edu.cn/~chen-quan/PDF/Journals/J02.pdf
  21. https://inria.hal.science/inria-00429624/document
  22. https://www.osti.gov/servlets/purl/1110555
  23. https://chapel-lang.org/presentations/2025-02-12-runtime.pdf
  24. https://ieeexplore.ieee.org/document/8514894
  25. https://vivkumar.github.io/papers/ia3-kumar-2016.pdf
  26. https://link.springer.com/article/10.1007/s10766-025-00804-4
  27. https://cs.uwaterloo.ca/~mkarsten/papers/ipdps2018-preprint.pdf
  28. https://www.sharcnet.ca/help/images/4/45/Introduction_to_POSIX_Threads.pdf
  29. https://www.cs.rice.edu/~vs3/PDF/Guo-thesis-2010.pdf
  30. https://arxiv.org/pdf/1810.13186
  31. https://apps.dtic.mil/sti/tr/pdf/ADA233557.pdf
  32. https://dl.acm.org/doi/abs/10.1109/TPDS.2007.70747
  33. https://www.cse.wustl.edu/~angelee/home_page/papers/ws-interactive.pdf
  34. https://www.usenix.org/system/files/conference/atc15/atc15-paper-delgado_update.pdf
  35. https://www.baeldung.com/thread-pool-java-and-guava
  36. https://softwaremill.com/threadpools-executors-and-java/
  37. https://i.cs.hku.hk/~clwang/papers/HPCAsia09-gossip.pdf
  38. https://www.intel.com/content/dam/develop/external/us/en/documents/intel-cilk-plus-white-paper.pdf
  39. https://dl.acm.org/doi/10.1145/277650.277725
  40. http://www.cs.umass.edu/~emery/classes/cmpsci691st/readings/PL/cilk5.pdf
  41. https://www.opencilk.org/posts/2025-05-13-opencilk-3-0-released/
  42. https://www.intel.com/content/www/us/en/docs/onetbb/developer-guide-api-reference/2021-6/how-task-scheduler-works.html
  43. https://www.csd.uoc.gr/~hy529/TBB.pdf
  44. https://rakyll.org/scheduler/
  45. https://blog.logrocket.com/implementing-data-parallelism-rayon-rust/
  46. https://hpc.dmi.unibas.ch/wp-content/uploads/sites/87/2021/09/giger_tasking_project.pdf
  47. https://www.researchgate.net/publication/340164825_Handling_Data_Skew_for_Aggregation_in_Spark_SQL_Using_Task_Stealing
  48. https://www.sciencedirect.com/science/article/abs/pii/S0743731520304214
  49. https://dl.acm.org/doi/10.1145/3404397.3404433
  50. https://dl.acm.org/doi/10.1145/2766450
Add your contribution
Related Hubs
User Avatar
No comments yet.