Yanyan's Wiki 软件工程研究入门 (2022)

本周阅读材料

教科书

教科书 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.csum.cmem-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 的 (这个基本是课后习题难度):

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

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

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

Creative Commons License    苏 ICP 备 2020049101 号