CH13-综合应用

本章会给出一些处理某些并发编程难题的提示。

计数难题

对更新进行计数

假设薛定谔想要对每一只动物的更新数量进行计数，并且这些更新使用一个没数据元素锁进行同步。这样的计数怎样才能做得最好？

当然，可以考虑第 5 章中任何一种计数算法，但是在这种情况下，最优的方法简单的多。仅仅需要在每一个数据元素中放置一个计数器，并且在元素锁的保护下递增元素就行了。

对查找进行计数

如果薛定谔还想对每只动物的查找进行计数，而这些查找由 RCU 保护。怎样的计数才能做到最好？

一种方法是像 13.1.1 节所述，由一个每元素锁来对查找计数进行保护。不幸的是，这将要求所有查找过程都获得这个锁，在大型系统中，这将形成一个严重的瓶颈。

另一种方法是对计数说“不”，就像 noatime 挂载选项的例子。如果这种方法可行，那显然是最好的办法。毕竟，什么都没有比什么都不做还快。如果查找计数不能被省略，就继续读下去。

第 5 章中的任何计数都可以做成服务，5.2 节中描述的统计计数可能是最常见的选择。但是，这导致大量的内存访问，所需要的计数器数量是数据元素的数量乘以线程数量。

如果内存开销太大，另一个方法是保持每 socket 计数，而不是每 CPU 计数，请注意图 10.8 所示的哈希表性能结果。这需要计数递增作为原子操作，尤其对于用户态来说更是这样。在用户态中，一个特定的线程可能随时迁移到另一个 CPU 上运行。

如果某些元素被频繁的查找，那么存在一些其他方法。这些方法通过维护一个每线程日志来进行批量更新，其对特定元素的多次日志操作可以被合并。当对一个特定日志操作达到一定的递增次数，或者一定的时间过去以后，日志记录将被反映到相应的数据元素中去。Silas Boyd-Wickizer 已经做了一些工作。

使用 RCU 拯救并行软件性能

本节展示如何对本书较早讨论的某些例子应用 RCU 技术。某些情况下，RCU 提供更加简单的代码，另外一些情况下则能提供更好的性能和可扩展性，还有一些情况下，同时提供两者的优势。

RCU 和基于每 CPU 变量的统计计数

5.2.4 节描述了一个统计计数的实现，该实现提供了良好的性能，大致的说是简单的递增，并且能够线性扩展——但仅仅通过 inc_count 递增。不幸的是，需要通过 read_count 读取其值的线程需要获得一个全局锁，因此招致高的高效，并且扩展性不佳。

设计

设计的目的是使用 RCU 而不是 final_mutex 来保护线程在 read_count 中的遍历，已获得良好的性能和扩展性，而不仅仅是保护 inc_count。但是，我们并不希望放弃求和计算的精确性。特别是，当一个特定线程退出时，我们绝对不能丢失退出线程的计数，也不能重复对它进行计数。这样的错误将导致将不精确的结果作为精确结果，换句话说，这样的错误使得结果完全没有意义。并且事实上，final_mutex 的一个目的是，确保线程不会在 read_count 运行过程中，进入并退出。

因此，如果我们不用 final_mutex，就必须拿出其他确保一致性的方法。其中一种方法是将所有已退出线程的计数和，以及指向每线程计数的指针放到一个单一的数据结构。这样的数据结构，一旦没 read_count 使用就保持不变，以确保 read_count 看到一致的数据。

实现

片段 13.5 第 1~4 行展示了 countarray 结构，它包含一个 total 字段，用于对之前已经退出线程的计数、counterp[] 数组，指向当前正在运行的每线程 counter。这个及饿哦股允许特定的 read_count 执行过程看到一致的计数总和，以及运行线程的集合。

第 6~8 行包含每线程 counter 变量的定义，全局指针 countarray 引用单签 countarray 结构，以及 final_mutex 自旋锁。

第 10~13 行展示 inc_count，与之前没有变化。

第 15~29 行展示 read_count，它被大量修改了。第 21~27 行以 rcu_read_lock 和 rcu_read_unlock 代替获得、释放 final_mutex 锁。第 22 行使用 rcu_dereference 将当前 countarray 数据结构的快照获取到临时变量 cap 中。正确的使用 RCU 将确保：在第 27 行的 RCU 读端临界区结束前，该 countarray 数据结构不会被释放掉。第 23 行初始化 sum 作为 cap->total，它表示之前已经退出的线程计数值之和。第 23~26 行将正在运行的线程对应的每线程计数值添加到 sum 中。最后第 28 行返回 sum。

countarray 的初始值由第 31~39 行的 count_init 提供。这个函数在第一个线程创建之前运行，其任务是分配初始数据结构，并将其置为 0，然后将它赋值给 countarray。

第 41~48 行展示了 count_register_thread 函数，他被每一个新创建线程所调用。第 43 行获取当前线程的索引，第 45 行获取 final_mutex，的 46 行将指针指向线程的 counter，第 47 行释放 final_mutex 锁。

