第十讲共享计数

对于基于锁的并发数据结构实现而言，锁本身即构成顺序瓶颈，导致对临界区的访问只能是顺序的。这类顺序瓶颈是由计算任务决定的，不允许并发或者并行，正如在（第 6 讲）空转锁的并发实现中通过队列机制来达到理想的顺序性能。

为了利用多核性能优势，提出有界池(Pool)概念，含有put, remove方法。

一、软件组合树

二、静态一致池和计数器

这里不理解，这里的图，自己静态一致。这里需要问一下

三、计数网

计数网（Counting Network）：任意多个令牌以任意次序从任意输入线进入网络，都将在输出线上输出；且不论令牌在输入线上是如何分布的，在输出线上的分布都是平衡的，且首先在顶线输出。

步进特性

例如，一个计数网有四条输入线和四条输出线（自上而下分别称作 1 线、2 线、3 线和 4 线）。若令牌数 n=4k（即令牌数是 4 的倍数，k >= 0），则每条输出线上输出的令牌是一样多的（即每条输出线都输出 k 个令牌）。若 n=4k+1，则 1 线上会多输出一个令牌（即 1 线输出 k+1 个令牌，其余三线各输出 k 个令牌）。若 n=4k+2，则 1 线和 2 线上会各多输出一个令牌（即 1 线、2 线各输出 k+1 个令牌，3 线、4 线各输出 k 个令牌），依此类推。这种性质称为步进特性（step property）。

四、衍射树

没有较为细节的内容！

五、扁平组合

扁平组合（Flat Combining）是一种粗粒度锁同步的方式。其基本结构如下：
一个全局锁；
一个用于记录组合次数的计数器；
一个以 head 为头指针的发布链表（publication list），由线程局部记录组成。

第十讲 共享计数