本周阅读材料
教科书
教科书 Operating Systems: Three Easy Pieces:
- 第 25 章 - Dialogue on Concurrency
- 第 26 章 - Concurrency and Threads
- 第 27 章 - Thread API
阅读理解示例代码
- thread.h 给了大家多线程编程的一个起点
- 它使用起来极为简单，例如 Hello World 的例子
- 用它可以做很多有趣的实验，例如 shm-test 测试共享内存、stack-probe.c 测试栈的大小。扩展并调试 (gdb 可以调试！) 这些样例程序能用实际经验解开你对多线程程序的困惑——例如，我们栈上变量的指针能传递给另一个线程使用吗？
- 但简短的代码里又有一些有趣的处理，例如我们使用了
wrapper函数，使得所有创建的线程都是同一个入口地址，实现了函数调用的 type safety (我们可以处理fn接受不止一个参数的情形)，而 wrapper 的技巧会在实验中用到。读完这段代码，就可以去阅读 pthreads 线程库的手册了
- 那些导致并发程序行为难以理解的例子：alipay.c、sum.c、mem-ordering.c 里也有很多值得学习的地方，观看视频回放，也许就有你第一遍听课时没有留意的有趣细节
- 关于 Peterson 算法，peterson-barrier.c 展示了如何编写 lock-free 的程序。你应该感受到，并发编程 (尤其是无锁的并发编程) 对新手是很不友好的。我们并不要求大家掌握
- 更重要的是使用 model-checker.py 理解 Peterson 算法 (和其他互斥算法) 的状态空间，你当然不要错过试一试别的程序。确保你理解了我们如何用
yield这种优雅地方式避免从头开始写一个解释器。当然，这个玩具 model checker 有一个最重大的缺陷：执行效率低。不过对于几百个状态的程序来说，效率也不算是个大问题
手工模拟并发程序执行
状态机是贯穿整个课程的重要概念，它帮助我们给出 C 和语言语言代码的形式语义、探索并发程序的行为……这一点从概念上并不难，但只有你真正试着仔细观察并发程序的状态空间 (例如手工写出 Peterson 算法的状态机)，以及近距离观察 model checker 输出的结果，你才会有 “第一手” 的体验，包括一些额外可能的思考：
- 如何使你画状态机时不显得那么累？例如，一个好的想法是在每一个状态迁移的时候，都直接在边上标记出 PC 的变化，这样就更容易对照代码执行程序
- 如何修改状态机模型，使得我们能够模拟宽松内存模型的行为？
- 状态空间中有相当多的 “重复” 和 “看似无意义的探索”。应该如何刻画这些重复？
- 如果我们想展示状态空间中最重要的那一部分，又应该怎么做？
实际上，这些已经是远远超过教科书的研究问题了！也许你在你模拟状态机执行的过程中，不由自主地就会问出这些非常有深度的问题，并产生一些自己的思考。所以，试着自己独立完成一个不 trivial 算法的证明，例如颇有挑战性的 dekker.py。此时你会被迫思考如何缩减程序的状态、理出程序的头绪 (就像我们在介绍 Peterson 算法时用了一个直观的比喻)。
并发编程：思考
并发超出了一般人类对这个世界的基础认识。我们即便假设所有的内存访问都是原子的 (被 __sync_synchronize() 包围)，根据每个线程读/写的数值恢复出一个全局的内存访问顺序也是 NP-Complete 的 (这个基本是课后习题难度)：
- The complexity of sequential consistency (SPDP'92)
这也意味着，并发程序的复杂性从根本上来说对人类是 “失控” 的。但从另一个角度，人类有在另外一个维度解决这个问题的 (工程) 办法：
某种程度上说，这是我们和现实世界复杂性的妥协。例如，在并发编程时总是使用线程池、队列、Map-Reduce 等容易理解的并发编程工具。此外，人类还发明了很多工具来帮助我们理解并发程序，model checker 就是其中之一。OSTEP 推荐了 helgrind: 基于 Valgrind 实现的并发错误检测工具；与它类似的有 ThreadSanitizer。你可以试一试，如果用 helgrind 检查我们的示例代码会发生什么？为什么？
