本文我们会回顾前几期讲过的不同类型的自旋锁算法，做一个学习总结。

首先我们先讲了 TASLock （test-and-set）和TTASLock(test-test-and-set) 并且将它们做了比较。两者都保证了互斥，以及无死锁。还讲到了指数后退锁。

TASLock 的缺点：

TAS 会导致CPU缓存失效。
每个自旋线程会发生 cache miss ，然后频繁占用系统总线。
其他操作会因为总线被占用而导致延迟。

TTASLock 的优势：

在CPU本地缓存的数据上自旋读取。
当锁被占用状态时不会去占用系统总线。

TTASLock 的缺点：

当释放锁的时候会引发总线流量风暴。

BackoffLock

BackoffLock 为了解决大量线程争用同一个锁的问题，争用过高的情况下每个参与争抢的线程获得锁的机会都很小，但是对系统的开销却很大。举一个生活中的例子就是很多人同时上公交车，期望能进入到公交车中。为了降低争用BackoffLock 使用的办法是让尝试获取锁没有成功的线程“后退”（其实也可以理解为暂停等待）一段时间之后，再去尝试获取锁，由此来降低争用。

BackoffLock 的优势：

实现起来比较简单。
性能要比 TTASLock 好。

BackoffLock 的缺点：

“后退”参数的设置要小心设置，根据机器的不同。
难以移植跨平台，不同的机器需要调整不同的“后退”参数。

在讲队列自旋锁的时候我们讨论了 ALock , CLHLock , MSCLock 以及时限队列锁（TOLock）。

队列自旋锁的优势是：

每个线程都在不同的存储单元上自旋，降低了cache一致性流量。
而且提高了临界区的利用率，也就是降低了争用，前一个节点在退出临界区后会主动通知后一个节点的线程。

ALock 的优势：

一个真正可扩展的锁。
简单而且较比容易实现。
保证了先到先服务（First-Come-First-Served）的公平性。
性能优于 TTASLock。

ALock 的缺点：

占用太多空间。每个线程都要占用一个单独的存储空间，O(LN)。
存在虚假共享的现象，需要在共享的 flag[] 数组之间填充 cache line 占用位。

CLHLock 的优势：

需要的空间比 ALock 要小，O(L+N) 。
保证了先到先服务（First-Come-First-Served）的公平性。
每个线程的开销都很小。

PS: L 表示锁的数量，N 表示线程的数量。

MCSLock 的优势：

保障了先到先服务的公平性。
每个线程都在自己CPU cache 上自旋。
线程固定很小的开销。

TOLock

TOLock具有CLHLock的大多数优点：在缓存的存储单元上进行本地自旋以及对锁空闲的快速检测。它也具有BackoffLock的无等待超时特性。然而，该锁也存在缺点，包括每次锁访问都需要分配一个新的节点以及在锁上自旋的线程在访问临界区之前有可能不得不回溯一个超时节点链条。

TTASLock 归功于 Clyde Kruskal , Larry Rudolph , Marc Snir。

指数后退是以太网路由技术中的著名技术，该技术是由　Anant Agarwal , Mathews Cherian 在多处理器互斥上下文中提出的。

Tom Anderson 发明了 ALock 算，他也是最早在共享存储器多处理器上进行自旋锁性能试验的研究人员之一。

MCSLock 是由 John Mellor Crummery 和 Michael Scott 发明，这可能是最著名的队列锁算法。

目前 Java 虚拟机采用了基于简化的监控算法的对象同步，如由 David Bacon ，Ravi Konuru ,Chet Murthy , Mauricio Serrano 所提出的ThinLock,由 Ole Agesen , Dave Detlefs , Alex Garthwaite , Ross Knippel , Y.S.Ramakrishna , Derek White 所提出的 Metalock, 以及由 Dave Dice 提出的 RelaxedLock。所有这些算法都是 MSCLock 算法的变种。

CLHLock 算法归功于 Travis Craig , Erik Hagersten , Anders Landin 。

无阻塞时限锁 TOLock 归功于Bill Scherer , Michael Scott 。

CompositeLock 及其变种由 Virendra Marathe , Mark Moir , Nir Shavit 提出。

在互斥中使用快速路径思路由Leslie Lamport 提出。

层次锁由Zoran Radovic , Erik Hagersten 提出。

HCLHLock 由Victor Luchangco , Daniel Nussbaum , Nir Shavit 提出。

Danny Hendler , Faith Fich , Nir Shavit 扩展了 Jim Burns , Nancy Lynch 的工作，证明了任何一种无饥饿互斥算法，即使采用类似 getAndSet() 或 compareAndSet() 这样的强操作，都需要 Ω(n) 的空间，这意味着我们之前讨论的队列锁算法都是空间最优的。