29. Lock-based Concurrent Data Structures

有了lock之后，就可以用在一些数据结构中，使其变得thread safe线程安全。问题来了：给定一个数据结构时，如何加入lock使其能够正常工作？如何加入lock才能有好的性能，使得多线程可以尽可能多地并发访问结构？

29.1 Concurrent Counters

以一个最简单的counter数据结构开始：

如何将上面的counter变成线程安全的counter？

可以看到，在counter中加入了lock，并且每次读写数据时都需要对其进行加锁。

让我们来康康现在这个线程安全的lock性能如何。

上图（Precise）展示了从1到4个线程，每个线程更新counter一百万次，实验环境是Intel2.7GHz I5 CPU。可以看到，随着线程数目的增大，该counter的性能逐渐变差。

Scalable Counting

如何解决上述多线程时性能价差的问题呢？其中一种方法叫做approximate counter。approximate counter对于每一个CPU都会设置一个局部物理计数器，并且还有一个全局计数器。对于这些计数器，相应地每个计数器都要有一个lock。

基本思路是：一个运行的线程要更新计数器时，更新的是其所在CPU对应的计数器，由于每个CPU对应计数器都有一个lock，因此在一个CPU上更新一定是同步的。因为每个CPU都有自己的计数器去，那么多CPU之间的线程，可以无连接的更新局部计数器，因此是scalable的。

但是，如何保证全局计数器保存的数值是最新的呢？局部计数器要定期把自己保存的值转移到全局计数器上，因此需要申请全局lock然后将自己的值加到全局计数器上，最后把自己的值重置为0。

问题又来了，将局部计数器的值转移到全局计数器上的频率是多少呢？这是由一个阈值S决定的，当局部计数器的值超过S，就转移。如果S较小，那么计数器可能就没有那么的scalable；如果S较大，计数器更scalable，但是可能计数值可能就没那么准确。

如果S=5：

代码长这样：

还是来康康性能，S值为1024：

可以看到，Approximate性能非常好。

下图展示了四个线程，每个线程更新一百万次，S对性能的影响：

29.2 Concurrent Linked Lists

现在来康康稍微复杂一点点的，链表。加入lock后初级版本长这样：

可以看到，在对链表进行读写操作前，先申请lock，在所有操作都结束后，再释放lock。

这种做法是有大概40%几率出bug的，咱也不知道会出什么bug，但显然这种方法就是不行。

因此，稍稍做一些调整，让对于锁的申请和释放只在真正的critical section前后进行，并且假设malloc()本身就是线程安全的：

Scaling Linked Lists

上面这个版本可以实现基本的线程安全了，但是还不够scalable。一种解决办法叫做hand-over-hand locking。思想非常简单，不再给每个链表一个lock，而是给链表中的每一个Node一个lock。对链表遍历时，必须先获取下一个node的lock，再释放当前node的lock。