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;
}
网友评论