Module bastion_executor::run_queue

Concurrent work-stealing deques with proportional stealing enabled.

Adapted from [crossbeam-deque].

These data structures are most commonly used in work-stealing schedulers. The typical setup involves a number of threads, each having its own FIFO or LIFO queue (worker). There is also one global FIFO queue (injector) and a list of references to worker queues that are able to steal tasks (stealers).

We spawn a new task onto the scheduler by pushing it into the injector queue. Each worker thread waits in a loop until it finds the next task to run and then runs it. To find a task, it first looks into its local worker queue, and then into the injector and stealers.

Queues

Injector is a FIFO queue, where tasks are pushed and stolen from opposite ends. It is shared among threads and is usually the entry point for new tasks.

Worker has two constructors:

• new_fifo() - Creates a FIFO queue, in which tasks are pushed and popped from opposite ends.
• new_lifo() - Creates a LIFO queue, in which tasks are pushed and popped from the same end.

Each Worker is owned by a single thread and supports only push and pop operations.

Method stealer() creates a Stealer that may be shared among threads and can only steal tasks from its Worker. Tasks are stolen from the end opposite to where they get pushed.

Stealing

Steal operations come in three flavors:

1. steal() - Steals one task.
2. steal_batch() - Steals a batch of tasks and moves them into another worker.
3. steal_batch_and_pop() - Steals a batch of tasks, moves them into another queue, and pops one task from that worker.

In contrast to push and pop operations, stealing can spuriously fail with Steal::Retry, in which case the steal operation needs to be retried.

Structs

Injector	An injector queue.
Stealer	A stealer handle of a worker queue.
Worker	A worker queue.

Enums

Steal

Possible outcomes of a steal operation.