#chase-lev #lock-free #scheduler #scheduling

crossbeam-deque

Concurrent work-stealing deque

12 releases (5 breaking)

new 0.6.1 Aug 9, 2018
0.5.2 Aug 2, 2018
0.5.1 Jul 7, 2018
0.3.0 Feb 10, 2018
0.1.1 Nov 29, 2017

#3 in Concurrency

Download history 32809/week @ 2018-05-18 33304/week @ 2018-05-25 36204/week @ 2018-06-01 38151/week @ 2018-06-08 34058/week @ 2018-06-15 34733/week @ 2018-06-22 34997/week @ 2018-06-29 34669/week @ 2018-07-06 38461/week @ 2018-07-13 37717/week @ 2018-07-20 34424/week @ 2018-07-27 38201/week @ 2018-08-03 36808/week @ 2018-08-10

154,831 downloads per month

Concurrent work-stealing deque

Build Status License Cargo Documentation

Usage

Add this to your Cargo.toml:

[dependencies]
crossbeam-deque = "0.6"

Next, add this to your crate:

extern crate crossbeam_deque;

The minimum required Rust version is 1.25.

License

Licensed under the terms of MIT license and the Apache License (Version 2.0).

See LICENSE-MIT and LICENSE-APACHE for details.


lib.rs:

A concurrent work-stealing deque.

This data structure is most commonly used in schedulers. The typical setup involves a number of threads where each thread has its own deque containing tasks. A thread may push tasks into its deque as well as pop tasks from it. Once it runs out of tasks, it may steal some from other threads to help complete tasks more quickly. Therefore, work-stealing deques supports three essential operations: push, pop, and steal.

Types of deques

There are two types of deques, differing only in which order tasks get pushed and popped. The two task ordering strategies are:

  • First-in first-out (FIFO)
  • Last-in first-out (LIFO)

A deque is a buffer with two ends, front and back. In a FIFO deque, tasks are pushed into the back, popped from the front, and stolen from the front. However, in a LIFO deque, tasks are popped from the back instead - that is the only difference.

Workers and stealers

There are two functions that construct a deque: fifo and lifo. These functions return a Worker and a Stealer. The thread which owns the deque is usually called worker, while all other threads are stealers.

Worker is able to push and pop tasks. It cannot be shared among multiple threads - only one thread owns it.

Stealer can only steal tasks. It can be shared among multiple threads by reference or by cloning. Cloning a Stealer simply creates another one associated with the same deque.

Examples

use crossbeam_deque::{self as deque, Pop, Steal};
use std::thread;

// Create a LIFO deque.
let (w, s) = deque::lifo();

// Push several elements into the back.
w.push(1);
w.push(2);
w.push(3);

// This is a LIFO deque, which means an element is popped from the back.
// If it was a FIFO deque, `w.pop()` would return `Some(1)`.
assert_eq!(w.pop(), Pop::Data(3));

// Create a stealer thread.
thread::spawn(move || {
    assert_eq!(s.steal(), Steal::Data(1));
    assert_eq!(s.steal(), Steal::Data(2));
}).join().unwrap();
MIT/Apache-2.0 license

Dependencies

Reverse deps