Java Happen-before 内存模型浅谈

larmbr | 2015-04-12 | Tags: Java, 同步机制, 内存模型

并发环境下的内存模型,是个很有趣又值得讨论的问题。本文探讨Java的Happen-before 内存模型。

内存模型(Memory Model)

无论是处理器这一层级的裸机,还是构建于裸机上的编程语言所建立的运行时环境(这是更高层级的机器),获取输入,执行,输出结果, 程序的因果性(Causality)都是本质的要求。

其中在单线程 情况下,这种因果性是由处理器内禀地保证的。也就是说,单一的执行流, 有下列指令序列:

例1:

A = 1; 
r1 = A;

执行完r1的结果一定保证是1. 这是直观的,毋庸置疑的。所以,可以这么说,单线程情况下,不需要内存模型,底层的处理器已经保证这一切了。

到了多线程情况下,事情复杂了。复杂的原因是线程访问共享的内存,从而带来的同步问题。同样的,每个线程内部的私有内存对象访问的因果性,仍是由线程内部内禀地保证。但对于共享的内存对象,因果性的保证就复杂了。执行流的同时性,指令乱序,把程序本身的顺序性减弱了,甚至打破了。因此须要定义明确的约束,来保证对于共享对象的时间顺序上的序列化,从而保证因果性。这就是内存模型存在的作用。

比如,内存模型至少需要提供以下保证:

  • 依赖性的内存访问必须序列化。 即:

    A = &V;
    B = *A;
    

    B的值依赖于A的地址取值,必须序列化。 

  • 对同一个内存对象的重叠读写必须序列化。即如例1所言。

顺序一致性内存模型(Sequential Consistency)

这是一种最强的内存模型。看看他的发明者Leslie Lamport对它的定义:

the results of any execution is the same as if the operations of all the processors were executed in some sequential order, and the operations of each individual processor appear in this sequence in the order specified by its program.

本质上,这种模型是把直观的单线程顺序向多线程推广。线程内部的指令是按程序顺序执行的,而线程之间的序列化则依赖于对共享内存对象访问的序列化。从而,整个程序获得了顺序一致性:

  • 线程内是顺序化的,线程内因果性得到保证。
  • 线程间依托对共享内存对象的序列化,从而保证线程间的因果性。即T1对内存对象M的写操作,可以被立即被其它线程观察到。

这种模型的效率低下,因为它阻止了运行时环境发挥可能的cache的能力,阻止处理器乱序,以最大化并行度. 没有处理器/编程语言采取这种模型(?)。Java也不例外。

Java 旧内存模型存在的问题

事实上Java之前采取的内存模型相当激进,或者说宽松,从而引起一些奇怪的问题。比如,之前的内存模型上,volatile的语义无法真正保证的。 volatile本意是保证volatile变量每次从内存中读取,以获得可能的由别的线程修改的新值,即对volatile变量的访问无法被乱序:对它的读一定保证在对它的最近一次写之后。但之前的内存模型,并未阻止编译器的对volatile变量和非volatile变量的乱序行为。这意味着volatile的语义可以被破坏:

这是网上找的例子:

例2:

class VolatileExample {
  int x = 0;
  volatile boolean v = false;
  public void writer() {
    x = 42;
    v = true;
  }

  public void reader() {
    if (v == true) {
      //uses x - guaranteed to see 42 ? Not guaranteed prior JSR 133 !
    }
  }
}

volatile变量v相当于一个标志,用来通知读者线程:可以读取x值。但是,编译器或运行时环境可以对volatile变量v和非volatile变量x乱序. 从而可能读者发现v为true时,读取x值时,x还没被赋值为42! 这在旧Java内存模型中没被禁止。

Happen-Before

JSR133[1]修复了之前的内存模型,并引入了Happen-Before的概念,用于约束一些tricky的奇怪的可能行为。

Happen-Before 是一种严格偏序顺序。这是个数学上概念,可以借助对应的全序的概念来理解严格偏序。全序(total order)是指在一个集合上的一种二元关系R,任意取集合中的两个元素,e1,e2, 在这种关系的意义下,都是可比较的。举例:自然数集合,R表示“小于等于”,那么任意两个自然数N1, N2,在“小于等于”意义下,一定是可以比较的: 要么N1 <=N2, 要么N2 <= N1.

严格偏序(strict partial order),从名字上看是更像是部分的顺序,抛开定义,它表示一个集合上的一种二元关系R,任意取集合中的两个元素,e1,e2, 在这种关系的意义下,可能可以比较,也可能不可以比较。举例:自然数集合上的‘<’关系。

Happen-Before 就可以类比于自然数集合上的‘<’关系。它作用于程序的所有可能的指令执行顺序集合的子集,规定了“在……之前发生”这种顺序。这个子集的定义在所以可能发生Data Race的地方,其它地方,依旧赋予编译器和运行时环境很大的自由,可以乱序,可以利用缓存,来提高效率。

