深入理解并行编程-分割和同步设计（五）-白红宇

作者：paul 译者：谢宝友，鲁阳，陈渝

并行快速路径

细粒度的设计一般要比粗粒度的设计复杂。在许多情况，绝大部分开销只由一小部分代码产生[Knu73]。所以为什么不把精力放在这一小块代码上。

这就是并行快速路径设计模式背后的想法，尽可能地并行化常见情况下的代码路径，同时不产生并行化整个算法所带来的复杂性。您必须理解这一点，不只算法需要并行化，算法所属的工作负载也要并行化。构建这种并行快速路径，需要极大的创造性和设计上的努力。

图1.1并行快速路径的设计模式

并行快速路径结合了两种以上的设计模式（快速路径和其他的），因此也成为了一种模板设计模式。下列并行快速路径的实例结合了其他设计模式，见图1.1。

1. 读写锁（1.1节将描述）。

2. Read-Copy-Update（RCU），多数作为读写锁的高性能代替者使用，将在第8.3节介绍，本章中不会对其进行深入讨论。

3. 层级锁（[Mck96]），第1.2节将进行介绍。

4. 资源分配器缓存（[McK96][MS93]）。第1.3节将进行介绍。

1.1. 读写锁

                  01          rwlock_t hash_lock;         
       
                  02                    
       
                  03           struct hash_table          
       
                  04          { 
         
                  05           long nbuckets;          
       
                  06           struct node **buckets;          
       
                  07          };         
       
                  08                    
       
                  09           typedef struct node { 
          
                  10           unsigned long key;          
       
                  11           struct node *next;          
       
                  12          } node_t;         
       
                  13                    
       
                  14           int hash_search(struct hash_table *h, long key)          
       
                  15          { 
         
                  16           struct node *cur;          
       
                  17           int retval;          
       
                  18                    
       
                  19          read_lock(&hash_lock);         
       
                  20          cur = h->buckets[key % h->nbuckets];         
       
                  21           while (cur != NULL) { 
          
                  22           if (cur->key >= key) { 
          
                  23          retval = (cur->key == key);         
       
                  24          read_unlock(&hash_lock);         
       
                  25           return retval;          
       
                  26          }         
       
                  27          cur = cur->next;         
       
                  28          }         
       
                  29          read_unlock(&hash_lock);         
       
                  30           return 0;          
       
                  31          }

图1.1：基于读写锁的哈希表搜索算法

如果同步开销可以忽略不计（比如程序使用了粗粒度的并行化），并且只有一小段临界区修改数据，那么让多个读者并行处理可以显著地增加可扩展性。写者与读者互斥，写者和另一写者也互斥。图1.1显示了哈希搜索如何用读写锁实现。

读写锁是非对称锁的一种简单实例。Snaman[ST87]描述了一种叹为观止的非对称锁，带有6个模式，在许多集群系统中使用。第6章进一步介绍了普通锁和读写锁的许多详细信息。

1.2. 层级锁

                  01           struct hash_table          
       
                  02          { 
         
                  03           long nbuckets;          
       
                  04           struct bucket **buckets;          
       
                  05          };         
       
                  06                    
       
                  07           struct bucket { 
          
                  08          spinlock_t bucket_lock;         
       
                  09          node_t *list_head;         
       
                  10          };         
       
                  11                    
       
                  12           typedef struct node { 
          
                  13          spinlock_t node_lock;         
       
                  14           unsigned long key;          
       
                  15           struct node *next;          
       
                  16          } node_t;         
       
                  17                    
       
                  18           int hash_search(struct hash_table *h, long key)          
       
                  19          { 
         
                  20           struct bucket *bp;          
       
                  21           struct node *cur;          
       
                  22           int retval;          
       
                  23                    
       
                  24          bp = h->buckets[key % h->nbuckets];         
       
                  25          spin_lock(&bp->bucket_lock);         
       
                  26          cur = bp->list_head;         
       
                  27           while (cur != NULL) { 
          
                  28           if (cur->key >= key) { 
          
                  29          spin_lock(&cur->node_lock);         
       
                  30          spin_unlock(&bp->bucket_lock);         
       
                  31          retval = (cur->key == key);         
       
                  32          spin_unlock(&cur->node_lock);         
       
                  33           return retval;          
       
                  34          }         
       
                  35          cur = cur->next;         
       
                  36          }         
       
                  37          spin_unlock(&bp->bucket_lock);         
       
                  38           return 0;          
       
                  39          }

图1.2：基于层级锁的哈希表搜索算法

层级锁背后的想法是尽可能长时间的持有一把粗粒度的锁，在此期间持有细粒度的锁。图1.2显示了我们的哈希表搜索如何采用层级锁的方式实现，不过这也显示了该方法的重大弱点：我们付出了获取第二把锁的开销，可以我们只持有它一小段时间。在这种情况下，简单的数据锁方法则更简单且性能又佳。

