[操作系统]6. 并发控制基础

[supergem3000]

6. 并发控制基础 (jyywiki.cn)

互斥问题

人类是sequential creature，编译优化+weak memory model导致难以理解的并发执行。 手段：“回退到”顺序执行。 插入神秘代码，使得所有其他神秘代码都不能并发。

void Tsum() {
stop_the_world();
// 临界区 critical section
sum++;
resume_the_world();
}

都不能并发了，那多处理器的意义是什么？实际上临界区代码是可能访问共享内存的代码，多数代码是不需要访问共享内存的。

失败的尝试

int locked = UNLOCK;

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

和山寨支付宝一样的错误，不能保证load + store操作原子性。 更严肃的尝试 假设：内存的读/写可以保证顺序、原子完成。 val = atomic_load(ptr)

• 看一眼某个地方的字条（只能看到瞬间的字）。
• 刚看完就可能被改掉。看到的值只是看的当时的值，信息可能滞后。 atomic_store(ptr, val)
• 往某个地方“贴一张纸条”（必须闭眼盲贴）。
• 贴完一瞬间就可能被覆盖。

  Peterson算法

  A 和 B 争用厕所的包厢：

  1. 想进入包厢之前，A/B 都首先举起自己的旗子
  2. A 往厕所门上贴上 “B 正在使用” 的标签；B 往厕所门上贴上 “A 正在使用” 的标签
  3. 如果对方举着旗，且门上的名字是对方，等待。否则可以进入包厢。
  4. 出包厢后，放下自己的旗子 (完全不管门上的标签)。

     如何理解Peterson算法？ 如何更好理解Peterson算法？ - 知乎 (zhihu.com) Peterson算法 - 维基百科，自由的百科全书 (wikipedia.org)

回到前文的假设：Atomic load/store。但这个假设在现代多处理器上并不成立。那么Peterson算法是错的吗？合理需求一定能实现。 Compiler barrier/volatile保证不被优化的前提下：

• 处理器提供特殊指令保证可见性
• 编译器提供__sync_synchronize()函数 想要实现load/store的原子性，仅靠编译器是做不到的，一定要靠编译器和处理器一起努力才能达到。

  原子指令

  普通的变量读写在编译器+处理器的双重优化下行为变得复杂。 解决方法：编译器和硬件共同提供不可优化、不可打断的指令。 实现正确的求和：Bus lock

  for (int i = 0; i < N; i++) {
  asm volatile("lock incq %0" : "+m"(sum));
  }

[supergem3000]

对课程视频中实现Peterson算法代码，使用了__sync_synchronize()让读写操作原子，视频评论区一位同学的看法：