10.5　锁的问题及对策

锁的问题

即便是使用上变得如此简便的锁，也还面临一些难题。

陷入死锁

假设有 A 和 B 两个作业，它们都能修改 X 和 Y 两个变量。A 按照先锁住 X 再锁住 Y 的顺序上锁，B 按照先锁住 Y 再锁住 X 的顺序上锁，在某些时间点有可能会产生问题。比如在 A 锁住了 X 的同时 B 又锁住了 Y，双方都会等待对方释放解锁。

这一现象叫做死锁。为了避免这一问题，程序员就需要在程序的整体上注意上锁的顺序，不仅要把握应该对什么上锁，还要把握好按什么顺序去上锁。

无法组合

另外，锁还有无法组合这一个问题。比如要从列表 X 中删除第一个值然后追加到另一个列表 Y 中，我们考虑下如何实现这个处理（图 10.1）。假设我们希望把整个处理作为一个完整不可分（原子性地）的过程执行。也就是说，在将从 X 删除的值到写入 Y 中的中间状态时，其他处理无法访问列表 X 和 Y。这种情况下该上什么样的锁呢？

图 10.1　完整不可分的处理

在线程安全的程序库中，程序员无需担心锁的控制方式，内部机制可以保证使用锁后删除操作或写入操作不会被中间介入 12。但这个锁无法保证将从 X 删除值往 Y 中写入时不会被中间介入。要防止中间介入，程序员必须用新的锁将这两个处理步骤包括起来，用 synchronized lock 把所有这些与 X 和 Y 读写相关的代码包括起来。这样就没能达到让程序员无需担心锁的控制方式的目的。那没有其他好方法了吗？

12也有不使用锁且线程安全的程序库，要展开来讲话题就变复杂，这里进行简单化处理。

借助事务内存来解决

有一种叫做事务内存的方法可以解决这一问题 13。这种方法把数据库中事务的理念运用到内存上，做法是先试着执行，如果失败则回退到最初状态重新执行，如果成功则共享这一变更（图 10.2）。它不是直接修改 X 或 Y，而是临时性地创建了一个版本对其进行修改，将一个完整不可分的过程执行完毕后才反映出最终的成果。

13Tim Harris, et al.“Composable Memory Transactions”, 2006. http://research.microsoft.com/pubs/67418/2005-ppopp-composable.pdf.

如果这个也拿试衣间来类比，情况就变得很奇怪了 14。我们还是借之前的例子来进一步说明。在这两个处理的中间状态，如果有其他线程的读取要中间介入进来将会怎样呢？答案是即使有别的处理要介入进来，也只是创建了另一个临时的版本，对其作的修改不会反映到原来的数据上，在其他的线程看来数据的状态还是和执行 X 删除操作之前一样。这样就不存在任何问题。

14如果硬要把它类比为试衣间那个例子，这个故事就变成：并行地存在进入试衣间的世界和没有进入试衣间的世界这样两个世界，当尝试进入试衣间有问题时，会折返到没有进入试衣间的世界中。这样的说法是完全没有现实意义的，当然这个可以在计算机世界中进行仿真。

图 10.2　创建另外的版本然后修改，处理结束后反映最终结果

假设有写入操作在中间介入进来（图 10.3），那么临时创建的版本就会被丢弃，重新回退到最初状态开始执行。这样一来，即使不上锁也可以顺利地进行并发处理。要注意的是，当写入的频率太高时，回退重 新执行的操作就会多次执行到，这样会导致性能下降。

图 10.3　如果遇到别的写入操作介入则重新执行

事务内存的历史

硬件事务内存

1986 年，一家名为 Symbolics 的公司提出基于硬件实现的事务 15。这家公司在 1981 年开始提供在硬件中安装了 LISP 语言的商用 LISP 机器——LM-2.

15Tom Knight,“ An Architecture for Mostly Functional Language”, 1986.

1986 年也是名为 MIPS R2000 的 CPU 诞生的一年。MIPS 是基于 RISC（Reduced Instruction Set Computer）这种旨在减少命令个数简化线路的设计方针制作出来的 CPU。它和在硬件中实现 LISP 语言或事务这一方针相悖而行。个中原因非常复杂，最终，Symbolics 在商业上也并未取得成功。

软件事务内存

在 10 后的 1995 年，一篇关于如何在软件中实现事务内存的论文发表了 {16[Nir Shavit, Dan Touitou, "Software transactional memory", 1995. ]}。

又一个 10 年之后，微软公司于 2005 年发表了一篇关于使用 Concurrent Haskell 在软件中实现事务内存的论文 17。

17Tim Harris, et al,“Composable Memory Transactions”, 2006. http://research.microsoft.com/pubs/67418/2005-ppopp-composable.pdf

在此前后的几年间，很多编程语言都实现了软件事务内存的功能。比如，2004 年 IBM 公司开发的 X10 和 2006 年 Sun Microsystems 公司开发的 Fortress 中都实现了这个功能。2007 年，基于 Java VM 的 Clojure 发布。现在已经有一些介绍它的图书出版。

事务内存成功吗

事务内存这一技术在将来值得期待吗？未来会怎样没人知道。微软公司于 2010 年中止了面向 .NET Framework 平台搭载软件事务内存的实验。这么做的理由众说纷纭，但是认为能用到软件事务内存的杀手级应用缺失这样的悲观意见有很多 18。

18“A (brief) retrospect on transactional memory”, http://www.bluebytesoftware.com/blog/2010/01/03/ABriefRetrospectOnTransactionalMemory.aspx.

另外，据说后续的 Intel 处理器将搭载事物内存的部分功能。如若实现，届时对于硬件事务内存就可以轻松一试了。至于今后将如何进一步发展，我们只能拭目以待。