非阻塞同步方法处理共享数据不使用锁机制，利用处理器提供的特殊指令(compare-and-swap等指令)设计相应算法保证访问共享数据的正确性，使多个任务可以同时访问共享数据。现在国外的主要研究方向为非阻塞同步算法设计、算法正确性的理论证明、算法性能测试等，并致力于在满足要求的前提下实现算法的高性能、平台无关和广泛应用。
2锁无关算法及ELABS算法实现技术
2.1锁无关算法的基本结构
大多数共享数据是以栈、队列等基本数据结构形式存在的。锁无关算法实现了多个任务可以同时操作的基本数据结构。锁无关算法包括多个处理共享数据的操作，如栈包括入栈、出栈两个基本操作。其中每一个操作的如图1所示。
图1锁无关算法中一个操作的流程图
Fig.1flowchatofanoperationoflock-freealgorithm
每个操作不断地试图修改共享数据直到成功为止。可以将每个操作分为循环部分、循环前部分、循环后部分，循环部分是一个潜在的无限循环。
2.2ELABS算法实现关键技术
ELABS算法由CAS(Compare-and-Swap)指令实现，在一条指令中完成对共享变量的测试和更新。CAS指令主要形式为CAS(&val，oldval，newval)，执行过程如下：val等于oldval时赋值val为newval，否则失败。使用CAS指令必须解决“ABA问题”：如果一个任务读取共享变量的值为A，在对共享变量赋新值之前共享变量被另一个任务修改为B后又改回A。则此时比较和交换操作虽然得到正确执行，但违背了对共享变量的读与写之间不能发生其他任务写操作的原则。最常用的解决方法是对变量添加一个修改计数,当对变量修改时加一，对变量和修改计数同时判定。这种方法未完全避免ABA问题，但将其发生的概率降低到极其低的水平，可以忽略不计。
为了提高算法的效率，ELABS算法根据栈结构的特点采用了消隐技术。消隐的工作机制即让一对相反且连续的操作进行数据交换，而不用对实际数据进行操作，从而简化了操作过程，减少了访问共享数据的冲突。对栈结构而言，入栈操作和出栈操作作用于同一位置，因此更加适合消隐技术的实现。
3ELABS算法及正确性证明
ELABS算法中栈包括栈头项、栈大小、栈数据数组，数据数组中的栈顶称为栈顶项。栈头项中包括栈顶索引、栈头项中的值是否有效的标记、修改计数、数据值，用于记录栈的状态并暂时存储最近入栈数据。
在LABS算法中同样采用栈头项暂存最近入栈数据，但任何操作必须首先将栈头中的数据复制到数据数组，而这样的操作有时是无意义的，如栈头项中的数据已经无效时。采用消隐技术可以通过栈头项实现数据的交换，而无需对数据数组进行操作。ELABS算法在栈头项中设置数据是否有效的标记，可得到如下简化操作：1)当入栈且标记无效时，直接修改栈头项并设置标记有效即可；2)当出栈且标记有效时，直接修改栈头项并设置标记无效即可。3)当出栈且标记无效时，先读取栈顶项再修改栈头项并设置标记无效，而读操作不会产生数据访问冲突。
(1)主要数据类型：
Top{index:15;tag:1;counter:16;intvalue;};
stackItem{intvalue;intcounter;};
stack{Toptop;intsize;stackItem*item;};
其中栈头项和数据项各占用8个字节。CAS64操作封装了可以操作8字节的CAS指令，要求必须为2个相邻的4字节。
(2)入栈操作
入栈操作首先获取栈头项，判定栈满时返回；然后判定栈头项标记是否有效，有效时将其写入数据项，如果失败则重新执行；最后组合新的栈头项内容并写入栈头项中，失败时重新执行。
(3)出栈操作
出栈操作首先获取栈头项，判定栈空时返回；然后获取栈顶项并组合新的栈头项内容并写入栈头项中，失败时重新执行；最后根据栈头项标记是否有效判定出栈的值在栈头项中还是栈顶项中。
由于ELABS算法正确性的验证不能采用实际测试程序，只能通过理论证明方法，算法的正确性包括安全性、可线性化、锁无关性。安全性是指保证算法符合具体数据结构的操作要求，如栈必须对栈顶进行操作；可线性化是指算法中每一个操作都会在一个特殊点生效，避免并发访问共享数据而可能出现的数据不一致风险；锁无关性是锁无关算法的本质特征，即保证整个系统会在有限的步骤内完成对同一共享数据的某些操作。4实验
实验一测试对比了基于锁的算法、LABS算法和ELABS算法实现的栈之间的性能,其中入栈、出栈的顺序随机产生。试验结果表明，ELABS比Lock、LABS具有更高的性能。随着并行度的增大，锁无关算法的执行速度越明显，并且在任务数量较少时也具有优势。
为测试消隐技术对性能的影响，实验二对实验一中的测试用例进行了限制，提高了可消隐操作的比例。试验结果表明，在存在大量消隐的情况下ELABS的性能优势更加明显，分别比Lock、LABS有大幅度提高，证明采用消隐技术提高了算法的执行速度。
锁无关算法不采用锁机制对任务之间进行同步，避免了锁机制引起的诸多缺点：1)避免死锁，多个任务可同时访问共享资源，打破了死锁发生的相互排斥、请求和保持等必要条件；2)避免优先级逆转，高优先任务无需获取访问共享资源的锁；3)提高容错性，单一任务的崩溃不会因为持有锁而导致其他任务的永久阻塞。
综合上述，ELABS算法具有更高执行速度，在一定程度上提高了实时系统的性能和实时性，并完全避免了使用锁而引起的死锁、优先级逆转、低容错性等缺点。
5总结
本文提出了一种采用消隐技术的锁无关栈算法，证明了该算法的正确性，并通过实验得到算法具有更高的执行速度，避免死锁、优先级逆转、低容错性等缺点。将该算法应用到对现有共享数据结构的改造中，将有利于提高实时系统的性能、确定性和容错性。