非阻塞自組織鏈表的研究.pdf

1、自組織鏈表是針對(duì)搜索問(wèn)題提出的,它能夠在響應(yīng)未知訪問(wèn)請(qǐng)求序列的過(guò)程中不斷調(diào)整節(jié)點(diǎn)位置,使鏈表結(jié)構(gòu)逐漸進(jìn)入一個(gè)能充分利用訪問(wèn)請(qǐng)求序列特性的狀態(tài),從而降低總體訪問(wèn)代價(jià),提高鏈表性能。隨著計(jì)算機(jī)硬件技術(shù)的發(fā)展,為了充分利用多處理器的協(xié)同計(jì)算能力,需要設(shè)計(jì)一種有效的共享并發(fā)自組織鏈表。
　　 非阻塞數(shù)據(jù)結(jié)構(gòu)使用非互斥方法,可以同時(shí)被多個(gè)并發(fā)線程訪問(wèn),避免了互斥方法中一個(gè)位于臨界區(qū)中的線程的延遲對(duì)其它線程產(chǎn)生的影響。它能夠保證在有限步內(nèi)至

2、少有一個(gè)線程能夠完成若干操作,具有更強(qiáng)的健壯性和更高的可依賴性。
　　 論文提出了兩種非阻塞自組織鏈表:只讀型非阻塞自組織鏈表和讀寫型非阻塞自組織鏈表。兩種新鏈表均滿足可線性化條件。其中讀寫型非阻塞自組織鏈表采用MTF規(guī)則,是已知的第一個(gè)支持常見(jiàn)字典操作的非阻塞自組織鏈表。
　　 只讀型非阻塞自組織鏈表中引入了“熱點(diǎn)”元素的概念。它為每個(gè)線程分配一個(gè)熱點(diǎn)數(shù)組,通過(guò)熱點(diǎn)數(shù)組來(lái)指導(dǎo)鏈表的自組織行為。此外,熱點(diǎn)數(shù)組還可以提高熱

3、點(diǎn)元素的查找效率,為充分利用高速緩存帶來(lái)了契機(jī)。
　　 讀寫型非阻塞自組織鏈表在數(shù)據(jù)節(jié)點(diǎn)之外引入了操作節(jié)點(diǎn)。一方面,執(zhí)行相關(guān)操作的線程之間通過(guò)操作節(jié)點(diǎn)相互通信、獲取其它線程的執(zhí)行結(jié)果、以及通知其它線程自身的執(zhí)行結(jié)果,保證了操作的非阻塞性和正確性。另一方面,通過(guò)讓操作節(jié)點(diǎn)起到數(shù)據(jù)節(jié)點(diǎn)的作用,能夠及時(shí)、準(zhǔn)確地對(duì)訪問(wèn)元素執(zhí)行MTF操作,從而實(shí)現(xiàn)鏈表的自組織行為。
　　 實(shí)驗(yàn)表明,當(dāng)訪問(wèn)請(qǐng)求序列具有較強(qiáng)局部性時(shí),兩種新鏈表的性能