2.互斥

现代多处理器系统上的互斥实现

• 互斥的问题定义和假设

• 自旋锁

• 互斥锁

物理世界是个状态机，“生命游戏”。

• 线程=人

• 共享内存=物理世界(世界里的人天生并行)

物理世界没有这种机制去保护资源，必须说我要去拿舍友的钱包，直接拿就行。互斥在保持资源的独占性。互斥锁=厕所包间的锁。

Peterson 算法是个协议，实现两个人上一个坑位。在共享内存上实现的互斥。但是在共享内存上实现互斥并不容易，实现互斥的根本困难：不能同时读/写共享内存

• load(看)，环顾四周的时候不可以写，而且，看一眼马上就闭眼。对于计算机来说，看到的东西马上就过时了。

• store(改变物理世界的状态)，不可以看，只能闭着眼睛动手，而且计算机也不知道把什么改成了什么

原子性，即使一条 ADD 的汇编指令，现代CPU也会把这个拆成指令来执行。当然这是操作系统课，用简单粗暴的算法解决问题，不是算法课研究互斥算法。

什么解决办法呢？改进硬件。修改互斥问题的前提假设。

互斥问题：定义与假设

如果要实现互斥的话，还是得多花一点时间，再去看看互斥的定义和假设。

实现一个算法是有假设的，如果硬件不遵循假设，一个算法的实现可能就是不对的。

这几节写程序用的最多的方法，就是类比真实世界，代码里一会儿=0 一会儿=1，要翻译成人的行为。即理解并发的工具：

• 线程 = 人(大脑的局部存储和计算)

• 共享内存 = 真实的物理世界

• 一切都是状态机

互斥问题：定义

互斥 (mutual exclusion)，“互相排斥”

锁是个数据结构，里面有两个方法，用来获得或者释放锁。 lock_t 数据结构和 lock/unlock API:

typedef struct {
  ...
} lock_t;
void lock(lock_t *lk);
void unlock(lock_t *lk);

lock 和 unlock 的行为，立即执行 or 等待拿到这把锁。以及对 API 的一些要求：

• 如果某个线程持有锁，则其他线程的 lock 不能返回 (Safety)

• 在多个线程执行 lock 时，至少有一个可以返回 (Liveness)

• 能正确处理处理器乱序、宽松内存模型和编译优化

困难的是最后一点。

前面一节中的 Peterson 算法的 C 实现，里面的 BARRIER 里既有编译器屏障，也有处理器屏障，这带来的问题是，我们谈互斥或者任何算法的时候，假设是非常重要的。在理想的假设下去写代码，即读写都是原子的，世界上不存在编译优化，但是 1960 年的假设在现代处理器上根本不成立。

实现互斥的基本假设

能不能让硬件帮忙多做一点点事。硬件为我们提供一条“瞬间完成”读和写的指令。

• 所有人闭眼，看一眼(load) 然后贴上标签(store)

  • 多人同时请求，硬件挑出一个获胜者

  • 失败者等待执行完成后才能继续执行

前面的代码不是一个很好的假设，既有编译器 barrier 也有 cpu barrier，一个更好的方式是，我们希望的是编程语言和计算机一起提供一个好的指令(或者函数)，即原子(atomic)指令。

void atomic_int(long *ptr);
int atomic_xchg(int val, int *ptr);

这两个函数的假设：

• 包含一个原子指令

  • 指令的执行不能被打断

• 包含一个 compiler barrier

  • 无论何种优化都不可越过此函数

• 包含一个 memory fence

  • 保证处理器在 stop-the-world 前所有对内存的 store 都 “生效”

  • 即对 resume-the-world 之后的 load 可见

这是一个很强大的假设，而且是软硬件协同为软件开发者提供的。

所有的 atomic 都会排列出一个顺序，按顺序执行，可以保证的是，前一个 atomic 发生的所有事情都对后一个 atomic 可见，当然，这也会带来一些性能上的小损失。

一个 atomic exchange 的实现

int xchg(int volatile *ptr, int newval) {
  int result;
  asm volatile(
    // 指令自带 memory barrier
    "lock xchgl %0, %1"
    : "+m"(*ptr), "=a"(result)
    : "1"(newval)
    // Compiler barrier
    : "memory"
  );
  return result;
}

