Non-scalable locks are dangerous

2019-03-21 本文已影响0人 CocoAdapter

Abstract

许多操作系统在内核中使用的是 non-scalable 的自旋锁来序列化一系列操作。当 CPU 核数上升到一定程度的时候，性能会急剧下降。作者用一个新的 Markov-based 性能模型来解释这个现象的本质原因。然后，用一个 scalable 的自旋锁解决了这个问题。

Introduction

non-scalable 的锁会造成真实系统里的性能下降
下降会随着 CPU 核心数的增加而突然出现
尽管关键路径代码可能很少，也还是会触发性能下降

通过 MCS lock 能解决性能问题，其它 scalable 的算法带来的获益很少或基本可忽略。

Are non-scalable locks a problem?

How non-scalable locks work

ticket lock，即类似于医院叫号，每个线程领一个 ticket，当 ticket 上的数字和一个 flag 相同的时候，获取到锁。ticket 的分发是原子操作，ticket 的数字是唯一的。
在 Linux 内核的实现中，

struct spinlock_t {
  int current_ticket ; // 当前持有锁的 ticket num
  int next_ticket ; // 下一个会被分发的 ticket num
}
void spin_lock ( spinlock_t *lock)
{
  int t =
  atomic_fetch_and_inc (&lock -> next_ticket );
  while (t != lock -> current_ticket )
  ; /* spin */
}
void spin_unlock ( spinlock_t *lock)
{
  lock -> current_ticket ++;
}

在多核系统中，这个数据结构被缓存在每个核内。一个解锁操作会失效掉各核的 cashline，强制重新从内存里读。在大部分体系结构里，这个读操作是顺序的（通过共享总线，at the cache line's home, or directory node），从而导致操作总时间与核数线性相关。

Benchmarks

Questions

Benchmarks 的结果抛出了三个问题：

为什么 collapse 会来的“早一些”？按理说，应该当核数增加到一定程度后，性能开始下降。
为什么性能下降这么多？
为什么性能下降这么快，而不是渐进的？N 个核心达到性能顶峰后，N + 2 就惨不忍睹。

Model

Hardware cache coherence

directory-based cache coherence protocol.

The directory

每个核有一个 cache directory，底层硬件比如 BIOS 把内存上一块区域均分给每个 directory。每个 directory 在自己的本地内存中包含每个 cache line 的一个指针，结构如下：
[tag | state | core ID]
state 的取值可能为：

invalid (I) - cache line 为空
shared (S) - cache line 中的数据与内存一致，有可能其它核的缓存中也有这个数据。
modified (M) - cache line 中的数据与内存不一致，有可能其它核的缓存中也有这个数据。

深入了解请 Google/百度 MESI 协议。这里等价于 MSI。

Netwrok messages

当一个核访问一个没被 cache 的 cache line 时，会发一个 load 或 store 请求给这个 cache line 的 home directory，而根据请求的不同和 cache line 的状态不同，home directory 可能需要发送信息给所有包含这个 cache line 的其它 directory，即其它核，其它核返回一些信息完成数据和状态的变化。

这部分内容也可参考 MESI 协议，这里打的比方和讲的细致程度不够。

Performance model for ticket locks

首先看一下锁申请的到达率和锁获得的服务率的定义：

a: 一个 CPU 核连续两次请求锁的平均间隔。
1/a: 单个核提交申请锁的概率。
(n-k)/a: 锁申请的到达率。ak 表示当申请获取锁的核数为 k 时，此时的到达率。
s: 序列化操作的耗时。
c: home directory 响应 cache line 请求的时间。在 cache 一致性协议中，home directory 轮流响应每一个 cahce line 请求。
c*k/2: 因为单个请求耗时 c，如果有 k 个请求，假设在 ki 时锁被请求成功，概率是均等的，那么平均下来，需要 k/2 个请求，总耗时 c*k/2。
s+c*k/2: 加上处理序列化操作部分的耗时，代表两次获取到锁之间的时间间隔。
1/(s+c*k/2): 锁获取的服务率。 sk 表示当申请获取锁的核数为 k 时，此时的服务率。

在本文的 Marklov 链模型中，不同的状态代表排队等待获取锁的不同核心数，用 Pk 表示处于该状态的概率。

没看懂
Pk * ak = Pk+1 * sk 然后基于此推出 Pk 的表达式，以及平均等待核数，就是个期望，用 w 表示。

image.png

那么显然，w 表示在自旋获取锁的核数，而 n - w 表示在做有用工的核数。

Validating the model

除了临界点，模型的曲线和实际是拟合的。临界点的意外，作者认为是因为 ticket lock 的性能在这时不是很稳定，而模型预测的平均、稳定状态的情况。

Implications of model results

ticket lock 的性能急剧下降是因为它本身的设计问题。原因在于 cache 一致性协议。
在 Markrov 模型里，如果一个锁上自旋等待了大量的核，要想减少自旋核数变得很困难，因为 sk 随着 k 的增长而迅速降低。也就是说，如果已经排了很长的队，那么服务率也会降低，而且是反比例函数，也就意味着下降很快。
性能急剧下降只会出现在 short serial sections。这个可以根据 sk 的定义式直接看出，s 对于 sk 的影响。换个理解方式，较少的获取核释放锁的操作，锁的性能对整体的性能影响很小。
这个性能急剧下降导致程序达不到 Amdahl's Law 所描述的加速比。

Which scalable lock?

scalable lock 的算法很多，怎么选？

Scalable lock

让 ticket lock 更加 scalable 的最简单的思想是线性回退（proportional back-off），但麻烦在选择合适的回退因子，即多大的常数来乘以 ticket number。
真正的 Scalable lock 保证在申请锁的时候只会产生常数的 cache misses，所有 Scalable 的算法实现都维护了一个等待者的队列，每个等待者在自己的队列上自旋；不同的是实现细节，影响 API 的设计。

MCS lock
MCS 显式维护了一个 qnode 数据结构的队列。申请锁的核，以原子操作的形式将自己添加到对列尾，把前序节点的 next 指针指向自己；获取到锁的时候，把锁的指针指向这个 qnode 节点。
只要不是在队首的节点，都自旋判断锁指针是否指向自己。
MCS 的实现中，为了不动态分配内存，qnode 是作为参数传入给 lock 和 unlock 函数的。
K42 lock
CLH lock
HCLH lock

Results

略

Using MCS locks in Linux

略。附 c 版本的 MCS 算法伪代码

stuct qnode{
    qnode* next;
    int locked;
}


void acquire_lock(qnode** queue, qnode* node){
    node.next = NULL;
    // atomic op, add node into queue, return its predecessor if exists
    qnode predecessor = fetch_and_store(queue, node);
    if(predecessor != NULL){
        // require but not get yet
        node.locked = 1;
        predecessor.next = node;
        // spin
        while(node.locked){};
    }
}

void release_lock(qnode** queue, qnode* node){
    if(node.next == NULL){
        // atomic op, if queue only contains node, and no new qnode is adding in progress
        if(compare_and_set(queue, node, NULL){
            return ;
        }
        // wait for the adding to finish
        while(node.next == NULL){};
    }
    // let the next spin core to get the lock
    node.next.locked = 0;
}