自旋锁的枝枝蔓蔓

近期在读《多处理器编程的艺术》一书，英文版的，最近发现技术类书籍中文翻译版的质量越来越差，译者很多都是单纯为了钱，其实他们在IT领域很多都是大白，因此还是看原汁原味的英文版吧，虽然吃点力，起码准确。我利用地铁上的时间读了自旋锁这一章，感觉很有收获。

自旋锁在单处理器非抢占OS上其实是没有意义的，只有在多处理器上才有意义，最简单的自旋锁就是乱抢的那种，可是所有的处理器上运行的线程都等待同一个变量，会导致所有的争抢锁的处理器的cache被刷新，因此设计者设计出一种新的自旋锁，每个线程自旋在本处理器的变量上，这样不会导致所有的处理器刷新缓存，该版本自旋锁的第一个实现就是array锁，然而array是静态分配大小的，如果争抢锁的线程很少，就会导致空间浪费，于是第二个实现就是队列锁，队列是按需动态扩展的，因此解决了第一个实现中的问题。虽然该种新的自旋锁避免了cache刷新，同时又防止了空间浪费，但是会导致饥饿问题，排在后面的争抢者可能会由于排队时间过长而损失其响应度，因此一种带有超时值的锁油运而生，这样就避免了自旋锁由于排队长期自旋，总之，只要排队自旋锁的队列过长，那么就有可能导致饥饿，那么有没有什么办法限制队列的长度呢？当然是有的，这就是复合锁，就是权衡了超时锁和排队锁的优势，并且加入了一层新的争抢的概念，该一层概念类似于令牌，也就是说只有拿到令牌的线程才可以排队争抢自旋锁，令牌的数量是有限的，因此就限制了队列的长度，如果一个线程拿到了令牌，但是排队超时了，那么它将放弃该令牌，抛出异常，由调用者决定接下来的动作。但是等一下，看看这个锁有什么问题，本来是争抢自旋锁，现在成了争抢令牌，这有何意义，其实争抢令牌是为了让争抢锁更加公平，避免饥饿现象，既然要避免饥饿，那么打破先来先服务是必要的，这个争抢令牌的过程就是打破先来先服务的过程，争抢令牌简单的使用了退避算法，为了不使系统在争抢令牌上开销过大。如果不是为了在已经避免了饥饿的超时锁的基础上兼顾公平性，超时锁已经很不错了，可是复合锁进一步加强了公平性，这种公平就是通过打破先来先服务实现的。