https://jyywiki.cn/OS/2023/build/lect6.ipynb

互斥问题

并发编程：从入门到放弃

人类是 sequential creature

• 编译优化 + weak memory model 导致难以理解的并发执行
• 有多难理解呢？
  • Verifying sequential consistency 是 NP-完全问题

人类是 (不轻言放弃的) sequential creature

• 有问题，就会试着去解决
• 手段：“回退到” 顺序执行
  • 标记若干块代码，使得这些代码一定能按某个顺序执行
  • 例如，我们可以安全地在块里记录执行的顺序

回退到顺序执行：互斥

插入 “神秘代码”，使得所有其他 “神秘代码” 都不能并发

• 由 “神秘代码” 领导不会并发的代码 (例如 pure functions) 执行

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

Stop the world 真的是可能的

• Java 有 “stop the world GC”
• 单个处理器可以关闭中断
• 多个处理器也可以发送核间中断

失败的尝试

int locked = UNLOCK;

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

  // critical section

  locked = UNLOCK;
}