技术开发部
无锁队列
计算机的资源是有限的，如果不加限制，对资源的并发访问将产生一系列问题，因此在并行计算中广泛使用了锁（lock）。
锁的引入带来的问题是效率的降低，因此在高效系统中，应尽可能避免锁的使用，关于无锁队列的理论研究和实践已经进行了很多年，理论已经证明，单生产者-单消费者队列的锁可以去掉，从而形成一个并发无锁队列（lock free queue）
除了高效，无锁队列还能防止优先级倒置（priority inversion）。
有三个优先级不同的task，A，B，C；A的优先级最高，B次之，C最低。其中A和C有共享的临界区。如果C已进入临界区，那么A在进入临界区之前，就会被阻塞。task B有可能打断C而进入运行状态，这样C什么时候从临界区退出，就是一个未知的时间。A只有C从临界区退出后才能被调度，A被阻塞的时间也是未知的。这样，低优先级的B先于高优先级的A被调度，优先级发生了逆转。
解决这个问题有两种手段：
1：Priority inheritance（优先级继承），如果一个高优先级的task被阻塞，与它共享临界区的低优先级的task在进入临界区后，优先级就会继承高优先级 task的优先级，保证它不会被其他优先级次高的任务打断。从临界区退出后，C的优先级恢复正常。这种方法的缺点是动态改变线程的优先级耗费了大量时间。
2：A priority ceiling（最高优先级），给临界区分配最高优先级，如果一个task进入临界区，就把临界区的优先级赋给它，已保证它不会被打断。从临界区退出后，task的优先级恢复正常。这种方法的缺点是假如没有高优先级A的存在，B将被延迟执行。
这两种解决方案带来的代价都是效率的降低，在实际系统中，除了无锁队列，还应采用其他方案，尽量避免对锁的使用，否则可能出现与预期相反的结果，而问题相当难于查找。
关于优先级倒置，和著名的火星探路者软件故障联系在一起，因而名声大噪。
在发生问题之前，探路者被认为是没有缺陷的，直到着陆几天后，系统被整个重置了，接下来发生的一切，带给我们很多启示。
发生如此重大的问题，如何迅速查找问题根源并解决？探路者所使用的系统记录了所有需要关心的事件，航天局工程师们通宵达旦一遍又一遍的重复运行这些事件，当只剩下一个工程师没有回家休息时，终于重现了故障，原来是优先级倒置。这提示我们，详细记录系统的运行对我们改正错误很重要，黑盒跟踪错误几乎是不可能的。
事实上，在发射前的测试中，出现过1、2次系统重置的现象，但无法重现和解释，出于本能，他们拒绝认为这是软件问题，而把其归结为硬件问题。各类系统中，有很多问题都是这么遗漏的，不应忽略任何异常偶发事件，直到找到根源。
这次事件也向我们展示了理论的重要性，多年前有人研究了此类问题并给出了解决方案，使得问题能得以迅速查找并解决。
这次事件还提示，长期运行的系统，在效率和正确性之间，首先应关注的是正确性，效率应该是其次的。
发生了重置事件，探路者的工作受影响了吗？答案是几乎没有，这不得不感谢它的设计者，设计充分考虑了容错性，即使系统完全重置，重新启动后也能不受影响的在原来基础上继续工作。
刚才扯远了，回到无锁队列，实现无锁队列，需要考虑到原子操作和内存屏障（memory barrier）。原子操作我们就不谈了，重点说一下内存屏障。
单核系统不会存在内存屏障问题，对多核系统，为提高效率，允许乱序执行，这样应该先写入内存的数据未必先写入，逻辑上会出现错误，解决的方法是在写入前，强迫cpu串行化，这就是内存屏障技术。
在intel系列cpu中，因为使用了强排序技术，很难测试到cpu乱序执行问题，但并非不会发生，因此在程序中还是要考虑这个问题。测试内存屏障的最佳cpu是power pc。
关于无锁队列的最详细介绍和实现，请参照http://www.audiomulch.com/~rossb/code/lockfree/ ，优先级倒置和内存屏障，请在google中查找。
