基于帮助机制的无界无等待通用构造算法

Unbounded Wait-free Universal Construction Algorithm Based on Help Mechanism

已有的无等待通用构造算法大多只考虑有界无等待的情况,并不适用于无界无等待并发模型。为此,提出一种新的无等待通用构造算法——UWUC。该算法使用Fetch&Add对象和列地址选通脉冲对象,给出新的排队方法,利用任意一段时间内到达的线程数有限的特性,实现无界无等待的通用构造。实验结果证明了该算法的无等待特性。

Existing wait-free universal construction algorithm only considers the bounded wait-free situation and can not be adapted to unbounded wait-free model. This paper presents a novel solution： Unbounded Wait-free Universal Construction（ UWUC for short） algorithm which uses Column Address Strobe（ CAS） object and FetchAdd object. The number of processes arrived during a time interval is finite,thus using a special queuing technical and helping mechanism implementing the unbounded wait-free universal construction. Experimental results show wait-free characteristics of UWUC algorithm.