并发编程网 - ifeve.com

原文链接，译文链接，译者：Noodles，校对：周可人

1.1.3 非阻塞技术

正如前面讨论的那样，非阻塞实现主要目的是为了消除由锁带来的相关问题，为了形式化研究这一概念，多种非阻塞演进条件已经在相关文献有所研究了，如wait-freedom演进条件，lock-freedom演进条件，和obstruction-freedom演进条件。满足wait-free演进条件的操作是指在执行自身包含的有限步骤之后，保证操作必须完成，而不用考虑其他操作发生的时序，满足lock-free演进条件的操作是指在执行自身包含的有限步骤之后，保证某些操作完成。满足obstruction-free演进条件的操作是指在不受其他操作干扰的情况下，执行它包含的有限步骤之后，保证其完成。

显然，wait-freedom是比lock-freedom强的演进条件，lock-freedom又比obstruction-freedom强。 但是，这三者都比以前那些使用像锁这样的阻塞构造的演进条件要强。虽然越强的演进条件看上去是可取的，但是通常来说，保证越弱的演进条件，实现起来越简单，效率更高，且更容易设计和验证。实际上，我们可以采用回退技术或者是精密的冲突管理技术对弱演进条件进行补偿。

图 1.2  CAS 操作的语义

回到共享计数器的例子中，从Fiesher的研究结果中（被Herlihy，Loui和Abu-Amara扩展到共享内存上），我们可以得出，一个共享计数器不能通过仅仅使用load和store指令来访问内存的来达到lock-free。上述研究结果表明，现有提议的实现中，一些异常的交叉操作可能导致不正确的结果。这些（异常的）交叉操作大多是是由于load和store是相互独立所引起的。这个问题可以通过将load和store指令合并为一个原子的硬件指令来解决。事实上，所有现代的多核处理器都提供了这样的同步指令，最常见的是compare-and-swap（CAS）和load-linked/store-conditional(LL/SC)。CAS指令的语义可见图1.2。为了说明问题，我们假定被atomically关键字标记的代码块必须原子性的执行，也即是说，其他线程看不到代码块执行的中间状态。CAS操作原子性地完成以下操作序列：从某个内存地址中加载，将所读的值和期望值对比，如果比较成功，那么将新的值写入到该内存地址。Herlihy[49]指出像CAS和LL/SC这样的指令是通用的：对于一个支持这样指令的系统，任意的并发数据结构都存在wait-free的实现方式。

一个简单的lock-free计数器可以通过CAS操作来实现。思路是这样实现fetch-and-inc：首先加载计数器的值，然后通过CAS操作来原子地将计数器的值改变为一个比加载值大1的值。CAS指令只有在加载和CAS操作之间，值发生改变的时候才无法增加计数器。对于这种情况，（操作）可以采取重试，（因为）由此导致的CAS失败不会造成影响。该实现属于lock-free方式，因为CAS会因为其他fetch-and-inc操作的成功而失败。但这不属于wait-free方式，因为单个fetch-and-inc操作可能在其CAS时会不断失败。

上面的例子介绍了一个对同步的乐观方案：fetch-and-inc操作在期望的大多数情况下，不会和其他并发操作产生冲突，从而快速地完成。但是，一旦出现资源竞争，则需要采用复杂的技术来解决(例如：回退)。

虽然上述的lock-free计数器是容易实现的，但是它有着和那些通过锁来实现的原始计数器相同的缺点：串行瓶颈和单点资源高竞争。人们很自然地会想到使用上面所讨论的类似的实现来改善这个简单实现的性能。但是通常情况下，优化一个非阻塞实现比优化一个阻塞实现难一些。简略来说，这是因为一个线程在执行序列操作的时候，可以通过锁来阻止其他线程的干扰，如果不用锁，那么我们的实现需要保证即使存在并发操作，结果仍然是正确的；在当前的系统架构中，这通常需要使用复杂和耗时的技术，而这样做会削弱我们对无锁并发的改进。在1.1.7节中，我们将深入讨论事务性内存技术，事务性内存使得设计和实现复杂的并发数据结构变得简单。但是，支持这一机制的硬件还不存在（译者注：当时不存在，在Intel Haswell上已经引入这一新技术了[1]）。

参考资料：

[1] http://software.intel.com/en-us/blogs/2012/02/07/transactional-synchronization-in-haswell