技术缘由

多核多线程下同时操作相同内存地址产生的竞态问题

CPU结构

image.png
image.png

乱序执行技术

1.编译器指令重排
现代编译器为优化而重新安排语句的执行顺序

int x, y, r;
void f()
{
    x = r;
    y = 1;
}

使用编译器优化选项后生成汇编代码

f:
        mov     DWORD PTR y[rip], 1
        mov     eax, DWORD PTR r[rip]
        mov     DWORD PTR x[rip], eax
        ret

2.处理器乱序执行
现代处理器采用指令并行技术,在不存在数据依赖性的前提下,处理器可以改变语句对应的机器指令的执行顺序来提高处理器执行速度

乱序处理器（Out-of-order processors）处理指令通常有以下几步：
a.指令获取
b.指令被分发到指令队列
c.指令在指令队列中等待，直到输入操作对象可用（一旦输入操作对象可用，指令就可以离开队列，即便更早的指令未被执行）
d.指令被分配到适当的功能单元并执行
e.执行结果被放入队列（而不立即写入寄存器堆）
f.只有所有更早请求执行的指令的执行结果被写入寄存器堆后，指令执行的结果才被写入寄存器堆（执行结果重排序，让执行看起来是有序的）
乱序执行相比有序执行能够避免等待不可用的操作对象（有序执行的第二步）从而提高了效率

#include <pthread.h>
#include <assert.h>
 
// -------------------
int cpu_thread1 = 0;
int cpu_thread2 = 1;
 
volatile int x, y, r1, r2;
 
void start()
{
    x = y = r1 = r2 = 0;
}
 
void end()
{
    assert(!(r1 == 0 && r2 == 0));
}
 
void run1()
{
    x = 1;
    r1 = y;
}
 
void run2()
{
    y = 1;
    r2 = x;
}
 
// -------------------
static pthread_barrier_t barrier_start;
static pthread_barrier_t barrier_end;
 
static void* thread1(void*)
{
    while (1) {
        pthread_barrier_wait(&barrier_start);
        run1();
        pthread_barrier_wait(&barrier_end);
    }
 
    return NULL;
}
 
static void* thread2(void*)
{
    while (1) {
        pthread_barrier_wait(&barrier_start);
        run2();
        pthread_barrier_wait(&barrier_end);
    }
 
    return NULL;
}
 
int main()
{
    assert(pthread_barrier_init(&barrier_start, NULL, 3) == 0);
    assert(pthread_barrier_init(&barrier_end, NULL, 3) == 0);
 
    pthread_t t1;
    pthread_t t2;
    assert(pthread_create(&t1, NULL, thread1, NULL) == 0);
    assert(pthread_create(&t2, NULL, thread2, NULL) == 0);
 
    cpu_set_t cs;
    CPU_ZERO(&cs);
    CPU_SET(cpu_thread1, &cs);
    assert(pthread_setaffinity_np(t1, sizeof(cs), &cs) == 0);
    CPU_ZERO(&cs);
    CPU_SET(cpu_thread2, &cs);
    assert(pthread_setaffinity_np(t2, sizeof(cs), &cs) == 0);
 
    while (1) {
        start();
        pthread_barrier_wait(&barrier_start);
        pthread_barrier_wait(&barrier_end);
        end();
    }
 
    return 0;
}

哪些操作是非原子的呢？

Accesses to cacheable memory that are split across bus widths, cache lines, and page boundaries are not guaranteed to be atomic by the Intel Core 2 Duo, Intel®Atom™, Intel Core Duo, Pentium M, Pentium 4, Intel Xeon, P6 family, Pentium, and Intel486 processors.
说点简单点，那些被总线带宽、cache line以及page大小给分隔开了的内存地址的访问不是原子的，你如果想保证这些操作是原子的，你就得求助于机制，对总线发出相应的控制信号才行

哪些操作本身是原子的？

1.单核处理器下中断发生在指令之间，因此单指令操作都是原子的
2.多核处理器下进行零次或一次对齐内存访问的汇编指令是原子的

CPU架构支持原子操作

1.锁内存总线
在x86体系中, CPU提供了HLOCK pin引线, 允许CPU在执行某一个指令(仅仅是一个指令)时拉低HLOCK pin引线的电位, 直到这个指令执行完毕才放开. 从而锁住了总线, 如此在同一总线的CPU就暂时无法通过总线访问内存了, 这样就保证了多核处理器的原子性
2.锁缓存
鉴于锁内存总线的开销较大，提出使用缓存锁，如果缓存在处理器缓存行中内存区域在LOCK操作期间被锁定，当它执行锁操作回写内存时，处理器不在总线上声言LOCK＃信号，而是修改内部的内存地址，并允许它的缓存一致性机制来保证操作的原子性，因为缓存一致性机制会阻止同时修改被两个以上处理器缓存的内存区域数据，当其他处理器回写已被锁定的缓存行的数据时会起缓存行无效

但是有两种情况下处理器不会使用缓存锁定。第一种情况是：当操作的数据不能被缓存在处理器内部，或操作的数据跨多个缓存行（cache line），则处理器会调用总线锁定。第二种情况是：有些处理器不支持缓存锁定。对于Inter486和奔腾处理器,就算锁定的内存区域在处理器的缓存行中也会调用总线锁定。

操作语义

可以和 LOCK 指令前缀一起使用的指令

BT, BTS, BTR, BTC   (mem, reg/imm)
XCHG, XADD  (reg, mem / mem, reg)
ADD, OR, ADC, SBB   (mem, reg/imm)
AND, SUB, XOR   (mem, reg/imm)
NOT, NEG, INC, DEC  (mem)

注意：XCHG 和 XADD (以及所有以 'X' 开头的指令)都能够保证在多处理器系统下的原子操作，它们总会宣告一个 "LOCK#" 信号，而不管有没有 LOCK 前缀

fetch_and_add

static inline int fetch_and_add(int* variable, int value)
  {
      __asm__ volatile("lock; xaddl %0, %1"
        : "+r" (value), "+m" (*variable) // input+output
        : // No input-only
        : "memory"
      );
      return value;
  }

内存栅栏语义

#define barrier() __asm__ __volatile__("": : :"memory")
#define sfece() __asm__ __volatile__("sfence" ::: "memory")  // 写操作有序
#define lfece() __asm__ __volatile__("lfence" ::: "memory")  // 读操作有序
#define mfece() __asm__ __volatile__("mfence" ::: "memory")  // 读写操作有序

image.png

应用

操作系统支持的锁、读写锁、信号量等机制都是基于底层原子操作支持的
(原子操作+等待队列，下回分解...)