Sorry, your browser cannot access this site
This page requires browser support (enable) JavaScript
Learn more >

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

最近两天先写点基础的, 这两天在看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

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

感性理解:

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

感性理解正确性:

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

一些思考:

  1. 能不能先改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:

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

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

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

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

自旋锁的缺陷

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

自旋锁的使用场景

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

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

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

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

Lock指令

x86的lock

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

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

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

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

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

RISC-V的另一种lock实现

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

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

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

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

互斥锁 (Mutex)

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

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

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

操作系统的操作:

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

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

Futex

自旋锁的两种情况:

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

Mutex的两种情况:

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

Fast Userspace muTexes (Futex) 的折衷:

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

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

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

评论