Jakub Kotur | 5dd645c | 2020-12-21 17:28:14 +0100 | [diff] [blame] | 1 | //! Concurrent work-stealing deques. |
| 2 | //! |
| 3 | //! These data structures are most commonly used in work-stealing schedulers. The typical setup |
| 4 | //! involves a number of threads, each having its own FIFO or LIFO queue (*worker*). There is also |
| 5 | //! one global FIFO queue (*injector*) and a list of references to *worker* queues that are able to |
| 6 | //! steal tasks (*stealers*). |
| 7 | //! |
| 8 | //! We spawn a new task onto the scheduler by pushing it into the *injector* queue. Each worker |
| 9 | //! thread waits in a loop until it finds the next task to run and then runs it. To find a task, it |
| 10 | //! first looks into its local *worker* queue, and then into the *injector* and *stealers*. |
| 11 | //! |
| 12 | //! # Queues |
| 13 | //! |
| 14 | //! [`Injector`] is a FIFO queue, where tasks are pushed and stolen from opposite ends. It is |
| 15 | //! shared among threads and is usually the entry point for new tasks. |
| 16 | //! |
| 17 | //! [`Worker`] has two constructors: |
| 18 | //! |
| 19 | //! * [`new_fifo()`] - Creates a FIFO queue, in which tasks are pushed and popped from opposite |
| 20 | //! ends. |
| 21 | //! * [`new_lifo()`] - Creates a LIFO queue, in which tasks are pushed and popped from the same |
| 22 | //! end. |
| 23 | //! |
| 24 | //! Each [`Worker`] is owned by a single thread and supports only push and pop operations. |
| 25 | //! |
| 26 | //! Method [`stealer()`] creates a [`Stealer`] that may be shared among threads and can only steal |
| 27 | //! tasks from its [`Worker`]. Tasks are stolen from the end opposite to where they get pushed. |
| 28 | //! |
| 29 | //! # Stealing |
| 30 | //! |
| 31 | //! Steal operations come in three flavors: |
| 32 | //! |
| 33 | //! 1. [`steal()`] - Steals one task. |
| 34 | //! 2. [`steal_batch()`] - Steals a batch of tasks and moves them into another worker. |
| 35 | //! 3. [`steal_batch_and_pop()`] - Steals a batch of tasks, moves them into another queue, and pops |
| 36 | //! one task from that worker. |
| 37 | //! |
| 38 | //! In contrast to push and pop operations, stealing can spuriously fail with [`Steal::Retry`], in |
| 39 | //! which case the steal operation needs to be retried. |
| 40 | //! |
| 41 | //! # Examples |
| 42 | //! |
| 43 | //! Suppose a thread in a work-stealing scheduler is idle and looking for the next task to run. To |
| 44 | //! find an available task, it might do the following: |
| 45 | //! |
| 46 | //! 1. Try popping one task from the local worker queue. |
| 47 | //! 2. Try stealing a batch of tasks from the global injector queue. |
| 48 | //! 3. Try stealing one task from another thread using the stealer list. |
| 49 | //! |
| 50 | //! An implementation of this work-stealing strategy: |
| 51 | //! |
| 52 | //! ``` |
| 53 | //! use crossbeam_deque::{Injector, Stealer, Worker}; |
| 54 | //! use std::iter; |
| 55 | //! |
| 56 | //! fn find_task<T>( |
| 57 | //! local: &Worker<T>, |
| 58 | //! global: &Injector<T>, |
| 59 | //! stealers: &[Stealer<T>], |
| 60 | //! ) -> Option<T> { |
| 61 | //! // Pop a task from the local queue, if not empty. |
| 62 | //! local.pop().or_else(|| { |
| 63 | //! // Otherwise, we need to look for a task elsewhere. |
| 64 | //! iter::repeat_with(|| { |
| 65 | //! // Try stealing a batch of tasks from the global queue. |
| 66 | //! global.steal_batch_and_pop(local) |
| 67 | //! // Or try stealing a task from one of the other threads. |
| 68 | //! .or_else(|| stealers.iter().map(|s| s.steal()).collect()) |
| 69 | //! }) |
| 70 | //! // Loop while no task was stolen and any steal operation needs to be retried. |
| 71 | //! .find(|s| !s.is_retry()) |
| 72 | //! // Extract the stolen task, if there is one. |
| 73 | //! .and_then(|s| s.success()) |
| 74 | //! }) |
| 75 | //! } |
| 76 | //! ``` |
| 77 | //! |
| 78 | //! [`new_fifo()`]: Worker::new_fifo |
| 79 | //! [`new_lifo()`]: Worker::new_lifo |
| 80 | //! [`stealer()`]: Worker::stealer |
| 81 | //! [`steal()`]: Stealer::steal |
| 82 | //! [`steal_batch()`]: Stealer::steal_batch |
| 83 | //! [`steal_batch_and_pop()`]: Stealer::steal_batch_and_pop |
| 84 | |
| 85 | #![doc(test( |
| 86 | no_crate_inject, |
| 87 | attr( |
| 88 | deny(warnings, rust_2018_idioms), |
| 89 | allow(dead_code, unused_assignments, unused_variables) |
| 90 | ) |
| 91 | ))] |
Joel Galenson | f0b1773 | 2021-08-09 10:27:52 -0700 | [diff] [blame] | 92 | #![warn( |
| 93 | missing_docs, |
| 94 | missing_debug_implementations, |
| 95 | rust_2018_idioms, |
| 96 | unreachable_pub |
| 97 | )] |
Jakub Kotur | 5dd645c | 2020-12-21 17:28:14 +0100 | [diff] [blame] | 98 | #![cfg_attr(not(feature = "std"), no_std)] |
Jakub Kotur | 5dd645c | 2020-12-21 17:28:14 +0100 | [diff] [blame] | 99 | |
| 100 | use cfg_if::cfg_if; |
| 101 | |
| 102 | cfg_if! { |
| 103 | if #[cfg(feature = "std")] { |
| 104 | use crossbeam_epoch as epoch; |
| 105 | use crossbeam_utils as utils; |
| 106 | |
| 107 | mod deque; |
| 108 | pub use crate::deque::{Injector, Steal, Stealer, Worker}; |
| 109 | } |
| 110 | } |