这里的实现用了内嵌汇编，不用在意实现，知道它是对的就 OK 了。内联汇编，前加 lock ，事实上，这个指令也并不需要让其让所有CPU真的停下，只要保证不动我要操作的事情就可以了。

有了原子指令，接下来我们就要用这个工具来实现互斥了。即直线这组函数

void lock(lock_t *lk);
void unlock(lock_t *lk);

我们可以设计出怎么样的原子指令？

交换，i++，是我们常用的。

即假设上的新想法

自旋锁(spin lock),用 xchg 实现互斥

如果能原子的实现交换，和物理世界很像了，一些直观想法也非常非常容易的实现。(硬件上的改进可以大大简化软件上的努力)

在厕所门口放一个桌子(共享变量)，上面放着🔑(共享变量的值)，实现互斥的协议：

• 想上厕所的同学(一条 xchg 指令，自带互斥)

  • stop the world天黑请闭眼，所有人不要动，不要看，不要摸

  • 看一眼桌子上有啥东西(🔑或者🔞)

  • 随便手上什么东西，交换桌上的🔑，把🔞放到桌上(覆盖之前有的东西)

  • resume the world

  • 期间看到🔑才能进厕所包厢

• 出厕所以后，

  • 把🔑放回桌上

代表可以进入厕所的钥匙只有 1 把，即进入临界区的变量只有 1 个，那么这个事情就是可以实现的。我们只用一个共享内存，用原子交换的方式实现互斥。而且正确性很显然。

所有的 xchg 都会排好顺序，第一个执行 xchg 成功进入临界区，这个锁的名字就是自旋锁，无法进去临界区的线程在一直自旋空转。

int table = YES;

void lock() {
retry:
  int got = xchg(&table, NOPE);
  if (got == NOPE)
    goto retry;
  assert(got == YES);
}

void unlock() {
  xchg(&table, YES);  // 为什么不是 table = YES; ?
}

如果在 unlock 之前这个线程发生了 crash，那么久坏了，死锁了，或者unlock之前发生返回了，钥匙永远的消失了，这是一种非常常见的死锁的方式。关于锁未释放引发的bug，我们偶尔也可以喜欢一次C++，他的RAII机制，使得在返回时的析构函数里自动释放。

因为我们的假设，要保证 lock 和 unlock 在任何情况下都要正确。

再来回顾在 xchg 的假设

• 包含一个原子指令

• 包含一个compiler barrier

• 包含一个memory barrier

一个真实的自旋锁的代码

int locked = 0;

void lock() {
  while (xchg(&locked, 1));
}

void unlock() {
  xchg(&locked, 0);
}

通常，读代码的话，遇到的这种代码。如果初次学习遇到的是这个代码，那么会花许多时间理解。但是上面进厕所的例子却是个很自然的想法。这个代码不那么好读了，但是和上面是等价的，需要在脑子里做翻译，0 代表没上锁，1 代表上锁。

• 上锁：用已上锁1和锁做交换，如果得到的是已上锁，那么就自旋

• 解锁：用0和锁交换

只要锁加的正确，在写并发程序的时候我们就不用处处小心，优化了以后也可以正确的运行。这就是操作系统里面要用到的自旋锁。就这这么简单。

无锁算法 cmpxchg

xchg 是一个比较简单的协议，实际上还有更强大的原子指令，cmpxchg，

• (lock) cmpxchg SRC, DEST

int cmpxchg_ref(int old, int new, int volatile *ptr)
{
  int tmp = *ptr;
  if (tmp == old)
  {
    *ptr = new;
  }
  return tmp;
}

行为看起来没复杂多少，好像又复杂了很多。

这条指令多出来的 compare 的用处，

并发修改链表

操作系统上使用互斥锁

我们正确的用自旋锁实现了互斥算法。但是，可以感觉到性能可能会有点小问题。

自旋锁的缺陷

• 自旋(共享变量)会触发处理期间的缓存同步，延迟增加

• 除了进入临界区的线程，其他处理器上的线程都在空转

  • 争抢锁的处理器越多，利用率越低

    • 4 个 CPU 运行 4 个 sum-spinlock 和 1 个 OBS

    • 任意时刻都只有一个 sum-atomic 在有效计算

    • 均分 CPU, OBS 就分不到 100% 的 CPU 了

