deque - 一个（大部分）无锁并发工作窃取双端队列

本模块包含 Chase-Lev 工作窃取双端队列的实现，该实现基于 "Dynamic Circular Work-Stealing Deque" 文章中的描述。实现主要基于 "Correct and Efficient Work Stealing for Weak Memory Models" 中使用 C11 原子操作的实现。

本双端队列唯一可能需要锁同步的部分是在双端队列增长时偶尔调用内存分配器。否则所有操作都是无锁的。

示例

use deque;

let (worker, stealer) = deque::new();

// 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 stealer2 = stealer.clone();
stealer2.steal();

历史

deque 模块最初由 Alex Crichton 在 2013-11-26 编写，提交为 Rust git 仓库中的 a70f9d7324a91058d31c1301c4351932880d57e8。

后来，他在 2014-11-24 的提交 71d4e77db8ad4b6d821da7e5d5300134ac95974e 中将其作为 sync 模块重写的部分删除。

随着 crates.io 包仓库的引入，我决定将其作为自己的 crate 恢复。代码基于重写 sync 模块之前 Rust 仓库中的版本。到目前为止的所有更改仅限于使代码和测试编译所需的更改。