【摘要】：隨著多核/眾核技術(shù)的發(fā)展,高并發(fā)的數(shù)據(jù)結(jié)構(gòu)成為并發(fā)程序設(shè)計的研究熱點。二叉搜索樹應用范圍廣泛,在并發(fā)數(shù)據(jù)結(jié)構(gòu)中占有重要地位。高并發(fā)無鎖二叉搜索樹算法的設(shè)計與實現(xiàn)將對并發(fā)程序的設(shè)計提供強有力支持。目前針對二叉搜索樹算法的研究,存在多個線程對共享資源的同步訪問問題。傳統(tǒng)解決方案使用鎖機制進行同步,以確保線程的安全訪問,但容易引起鎖競爭和死鎖等問題,導致算法效率低下。針對二叉搜索樹算法使用鎖機制引起的問題,本文提出了一種新的無鎖算法。該算法使用比較和交換(CAS)指令,在異步共享內(nèi)存系統(tǒng)中完成對二叉搜索樹的搜索,插入和刪除操作。本文算法使用外部(面向葉子)搜索樹模型,該模型的優(yōu)點是不存在刪除具有兩個孩子結(jié)點的情況,從而提高了刪除操作的效率。與研究二叉搜索樹需要獲得內(nèi)部節(jié)點的方式不同,本文算法運用整體的思想,通過操作子樹來處理插入和刪除操作。本文介紹了無鎖二叉搜索樹算法的設(shè)計細節(jié),在各種條件(不同的樹形大小,工作量分布和爭用度)下進行了實驗,將本文的算法與Bronson等人基于鎖的算法、Ellen等人基于無鎖的算法進行了吞吐量大小的比較。實驗結(jié)果表明,當線程數(shù)大于4時,本文算法的吞吐量優(yōu)于其他兩個并發(fā)BST算法,可以有效地減少更新(插入或刪除)操作之間的爭用。當并發(fā)性較高時,本文的算法將具有一定競爭力。
【圖文】：

上述 7 類演進條件，按照演進條件的限定要求對其進行從小到塞、無饑餓、無干擾、無鎖、無等待、有界無等待、集居數(shù)無程度比較低則線程并發(fā)執(zhí)行的操作會被其他任務或因素影響，反之，線程并發(fā)執(zhí)行的操作受到的干擾少，性能得到提升。演低的演進條件。如果某個數(shù)據(jù)結(jié)構(gòu)符合演進程度高的要求，，則低的要求[44]。如：“無鎖的數(shù)據(jù)結(jié)構(gòu)是無干擾的”（反之不對法包含無干擾方法的要求。

使用原子操作的方式進行多線程并。統(tǒng)計顯示執(zhí)行CAS操作運行的時間大約是鎖以它是并發(fā)數(shù)據(jù)結(jié)構(gòu)設(shè)計的重要方式[47]。使用，它不僅可以使程序的性能得到提升，有效避展的。使用CAS操作方式在并發(fā)數(shù)據(jù)結(jié)構(gòu)設(shè)計叉搜索樹。無鎖并發(fā)中CAS的用法：的有鎖方式 假設(shè)在多線程環(huán)境下需要實現(xiàn)具otalCount，由于線程會并發(fā)修改totalCount計數(shù)器行同步，如下圖 2-4 所示。
【學位授予單位】：河北科技大學
【學位級別】：碩士
【學位授予年份】：2019
【分類號】：TP311.12

【參考文獻】

相關(guān)期刊論文 前2條

1 王防修;周康;;一種構(gòu)建嚴格平衡二叉搜索樹的非遞歸算法[J];武漢工業(yè)學院學報;2013年04期

2 孫召偉;趙建利;朱東生;;數(shù)據(jù)結(jié)構(gòu)中遞歸轉(zhuǎn)非遞歸算法分析及模型設(shè)計研究[J];河北科技大學學報;2011年01期

相關(guān)博士學位論文 前1條

1 彭建章;非阻塞算法與多進程網(wǎng)絡程序優(yōu)化研究[D];中國科學技術(shù)大學;2013年

相關(guān)碩士學位論文 前5條

1 劉正陽;C/C++多線程程序并發(fā)訪存問題的軟件分析研究[D];北京郵電大學;2017年

2 謝文韜;基于無鎖結(jié)構(gòu)的大容量數(shù)據(jù)高性能檢索系統(tǒng)研究[D];東南大學;2017年

3 路佳佳;面向多核共享內(nèi)存的低功耗研究[D];北京工業(yè)大學;2016年

4 曹紅星;一種無鎖并發(fā)跳表算法的可線性化證明[D];中國科學技術(shù)大學;2014年

5 劉恒;并發(fā)數(shù)據(jù)結(jié)構(gòu)及其在動態(tài)內(nèi)存管理中的應用[D];重慶大學;2013年

本文編號：2652188