计数网络

一个用于并发计数的无锁数据结构库。

使用方法

extern crate counting_networks;

use counting_networks::counters::{Counter, BitonicCountingNetwork};

许可协议

计数网络主要在 MIT 许可证和 Apache 许可证（版本 2.0）的条款下分发。

请参阅 LICENSE-APACHE 和 LICENSE-MIT 以获取详细信息。

lib.rs:

计数网络是一种并发数据结构，它提供对特定操作的阻塞访问，最常见的是 fetch-and-inc。

它们首先在 James Aspnes、Maruice Herlihy 和 Nir Shavit 的论文中介绍 [1]。

构建

计数网络是由称为平衡器的简单组件组成的。平衡器可以想象成接收两个输入线并产生两个输出线的元素。通过结构移动的线程可以用沿着这些线传递的令牌来表示。平衡器将交替发送到达输入线的令牌到顶部输出线或底部输出线。这确保了到达的令牌在输出之间以平衡的方式分布。

例如（其中数字表示令牌进入的顺序）

7 6 4 2 1 ──╥── 1 3 5 7
      5 3 ──╨── 2 4 6

计数网络是更广泛类型的网络，称为平衡器网络的一个子类，这些网络使用这些元素构建。平衡器（以及平衡网络的一般而言），将确保每对线之间令牌数量的差异是有限的。它们也被称为 k-平滑网络，其中 k 是限制 [2]。计数网络等同于 1-平滑网络，其中每个线上的输出差异始终为 1。计数网络另一个特性是它们将始终以模网络大小递增的顺序输出令牌。

一个展示这一点的更大示例

      ─────╥────╥─────╥─── 1 5
4 3 1 ─────╨────║──╥──╨─── 2 6
5     ─────╥────║──╨──╥─── 3 7
7 6 2 ─────╨────╨─────╨─── 4

这可以应用于实现共享计数器，一种提供 fetch-and-inc 操作的数据结构，通过在每个输出线上附加一个局部计数器，以便每个离开网络的令牌都会获取计数器的值，并将其增加网络宽度。第 i^th 线将具有初始包含值 i 的计数器 c_i。如果 w 是网络输出宽度，则本地计数器将发出 i、i + w、i + 2w、i + 3w、... 的值。

论文

阅读 Aspnes 等人撰写的论文，作为本主题的入门。还有一本教科书的部分内容，对并发数据结构进行了精彩的概述，并说明了计数网络在其中的位置。寻找关于 Fetch-and-φ 结构的部分。另一篇论文提供了平衡/平滑网络的更广泛背景。最后，关于排序网络的维基百科页面相当直观，你可以看到它们如何与其他类型的网络相关。