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

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

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