并发中的互斥

好家伙, 我已经三个多月没写东西啦!

最近两天先写点基础的, 这两天在看jyy的操作系统课和6.S081, 恶补一下操作系统的知识.

过几天写一下这个学期一直在研究的分布式系统, Raft啥的.

互斥

互斥就是禁止多个线程同时访问同一个资源, 这个资源叫做临界资源. 并行编程最大的几个问题之一是多个线程的执行流会被来回切换, 你永远想象不到一个线程会在什么时候被打断. 还有就是编译器, 现代处理器都会在不同级别上乱序执行, 不过这个也不是今天讨论的重点, 这个主要靠barrier去解决.

比如这样的:

int locked = UNLOCK;

void critical_section() {
retry:
  if (locked != UNLOCK) {
    goto retry;
  }
  locked = LOCK;

  // critical section

  locked = UNLOCK;
}

一个失败的锁的尝试, 多个线程可能同时判断到locked为unlock.

重点在于处理器不保证load+store的原子性

Peterson算法

Peterson算法实现了两个线程的互斥, 不需要任何复杂原子操作.

两个线程争夺临界区: 每个线程自己有个标志, 临界区有个标志turn

把自己的标志亮起来.
把临界区的标志turn改为对方.
如果对方的标志亮起来, 并且turn是对方, 就等待, 否则进入临界区.
出临界区, 熄灭自己的标志.

感性理解:

如果只有一个线程想要进入临界区, 那显然正确.
两个线程同时想要进入临界区, 两个线程都会把自己的标志亮起来, 并且去修改turn.
先修改turn的那个线程把turn改为了对方, 但是后面另一个线程会把自己的turn改回自己.
turn决定了到底谁进入临界区, 手快🈶️, 手慢🈚️.

感性理解正确性:

如果两个线程都想访问临界区, 但是一个线程A比较快, 把turn改为了对方:
1. 如果另一个线程B还没有亮起自己的标志, 那A就直接进了, 一会B亮标志再改turn的时候会因为turn被自己改成了A而阻塞, 直到A退出临界区, 灭掉了A的标志.
2. 如果另一个线程已经亮起了自己的标志, 那A会阻塞到B把turn改为A之后, A进入临界区, B同样会被阻塞.
也就是说, 因为大家都会把turn改为对方, 所以大家都会阻塞直到所有人都改了turn, 这时候就根据turn是谁决定谁进入临界区.

一些思考:

能不能先改turn, 再亮标志?
1. 肯定不行, 假如A先把turn改成了B, 然后因为这时候A没有亮标志, 所以B可以直接改turn为A+亮标志+进入临界区, 这时候A因为看到turn为自己, 也可以直接进入临界区, 就寄了.

Peterson算法属于比较一般的互斥算法, 只要内存模型是顺序一致的(Sequential Consistent), 就可以实现两个线程的互斥, 不需要任何复杂原子性的操作. 类似的算法还有dekker, 都比较复杂, 现代操作系统一般可以依赖于硬件实现的原子操作来简化互斥.

为了防止编译器和处理器在不同级别上的乱序优化, 可能需要在某些地方加不同级别的Barrier.

Model Checking

使用工具来检验模型的正确性!

其实就遍历多个线程状态机转移的每一种情况, bfs枚举.

可以使用python来模拟这个操作, 每一行语句后面加一个yield, 每一个线程包装成一个generator, 一次__next__() 就相当于一个线程执行了一步, 每一行都相当于一个原子操作.

现代软件自动化测试工具会加很多优化, 比如如果两个线程的某几步涉及到的内存完全不相关, 那他们这几步的顺序是无所谓的…诸如此类.

还可以用来检查filesystem的正确性, 和其他内存模型下的算法正确性…

锁

但是Peterson的假设太弱了, 没有任何复杂的原子操作, 只有load和store.

自旋锁是加了一个原子指令: lock.

互斥锁是增加了操作系统作为调度者.

Futex是结合了自旋锁和互斥锁的优点, 目前使用的Mutex很多都是Futex.

自旋锁 (Spinning Lock)

lock xchg %1, %2. 原子性的交换%1和%2.

实际上这就是一个load+store:

load了%1到%2.
Store了%2到%1.

如果一个有共享内存a, 0代表未上锁, 1代表上锁.

那么让b为1, xchg a, b, 检查a

如果b是1, 说明本来a本来就是1, 说明已经有人上过锁了, 返回xchg重试.
如果b是0, 说明本来a是0, 没有人上锁, 现在我们把a换成了1, 我们可以安心访问临界资源了.
从临界区退出后, 把a改回0.

自旋锁的缺陷

访问共享变量的自旋会出发多处理器之间的同步, 拖累性能.
一个线程抢占到锁之后, 其他处理器都在空转!
获得自旋锁的线程可能会被操作系统切换出去! 其他线程啥也别想干.

自旋锁的使用场景

临界区几乎不拥堵, 不太会出现多个线程抢占的情况.
持有自旋锁的时候可以禁止流切换, 但是一般的程序也没这个权利.

所以基本只有在操作系统内核中才会使用自旋锁:

操作系统可以关闭中断和抢占, 保证锁的持有者很快就会释放锁

但是即使这样也很难用好自旋锁.

Lock指令

x86的lock

在三十年前的80486时期就已经支持双路处理器, 支持lock了.

lock指令会保证, 在lock之前的所有store都已经写入内存.

在早期缓存是所有处理器共享的时候, 一个处理器执行lock指令时, 会把总线锁上, 这样其他处理就不会干扰他的原子操作.

但是现代处理器内部就有缓存, x86就要在L1级别的cache上保证一致性. 所有的L1 Cache都是串起来的, 一个处理器执行了原子性更改内存的操作, 需要更改所有出现这个块的缓存.

这也是x86背负的巨大历史包袱之一.

RISC-V的另一种lock实现

常见的原子操作基本都分为三步:

load.
exec, 即处理器自己在进行计算.
store.

RISC-V认为exec操作可以多次进行, 影响不大, 所以使用了Load-Reserved/Store-Conditional策略:

在执行原子操作前, 把需要影响到的内存打上Reserved标记.
如果计算期间有中断, 或者有其他处理器写入, 标记都会清除.
store时判断是否有标记, 没有标记就重试.

互斥锁 (Mutex)

互斥锁可以让没抢到锁的线程被操作系统阻塞, 操作系统可以去执行其他线程.

当然, 一般的用户程序也没这个权利, 所以互斥锁需要通过系统调用进入内核.

syscall(SYSCALL_lock, &lk); 尝试获取锁lk, 如果失败, 进入阻塞.
syscall(SYSCALL_unlock, &lk); 释放lk, 唤醒其他因为lk而阻塞的线程.

操作系统的操作:

先获取锁的线程, 得到锁, 操作系统让lk=1.
后获取锁的线程, 进入阻塞队列.
得到锁的线程释放锁后, 唤醒阻塞队列中的一个线程执行.
如果阻塞队列为空, lk=0;

操作系统使用自旋锁来保证自己的操作是原子的.

Futex

自旋锁的两种情况:

更快的fast path: xchg成功, 进入临界区, 开销很小.
更慢的slow path: xchg失败, 浪费资源自旋.

Mutex的两种情况:

更快的slow path: 上锁失败, 直接阻塞.
更慢的fast path: 无论如何都要进入内核.

Fast Userspace muTexes (Futex) 的折衷:

Fast path: 一条原子指令, 上锁成功直接返回.
Slow path: 上锁失败, 阻塞.

Linux大范围地使用Futex代替Mutex.

在FreeBSD, Linux中的Golang里的sync.Mutex, 实际上也是Futex.