小问题1.1：哪种情况下使用层级锁最好？

1.3. 资源分配器缓存

本节展示了一种简明扼要的并行内存分配器，用于分配固定大小的内存。更多信息请见[MG92][MS93][BA01][MSK01]等书，或者参见Linux内核[Tor03]。

1.3.1. 并行资源分配问题

并行内存分配器锁面临的基本问题是在普通情况下快速地进行内存分配和释放，和在不理想情况下有效的分布内存之间的矛盾。

假设有一个直接了当的数据所有权类型的程序——该程序简单地将内存按照CPU数划分，这样每个CPU都有自己的一份。比如，该系统有2个CPU和2G内存（和我正在敲字的这台电脑一样）。我们可以为每个CPU分配1G内存，这样每个CPU都可以访问属于自己的那一半内存，无须加锁，以及不必关心锁带来的复杂性和开销。不幸的是，这种简单的模型存在问题，如果有一种算法，让CPU0分配所有内存，让CPU1释放所有内存，在在生产者-消费者算法中是可能的，这样模型就失效了。

另一个极端，代码锁，则受到大量锁竞争和通信开销的影响。

1.3.2. 资源分配的并行快速路径

图1.3：分配器缓存概要图

常见的解决方案让每个CPU拥有一块规模适中的内存块缓存，以此作为快速路径，同时提供一块较大的共享内存池分配额外的内存块，该内存池用代码锁保护。为了防止任何CPU独占内存块，我们给每个CPU的缓存可以容纳的内存块大小做一限制。在双核系统中，内存块的数据流如图1.3所示：当某个CPU的缓存池已满时，该CPU释放的内存块将传送到全局缓存池中，类似地，当CPU缓存池为空时，该CPU所要分配的内存块是从全局缓存池中取出来的。

1.3.3. 数据结构

                  01          #define TARGET_POOL_SIZE 3         
       
                  02          #define GLOBAL_POOL_SIZE 40         
       
                  03                    
       
                  04           struct globalmempool { 
          
                  05          spinlock_t mutex;         
       
                  06           int cur;          
       
                  07           struct memblock *pool[GLOBAL_POOL_SIZE];          
       
                  08          } globalmem;         
       
                  09                    
       
                  10           struct percpumempool { 
          
                  11           int cur;          
       
                  12           struct memblock *pool[2 * TARGET_POOL_SIZE];          
       
                  13          };         
       
                  14                    
       
                  15           DEFINE_PER_THREAD(struct percpumempool, percpumem);

图1.4：分配器缓存数据结构

图1.4是一个“玩具式”缓存分配器的数据结构。图1.3的全局缓存池由globalmem实现，类型为strcut globalmempool，两个CPU的缓存池是由每CPU变量percpumem实现，类型为struct percpumempool。这两个数据结构都有一个pool字段，作为指向内存块的指针数组，从下标0开始向上填充。这样，如果globalmem.pool[3]为NULL，那么从下标4开始的数组成员都为NULL。cur字段包含pool数组中下标最大的非空元素，为-1表示所有pool数组的成员为空。从globalmem.pool[0]到globalmem.pool[globalmem.cur]的所有成员必须非空，而剩下的成员必须为空。

图1.5：分配器缓冲池概要图

对pool数据结构的操作见图1.5，图中的六个格子代表pool字段中的数据指针，他们前面的数字代表cur字段。深色的格子代表非空的指针，浅色的格子代表NULL指针。虽然有些让人迷惑，但是请注意该数据结构有一个重要的性质：cur字段总是比非空指针的个数少一个。

1.3.4. 分配函数

                  01           struct memblock *memblock_alloc(void)          
       
                  02          { 
         
                  03           int i;          
       
                  04           struct memblock *p;          
       
                  05           struct percpumempool *pcpp;          
       
                  06                    
       
                  07          pcpp = &__get_thread_var(percpumem);         
       
                  08           if (pcpp->cur < 0) { 
          
                  09          spin_lock(&globalmem.mutex);         
       
                  10           for (i = 0; i < TARGET_POOL_SIZE &&          
       
                  11          globalmem.cur >= 0; i++) { 
         
                  12          pcpp->pool[i] = globalmem.pool[globalmem.cur];         
       
                  13          globalmem.pool[globalmem.cur--] = NULL;         
       
                  14          }         
       
                  15          pcpp->cur = i - 1;         
       
                  16          spin_unlock(&globalmem.mutex);         
       
                  17          }         
       
                  18           if (pcpp->cur >= 0) { 
          
                  19          p = pcpp->pool[pcpp->cur];         
       
                  20          pcpp->pool[pcpp->cur--] = NULL;         
       
                  21           return p;          
       
                  22          }         
       
                  23           return NULL;          
       
                  24          }

图1.6：分配器缓存的分配函数

在图1.6中可以见到分配函数memblock_alloc()。第7行获得当前线程的每线程缓存池，第8行检查缓存池是否为空。

