面向并行安全网关流水线模型的无锁队列算法  

A Lock-Free Queue Algorithm for Pipeline Model of Parallelism Security Gateway

作　　者：高志民[1] 姚崎[1] 

机构地区：[1]北京交通大学计算机与信息技术学院,北京100044

出　　处：《北京交通大学学报》2010年第5期8-13,19,共7页JOURNAL OF BEIJING JIAOTONG UNIVERSITY

基　　金：国家"863"计划项目资助(2007AA01Z410);电子信息产业发展基金项目资助(2007-329)

摘　　要：提出一种适用于并行安全网关流水线模型中共享数据缓冲区操作的无锁队列算法.与其他类似算法比较,该算法采用链表结构组织队列数据,避免了采用循环数组结构引起的缓冲区长度限制和内存浪费的问题;与通用的链表队列无锁算法比较,算法实现更为简洁,执行效率更高.证明了算法具有线性化和非阻塞特性.通过模拟试验,验证了算法在理想环境和各种实际应用环境中都具有较好的性能指标.A lock-free queue algorithm for shared data buffer operation in pipeline model of parallelism security gateway is proposed in this paper. Comparing other similar algorithm that employs static cycle data array, dynamic linked list data structure is adopted in the proposed algorithm and thus restriction of data buffer length and memory waste is eliminated. Comparing the general lock-free algorithm for linked list queue, implementation of the proposed algorithm is simple and fast. Also, the linearizability and non-block attribution of the algorithm is proved in the paper. Finally, the results of simulation experiment show that performance of the new proposed algorithm is good not only in ideal experiment environment but also in all kinds of realistic experiment environment.

关 键 词：安全网关 流水线模型 生产者/消费者队列 无锁算法 

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