基于副本的非阻塞自組織鏈表.pdf

1、自組織鏈表是一種具有啟發(fā)意義和實用價值的數(shù)據(jù)結構,它能夠響應訪問模式的變化,調(diào)節(jié)鏈表結構以改善鏈表的性能,并已經(jīng)被成功應用到數(shù)據(jù)壓縮算法、凸包算法和計算最大值點。隨著計算機多核技術的發(fā)展,為了充分利用多核的協(xié)同計算能力,需要設計一種高效的并發(fā)自組織鏈表結構。
　　非阻塞數(shù)據(jù)結構使用非互斥的方法實現(xiàn)并發(fā),使互斥資源能夠被多于一個線程同時訪問,避免了互斥方法中的死鎖、優(yōu)先級反轉(zhuǎn)和護航問題。它能保證至少有一個線程能夠在有限時間內(nèi)完成操作

2、,具有更好的健壯性和可靠性,并可以獲得比互斥方法更好的性能。因此,提出了實現(xiàn)非阻塞自組織鏈表的設想。
　　本文提出了基于副本的非阻塞自組織鏈表。為鏈表中的結點維護一個副本結點,通過移動副本結點實現(xiàn)對鏈表的自組織。鏈表分為無序的副本結點和有序的數(shù)據(jù)結點兩部分,通過副本結點能快速訪問數(shù)據(jù)結點,數(shù)據(jù)結點部分采用的是Michael的算法,副本結點部分應用的是MTF規(guī)則。鏈表結構簡單,能保證可線性化的正確性和非阻塞的演進性。
　　實驗