第 50~70 行展示了 count_unregister_thread 函数，没一个线程在退出前，条用此函数。第 56~60 行分配一个新的 countarray 数据结构，第 61 行获得 final_mutex 锁，第 67 行释放锁。第 62 行将当前 countarray 的值复制到新分配的副本，第 63 行将现存线程的 counterp 添加到新结构的总和值中，第 64 行将真正退出线程的 counterp[] 数组元素置空，第 66 行保留当前值(很快就会变成旧的)countarray 结构的指针引用，第 66 行使用 rcu_assign_pointer 设置 countarray 结构的新版本。第 68 行等待一个优雅周期的流逝。这样，任何可能并发执行 read_count，并且可能拥有对旧的 countarray 结构引用的线程，都能退出它们的 RCU 读端临界区，并放弃对这些结构的引用。因此，第 69 行能够安全释放旧的 countarray 结构。

讨论

对 RCU 的使用，使得正在退出的线程进行等待，直到其他线程保证，其已经结束对退出线程的 thread 变量的使用。这允许 read_count 函数免于使用锁，因而对 inc_count 和 read_count 函数来说，都为其提供了优良的性能和可扩展性。但是这些性能和扩展性来自于代码复杂性的增加。希望编译器和库函数的编写者能够提供用户层的 RCU，以实现跨越线程安全访问 thread 变量，大大减少 thread 变量使用者所能见到的复杂性。

RCU 及可插拔 IO 设备的计数器

5.5 节展示了一对奇怪的代码段，以处理对可插拔设备的 IO 访问计数。由于需要获取读写锁，因此这些代码段会在快速路径上(开始一个 IO)招致过高的负载。

执行 IO 的代码与原来的代码非常类似，它使用 RCU 读端临界区代替原代码中的读写锁的读端临界区。

1 rcu_read_lock(); 
2 if (removing) { 
3 	rcu_read_unlock(); 
4 	cancel_io(); 
5 } else { 
6 	add_count(1); 
7 	rcu_read_unlock(); 
8 	do_io(); 
9 	sub_count(1); 
10 }

RCU 读端原语拥有极小的负载，因此提升了快速路径的速度。

移除设备的新代码片段如下：

1 spin_lock(&mylock); 
2 removing = 1; 
3 sub_count(mybias); 
4 spin_unlock(&mylock); 
5 synchronize_rcu(); 
6 while (read_count() != 0) { 
7 	poll(NULL, 0, 1); 
8 } 
9 remove_device();

在此，我们将读写锁替换为排他自旋锁，并增加 synchronize_rcu 以等待所有 RCU 读端临界区完成。由于 synchronize_rcu 的缘故，一旦我们允许到第 6 行，就能够知道，所有剩余 IO 已经被识别到了。

当然 synchronize_rcu 的开销可能比较大。不过，既然移除设备这种情况比较少见，那么这种方法通常是一个不错的权衡。

数组及长度

如果我们有一个受 RCU 保护的可变长度数组，如下面的代码片段：

1 struct foo { 
2 	int length; 
3 	char *a; 
4 };

数组 ->a[] 的长度可能会动态变化。在任意时刻，其长度由字段 ->length 表示。当然，这带来了如下竞争条件。

数组被初始化为 16 个字节，因此 length 等于 16。
CPU0 紧挨着 length 的值，得到 16。
CPU1 压缩数组长度到 8，并将 ->a[] 赋值为指向新 8 字节长的内存块的指针。
CPU0 从 ->a[] 获取到新的指针，并且将新值存储到元素 12 中。由于数组仅仅有 8 个字符，这导致 SEGV 或内存破坏。

我们可以使用内存屏障来放置这种情况。该方法确实可行，但是带来了读端的开销，更糟的是需要显式使用内存屏障。

一个更好的办法是将值及数组放进同一个数据结构，如下所示：

1 struct foo_a { 
2 	int length; 
3 	char a[0]; 
4 }; 
5 
6 struct foo { 
7 	struct foo_a *fa; 
8 };

分配一个新的数组(foo_a 数据结构)，然后为新的数组长度提供一个新的存储空间。这意味着，如果某个 CPU 获得 fa 引用，也就能能确保 length 能够与 a 的长度相匹配。

数组最初为 16 字节，因此 length 等于 16.
CPU0 加载 fa 的值，获得指向数据结构的指针，该数据结构包含值 16，以及 16 字节的数组。
CPU0 加载 fa->length 的值，获得其值 16.
CPU 压缩数组，使其长度为 8，并且将指针赋值为新分配的 foo_a 数据结构，该结构包含一个 8 字节的内存块 a。
CPU 0 从 a 获得新指针，并且将新值存储到第 12 个元素。由于 CPU0 仍然引用旧的 foo_a 数据结构，该结构包含 16 字节的数组，一切都正常。

当然，在所有情况下，CPU1 必须在释放旧数组前等待下一个优雅周期。

散列问题

本节着眼于在处理哈希表时，可能会碰上的一些问题。请注意，这些问题也适用于许多其他与搜索相关的数据结构。

对更新友好的哈希表遍历

如果需要对哈希表中的所有元素进行统计扫描。例如，薛定谔可能希望计算所有动物的平均长度——重量比率。更进一步假设，薛定谔愿意忽略在统计扫描进行时，那些正在从哈希表中添加或移除的动物引起的轻微错误。那么如何来控制并发性？

一种方法是：将统计扫描置于 RCU 读端临界区之内。这允许更新并发的进行，而不影响扫描进程。特别是，扫描过程并不阻塞更新操作，反之亦然。这允许对包含大量数据元素的哈希表进行扫描，这样的扫描将被优雅的支持，即使面对高频率的更新时也是如此。

Feedback

Was this page helpful?

Glad to hear it! Please tell us how we can improve.

Sorry to hear that. Please tell us how we can improve.