• 持有自旋锁的线程可能被操作系统切换出去

  • 操作系统不 “感知” 线程在做什么，拿着钥匙回去睡觉了，其他人在等着上班

  • (但为什么不能呢？)

  • 实现 100% 的资源浪费

衡量程序的性能，时间和空间，算的快省内存。此外并发编程评价好坏，scalability，伸缩性，随着CPU或者线程的数量变化，运行的时间和内存会有什么样的变化？

有些程序，并行了的效率还不如不并行，参考教材，并发带来的性能问题。一个原因是现代的多处理器都是有缓存的，我们 sum++ 的时候并不是真的读写到 DDR 里，所以多处理器读写共享变量的时候，要从另一个 CPU 上拉 chche，这个过程要时间。

当然，自旋锁到今天，仍然也有他的使用场景，需要满足一些条件:

• 临界区几乎不拥堵。不会发生锁的争抢，几乎只有一个线程进入临界区。

  • 比如一个队列，去用几个ns，算用几个ms

• 持有自旋锁时禁止执行流切换

  • 但是应用程序做不到，如果可以，意味着写个while(1) 就能卡死cpu

自旋锁是在多处理器上实现互斥的唯一方法，关中断也可以实现临界区但只能关当前CPU的中断，关其它CPU的中断不是合理的设计，。

因此，使用场景：操作系统内核的并发数据结构(短临界区)，操作系统可以决定不要切换，中断也不要来。

• 操作系统可以关闭中断和抢占

  • 保证锁的持有者在很短时间内可以释放

• 有时候这个中断并不是真的关掉了，比如虚拟机，

如 fork 一个新进程，插入链表的时候。这也基本上是自旋锁唯一的使用场景。

自旋锁的使用是个很大的难题，在2010年还可以发一篇计算机的顶会，OSDI，来说linux的自旋锁使用的有多烂。

在实际的应用场景里，我们有这样的需求，在临界区里 printf，或者写一个文件，别人不要写这个文件。即长临界区的互斥。

这是个很自然的需求，显然不能做自旋锁，如果要打印到串口，那比文件IO还要慢，这是电路上决定的。那该怎么办呢？与其干等着上厕所，不如先去吃个饭，回来再看看厕所门的钥匙在不在桌上。

线程把自旋改成让出CPU，但是“让”不是C语言代码本身可以做到的事情，代码本身只能运算。只能请求操作系统帮忙挂起自己

对于linux的线程来说，想实现长临界区的互斥很简单，加一个系统调用就好了。把锁的实现放到系统调用里

• syscal(SYSCALL_lock, &lk)

  • 试图获得 lk，但如果失败，就切换其他线程

• syscal(SYSCALL_unlock, &lk)

  • 释放 lk，如果有等待的线程就唤醒线程

操作系统就是更衣室的管理管

• 先到的人(线程)

  • 成功获得手环，进入游泳馆

  • *lk = 🔒 系统调用直接返回

• 后到的人

  • 不能进入游泳馆，排队等待

  • 线程放入等待队列，执行线程切换

• 洗完澡出来的人

  • 交换手环到管理员，管理员把手环给排队的人

  • 等待队列有人，取出一个线程允许执行

  • 等待队列为空，*lk = ⚪

管理员使用自旋锁确保自己处理手环是原子的。

互斥的一些讨论

自旋锁有个好处，快的时候很快

• 更快的 fast path

  • 一条指令就进入了，开销小

• 更慢的 slow path

  • xchg 不停交换没用的东西，浪费CPU自选等待

睡眠锁

• 更快的 slow path

  • 上锁失败线程不再占用CPU

• 更慢的fast path

  • 上锁成功也需要进出内核

我们又想快的时候一条指令进入，又不想进系统调用，该怎么办呢？

Futex = Spin + Mutex

Futex

• fast path 一条原子指令，上锁成功立即返回

• slow path 上锁失败，执行系统调用睡眠

  • 这也是性能优化最常见的技巧

问题求解课，性能优化。 

POSIX 线程库中的互斥锁，(pthread_mutex)

• 观察系统调用strace