std​::sync

Modules

arc
atomics
deque
mpmc_bounded_queue
mpsc_queue
spsc_queue
[src]

Module std::sync::deque

A (mostly) lock-free concurrent work-stealing deque

This module contains an implementation of the Chase-Lev work stealing deque described in "Dynamic Circular Work-Stealing Deque". The implementation is heavily based on the pseudocode found in the paper.

This implementation does not want to have the restriction of a garbage collector for reclamation of buffers, and instead it uses a shared pool of buffers. This shared pool is required for correctness in this implementation.

The only lock-synchronized portions of this deque are the buffer allocation and deallocation portions. Otherwise all operations are lock-free.

Example

use std::rt::deque::BufferPool;

let mut pool = BufferPool::new();
let (mut worker, mut stealer) = pool.deque();

// Only the worker may push/pop
worker.push(1);
worker.pop();

// Stealers take data from the other end of the deque
worker.push(1);
stealer.steal();

// Stealers can be cloned to have many stealers stealing in parallel
worker.push(1);
let mut stealer2 = stealer.clone();
stealer2.steal();
BufferPool

The allocation pool for buffers used by work-stealing deques. Right now this structure is used for reclamation of memory after it is no longer in use by deques.
Stealer

The stealing half of the work-stealing deque. Stealers have access to the opposite end of the deque from the worker, and they only have access to the steal method.
Worker

Worker half of the work-stealing deque. This worker has exclusive access to one side of the deque, and uses push and pop method to manipulate it.
Stolen

When stealing some data, this is an enumeration of the possible outcomes.