哈希表是一種實(shí)用的數(shù)據(jù)結(jié)構(gòu),具有常數(shù)級的訪問效率。一種常用的實(shí)現(xiàn)是將元素存儲到桶中從而避免哈希沖突,桶間的操作相互獨(dú)立。多處理器下的并發(fā)哈希表,其桶的設(shè)計(jì)是一個(gè)重要的研究課題,一方面,掃描桶的過程增加了整體的時(shí)間開銷;另一方面,哈希表的并發(fā)調(diào)整也對桶的實(shí)現(xiàn)提出了更高的正確性要求。自適應(yīng)的桶可以根據(jù)請求序列動(dòng)態(tài)地調(diào)整桶內(nèi)元素的順序,從而提高自身訪問效率,在局部性數(shù)據(jù)下具有很大優(yōu)勢。因此論文對自適應(yīng)的非阻塞哈希表進(jìn)行研究,通過改進(jìn)哈希表的桶,使其能夠適應(yīng)局部性數(shù)據(jù)。論文主要完成了以下工作。1)在已有的無鎖哈希表的基礎(chǔ)上進(jìn)行改進(jìn),實(shí)現(xiàn)了一個(gè)自適應(yīng)的無鎖哈希表算法。算法思想是將桶實(shí)現(xiàn)為一個(gè)無鎖的Move-To Front鏈表,主要挑戰(zhàn)是需要將該鏈表實(shí)現(xiàn)為一個(gè)可凍結(jié)集合,設(shè)計(jì)拆分與合并操作,使其在保證性能的同時(shí)協(xié)調(diào)哈希表的并發(fā)調(diào)整和鏈表操作。2)優(yōu)化桶在只讀場景下的行為,實(shí)現(xiàn)了加速的無鎖哈希表。優(yōu)化思想是在執(zhí)行桶內(nèi)查詢時(shí)以只讀的方式預(yù)先探測,避免一些鏈表更新的消耗。3)在演進(jìn)性上進(jìn)行擴(kuò)展,實(shí)現(xiàn)了一個(gè)無等待的哈希表算法。主要挑戰(zhàn)是桶的無等待特性不能保證哈希表的無等待特性,設(shè)計(jì)思想是為線程設(shè)置優(yōu)先級... 

【文章頁數(shù)】：65 頁

【學(xué)位級別】：碩士

【文章目錄】：
摘要
abstract
第一章 緒論
    1.1 研究背景及意義
    1.2 MTF鏈表
    1.3 并發(fā)對象
        1.3.1 正確性條件
        1.3.2 演進(jìn)性條件
        1.3.3 CAS操作
    1.4 內(nèi)存管理
    1.5 論文工作
    1.6 論文組織結(jié)構(gòu)
第二章 相關(guān)工作
    2.1 阻塞的哈希表
        2.1.1 典型的阻塞哈希表
    2.2 非阻塞的哈希表
        2.2.1 典型的非阻塞哈希表
第三章 算法設(shè)計(jì)
    3.1 自適應(yīng)的無鎖哈希表
        3.1.1 數(shù)據(jù)結(jié)構(gòu)
        3.1.2 算法概述
        3.1.3 凍結(jié)操作
        3.1.4 查找操作
        3.1.5 調(diào)用操作和響應(yīng)操作
        3.1.6 拆分操作和合并操作
    3.2 自適應(yīng)的無鎖哈希表的加速算法
    3.3 自適應(yīng)的無等待哈希表
第四章 算法正確性證明
    4.1 可線性化性
    4.2 無鎖特性
    4.3 無等待特性
第五章 算法性能分析
    5.1 實(shí)驗(yàn)說明
    5.2 實(shí)驗(yàn)結(jié)果
第六章 結(jié)論
    6.1 總結(jié)
    6.2 展望
參考文獻(xiàn)
發(fā)表論文和參加科研情況說明
致謝


【參考文獻(xiàn)】：
期刊論文
[1]基于低沖突幫助機(jī)制的快速無等待哈希表算法[J]. 李鵬飛,張坤龍,康超凡.  計(jì)算機(jī)工程. 2015(11)

碩士論文
[1]基于換位規(guī)則的非阻塞自組織鏈表[D]. 李鵬飛.天津大學(xué) 2016
[2]基于副本的非阻塞自組織鏈表[D]. 譚龍飛.天津大學(xué) 2012
[3]非阻塞自組織鏈表的研究[D]. 吳宗遠(yuǎn).天津大學(xué) 2010



本文編號：3705444