第24章美丽的并发-北京大学数学科学学院.PDF

第 24 章 美丽的并发 Simon Peyton Jones 免费午餐已经结束[1]。以往我们习惯于通过购买新一代 CPU来加快程序的运行速 度，但现在，这样的好时光已经一去不复返了。虽说下一代芯片会带有多个 CPU， 但每个单独的 CPU的速度却不会再变快了。所以，如果想让程序跑得更快的话， 你就必须得学会编写并行程序[2]。 [1]Herb Sutter, The free lunch is over: a fundamental turn toward concurrency in software, Dr. Dobbs Journal, March 2005. [2]Herb Sutter and James Larus, Software and the concurrency revolution, ACM Queue, Vol. 3, No. 7, September 2005. 并行程序的执行是非确定性的，因而测试起来自然也就不容易；并发程序中有的 bug甚至可能会无法重现。我对漂亮程序的定义是“简单而优雅，乃至于显然没 有任何错误”，而不仅仅是“几乎没有任何明显的错误” [3] 。要想编写出能够可 靠运行的并行程序，程序的美感是尤其要注意的方面。可惜一般来说并行程序总 归没有它们相应的非并行（顺序式的）版本漂亮；尤其是在模块性方面：并行程 序的模块性相对较弱。这一点我们后面会看到。 [3]This turn of phrase is due to Tony Hoare. 本章将介绍软件事务内存（STM）。软件事务内存是一项很有前景的技术，它提 出了一种针对共享内存并行处理器编程的新手段，正如刚才所言，传统并行程序 的模块性较弱，而这正是软件事务内存的强项。我希望你读完本章后能和我一样 对这项新技术感到振奋。当然，软件事务内存也并非万灵药，但它的确对并发领 域中令人望而却步的问题发起了一次漂亮且令人鼓舞的冲击。 24.1 一个简单的例子：银行账户 假设有这样一个简单的编程任务： 编写一段程序，将钱从一个银行账户转移到另一个账户。为了简化起见，两个账 户都是存放在内存里面的——也就是说你不用考虑跟数据库的交互。要求是你的 代码在并发环境中也必须能够正确执行，这里所谓的并发环境也就是指可能存在 多个线程同时调用你的转账函数，而所谓能够正确执行则是指任何线程都不能 “看到”系统处于不一致的状态（比如看到其中一个账户显示已被取出了一笔钱 然而同时另一个账户却显示还没有收到这笔钱）。 这个例子虽说有点人为捏造的味道，但它的优点是简单，因而我们便能将注意力 集中在它的解决方案上，后面你会看到，Haskell结合事务内存将会给这个问题 带来新的解决方案。不过此前还是让我们先来简单回顾一下传统的方案。 24.1.1 加锁的银行账户 目前，用于协调并发程序的主导技术仍是锁和条件变量。在一门面向对象的语言 中，每个对象上都带有一个隐式的锁，而加锁则由 synchronized方法来完成， 但原理与经典的加锁解锁是一样的。在这样一门语言中，我们可以将银行账户类 定义成下面这样： class Account { Int balance; synchronized void withdraw( Int n ) { balance = balance - n; } void deposit( Int n ) { withdraw( -n ); } } withdraw方法必须是 synchronized的，这样两个线程同时调用它的时候才不会 把 balance减错了。synchronized关键字的效果就等同于先对当前账户对象加 锁，然后运行 withdraw方法，最后再对当前账户对象解锁。 有了这个类之后，我们再来编写 transfer转账函数： void transfer( Account from, Account to, Int amount ) { from.withdraw( amount ); to.deposit( amount ); } 对于非并发程序来说以上代码完全没问题，然而在并发环境中就不一样了，另一 个线程可能会看到转账操作的“中间状态”：即钱从一个账户内被取走了，而同 时另一个账户却还没收到这笔钱。值得注意的是，虽然 with