自适应非阻塞哈希表的研究

发布时间：2022-11-11 17:26

　　哈希表是一种实用的数据结构,具有常数级的访问效率。一种常用的实现是将元素存储到桶中从而避免哈希冲突,桶间的操作相互独立。多处理器下的并发哈希表,其桶的设计是一个重要的研究课题,一方面,扫描桶的过程增加了整体的时间开销;另一方面,哈希表的并发调整也对桶的实现提出了更高的正确性要求。自适应的桶可以根据请求序列动态地调整桶内元素的顺序,从而提高自身访问效率,在局部性数据下具有很大优势。因此论文对自适应的非阻塞哈希表进行研究,通过改进哈希表的桶,使其能够适应局部性数据。论文主要完成了以下工作。1)在已有的无锁哈希表的基础上进行改进,实现了一个自适应的无锁哈希表算法。算法思想是将桶实现为一个无锁的Move-To Front链表,主要挑战是需要将该链表实现为一个可冻结集合,设计拆分与合并操作,使其在保证性能的同时协调哈希表的并发调整和链表操作。2)优化桶在只读场景下的行为,实现了加速的无锁哈希表。优化思想是在执行桶内查询时以只读的方式预先探测,避免一些链表更新的消耗。3)在演进性上进行扩展,实现了一个无等待的哈希表算法。主要挑战是桶的无等待特性不能保证哈希表的无等待特性,设计思想是为线程设置优先级... 

【文章页数】：65 页

【学位级别】：硕士

【文章目录】：
摘要
abstract
第一章 绪论
    1.1 研究背景及意义
    1.2 MTF链表
    1.3 并发对象
        1.3.1 正确性条件
        1.3.2 演进性条件
        1.3.3 CAS操作
    1.4 内存管理
    1.5 论文工作
    1.6 论文组织结构
第二章 相关工作
    2.1 阻塞的哈希表
        2.1.1 典型的阻塞哈希表
    2.2 非阻塞的哈希表
        2.2.1 典型的非阻塞哈希表
第三章 算法设计
    3.1 自适应的无锁哈希表
        3.1.1 数据结构
        3.1.2 算法概述
        3.1.3 冻结操作
        3.1.4 查找操作
        3.1.5 调用操作和响应操作
        3.1.6 拆分操作和合并操作
    3.2 自适应的无锁哈希表的加速算法
    3.3 自适应的无等待哈希表
第四章 算法正确性证明
    4.1 可线性化性
    4.2 无锁特性
    4.3 无等待特性
第五章 算法性能分析
    5.1 实验说明
    5.2 实验结果
第六章 结论
    6.1 总结
    6.2 展望
参考文献
发表论文和参加科研情况说明
致谢


【参考文献】：
期刊论文
[1]基于低冲突帮助机制的快速无等待哈希表算法[J]. 李鹏飞,张坤龙,康超凡.  计算机工程. 2015(11)

硕士论文
[1]基于换位规则的非阻塞自组织链表[D]. 李鹏飞.天津大学 2016
[2]基于副本的非阻塞自组织链表[D]. 谭龙飞.天津大学 2012
[3]非阻塞自组织链表的研究[D]. 吴宗远.天津大学 2010



本文编号：3705444