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

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

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