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

摘要

已有的无等待通用构造算法大多只考虑有界无等待的情况,并不适用于无界无等待并发模型.为此,提出一种新的无等待通用构造算法——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 Fetch&Add 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.