基于換位規(guī)則的非阻塞自組織鏈表.pdf

1、自組織鏈表可以根據(jù)訪問(wèn)序列動(dòng)態(tài)地調(diào)整鏈表結(jié)構(gòu)，從而降低平均訪問(wèn)時(shí)間，提高鏈表的性能。如果被訪問(wèn)的數(shù)據(jù)具有較強(qiáng)的局部性，自組織鏈表將比傳統(tǒng)的鏈表更具優(yōu)勢(shì)。隨著多核處理器的日益普及，為了充分利用多核的優(yōu)勢(shì)，并發(fā)數(shù)據(jù)結(jié)構(gòu)的研究越來(lái)越引人注目。其中，并發(fā)鏈表的研究成效顯著，出現(xiàn)了越來(lái)越多的實(shí)用的并發(fā)鏈表算法，而且已經(jīng)在工程上得到了應(yīng)用。然而，并發(fā)自組織鏈表的研究屈指可數(shù)。
　　論文在已有研究的基礎(chǔ)上，完成了以下工作。1）首次提出了基于換位

2、規(guī)則的無(wú)鎖和無(wú)等待自組織鏈表算法。算法的基本思想是查找線程在訪問(wèn)的結(jié)點(diǎn)上進(jìn)行標(biāo)記，然后嘗試將其與其直接前驅(qū)相交換;發(fā)現(xiàn)該標(biāo)記的其他線程會(huì)嘗試幫助未完成的交換。2）實(shí)現(xiàn)了第一個(gè)無(wú)等待的MTF自組織鏈表算法。算法采用幫助機(jī)制保證了相關(guān)操作結(jié)點(diǎn)的插入是無(wú)等待的，從而保證了整個(gè)算法是無(wú)等待的。3)對(duì)快路徑-慢路徑這種提升無(wú)等待算法性能的技術(shù)做了分析，指出快路徑-慢路徑方法具有一定的局限性。如果算法的無(wú)鎖版本與無(wú)等待版本不能兼容，這種方法就不能使