X86平台乱序执行简要分析（翻译为主）

时间：2021-12-03 18:49:14

　　多处理器使用松散的内存模型可能会非常混乱，写操作可能会无序，读操作可能会返回不是我们想要的值，为了解决这些问题，我们需要使用内存栅栏（memory fences），或者说内存屏障（memory barrier）。

　　X86平台可能还算是使用松散内存模型的多处理器中还算比较好的了，它针对内存顺序有一定的规范要求，原文如下：

Loads are not reordered with other loads.

Stores are not reordered with other stores.

Stores are not reordered with older loads.

In a multiprocessor system, memory ordering obeys causality (memory ordering respects transitive visibility).

In a multiprocessor system, stores to the same location have a total order.

In a multiprocessor system, locked instructions have a total order.

Loads and stores are not reordered with locked instructions.

　　其中Load是载入的意思，Store是存储的意思，我们可以简单的对应read和write。这些规则主要的意思就是，Load操作不会和其他Load操作进行操作重排，Store操作不会和其他Store操作进行重排，Store操作不会和之前的Load操作进行重排，使用锁指令的时候不会进行操作重排，其中有些意思我也不是理解的非常透彻，大家自己理解。

　　同时X86平台也提供了内存屏障的操作指令，例如mfence，lfence和sfence。但是使用内存屏障指令会导致执行效率的下降，因为CPU需要循环等待。

　　这里有个重要的问题，你既不希望编译器针对你的代码加上栅栏导致运行效率过低，同时也不希望它给你生成不正确的代码。

　　在X86平台上，有一条重要的事项没有保障，就是“Load操作可能在不同的位置上面比它之前的Store操作更早的执行”，这里的位置是内存位置，比如我们简单的认为是一个变量。

　　有一个例子可以说明这个问题，比如x和y是在共享内存中的，他们被初始化为0，r1，r2是处理器的2个寄存器。

Thread 0 Thread 1
mov [_x], 1 mov [_y], 1
mov r1, [_y] mov r2, [_x]

　　当Thread0, 和1这两个线程同时在不同的CPU上被执行，就可能会发生r1, r2的值为0的情况。注意发生这种情况的原因就是因为CPU在Store操作之前先执行了Load操作。

　　发生这种事情会有什么影响呢？那我们举一个多线程锁的特殊例子，Peterson lock，它是一个针对2个线程互斥的特殊算法。它假设2个线程都有自己的线程ID，不是0，就是1，也就是说其中一个线程ID为0，一个为1.他的实现代码是这样的。

class Peterson

{

private:

    // indexed by thread ID, 0 or 1

    bool _interested[];

    // who's yielding priority?

    int _victim;

public:

    Peterson()

    {

        _victim = ;

        _interested[] = false;

        _interested[] = false;

    }

    void lock()

    {

        // threadID is thread local,

        // initialized either to zero or one

        int me = threadID;

        int he =  - me;

        _interested[me] = true;

        _victim = me;

        while (_interested[he] && _victim == me)

            continue;

    }

    void unlock()

    {

        int me = threadID;

        _interested[me] = false;

    }

}

　　为了解释这个算法是如何工作的，让我们假设一下，我们就是其中的一个线程。当我（就是那个线程）需要获得锁的时候，我先将我感兴趣的_interested slot置为true，只有我能写这个slot，其他的线程只能读。同时我将_victim（牺牲者）置为我自己的ID。然后我检查另外的一个线程是否已经获得了锁，如果另外的线程已经获取到了锁，那么我就Spin，也就是循环等待。但是一旦另外的线程释放了锁，并且将它自己设置为_victim，那我就可以获取到锁了，然后就可以针对临界区的数据进行操作了。

　　如果已经基本理解了这个算法的意思，我们将问题简化一下，只抽取其中最关键部分的代码，将_interested数组中的2个slot，使用2个变量zeroWants和oneWants来替代。

　　他们初始化为：

zeroWants = false;

oneWants = false;

victim = ;

　　考虑2个线程同时操作时，我们列出下面的表格：

Thread 0 Thread 1
zeroWants = true;
victim = 0;
while (oneWants && victim == 0)
     continue;
// critical code
zeroWants = false;		 oneWants = true;
victim = 1;
while (zeroWants && victim == 1)
      continue;
// critical code
oneWants = false;

　　最后，我们再将上面的表格转换成伪汇编代码

Thread 0 Thread 1
store(zeroWants, 1)
store(victim, 0)
r0 = load(oneWants)
r1 = load(victim)		 store(oneWants, 1)
store(victim, 1)
r0 = load(zeroWants)
r1 = load(victim)

　　先我们来看下Load和Store zeroWants和oneWants2个变量，在上面的表格是我们期待的正确Load和Store顺序。但是处理器是允许先Load oneWants，然后再Store zeroWants的，同样也允许先Load zeroWants，然后再Store oneWants的。那么乱序执行的样子就可能就是下表这个样子：

Thread 0 Thread 1
r0 = load(oneWants)
store(zeroWants, 1)
store(victim, 0)
r1 = load(victim)		 r0 = load(zeroWants)
store(oneWants, 1)
store(victim, 1)
r1 = load(victim)

　　如果这样执行的话，由于zeroWants和oneWants初始化为0，那么r0, r1也就会变成0，那么spin loop（循环等待）就永远不会被执行，2个线程同时可以针对临界区的数据进行操作！ Peterson lock 在X86平台上就失效了！

　　当然是有办法解决这个问题的，那么就是使用fence类的指令来强制按照正确的顺序执行。在同一个线程中，fence指令可以加在任何store zeroWants和load oneWants之间，在另外一个线程中情况也是一样。这样就能保证正确的执行顺序了。

　　当然我们在平时的编程过程中，并不需要过多的考虑乱序执行以及内存屏障，我们的操作系统比如linux，在它实现加锁的时候，已经将内存屏障的指令加入进去了。

相关文章