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

Unbounded Wait-free Universal Construction Algorithm Based on Help Mechanism

作　　者：苏浩 张坤龙[1] 李鹏飞[1] 

机构地区：[1]天津大学计算机科学与技术学院

出　　处：《计算机工程》2017年第11期22-26,共5页Computer Engineering

基　　金：国家自然科学基金(61303021);水利部公益性行业科研专项基金(201401033)

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

关 键 词：并发数据结构 无等待 通用构造 无界无等待 非阻塞 列地址选通脉冲 

分 类 号：TP309[自动化与计算机技术—计算机系统结构]