排队自旋锁的引入
自旋锁spinlocks保证了对于共享资源的互斥访问，对于smp代码安全提供了一种高效解决方案。但是近来人们也发现了自选锁的一个很大的缺陷：缺乏公平！这怎么说呢？当自旋锁被占用期间，如果其他CPU需要使用该锁的话，必须等待；一旦自旋锁被释放，那么这些等待的CPU谁会首先获得锁呢？没有人知道！很可能的一种情况是，当前释放锁的CPU因为拥有当前的cache line而再次占用锁。也就是说，其它CPU获得锁的时间不定，有可能最先提出锁要求的CPU最后获得锁，这就造成了不公平现象(饥饿)！解决了这个问题，提出了“Ticket spinlock”的概念，按照要求锁的先后顺序，让最先要求锁的CPU在第一时间获得锁，后要求锁的CPU排队等候。
传统spinlock的实现方式
在2.6.24之前的内核代码中，spinlock被实现为一个全局的整形变量，初始化为1表示锁未被占用；当需要获取锁时，spin_lock()会将变量减1，然后判断是否是0，是的话就拥有了锁，否则循环重试(减1，是否为0)；拥有锁的CPU释放锁时，spin_unlock()会简单的将变量置为1。下一次哪个CPU获得锁，就不得而知了，这就为可能的饥饿埋下了隐患。
排队自旋锁的实现方式
Nick Piggin的排队自旋锁是在2.6.25内核中引入的。大家可能有这样的经历：去银行处理业务的时候，银行一般都有一个排队机，供客户抽号；如果客户抽的号正在柜台上被叫，则可以直接去办理业务；如果抽的号比柜台上正办理业务的号大，那就要等待。Nick Piggin的排队自旋锁就是这个道理：将spinlock的整形变量当成两部分来看，分别是next和owner(当CPU<256的时候，仅使用变量的低16位，此16位的高8位为next，低8位为owner；当cpu>256的时候，变量的32位全被使用，高16位为next，低16位为owner)；锁初始状态为0，即next=owner=0；需要获取锁时，spin_lock()内部会首先返回当前的next值，并同时将其加1，然后判断返回next是否等于owner，相等的话，锁获取成功，否则循环判断(判断返回next是否等于owner)；锁释放时，spin_unlock()会将owner的值加1，这样第一个要求锁的CPU就有能力在第一时间获取锁，其它竞争者只能排队等候了，That's it！完全公平了，不存在恶意争抢的问题了，但这就完美了吗？
针对Ticket spinlock继续思考
排队自旋锁的确保证了彻底公平，但似乎缺少那么点人性美德。银行排队的时候，如果遇到了行动不便的老人，你会不会让他/她先处理业务呢？我想您一定会的吧。所以排队自旋锁的实现上可否允许高优先级业务加塞，以体现内核之美德呢？我的方案是将spinlock的整形变量分成三个部分，相比ticket spinlock加入一个标志位，置位的话表示本业务优先级高，需要加塞，应该在可能的第一时间获取锁，你觉得如何？
另外的一个思考就是，spinlock是非常执着的，不达目的绝不罢休的那种人(原地死等)。如果给spinlock加入一个超时机制的话是不是会更美好呢？那就接着切分那个整形变量吧^_^，如果32位不够的话，可以考虑将该变量升级成64位的。
当然了，内核黑客都是深不可测的，以上两个问题他们应该也都想到了吧，那为什么没有实现呢？也许由于spinlock是定位在最底层、最高效的互斥机制，必须要保证其最简化，以保证对系统效率的影响降至最低。who knows～
本文参考了如下文章：
阅读(1757) | 评论(0) | 转发(0) |