其中定义的子集,也就是必须遵守 Happen-Before 的地方[2有:

An unlock on a monitor happens-before every subsequent lock on that monitor.
A write to a volatile field happens-before every subsequent read of that field.
A call to start() on a thread happens-before any actions in the started thread.
All actions in a thread happen-before any other thread successfully returns from a join() on that thread.
The default initialization of any object happens-before any other actions (other than default-writes) of a program.

解释下:

  • 4.1. T1释放锁L,必须发生在,紧接着,T2获取锁L这件事之前。这是符合直觉的,也是锁提供互斥和同步的根本(参看我之前的文章锁与内存屏障
  • 4.2. 这个保证可以解决对volatile变量和非volatile变量的乱序, 从而解决例2中的问题。

Happen-Before并不足够

Happen-Before貌似可以决问题了,但如规范中所说,并不够。因为Happen-Before本质上等同于有向无环图。这样,大部分情况下,指令序列是不会形成闭环的,所以Happen-Before 能保证正确的序列化,因而保证因果性。

但是,如规范中17.4.8所举例子,两个线程的指令序列刚好能形成一个闭环:

Init:  x == 0, y ==0

Thread 1           Thread 2
============       ================
r1 = x;            r2 = y;
if (r1 != 0)       if (r2 != 0)
    y = 1;             x = 1;

LOAD x -> STORE 1 to y -> LOAD y -> STORE 1 to x
  |                                       |
  <--------------------------------------<

直观上看, 上例中最后结果应该是y == 0, x == 0。 但是,在Happen-Before的语义下,可以观察到以下结果:

r1 = x;  // see write of x = 1
y = 1;
r2 = y;  // see write of y = 1
x = 1;

这是非常反直觉,并且应该是被认为错误的!

但是,Happen-Before的语义神奇地允许这样的事发生!看上面图中的环,我们可以看到,Store 1 to x 是Happen-Before Load x 的。

也许你会argue: r1读取的是未发生的x = 1的值, 这怎么可能! 但注意, Happen-Before并不要求时间顺序上的前后, 规范中17.4.5有这样一句话:

It should be noted that the presence of a happens-before relationship between two actions does not necessarily imply that they have to take place in that order in an implementation. If the reordering produces results consistent with a legal execution, it is not illegal.

所以,Java的内存模型中要求实现应该注意上例这种可能,以免出现这种奇葩的结果,这也是Java Memory Model作者之一的Jeremy Manson 的文章:Java Concurrency (&c): Causality and the Java Memory Model中所表达的,因果性的正确保证,你要保证这两点:

That write happened before it, or
You have already justified the write.

第二条就是额外加的限制。针对上面的例子,如果我们认可 x = 1 发生是合法的,那么自然也就应该接受这种奇葩的结果:r1居然可以读到未来的写到x中的值,但这正是Happen-Before语义允许的。如果我们不认可x = 1 的发生,那就能排除这种结果。

从规范上看,Java现在的内存模型是不允许的,而这是虚拟机实现者应该认真关切的。

* * * * * * 全文完 * * * * * *

参考:

[1]: The Java Memory Model

[2]: Java Language Specification 17.4.4

锁与内存屏障

larmbr | 2014-11-14 | Tags: Linux内核, 同步机制

内存屏障是Linux内核编程或编写多处理器程序, 无法避免, 需要慎之又慎对待的棘手问题。幸好, 内核中提供的各种锁原语, 在提供同步/互斥的机制的同时, 也保证了对内存屏障的正确处理。

通用锁机制

  • 锁是为了保护可能被从并发的多个程序执行流访问同一块数据对象而引入的序列化手段。 并发的多个程序执行流可能有以下几种场景:

    1. 多个CPU情况。它们并发访问同一临界区。

    2. 只有一个CPU情况。此时只有一个执行流, 它访问数据对象C。 但是, 该执行流可以被中断, 比如来了一个异步网络数据包, 我们不妨称之为中断。处理这个数据包的中断例程, 如果也访问这个数据对象, 那么这个对象也变成临界区。此时场景等价于多CPU场景, 并发访问同一临界区。

    3. 有些设有DMA能力的设备, 能绕过CPU直接访问内存。所以, 这种场景下, 也能构成CPU, 设备并发访问同一临界区的情况。

为了避免这种竟争情况, 要引入一种序列化机制, 使得并发的访问变成序列化。这种序列化机制是一种凭证, 每参与者都必须先获取该凭证, 才能执行操作; 操作完毕, 要归还凭证。形象化地称该凭证为锁。所以,

    第一, 锁具有序列化的作用。
  • 有了序列化保证并未完事。在我们以锁的作比拟的例子中, 我们有一个隐含假设: 一个拿锁进临界区的参与者, 它见到的"作案现场" 必定是上一个进入者离开时的现场。这在现实中是必然的, 也是直观的。但在系统中, 这并不是必然的。主要有以下两种原因:

    1. 由于出于性能的考量, 在超线程, 流水线等技术持续压榨CPU的同时, CPU还会在合适的情况下采取乱序执行, 也就是, 真实的指令执行顺序并不一定等同程序编写时的程序顺序
    2. 此外, CPU的访问是存在层级的, 简言之, 即先cache, 再内存。 在多CPU的体系架构中, 每个CPU都有自己局部的内存, 当然它也可以访问别的CPU的局部内存。 这意味着, CPU访问离它近的内存快, 访问远的内存慢。 所以, 这会由于cache的刷新延迟而导致访问内存一致性的问题。 也就是内存被修改了, cache还没来得及刷新, CPU就来访问了, 此时访问的是一个无效的旧值。 也就是, 执行顺序并不一定等同于观察顺序

锁的实现还必须保证解决这两个问题, 所以,

   第二, 锁具有保持访存一致性的作用。

锁与内存屏障的关系

回到Linux内核中的锁机制, 不妨举Mutex为例, 以说明上文两点是如何保证的:

1 互斥机制。Metux是互斥锁。拿到该锁者, 独占访问, 称之为ACQUIRE操作; 访问完毕, 需释放锁, 称之为RELEASE操作。这种互斥保证了序列化。

2 ACQUIRERELEASE上附加保持访存一致性的语义:

ACQUIRE: 对于所有其它参与者来说, 在此操作后的所有读写操作必然发生在ACQUIRE这个动作之后。 前面半句状语从句很重要, 它保证执行顺序等同于观察顺序 。
RELEASE: 对于所有其它参与者来说, 在此操作前的所有读写操作必然发生在RELEASE这个动作之前。 前面半句状语从句很重要, 它保证执行顺序等同于观察顺序 。

注意, 这其中任意一个操作, 都只保证了一半的顺序:

对于ACQUIRE来说, 并没保证ACQUIRE前的读写操作不会发生在ACQUIRE动作之后。
对于RELEASE来说, 并没保证RELEASE后的读写操作不会发生在RELEASE动作之前。

但是, ACQUIRERELEASE配对起来使用后, 就有了完全顺序, 成为一个屏障性的保证, 术语叫memory barrier。 如下:

    |        CPU A                      CPU B
    |-----------------------   -----------------------
  时|
    |      ACQUIRE M
  间|
    |      <临界区>
  顺|
    |      RELEASE M   <---1
  序|                      2--->      ACQUIRE M
    |
    |                                 <临界区>
    |
    |                                 RELEASE M
    ↓

上图, CPU A, CPU B先后进入由Mutex M保护的临界区。

看标1, 2这两行。这两行, 一个RELEASE, 再一个ACQUIRE。实现了一个屏障。它保证 :

12 之前的读写, 不会穿越这个屏障,

12 之后的读写, 不会穿越这个屏障。

只要看下前面的ACQUIRERELEASE的语义, 就可证明。

同时, ACQUIRERELEASE的语义中"对于所有其它参与者来说"这一要求, 又保证了执行顺序等同于观察顺序。

因此, Mutex能实现序列化的同时, ACQUIRERELEASE的语义保证, 共同实现了访存一致性。

不同平台,内存顺序模型(memory ordering model)不同。X86采用的是很强的内存序模型,叫process consistency memory ordering。 也就是,它保证执行顺序等同于观察顺序。在处理器级别已经有cache coherence保证。对于弱模型平台,则必须在ACQUIRERELEASE的中显式实现。

* * * * * * 全文完 * * * * * *

Linux同步机制--可取消的MCS自旋锁

larmbr | 2014-07-27 | Tags: Linux内核, 同步机制, MCS自旋锁

上一篇文章介绍了MCS自旋锁的原理, 这一篇将要描述它的升级版: 可取消的MCS自旋锁

可取消的MCS自旋锁主要用于内核锁机制mutex的实现中。当CPU在获取mutex时, 如果发现锁已经被持有, 且持有者正在其他CPU上运行, 则采取优化做法, 不是去睡眠等待, 而是自旋等待, 因为很大可能持有者马上就要释放锁了。这个自旋等待就用到MCS自旋锁, 而且, 当CPU在自旋等待过程中, 如果发现需要调度, 那么它应该要放弃等待, 所以得实现可取消的语义。

本文将分析该锁的实现, 由上一篇文章知道, MCS自旋锁的实现其实是一个链表, 因此, 可取消的MCS自旋锁必须小心地处理并发情况, 比如多个CPU竞争时, 在取消操作时, 要考虑可能的并发的取消操作或解锁操作。我们将会看到, 内核的实现是如何小心地利用原子操作及优美谨慎的编程技巧来处理这些可能的并发情况的。整个实现代码在kernel/locking/mcs_spinlock.c及相关头文件中, 不到300行, 却体现了无锁并发编程的美感与技巧, 称之为"刀锋上的舞蹈"亦不为过。

本文假设你已经知道MCS自旋锁的原理, 如果不清楚, 可以先阅读MCS自旋锁的原理, 后述所有描述中, 有前文一词, 均指此文。另, 本文的代码描述基于编写本文时Mainline kernel最新的v3.16-rc7。之后可能会随着代码的变迁而更新本文。

数据结构

由前文可知, MCS自旋锁保持着每CPU的本地锁; 另还有一个全局锁, 由前文最后的总结第3, 4点可知, 全局锁其实可以退化为一个指向CPU本地锁的指针, 并且, 由于自旋锁的非可重入性, 本地锁和CPU一一对应, 所以指向本地锁的指针可以用CPU的ID来代替。

所以我们看到实现中, 这个全局锁为:

#define OSQ_UNLOCKED_VAL (0)

struct optimistic_spin_queue {
        /*  
        ¦* Stores an encoded value of the CPU # of the tail node in the queue.
        ¦* If the queue is empty, then it's set to OSQ_UNLOCKED_VAL.
        ¦*/
        atomic_t tail;
};

这和前文的描述一致: 全局锁里保存着指向最后进入等待链表的本地锁的指针, 不过替换为等价的CPU的ID而已。

可以看到这个锁的名字很奇怪。如前文所说, 此锁是为了优化mutex实现的自旋锁, 所以optimistic spin由此而来;前一篇关于MCS自旋锁的文章提到, 其实现就是一个链表, 所以queue亦得到解释。因为该锁是基于特定的使用目的, 所以使用这个名字, 但从通用的锁机制来说, 这不是一个好名字。

至于本地锁, 是一个每CPU的结构, 定义为:

struct optimistic_spin_node {
    struct optimistic_spin_node *next, *prev;
    int locked; /* 1 if lock acquired */
    int cpu; /* encoded CPU # value */
};

与前文的锁结构相比, 多了一个向前的指针, 因此该链表变为双链表。同时还增加了一个cpu字段, 用于指向该结构绑定的CPU。

实现

一. 加锁原语: bool osq_lock(struct optimistic_spin_queue *lock)

下文将逐段解析源码实现。

1. 快速路径, 无竞争情况

bool osq_lock(struct optimistic_spin_queue *lock)
{
    struct optimistic_spin_node *node = this_cpu_ptr(&osq_node);
    struct optimistic_spin_node *prev, *next;
    int curr = encode_cpu(smp_processor_id());
    int old;

    node->locked = 0;
    node->next = NULL;
    node->cpu = curr;

    old = atomic_xchg(&lock->tail, curr);       <--- (1)
    if (old == OSQ_UNLOCKED_VAL)
        return true;

这一意群, 主要实现尝试加锁的操作。(1)处, 由前文可知, 这里通过一个原子交换, 然后检测锁旧值, 若为OSQ_UNLOCKED_VAL, 则表示锁之前为空闲状态, 而且, 原子交换把锁的旧值改为本地的CPU的ID, 表示成功持有, 所以, 返回成功。

2. 慢速路径, 竞争下的自旋等待

    prev = decode_cpu(old);                     <--- (2)
    node->prev = prev;
    ACCESS_ONCE(prev->next) = node;

    while (!smp_load_acquire(&node->locked)) {
        /*
         * If we need to reschedule bail... so we can block.
         */
        if (need_resched())
            goto unqueue;

        arch_mutex_cpu_relax();
    }
    return true;

unqueue:
       ......

如果失败, 表示锁被其他CPU持有, 所以(2)处, 由前文所知, 把本地锁地址放入前一个等待者(或当前持有者)的next字段, 表示把自己加入等待队列。

接着进入一个循环, 在本地锁上进行自旋等待, 轮询locked字段是否变为1, 即是否获得锁了, 是就返回成功; 不是则继续自旋, 并继续查询。 这里的一个辅助宏:

#define smp_load_acquire(p)                     \
({                                  \
    typeof(*p) ___p1 = ACCESS_ONCE(*p);             \
    compiletime_assert_atomic_type(*p);             \
    smp_mb();                           \
    ___p1;                              \
})

用ACCESS_ONCE宏, 强制在每一次轮询中, 重新加载locked的值, 并加入一个最重量级的内存屏障, 以保证屏障前的读/写指令都发生于屏障后的读/写指令。这里还加了个编译时的检查, 保证p的类型是原子的, 亦即底层能以一个指令或原子方式读取该值, 以避免非原子方式读取到中间状态的值。

在自旋过程中, 一但发现自己需要被调度, 则应该放弃自旋等待, 即进入退出等待队列, 跳转到unqueue标号后的处理内容。这正是可取消的语义。

2 放弃等待

接下来是实现可取消语义的重头戏, 在这里将要小心处理并发的可能, 使用原子交换等操作, 避免了使用其他同步机制, 这是无锁并发编程的精彩所在。由于可能存在并发的前向节点或后向节点的离队操作, 所以这里有两点准则, 保证并发的正确性, 即

每个节点在离队前, 要主动解除前向节点指向自己的联系。
每个节点要确保自己的后向联系是一个确定的节点后, 解除与之联系, 才可离队; 或者确保自己是一个最末节点时, 才可离队。

为了证明为什么这两点准则的正确性, 我们不妨枚举可能的情况, 以证明这两点准则能产生约束, 保证顺序地离队, 从而保证正确性。

证明:

在离队时, 需要完成两个操作: 与前向节点解除联系, 以及, 与后向节点解除联系。因此, 我们枚举所有可能情况。

1 当在解除与前向节点的联系时, 遭遇并发的前向节点离队。

  • 如果前向节点的离队操作在我们之前, 那由准则1, 我们将一直阻塞, 因为与前向节点的解除联系, 是必须由我们主动完成的。所以, 能保证前向离队后, 再到我们离队。

  • 如果前向节点的离队操作在我们之后, 那由准则2, 前向节点将一直阻塞, 因为它要等待一个确定的后向节点, 解除与之联系后, 才能离队, 所以, 能保证我们离队后, 前向节点再离队。

2 当在解除与后向节点的联系时, 遭遇并发的后向节点离队。

  • 如果后向节点的离队操作在我们之前, 那由准则2, 我们将一直阻塞, 因为我们要等待一个确定的后向节点, 解除与之联系后, 才能离队, 所以, 能保证后向节点离队后, 再到我们离队。

  • 如果后向节点的离队操作在我们之后, 那由准则1, 后向节点将一直阻塞, 因为对于它来说, 与前向节点解除, 必须由它主动完成的。所以, 能保证我们离队后, 后向节点再离队。

综上, 存在一个确定的离队顺序, 从而保证正确性。

因此, 实现分3步, 第一步, 是解除与prev节点的联系, 同时令其后向联系为空, 这样prev因为不满足第2点, 不会提前离队。第二步, 满足第2点的时后, 解除与next节点的联系, 此时对于next节点来说, 前向节点不指向它了, 所以它要等待前向节点指向它, 然后自己主动解除与联系后才可离队。第三步, 此时, 中间节点已经完成前后向联系而离队了, 而前向, 后向节点由第一步, 第二步可知, 还在等待, 所以建立它们之间的联系, 然后它们才能继续运转, 完成自己的离队操作。

2.1 解除前向联系

unqueue:
    /*
 * Step - A  -- stabilize @prev
 *
 * Undo our @prev->next assignment; this will make @prev's
 * unlock()/unqueue() wait for a next pointer since @lock points to us
 * (or later).
 */
for (;;) {
    if (prev->next == node &&                              <--- (3)       
        cmpxchg(&prev->next, node, NULL) == node)          <--- (4) 
        break;

    /*
     * We can only fail the cmpxchg() racing against an unlock(),
     * in which case we should observe @node->locked becomming
     * true.
     */
    if (smp_load_acquire(&node->locked))                 <--- (5)
        return true;

    arch_mutex_cpu_relax();

    /*
     * Or we race against a concurrent unqueue()'s step-B, in which
     * case its step-C will write us a new @node->prev pointer.
     */
    prev = ACCESS_ONCE(node->prev);                     <--- (6)
}

准则1, 退出等待队列的第一步就是主动把自己与前向节点prev解除联系, 即令prev->next = NULL

先判断prev->next是不是指向自己, 不是的话, 说明我们遭遇并发的prev节点的修改; 是的话, 用一个原子交换操作完成prev->next = NULL, 并返回原来的值。如果检查原来的值不是自己, 说明(3)和(4)之间遭遇了并发的prev节点的修改。

理想情况是这两个判断为真, 由准则1, 我们已经主动完成了解除prev后向联系的操作; 否则, 我们必须等待一个合法的前向节点指向我们, 由我们来主动解除与之联系。所以由(6), 我们重新获取前向节点, 在新一轮循环里检查其是否指向我们。

这里有个特殊情况, 如果prev是在完成解锁操作的话, 那么很可能, 轮到我们获得锁了, 因此有(5)这一个判断, 获取到锁的话, 返回成功, 函数结束。

总之, 完成这一步, 退出循环的要求是满足准则1

2.2 解除后向联系

/*
 * Step - B -- stabilize @next
 *
 * Similar to unlock(), wait for @node->next or move @lock from @node
 * back to @prev.
 */
next = osq_wait_next(lock, node, prev);
if (!next)
    return false;

准则2, 我们必须等待后向节点是一个确定的节点后, 解除与之联系, 才能离队, 因为结合准则1, 这样能序列化一个并发的后向节点的离队操作, 从而保证正确性。又或者有一种特殊情况, 那么就是我们已经是队列最后一个节点, 那么就没有后结点了, 我们可以检测这种特殊情况, 满足的话, 就能快速离队。

所以, osq_wait_next()函数正是实现上述操作的, 如下:

static inline struct optimistic_spin_node *
osq_wait_next(struct optimistic_spin_queue *lock,
          struct optimistic_spin_node *node,
          struct optimistic_spin_node *prev)
{
    struct optimistic_spin_node *next = NULL;
    int curr = encode_cpu(smp_processor_id());
    int old;

    old = prev ? prev->cpu : OSQ_UNLOCKED_VAL;

    for (;;) {
        if (atomic_read(&lock->tail) == curr &&               
            atomic_cmpxchg(&lock->tail, curr, old) == curr) {   <--- (7)
            break;
        }

        if (node->next) {                                       <--- (8)
            next = xchg(&node->next, NULL);
            if (next)
                break;
        }

        arch_mutex_cpu_relax();
    }

    return next;
}

我们可以看到, 在(7)处, 正是先判断这种特殊情况, 如果满足, 我们快速完成了与后向节点的解除联系操作。

否则, 我们在(8)处, 检查后向节点是一个确定的节点, 然后解除与它的联系。这些都与前面的分析一致。

总之, 完成这一步, 退出循环的要求是满足准则2

2.3 自己离队, 建立前,后向节点的联系

/*
 * Step - C -- unlink
 *
 * @prev is stable because its still waiting for a new @prev->next
 * pointer, @next is stable because our @node->next pointer is NULL and
 * it will wait in Step-A.
 */
ACCESS_ONCE(next->prev) = prev;
ACCESS_ONCE(prev->next) = next;

return false;

结合代码注释, 其实它解释的就是准则1准则2保证的, 我们已经离队, 建立前, 后向节点的联系, 完成操作。

二. 解锁原语: void osq_unlock(struct optimistic_spin_queue *lock)

解锁的操作相对加锁, 简单得多, 如下:

void osq_unlock(struct optimistic_spin_queue *lock)
{
    struct optimistic_spin_node *node, *next;
    int curr = encode_cpu(smp_processor_id());

    /*
     * Fast path for the uncontended case.
     */
    if (likely(atomic_cmpxchg(&lock->tail, curr, OSQ_UNLOCKED_VAL) == curr))
        return;

    /*
     * Second most likely case.
     */
    node = this_cpu_ptr(&osq_node);
    next = xchg(&node->next, NULL);
    if (next) {
        ACCESS_ONCE(next->locked) = 1;
        return;
    }

    next = osq_wait_next(lock, node, NULL);
    if (next)
        ACCESS_ONCE(next->locked) = 1;
}

结合前文, 解锁时是一个原子交换操作, 把当前全局锁中保存的队列最后一个节点与自己交换, 然后检查, 如果发现存放的是自己, 则说明当前没有别人竞争锁, 解锁完成。

如果发现不是自己, 说明有人在等待, 把对方的locked置为1, 告诉其已经获得锁, 完成操作。

如果此时, 对方恰好在进行离队操作, 那么我们要等待, 直到下一个节点稳定下来, 把其locked置为1, 告诉其已经获得锁, 完成操作。

总结

在前文的基础上, cancelable语义增加了MCS自旋锁的功能, 使其能在自旋等待中, 放弃等待, 完成离队操作。我们看到了代码是如何以巧妙的实现, 完成无锁并发编程, 解决在放弃等待, 离队过程中的可能的竞争问题的。应当说, 这是一个相当优雅的同步机制。

* * * * * * 全文完 * * * * * *

Linux同步机制--MCS自旋锁

larmbr | 2014-07-26 | Tags: Linux内核, 同步机制, MCS自旋锁

MCS自旋锁简介

MCS自旋锁, 顾名思义, 是一种自旋锁的实现方式。它的名字中的"MCS"来自于两位发明者的名字缩写: Mellor-Crummey和Scott。这种自旋锁的一个显著优点是:减少了CPU cacheline bouncing的问题。所谓CPU cacheline bouncing, 是指几个CPU的cacheline反复失效这一现象, 勿庸多言, 这种行为对性能是巨大的损耗。而传统的自旋锁实现都存在这一问题, 因为自旋锁的本质就是CPU在一个表示锁状态的对象上进行紧密的轮询(tight loop), 以等待锁是空闲的状态, 进而获取之。这个对象可以是一个bit, 也可以是一个整型变量, 不同实现采取不同方案。但传统的自旋锁实现都逃不开这样一个桎梏: 轮询时把该对象拷贝到本地CPU的cacheline, 检测其状态, 如果空闲, 获取该锁;如果不空闲, 则进入紧密轮询, 再把该对象拷贝到本地CPU的cacheline, 重新检测其状态, 以期别人已经释放该锁。这种现象在锁是个热点时更为严重, 多个CPU竞争该锁, 每个CPU都上演这一幕, 从而造成CPU cacheline bouncing的问题。

MCS自旋锁如何巧妙解决这一问题, 在下一节描述。虽然这一种锁相对当前Mainline kernel中的ticket spinlock实现具有上述的优势, 但它依然没代替前者成为内核中采取的方案, 原因是它的实现占用空间太多, 而自旋锁在内核中使用很多, 有些地方对该锁的大小非常敏感, 因此无法被采纳。不过, 在内核另一种加锁机制mutex的实现中, 就使用了它, 以进行优化。关于MCS自旋锁的更多介绍, 可以参阅这篇论文, 或lwn站点上的文章: MCS locks and qspinlocks

MCS自旋锁原理

MCS自旋锁的特色就在于它显著减少CPU cacheline boucing的问题。这一问题的根源在于在轮询中, 每个循环都要把锁对象复制到本地CPU cacheline中来检查, 如果能减少这一开销, 这一问题就能解决。MCS自旋锁正是这样做的, 每次轮询, 都是访问本地CPU的锁对象, 而不是全局的那个锁对象, 这样就显著减少CPU cacheline boucing的问题。初听起来不可思议, 它如何保证本地CPU的锁对象能准确反映全局锁对象的状态的呢? 这正是它实现的高明之处。

另外, 这种实现方式, 甚至可以不需要存在一个全局的锁对象! 后文将"全局锁对象"简称为"G", 将某CPU X的本地锁对象简称为"LX"。

一个MCS自旋锁像这样:

struct mcs_spinlock {
    struct mcs_spinlock *next;
    int locked;
}

其中next字段是一个指针, 指向下一个锁; locked字段则表示锁的状态, 0为空闲, 1为锁被占用

接下来将以一个双CPU的模型来描述该锁是如何工作的。一开始, 只有锁G, 如图:

          G
    +--------------+
    | next == NULL |
    +--------------+
    | locked == 0  |
    +--------------+

当CPU-1准备获取该锁时, 它用G->next字段, 与L1的地址, 进行原子交换操作: xchg(G->next, L1), 交换操作是一个三步骤的操作, 使用原子方式, 避免看见中间状态, 使实现变复杂。交换后, 如图:

           G                  L1 == NULL
     +--------------+      +--------------+
     | next == &L1  |      | next == NULL |
     +--------------+      +--------------+
     | locked == 0  |      | locked == 0  |
     +--------------+      +--------------+

然后, CPU-1检查L1的值, 发现其为NULL, 这表示CPU-1获得了锁。

此时, 若CPU-2也想获得这个锁, 它进行一样的操作, 用本地锁对象L2, 与全局锁G进行next字段的原子交换操作: xchg(I->next, L2->next)。交换后, 如图:

           G                     L1                  L2 == &L1
     +--------------+      +--------------+      +--------------+
     | next == &L2  |      | next == &L2  |      | next == NULL |
     +--------------+      +--------------+      +--------------+
     | locked == 0  |      | locked == 0  |      | locked == 0  |
     +--------------+      +--------------+      +--------------+

然后, CPU-2检查L2的值, 发现其不为NULL, 而是存放着L1的地址, 于是, 它知道现在锁被CPU-1获取着, 于是, 它将L1->next标记为自己的地址: &L2。然后, CPU-2将在本地锁对象L2上进行轮询, 检测L2->locked的状态!

当CPU-1准备释放锁时, 它将和G->next进行一次比较并交换操作: cmpxchg(G->next, L1, NULL)。若G->nextL1, 则将G->next赋值为NULL, 并返回L1; 否则不交换, 只返回G->next的旧值。翻译为大白话, 就是CPU-1检查G是否还指向自己, 如果是, 则将G->next赋为空值, 表示释放锁;否则, 表示有人在等待。

此时, CPU-1发现返回的值是L2的地址, 而不是NULL, 知道CPU-2在等待。于是, 它将L1->next置为NULL, 并将L2->locked的值置为1, 这样就完成了锁的易主, CPU-1释放了锁, CPU-2获得锁。

而此时, CPU-2正在L2上轮询, 当它发现L2->locked变为1时, 它知道自己获取锁了, 停止轮询。

回顾整个过程, 有4点重要的内容:

  • 当要获取锁且锁繁忙时, CPU-2只要在本地锁对象上轮询, 检测本地锁状态即可, 当CPU-1释放锁时, 会更新CPU-2的锁状态, 于是, CPU-2就知道自己获得锁了。这就避免了CPU cacheline bouncing的问题。

  • 这个实现也是公平的, 要获取锁的CPU将依次排队, 以到达的次序获取锁。这是一个队列, 每个本地CPU的next字段指向下一个要获得锁的CPU。

  • 此外, 我们可以发现, 全局锁Glocked字段其实是用不着的, 因此, 实现上, 我们可以省去这个字段, 只保留一个指针, 此时, G退化为一个指示器, 指向当前队列最后一个锁对象, 即最后到达的要获取锁的CPU的锁对象。我们可以看到内核的代码实现中其实就是这么做的。详见内核源码: kernel/locking/mcs_spinlock.h

  • 再进一步, 我们可以发现, 指向本地CPU的锁对象的指针其实是和CPU一一对应的。意思就是, 当我们发现指向CPU-2的本地锁对象指针时, 我们就知道CPU-2在等待这个锁。原因是一个特定的自旋锁对于一个CPU来说, 是不可重入的, 因为当一个CPU获取该锁时, CPU是关本地中断的, 也禁止抢占的, 这防止了从本地CPU的其他上下文, 如中断, 获取该锁的可能, 以避免死锁。基于此, 这个指针可以进一步替换为CPU号, 这就是内核中可取消的MCS自旋锁的做法, 这是下一篇文章的内容。

* * * * * * 全文完 * * * * * *

Linux内核中避免内存碎片的方法(1)

larmbr | 2014-04-08 | Tags: Linux内核, 内存管理, 内存碎片

内存碎片化(Memory fragmentation)一直是内存管理中一大难题,即使在现代分页模式下的虚拟内存,这一问题仍然存在; Linux也不例外。随着系统的运行,内存页的分配遍布整个主存区域,使得要找出连续的物理内存页都很困难,虽然虚拟内存可以解决这个问题:它把不连续的内存页映射为进程地址空间中连续的页。但这并不是本质地解决问题,内存碎片化会导致伙伴系统中的大阶数内存页[1]分配失败,而有时候,大阶数的内存页分配是无法避免的,比如一些低端设备需要访问的DMA区域就必须是连续的内存页。

针对这个问题,Linux内存开发者提出不同的解决方法,比如成块回收(Lumpy Recalim)就是在分配高阶内存页失败后进入页面回收时,尝试成块回收目标回收页相邻的页面,以形成一块满足需求的高阶连续页块。这种方法有其局限性,就是成块回收时没有考虑被连带回收的页面可能是“热页”,即被高强度使用的页,这对系统性能是损伤。

此外,在去碎片化时,需要移动或回收页面,以腾出连续的物理页面,但这可能由于一颗“老鼠屎就坏了整锅粥”——由于某个页面无法移动或回收,导致整个区域无法组成一个足够大的连续页面块。这种页面通常是内核使用的页面,因为内核使用的页面的地址是直接映射(即物理地址加个偏移就映射到内核空间中),这种做法不用经过页表翻译,提高了效率,却也在此时成了拦路虎。

直到2007年,常年在这一领域坚持不懈的Mel Gorman[2]的补丁系列Group pages of related mobility together to reduce external fragmentation v28在历经漫长的28次个版本修改后终于进入内核。他的方法就是针对上面说的这种情况而考虑的,从而解决了这一拦路虎。这种方法以他最终版本时的方法叫做:页面聚类(Page Clustering)

页面聚类

Mel Gorman观察到,所有使用的内存页有三种情形:

`容易回收的(easily reclaimable)`:  这种页面可以在系统需要时回收,比如缓存页(page cache),它们可以轻易的丢弃掉而不会有问题(有需要时再从后备文件系统中读取); 又比如一些生命周期短的内核使用的页,如DMA缓存区。
`难回收的(non-reclaimable)`:  这种页面得内核主动释放,很难回收,内核使用的很多内存页就归为此类,比如为模块分配的区域,比如一些常驻内存的重要内核结构所占的页面。
`可移动的(movable)`:  用户空间分配的页面都属于这种类型,因为用户态的页地址是由页表翻译的,移动页后只要修改页表映射就可以(这也从另一面应证了内核态的页为什么不能移动,因为它们采取直接映射)。

因此,Mel Gorman对伙伴页分配算法做了一点小修改,对每一阶页面,根据分配标志(GFP_RECLAIMABLE对应上述第一种,GFP_MOVABLE对应上述第三种,无聚类标志的对应剩下的第二种),会有三个对应的list中存放相应的页面。每次分配时,根据分配标志从对应list中分配; 在返回页面给伙伴系统时,也会返回到对应的list。这样,随着时间推移,相同分配类型的页面会被聚类到一起。

这样,结合上述的Lumpy Reclaim, 回收页面时,就能保证回收同一类型的; 或者在移动页面时(migrate page), 就能移动可移动类型的页面,从而腾出连续的页面块,以满足高阶分配。

此外,在之前的版本中,Mel的这种按可移动性分三个list的做法得到别的开发者的质疑,他们认为这种分类的做法是内存zone被设计出来的初衷(内存zone分为ZONE_NORMAL,即低端内存;ZONE_HIGHMEM, 即高端内存; ZONE_DMA, 即dma设备专门访问的内存区域),因此Mel这种在伙伴系统中分出三个list的做法他们不大认可。针对这一点,Mel在这第28版本中,还引入了一个叫ZONE_MOVABLE的zone。注意现有的三种zone是实实在在的物理内存区域,而Mel引入的这个则是人为创建的,实际上,组成ZONE_MOVABLE的页来自每一个Node的ZONE_HIGHMEM区。它的目的就是满足使用__GFP_MOVABLE标志的分配, 跟前面的基于list的做法目的一致,只不过是套入了现有的zone框架。

带来的改变

这种做法带来的效果是明显的,如Mel在邮件中所说:

Our tests show that about 60-70% of physical memory can be allocated on a desktop after a few days uptime. In benchmarks and stress tests, we are finding that 80% of memory is available as contiguous blocks at the end of the test. To compare, a standard kernel was getting < 1% of memory as large pages on a desktop and about 8-12% of memory as large pages at the end of stress tests.

下篇文章将讲解Linux内核中另一个去碎片化的功能:Memory compaction。

参考:

[1]: 这是伙伴分配算法中的概念,一个阶数为3的分配表示要分配23=8页连续物理内存页。

[2]: 这位大名鼎鼎的内核黑客就是《Understanding the Linux Virtual Memory Manager》此书的作者。

Linux内核中的内存屏障(2)

larmbr | 2014-02-16 | Tags: Linux内核, 内存管理

上一篇文章介绍了为什么需要内存屏障和什么是内存屏障。这篇主要介绍Linux内核中的内存屏障API。

内存屏障API分类

如前文所述,在处理器和编译器层次,都可能会对程序指令顺序进行重排,所以Linux分别提供了这两个层次的内存屏障API。此外,对于一些使用MMIO(内存映射IO)的设备,Linux也提供了相应的内存屏障API-mmiowb()(本文不会介绍)。

编译器内存屏障

内核在这一层次提供了唯一一个API, 叫做barrier()。使用这个API可以防止因为编译器的指令优化重排。

对于内核主要支持的GCC编译器,这个API利用了内联汇编,典型实现如下:

 #define barrier() __asm__ __volatile__("": : :"memory")

汇编指令部分什么也没有,在破坏描述符部分有个memory关键字,该关键字强制gcc编译器假设所有内存单元均被汇编指令修改,因此使得所有缓存无效,cpu将不得不重新读取内存中的数据。

对于Intel的编译器,这个API直接利用了编译器内建函数实现该功能:

#define barrier() __memory_barrier()  

处理器内存屏障

对应前文的描述,处理器提供了对应的API,总结如下图:

        类型              强制版本               SMP条件性版本
   =============== ======================= ===========================
        写屏障             wmb()                   smp_wmb()
        读屏障             rmb()                   smp_rmb()
       通用屏障             mb()                    smp_mb()
    数据依赖屏障   read_barrier_depends()  smp_read_barrier_depends()

强制版本表示,该版本对应的API确实提供其对应的屏障语义。

SMP条件性版本则视乎内核是编译成单处理器版本还是多处理器(SMP)版本, 实现有所不同。

  • 如果是编译成单处理器版本,则其实现仅仅是一个简单的barrier()编译器屏障。因为在单处理器上,程序的因果性是由处理器内在地保证的,无论处理器进行如何的重排,并不会改变程序的最终语义(否则这就是个有问题的处理器了), 所以只要一个编译器优化屏障,确保在编译器这一层次不会因为优化而重排了指令,改变了语义即可。不过如果在单处理器上处理与有着松散的MMIO访问模型的设备,那么内存屏障仍然是需要的,这就是强制版本发挥作用的场所了。

  • 如果是编译成多处理器版本,则会实现对应的屏障语义。下面就x86架构分析Linux内核的实现。

前一篇文章说过,x86是一种叫流程一致性(process consistency)的模型,简言之:对于某个处理器的写操作,它可以按照其意愿重排执行顺序,对于所有其它处理器,他们的观察顺序,就是它实际的执行顺序。因此,在x86架构上,只要保证对写操作加入必要的内存屏障以保证其顺序,那么我们也可以保证别的处理器一定会看到这种实际的执行顺序。

Linux还会根据x86处理器的新旧,采取不同的实现。

  • 如果处理器支持SSE/SSE2特性,则这几个内存屏障API的对应实现如下:

     #define mb()    asm volatile("mfence":::"memory")
     #define rmb()   asm volatile("lfence":::"memory")
     #define wmb()   asm volatile("sfence":::"memory")
    

这几条*fence指令是支持SSE/SSE2的x86处理器才引入的内存访问序列化指令,在这里起了内存屏障的作用。注意,实现中还给加了编译内存屏障的功能,也就是这几个处理器内存屏障也包含编译器层次的内存屏障。

  • 如果处理器不支持SSE/SSE2特性,则这几个内存屏障API的对应实现如下:

     #define mb()    asm volatile("lock; addl $0,0(%%esp)":::"memory")
     #define rmb()   asm volatile("lock; addl $0,0(%%esp)":::"memory")
     #define wmb()   asm volatile("lock; addl $0,0(%%esp)":::"memory")
    

其中关键的是lock指令,读写内存的指令在发起时,处理器会向总线发出一个lock#的信号,阻塞住其它内存访问请求,它禁止处理器乱序,并保证内存访问操作会以同样的顺序被其他处理器观察到。这种做法就实现了内存屏障的作用。

至于smp_read_barrier_depends()API, 前一篇文章说过,这种内存屏障的引入只是因为DEC ALPHA极其松散的内存模型引发的这种奇怪的数据依赖乱序,而别的所有处理器都有严格保证了这种情况下不会乱序,所以,可以看到x86架构上该API实现为空操作。

内核中还有其他一些接口隐含地包含了内存屏障的功能,如各种加锁原语, 关中断函数, 调度函数, 睡眠与唤醒函数, 等等。详细可以查阅内核文档Documentation/memory-barriers.txt

何时需要使用内存屏障API

其实内核开发中大部分时候都不须要直接与这些内存屏障API直接打交道,即使需要也大部分被更直观的函数代替,因为这些函数的实现中就封装了内存屏障,典型的就是各种锁的使用。

内核文档Documentation/memory-barriers.txt列举了四种需要使用内存屏障API的情况。

1.处理器间的互操作

典型情况就是处理间通过某个或某几个全局状态/变量进行通信,比如信号量的实现。

2.原子操作

技术上来说,这种情况其实属于第一种情况,也是处理器间就共享变量的互操作。所有修改了共享内存中的某个位置并返回该位置的状态(旧值或新值)的原子操作,都暗含着需要一个条件性的SMP通用屏障(smp_mb())。

但不是所有原子操作都包含内存屏障的语义,比如atomic_readatomic_set就没有。更多参阅内核文档Documentation/atomic_ops.txt

3.访问设备

如前文所说,很多设备都以内存映射IO(MMIO)的方式访问,即读/写设备控制器跟读/写内存位置一样。对于这样的方式,如果处理器或编译器重排了指令,可能导致错误的行为,甚至损坏设备。Linux内核中的访问API如write*()read*()都能正确地处理这种情况,因为它包含了必要的内存屏障。

4.中断操作

当设备驱动程序在一个处理器上操控设备,比如往某个地址控制寄存器写入端口,并往数据寄存器写入数据,另一个处理器上发生了中断,该设备的中断处理程序被调用, 它也往设备进行写入端口,读出数据的操作, 这两个交织的控制流可能会被处理器乱序,从而产生错误的操作。在大多数情况下,这种情况不会发生,因为这种情况下的I/O访问都会被严格的序列化,但如果没有的话,就要加入必要的I/O内存屏障,比如mmiowb()

参考: