Two Lock Queue

MPMC queue based on the michael-scott "two lock queue" algorithm.

Documentation

License

two-lock-queue is primarily distributed under the terms of both the MIT license and the Apache License (Version 2.0), with portions covered by various BSD-like licenses.

See LICENSE-APACHE, and LICENSE-MIT for details.

lib.rs:

Multi-producer, multi-consumer FIFO queue communication primitive.

This crate provides a multi-producer, multi-consumer, message-based communication channel, concretely defined among two types:

• Sender
• Receiver

A Sender is used to send data to a Receiver. Both senders and receivers are clone-able such that sending and receiving can be done concurrently across threads.

Disconnection

The send and receive operations will all return a Result indicating whether the operation succeeded or not. An unsuccessful operation is normally indicative of the other half of the channel having "hung up" by being dropped in its corresponding thread.

Once half of a channel has been deallocated, most operations can no longer continue to make progress, so Err will be returned.

Examples

Simple usage:

use std::thread;

let (tx, rx) = two_lock_queue::channel(1024);

for i in 0..10 {
    let tx = tx.clone();
    thread::spawn(move || {
        tx.send(i).unwrap();
    });
}

let mut threads = vec![];

for _ in 0..10 {
    let rx = rx.clone();
    threads.push(thread::spawn(move || {
        let j = rx.recv().unwrap();
        assert!(0 <= j && j < 10);
    }));
}

for th in threads {
    th.join().unwrap();
}

Algorithm

The algorithm is a variant of the Michael-Scott two lock queue found as part of Java's LinkedBlockingQueue. The queue uses a mutex to guard the head pointer and a mutex to guard the tail pointer. Most of the time, send and receive operations will only need to lock a single mutex. An AtomicUsize is used to track the number of elements in the queue as well as handle coordination between the producer and consumer halves.