如果为空，第9-16行尝试从全局缓存池中取出内存块填满每线程缓存池，第9行获取自旋锁，第16行释放自旋锁。第10-14行从全局缓存池中取出内存块，移至每线程缓存池，直到每线程缓存池达到目标大小（半满）或者全局缓存池耗尽为止，第15行将每线程缓存池的cur字段设置为合适大小。

接下来，第18行检查每线程缓存池是否还是为空，如果不是，第19-21行取出一个内存块返回。如果为空，第23返回内存耗尽的不幸消息。

1.3.5. 释放函数

                  01           void memblock_free(struct memblock *p)          
       
                  02          { 
         
                  03           int i;          
       
                  04           struct percpumempool *pcpp;          
       
                  05                    
       
                  06          pcpp = &__get_thread_var(percpumem);         
       
                  07           if (pcpp->cur >= 2 * TARGET_POOL_SIZE - 1) { 
          
                  08          spin_lock(&globalmem.mutex);         
       
                  09           for (i = pcpp->cur; i >= TARGET_POOL_SIZE; i--) { 
          
                  10          globalmem.pool[++globalmem.cur] = pcpp->pool[i];         
       
                  11          pcpp->pool[i] = NULL;         
       
                  12          }         
       
                  13          pcpp->cur = i;         
       
                  14          spin_unlock(&globalmem.mutex);         
       
                  15          }         
       
                  16          pcpp->pool[++pcpp->cur] = p;         
       
                  17          }

图1.7：分配器缓存的释放函数

图1.7是内存块的释放函数。第6行获取当前线程的缓存池指针，第7行检查该缓存池是否已满了。

如果是，第8-15行将每线程缓存池一半的内存块释放给全局缓存池，第8行和第14行获取、释放自旋锁。第9-12行实现将内存块从本地移至全局缓存池的循环，第13行将每线程缓存池的cur字段设置为合适的大小。

接下来，第16行将刚刚释放的内存块放入每线程缓存池。

1.3.6. 性能

图1.8：分配器缓存的性能

图1.8是粗略的性能数据，在1Ghz（每个CPU 4300 bogomips）的双核Intel x86处理器上运行，每个CPU的缓存至多可以装下6个内存块。在这个微型benchmark中，每个线程重复分配一组内存块，然后释放，一组内存块的数目以“分配运行长度”的名字显示在x轴上。y轴是每毫秒成功分配/释放的数目——失败的分配不计入内，“+”来自于单线程的运行结果。

从图中可以发现，运行长度在6之前拥有线性的扩展性，性能也非常优秀，不过当运行长度大于6以后，性能开始变得低下，扩展性甚至为负值。鉴于此，将TARGET_POOL_SIZE设置的足够大非常重要，幸运的是在实践中很容易做到这点[MSK01]，尤其是内存容量疯涨的今天。比如，在大多数系统中，将TARGET_POOL_SIZE设置为100是很合理的，这样可以保证有99%的时间是使用每线程缓存池分配和释放的。

从图中可知，使用数据所有权思想的例子相较于使用锁的版本，极大地提升了性能。在常规情况中避免使用锁，正是本书不断重复的主题。

小问题1.1：图1.8中存在一个性能提升的模式：增加三个样本中的运行长度，比如10，11和12，为什么不这么做？

小问题1.2：当运行长度为19或更大时，两线程测试开始出现分配失败。如果全局缓存池的大小为40，每CPU缓存池的大小为3，那么可以出现分配失败的最小分配运行长度是多少？

1.3.7. 真实世界中的设计

并行的“玩具”资源分配器非常简单，但是真实世界中的设计在几个方面扩展这个方案。

首先，真实的资源分配器需要处理各种不同的资源大小，在“玩具”中只能分配固定大小。一种比较流行的做法是提供一系列固定大小的资源，恰当地放置以平衡内碎片和外碎片，比如1980年代晚期的的BSD内存分配器[MK88]。这样做就意味着每种资源大小都要有一个“globalmem”变量，同样对应的锁也要每种一个，因此真实的实现将采用数据锁，而非“玩具”程序中的代码锁。

其次，产品级的系统必须可以改变内存的用途，这意味着这些系统必须能将内存块组合成更大的数据结构，比如页[MS93]。这种组合也需要锁的保护，这种锁也必须是一种资源大小一个的。

第三，组合后的内存必须回到内存管理系统，内存页也必须是从内存管理系统分配的。这一层面所需要的锁将依赖于内存管理系统，但也可以是代码锁。在这一层面中使用代码锁通常是可以容忍的，因为在设计良好的系统中很少触及这一级别[MSK01]。

尽管真实世界的设计要复杂许多，但背后的思想是一样的——并行的快速路径。

表1.1：真实世界中的并行分配器

1.5. 性能总结

@@@ summarize performance of the various options. Forward-reference to the RCU/NBS section.