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

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

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

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