锁的开销锁的开销是巨大的，特别是对于多核多处理来讲。
引入多处理，本身就是为了将并行化处理以提高性能，然而由于存在共享临界区，而这个临界区同时只能有一个线程访问(特别是对于写操作)，那么本来并行的执行流在这里被串行化了，形象地看，这里好像是宽阔马路上的一个瓶颈，由于串行化是本质上存在的，因此该瓶颈就是不可消除的。问题是线程执行流如何度过这个瓶颈，很显然，它们谁都绕不开，现在问题是是它们到达这个瓶颈时该怎么办。
很显然，斗殴抢先是一种不合理但实用的简单方案，朴素的自旋锁就是这么设计的。然而，更加绅士的做法就是，既然暂时得不到通行权，那么自己先让出道路，sleep一会儿，这种方式就是sleep-wait方式，与之对应的就是持续spin-wait方式。问题是线程本身如何对这二者做出明智的选择。事实上，这种选择权交给了程序，而不是执行中的线程。
不要试图比较sleep-wait和spin-wait的性能，它们都是损耗了性能-因为串行化。其中，sleep-wait的开销在切换(涉及到进程，线程的切换比较，比如寄存器上下文，堆栈，某些处理器上cache刷新，MMU tlb刷新等)，而spin-wait的开销很显然，就是持续浪费CPU周期，虽然没有切换的开销，但事实上，它这段时间什么也做不了。
为什么要引入spin-wait这种方式呢？因为如果始终是sleep-wait，那么sleep线程A切换到别的线程B后，锁被释放了，系统不一定能保证sleep的那个线程可以获得CPU从而切回来，即便如此，付出巨大的切换代价，有时间隔很短，线程B并没有由于线程A的绅士行为获得收益，这种姿态显然是不值得的，还不如保留本质，持续斗殴。
和中断相比，锁的开销更加巨大，如果可以通过关中断的方式换取无锁操作，那么这是值得的，但是(最讨厌且永恒的“但是”)，你要考虑关中断的副作用，比如增加了处理延迟，然后你必须拿这种新的代价和锁的开销进行对比，权衡这种交易是否值得。
要开始本文了，为了简便起见，我不会给出太多的和处理器相关的细节，而是集中针对自旋锁本身。这些细节比如CPU cache机制，缓存一致性协议，内存屏障，Intel的pause指令，流水线，总线锁等，还好，这些概念都是可以很方便baidu出来的，不用去墙外。
关于自旋锁
Linux内核一开始就引入了自旋锁，所谓的自旋锁在等待锁过程中的行为就是原地打转，有人会觉得这浪费了CPU周期，但是你要明白，系统设计就是一场博弈，虽然不是零和，但是也要尽力寻找折中点，然而却没有两全其美的方案。
如果不原地打转，又该如何呢？很显然就是切换到别的线程，等待持锁者释放锁的时候，再将它唤醒，然而这里又有两次斗殴，首先，如果有多方都竞争一个锁，那么全部将它们唤醒，提供一个斗殴场地，等待一个胜出吗？退而求其次，即便仅仅唤醒首先排队的那个线程，task切换的开销算进去了吗？所以说，如果原地打转浪费的CPU周期小于两次切换开销浪费的CPU周期，那么原地打转就是合理的，这么说来，原地打转的时间越短越好。
就是如此。自旋锁的应用场合就是短时间持有临界区的场合，它是一种短期锁，如果占据临界区过久，随着原地打转浪费的CPU周期的增加，其开销将逐渐大于两次切换(切换开销是固定的-不考虑cache等)，因此，理论上，能算出自旋锁在持锁期间可以执行多少代码。爆炸！
Linux自旋锁历史概览Linux自旋锁发展了两代，第一代自旋锁是一种完全斗殴模式的无序自旋锁，也就是说，如果多个CPU同时争抢一个自旋锁，那么待持锁者解锁的时候，理论上它们获得锁的机会是不固定的，和cache等一系列因素相关，这就造成了不公平，第一个开始争抢的CPU不一定第一个获得…这就需要引入一个秩序，于是第二代Ticket自旋锁就设计出来了。
Ticket自旋锁的设计非常巧妙，它将一个CPU变量，比如32位的值分为高16位和低16位，每次lock的时候，CPU将高16位原子加上0x01(通过锁总线)，然后将该值和低16位比较，如果相等则成功，如果不等则自旋的同时持续比较这两个值，而unlock操作则是简单递增锁的低16位加0x01(理论上不需要锁总线，因为不会有两个及以上的CPU同时拥有锁进行unlock操作，但是还是要考虑CPU的特性…)。这就是所谓的Ticket自旋锁的全部。
最近遇到了锁优化的问题，众所周知，锁优化是一个很精细的活儿，它既不能太复杂也不能太简单，特别是自旋锁的设计，更是如此。然而自旋锁设计的优势也很明显，那就是它让你少考虑很多问题：
1.一个CPU同时只能在一个自旋锁上自旋；
2.一旦开始自旋，直到获得锁，中间不能放弃退出自旋。
自旋锁的应用场合必须要明了，它不适合保护很大的临界区，因为这将导致自旋过久，它也不适合大量CPU的情况，因为它会导致自旋延时的N倍，虽然一段临界区很小，但是一个CPU自旋的时间可能是N倍，N为CPU的数量。这就引出了一个争论，Ticket排队自旋锁真的比斗殴型哄抢自旋锁好吗？如果不考虑cache亲和，斗殴型的自旋锁可以将每个CPU自旋的时间收敛到平均时间，而Ticket自旋锁将出现两极分化，也就是说，最长自旋时间和最短自旋时间是一个固定的倍数关系，，随着CPU数量的增加，排队公平导致的不合理性将加大，你要知道，任何情况下队列都不可能超过一个临界值，超过了不满情绪将会增加，虽然这种长延时只是因为你来得晚导致的，看似很公平，实际上并不公平，因为并不清楚你来得晚的原因。
目前没有一种好的方案解决这个问题，一般情况，如果队列过长，工作人员会建议你一会儿再来看看，或者贴上大致的预估时间，你自己来绝对是排队还是放弃。
try lock返回的预估信息我建议在自旋锁加锁前，先try lock一次，正如现如今的实现一样，然而这个try并没有给出除了成功或者失败之外的信息，事实上更好的方式是，try，并且try返回一些有用的信息，比如等待预估时间，队长等统计信息，以供调用者决定是就地自旋还是干点别的。谁说内核中不能做大数据分析，很多统计信息和建议都可以通过数据分析得到。
此外，对于该统计信息，可以对spin操作本身进行优化，就是说，内部的pause指令可以进行优化，这对流水线是有益的。
我的自旋锁设计
为什么我要设计一个新的自旋锁，一方面是我觉得Ticket自旋锁多个CPU虽然靠递增高位实现了排队，但是它们同时不断地检测自旋锁本身的值，cache有点浪费，所有的CPU cache上均会出现完全一样的自旋锁，并且一旦锁被unlock，还会触发cache一致性协议行为，另一方面，我觉得用一个32位(或者随便其它什么CPU内部类型)分为高低两部分来实现自旋锁虽然巧妙但是又过于简单，第三方面，我前些日子特别推崇小巧结构体实现的IP转发表，如今又重温更加小巧的Ticket自旋锁，心里总是有些嫉妒，所以怎么也得按照我的思路来一个”符合我的观念的“设计吧，事情就是这么开始的。
在per CPU结构体上自旋如何解决线程间同步问题，这个问题确实不好解决，但是自己管自己，也就是操作本地数据，总是一个合理的思路。
当爱丽思丢失了通往仙境的钥匙，
