【NJU OS】03 多处理器编程

并发的基本单位：线程

共享内存的多个执行流

执行流拥有独立的堆栈/寄存器
共享全部的内存 (指针可以互相引用)
用状态机的视角就很容易理解了！

• 放弃 (1)：原子性
• 放弃 (2)：顺序
• 放弃 (3)：可见性

并发编程：思考

并发超出了一般人类对这个世界的基础认识。我们即便假设所有的内存访问都是原子的 (被 __sync_synchronize() 包围)，根据每个线程读/写的数值恢复出一个全局的内存访问顺序也是 NP-Complete 的 (这个基本是课后习题难度)：

• The complexity of sequential consistency (SPDP’92)

这也意味着，并发程序的复杂性从根本上来说对人类是 “失控” 的。但从另一个角度，人类有在另外一个维度解决这个问题的 (工程) 办法：

作出合适的抽象，并且只写自己能控制得了的代码。

某种程度上说，这是我们和现实世界复杂性的妥协。例如，在并发编程时总是使用线程池、队列、Map-Reduce 等容易理解的并发编程工具。此外，人类还发明了很多工具来帮助我们理解并发程序，model checker 就是其中之一。OSTEP 推荐了 helgrind: 基于 Valgrind 实现的并发错误检测工具；与它类似的有 ThreadSanitizer。