基于MTF規則的非阻塞自組織鏈表

康 超 凡

(天津大學計算機科學與技術學院 天津 300000)

?

基于MTF規則的非阻塞自組織鏈表

康 超 凡

(天津大學計算機科學與技術學院 天津 300000)

自組織鏈表是一種特殊的鏈表。與靜態鏈表相比，將自組織鏈表應用于并發環境下，需要考慮自組織操作對鏈表狀態的改變。因此，對于并發自組織鏈表，尤其是具有非阻塞特性的自組織鏈表的研究更加復雜。近些年來，并發鏈表的研究成果顯著，而關于并發自組織鏈表算法的研究屈指可數。在這種背景下，提出了一種基于MTF(Move-To-Front)自組織規則的無鎖自組織鏈表，證明了該鏈表算法實現了在集合上的插入、刪除，以及查找操作，并且算法的實現是無鎖的。實驗結果表明，該算法的性能在大多數情況下都優于Harris算法，具有一定的使用價值。

并發 無鎖 自組織 鏈表

0 引 言

鏈表是一種常見的數據結構，可以使用非連續的存儲空間來存儲結點元素。在程序設計中，鏈表實現簡單，性能優越，具有非常廣泛的應用。自組織鏈表是一種特殊的鏈表，最初源于搜索問題，是McCabe在1965年提出的[1]。自組織鏈表可以在鏈表的訪問過程中對鏈表結點進行動態調整，在訪問數據具有較強的局部性的時候，自組織鏈表與靜態鏈表相比具有更高的搜索速率和更短的平均訪問時間，從而表現出更好的性能。

針對于自組織鏈表的鏈表更新問題，最常用的確定型聯機算法主要有三種:MTF(Move-To-Front)、TP(Transpose)，以及FC(Frequency-Count)[2]。MTF規則是每次對鏈表進行訪問時，將被訪問的結點移動到鏈表頭部；TP規則是每次訪問鏈表結點時，將被訪問的結點與其直接前驅進行交換；FC規則是一種基于訪問計數的自組織規則，需要額外的空間記錄鏈表中每個結點的被訪問次數，當結點被訪問時，次數加1，同時維護鏈表，使鏈表中的結點按照被訪問次數非遞增的順序排列。

在當前的多核處理器時代，并發程序與傳統的串行程序相比，更能充分發揮多核處理器的優勢。近些年來，并發程序設計問題成為人們重點研究和討論的問題。

數據結構是程序設計的基礎與核心，鏈表是一種常見的數據結構，為了發揮多處理器的優勢，并發鏈表的設計與實現，具有重要的意義。根據不同的同步機制，并發鏈表可以分為阻塞鏈表和非阻塞鏈表。

阻塞鏈表的實現一般采用加鎖的方法，如粗粒度同步鏈表、細粒度同步鏈表、樂觀同步鏈表，以及惰性同步鏈表等。這種加鎖的算法實現較為簡單，但是可能會帶來死鎖和優先級反轉等問題。

與阻塞鏈表相比，非阻塞鏈表不使用鎖來實現同步，而是使用更強的原子指令。在非阻塞鏈表中，線程間的執行是互不影響的，某一個線程的延遲并不會對其他線程的執行帶來影響。而根據不同的演進性條件，非阻塞又分為無妨礙、無鎖，以及無等待。三個演進性條件依次增強。其中無妨礙特性保證了如果在線程調用過程中其他所有線程調用被暫停，那么該線程調用將在有限步驟內完成；無鎖保證了至少存在一個線程調用能夠在有限步驟內完成；無等待是最強的演進性條件，在無等待條件下，所有線程調用都能夠在有限步驟內完成[3]。

Valois提出了第一個基于CAS(compare-and-swap)的無阻塞并發鏈表[4]。在Valois的鏈表中，在普通結點之間添加了輔助結點，用來解決并發操作中可能出現的插入丟失和刪除丟失問題，同時使用backlink技術實現快速重做。之后Harris提出了另一種簡單有效的無鎖鏈表的實現方法[5]。Harris的算法主要思想是在鏈表中的結點被物理刪除之前先對結點進行標記。Harris的算法與Valois的算法相比，實現更加簡單，并且性能更好。之后，Michael提出一個靜態的無鎖哈希表的算法[6]，其中哈希表中桶的實現使用了一種基于Harris算法的無鎖鏈表算法。這種鏈表算法與Harris鏈表算法大同小異，二者合稱為Harris-Michael算法。Fomitchev和Ruppert將Valois和Harris算法的思想相結合，提出了一種新的無鎖鏈表的實現方法，并且使用分攤分析證明了算法有較好的平均復雜度[7]。Braginsky等則提出了一種基于局部感知的無鎖鏈表的實現方法[8]。Timnat等提出了第一個基于單CAS指令的無等待鏈表算法[9]，算法在Harris的無鎖并發鏈表的基礎上，通過使用幫助機制實現了具有無等待演進特性的并發鏈表。Zhang等設計并實現了新的無鎖和無等待的無序鏈表的算法，具有良好的性能[10]。

自組織鏈表是一種非常具有實用價值的數據結構，將自組織鏈表應用于并發環境下，可以充分發揮多核處理器的優勢，獲得更好的執行性能。阻塞方式的實現簡單，但是加鎖的方法使算法難以實現高并行性；非阻塞方式與阻塞方式相比具有更好的可靠性和健壯性。Herlihy[11-13]等證明了使用CAS操作原語能夠實現任何非阻塞數據結構，但是這種通用構造的方法實現較為復雜，并且效率不高。因此，對于實現非阻塞自組織鏈表算法，需要更加精細的設計。

將自組織鏈表應用于并發環境下，自組織規則的應用會給算法的設計帶來新的問題，難以保證算法的正確性。以基于MTF規則的自組織鏈表為例，在應用MTF規則時，需要將被訪問的結點移動到鏈表的頭部，具體操作為：先將結點從原位置刪除，再插入到鏈表的頭部。在單個線程對鏈表進行順序訪問時，上一次的訪問中對訪問結點位置的調整不會影響到當前對鏈表的訪問。然而在多線程的并發環境下，多個線程可以同時對共享鏈表進行操作，一個線程所執行的MTF自組織操作，將訪問結點移動到鏈表頭部的過程中，可能會影響到另外的線程對該結點的訪問，從而造成相應的訪問錯誤。這也是在設計非阻塞自組織鏈表的過程中所需要解決的難點問題。

譚龍飛提出了一種基于副本的無鎖自組織鏈表[14]。這個算法在鏈表數據結點的基礎上又引入了數據結點的副本結點。算法中對MTF自組織規則的執行只在副本結點中進行，而不會修改數據結點，從而巧妙地解決了由于MTF導致的由于其他線程將結點移動到鏈表頭部而導致可能出現的結點在鏈表中而搜索不到的問題。鏈表的實現較為簡單，但是增加了維護副本結點的空間開銷。

1 算法設計

本文實現了一個基于MTF規則的無鎖自組織鏈表算法。鏈表的結構如表1所示。

表1 無鎖MTF自組織鏈表結構及初始化

鏈表中的結點分為五個域：key域和next域分別表示結點的鍵值和指向下一個結點的指針；state域表示該結點目前所處的狀態：其中，DAT表示該結點可能屬于集合元素，REM表示該結點最終將要被邏輯刪除，INV表示該結點已經被邏輯刪除；result域表示操作的結果：FND表示找到目標結點，NFD表示沒有找到目標結點，UNK表示目前還沒有找到目標結點；friend指針域，指向當前結點的下一個朋友結點，所謂朋友結點，指的是鏈表中當前結點之后，與當前結點具有相同鍵值并且state=DAT的結點。在鏈表中，通過每個結點的firend指針形成相應的朋友鏈，同時用dummy來表示朋友結點的結束。

算法實現了鏈表的查找、刪除和插入方法。這三個方法的主要思想是在鏈表的頭部插入相應的操作結點，然后調用search方法向后進行鏈表的遍歷。同時在遍歷的過程中對朋友結點進行監聽。search方法是查找、刪除和插入操作的基礎和核心部分。

算法中對于在鏈表頭部插入的操作結點定義如下：

數據結點: state=DAT&result=FND

查找結點: state=DAT &result=UNK

刪除結點: state=REM&result=UNK

插入結點:數據結點+刪除結點

算法的偽代碼如表2-表6。

表2 search方法

表3 contains方法

表4 insert方法

表5 remove方法

表6 enlist方法

1.1 搜索操作

search方法是整個算法中的基礎算法，鏈表的插入、刪除，以及查找操作都會調用這個方法。search方法以home結點作為當前結點開始向后進行鏈表的遍歷，搜索與home結點鍵值相等的結點，處理并返回搜索結果的布爾值。

search方法在遍歷鏈表過程中，會遇到以下情況：

(1) 對home結點或新加入的朋友結點進行監聽，如果監聽到朋友結點得到NFD或者FND的搜索結果，則結束遍歷。

(2) 搜索到狀態為INV的結點，此結點表示已經被邏輯刪除，對其進行物理刪除，并繼續向后遍歷。

(3) 搜索到與home結點鍵值不相等的結點，繼續向后遍歷。

(4) 搜索到與home結點鍵值相等的狀態為DAT的數據結點或者搜索結點，此結點為朋友結點，將其加入到朋友鏈中，同時改為監聽此結點，并繼續向后遍歷。

(5) 搜索到與home結點鍵值相等狀態為REM的刪除結點，設置線程搜索結果result值為NFD，結束遍歷。

(6) 遍歷到鏈表尾部，結束遍歷。

search方法在結束遍歷之后，無論是自己得到操作結果還是從朋友結點監聽得到操作結果，都一定會得到FND或者NFD的結果。接下來線程將此結果通知到所有朋友結點，并對這些朋友結點進行邏輯刪除。

完成上述兩步操作之后，可以保證home結點之后將不存在與home結點鍵值相等的查找結點或者數據結點。

1.2 查找操作

contains方法是查找操作，方法以需要查找的鍵值作為參數，查找鏈表中具有相同鍵值的結點，并返回查找結果的布爾值。contains方法首先創建一個查找結點home={key=x，state=DAT，result=UNK}，并且調用enlist方法將該結點插入到鏈表的頭部，然后從該結點開始調用search方法進行遍歷，最后contains方法返回search方法的搜索結果。如果search方法返回true，則表示鏈表中home結點之后存在目標結點，并且在search方法返回之前將目標結點邏輯刪除，contains方法最初插入的查找結點作為數據結點，相當于執行了MTF操作，contains方法直接返回true，表示查找成功；如果search方法返回false，則表示鏈表中home結點之后不存在目標結點，contains方法將home結點邏輯刪除之后返回false表示查找失敗。

1.3 刪除操作

remove方法是刪除操作，方法將需要刪除的鍵值作為參數，刪除鏈表中具有相同鍵值的結點，并返回刪除是否成功的布爾值。

remove方法首先創建一個刪除結點home={key=x，state=REM，result=UNK}，并調用enlist方法將此結點插入到鏈表頭部，從該結點開始調用search方法對鏈表進行遍歷。如果search方法返回true，說明鏈表中home結點之后存在目標結點，并且在search方法返回之前將目標結點邏輯刪除，remove方法將home結點邏輯刪除后，返回true，表示刪除成功；如果search方法返回false，表示鏈表之中在home結點之后不存在目標結點，remove方法將home結點邏輯刪除后，返回false表示刪除失敗。

1.4 插入操作

insert方法為鏈表的插入操作，該方法以需要插入的鍵值為參數，向鏈表中插入該鍵值的結點，并且返回插入操作是否成功的布爾值。

insert方法首先創建一個數據結點和一個刪除結點。node={key=x，state=DAT，result=FND}是數據結點，home={key=x，state=REM，result=UNK}是刪除結點，并且node結點的next域指向home結點。接下來，以home結點為起始結點調用search方法進行鏈表的遍歷，如果search方法返回true，表示鏈表中home結點以后存在目標結點，并且在search方法返回之前已經將目標結點刪除，insert方法在search方法返回true之后，將home結點邏輯刪除。最初在鏈表頭部插入的數據結點相當于對原數據結點執行了MTF操作，最后insert方法返回false表示插入失敗；如果search方法返回false，表示鏈表之中home結點之后不存在目標結點，insert方法在search方法返回false之后，將home結點邏輯刪除。最初在鏈表頭部插入的數據結點相當于新插入的數據結點，并且執行了MTF操作，最后insert方法返回true表示插入成功。

1.5 結點加入操作

enlist方法是向鏈表頭部插入操作結點的方法。該方法輸入參數包括first結點和last結點，enlist方法首先將last結點指向head指向的結點，然后使用CAS操作扭轉head指針指向first結點。方法反復執行這一過程直至CAS操作成功。調用enlist方法將操作結點插入到鏈表頭部這一過程是無鎖的，當有多個線程同時執行這一操作時，至少有一個線程的CAS操作能夠成功執行并返回。

2 正確性證明

并發對象的行為可以用安全性和活性來描述，也稱為正確性和演進性[3]，安全性是指算法實現了一個抽象數據結構，活性指的是算法的演進性保證，包括阻塞特性和非阻塞特性。

常見的正確性條件有靜態一致性、順序一致性和可線性化特性。其中可線性化特性是一種較強的條件約束，適用于可線性化組件構成的高層系統[3]。本文使用可線性化特性作為算法的正確性條件。

本文中提出的算法沒有加鎖，同時保證了總有一個線程調用能夠在有限步驟內完成，具有無鎖的演進特性。

本文將在2.1節和2.2節分別對算法的可線性化性和無鎖特性進行說明。

2.1 算法的可線性化性

要證明算法實現的數據結構對應一個順序對象的可線性化實現，只需要找到一個可線性化點。

本節對算法的可線性化證明的主要框架是把算法的實現映射到一個抽象的整型集合，證明該算法實現了一個整形集合，并且算法中的每個成功的或者失敗的insert、remove，以及contains方法都在可線性化點上發生。

無鎖自組織鏈表實現了一個抽象的整數集合，由以h為起點的鏈表中元素到抽象集合的映射關系如下：

定義基于MTF無鎖自組織鏈表的可線性化點為：

insert(x)操作、remove(x)操作，以及contains(x)操作的可線性化點都在enlist中成功的CAS操作。

對于線程p執行insert(x)操作：若在執行CAS操作之前x?AbsSet(head)，如果p成功執行CAS操作，將鍵值為x的數據結點和刪除結點插入到鏈表中，那么insert(x)返回true，x∈AbsSet(head)；若在執行CAS操作之前x∈AbsSet(head)，如果p成功執行CAS操作，將鍵值為x的數據結點first和刪除結點last插入到鏈表中，相當于對鍵值為x的結點執行了MTF操作，并且search方法的執行保證了first結點之后不存在有效的鍵值為x的數據結點或查找結點。insert(x)返回false。

對于線程p執行remove(x)操作：若在執行CAS操作之前x?AbsSet(head)，如果p成功執行CAS操作，將鍵值為x的刪除結點插入到鏈表中，search方法的執行保證了刪除結點得到NFD的遍歷結果，remove(x)方法返回false；若在執行CAS操作之前x∈AbsSet(head)，如果p成功執行CAS操作，將鍵值為x的刪除結點插入到鏈表中，search方法的執行保證了刪除結點之后不存在鍵值為x的結點，成功執行了刪除操作，remove(x)方法返回true，且x?AbsSet(head)。

對于線程p執行contains(x)操作：若在執行CAS操作之前x?AbsSet(head)，如果p成功執行CAS操作，將鍵值為x的查找結點插入到鏈表中，search方法的執行保證了查找結點得到NFD的遍歷結果，contains(x)方法返回false；若在執行CAS操作之前x∈AbsSet(head)，如果p成功執行CAS操作，將鍵值為x的查找結點插入到鏈表中，相當于對鍵值為x的結點執行了MTF操作，同時保證了查找結點之后不存在鍵值為k的數據結點或查找結點，contains(x)返回true。

綜上所述，本文提出的基于MTF自組織規則的無鎖自組織鏈表是可線性化的。

2.2 算法的無鎖特性

該算法提供的關于鏈表的插入、刪除和查找操作都是先創建相應的操作結點，并調用enlist方法將操作結點加入到鏈表的頭部，接下來再進行search操作。

線程調用enlist方法將操作結點加入到鏈表頭部的過程需要循環調用CAS操作，直到操作成功。當有多個線程同時執行操作結點的加入，CAS操作可以保證至少有一個線程可以插入成功，因此這一個過程是無鎖的。

search方法對鏈表中的結點進行遍歷，并物理刪除已經被邏輯刪除的結點，search對結點的遍歷最長會遍歷到鏈表的尾部，而且鏈表是無環的，因此遍歷操作必然會在有限步驟內完成。

綜上所述，該算法的實現是無鎖的。

3 組織鏈表的性能分析

3.1 實驗環境與實驗內容

實驗是在4核8線程64位計算機上運行，計算機內存為8 GB，操作系統為Microsoft Windows 10，Java版本為1.8，算法在MyEclipse下用Java實現。

本實驗中共實現了三個算法：

Harris：Harris-Michael實現的無鎖有序的鏈表算法，鏈表中結點按升序排列；

MTFList：本文實現的基于MTF規則的無鎖自組織鏈表算法；

TanList：文獻[14]實現的基于副本的無鎖自組織鏈表方法。

本文中實驗所使用的實驗數據取自并發自組織搜索樹[15],使用的實驗數據來源是具有局部性的數據集[16]。數據集中包含了33 135 073條IP記錄，實驗中根據需要，將這些IP記錄通過哈希映射轉換為整形。實驗中每個線程從一個共享數組中相互獨立地獲取實驗數據。

在實驗中，通過在不同的操作比例和鍵值范圍下運行算法，以吞吐率作為算法的性能指標，查看隨著線程數目的變化，吞吐率的變化情況。其中操作比例指的是查找、插入和刪除操作的調用比例，分三種情況：34%/33%/33%、50%/45%/5%，以及90%/9%/1%；鍵值范圍指的是結點中鍵值的取值范圍，分為三種情況：0～512、0～2 048，以及0～8 192。實驗在初始化時，會預先向鏈表中插入數目為鍵值范圍一半的結點。在實驗過程中，線程根據選定的操作比例，隨機選擇操作類型。

3.2 實驗結果與實驗分析

根據操作比例和鍵值范圍的不同取值，實驗共分為9組，每組實驗運10次，每次運行5秒鐘，最終結果取平均值。實驗結果如圖1-圖9所示。

圖1 不同線程數下的吞吐率(鍵值范圍0～512，操作比例34%/33%/33%)

圖2 不同線程數下的吞吐率(鍵值范圍0～2 048，操作比例34%/33%/33%)

圖3 不同線程數下的吞吐率(鍵值范圍0～8 192，操作比例34%/33%/33%)

圖4 不同線程數下的吞吐率(鍵值范圍0～512，操作比例50%/45%/5%)

圖5 不同線程數下的吞吐率(鍵值范圍0～2 048，操作比例50%/45%/5%)

圖6 不同線程數下的吞吐率(鍵值范圍0～8 192，操作比例50%/45%/5%)

圖7 不同線程數下的吞吐率(鍵值范圍0～512，操作比例90%/9%/1%)

圖8 不同線程數下的吞吐率(鍵值范圍0～2 048，操作比例90%/9%/1%)

圖9 不同線程數下的吞吐率(鍵值范圍0～8 192，操作比例90%/9%/1%)

在每組實驗結果圖中，橫軸表示線程數目，縱軸表示吞吐率。通過實驗結果可以看出，在每組實驗中，隨著線程數目的增加，吞吐率也在增長。并且，與Harris和TanList兩個算法相比，本文提出的MTFList算法的實驗性能都是最好的。原因是該算法能充分利用數據的局部性，從而提高鏈表的訪問速率。

通過圖1、圖2和圖3，圖4、圖5和圖6，圖7、圖8和圖9可以看出，在操作比例不變的情況下，隨著鍵值范圍的增加，每個算法的吞吐率都有所下降，但隨著線程數目增加，每個算法吞吐率增加的基本趨勢是不變的。

通過圖1、圖4和圖7，圖2、圖5和圖8，圖3、圖6和圖9可以看出，在鍵值范圍不變的情況下，隨著查找和插入操作比例的增加，進行自組織操作的概率增加，本文提出的基于MTF無鎖自組織鏈表的算法性能優于其他兩個算法。

上述9組實驗，通過控制變量的方法，觀察了鍵值范圍、操作比例,以及線程數目對算法性能的影響，可以得出如下結論：

(1) 在固定的操作比例和鍵值范圍下，隨著線程數目的增加，每個算法的性能都有所提高。

(2) 隨著鍵值范圍的增大，鏈表初始化時，鏈表的長度增加，執行操作時平均訪問結點數目有所增加，因此，各個算法的性能都有所下降。

4 結 語

并發自組織鏈表能夠充分發揮多核處理器的優勢，在并發環境下可以通過動態調整訪問結點在鏈表中的位置來提高鏈表訪問效率，從而獲取更好的性能。鏈表的無鎖實現方式保證了總有一個線程能夠完成操作，與基于鎖的實現方式相比，避免了死鎖和優先級反轉等問題，具有更好的可靠性和健壯性；同時自組織鏈表在數據局部性較強的情況下，能夠表現出更好的執行性能。

本文對目前已有的并發鏈表進行了總結和歸納，并提出了一個基于MTF規則的無鎖自組織鏈表。并對新算法的可線性化性無鎖特性進行了討論。

本文設計的算法的實現是無鎖的，即保證了總有一個操作能夠完成操作。算法中，只有enlist的過程是無鎖的，其他的過程都可以在有限步驟內完成，具有無等待的特性。因此，對enlist算法進行修改，確保enlist操作能夠在有限步驟內完成，則可以實現一個無等待的MTF自組織鏈表。

針對并發環境下非阻塞自組織鏈表的研究還有很大的空間。除了MTF自組織規則，還有TP以及FC規則，都可以考慮將基于這些規則的鏈表應用于并發環境下。

[1] McCabe J. On serial files with relocatable records[J]. O-perations Research, 1965, 13(4): 609-618.

[2] Albers S, Westbrook J. Self-organizing data structures[M]//Online Algorithms. Springer Berlin Heidelberg, 1998: 13-51.

[3] Herlihy M, Shavit N. The Art of Multiprocessor Progra-mming, revised first edition[M]. Morgan Kaufmann, 2012.

[4] Valois J D. Lock-free linked lists using compare-and-swap[C]//Proceedings of the fourteenth annual ACM sympos-ium on Principles of distributed computing. ACM, 1995:214-222.

[5] Harris T L. A pragmatic implementation of non-blocking linked-lists[C]//International Symposium on Distributed C- omputing. Springer Berlin Heidelberg, 2001: 300-314.

[6] Michael M M. High performance dynamic lock-free hashtables and list-based sets[C]//Proceedings of the fourteent-h annual ACM symposium on Parallel algorithms and ar-chitectures. ACM, 2002: 73-82.

[7] Fomitchev M, Ruppert E. Lock-free linked lists and skip lists[C]//Proceedings of the twenty-third annual ACM sy-mposium on Principles of distributed computing. ACM, 2 004: 50-59.

[8] Braginsky A, Petrank E. Locality-conscious lock-free lin-ked lists[C]//International Conference on Distributed Computing and Networking. Springer Berlin Heidelberg, 2011:107-118.

[9] Timnat S, Braginsky A, Kogan A, et al. Wait-free linked-lists[C]//International Conference on Principles Of Distri-buted Systems. Springer Berlin Heidelberg, 2012: 330-344.

[10] Zhang K, Zhao Y, Yang Y, et al. Practical non-blockingunordered lists[C]//International Symposium on Distributed Computing. Springer Berlin Heidelberg, 2013: 239-253.

[11] Herlihy M P. Impossibility and universality results for wait-free synchronization[C]//Proceedings of the seventh annual ACM Symposium on Principles of distributed computing. ACM, 1988: 276-290.

[12] Herlihy M. Wait-free synchronization[J]. ACM Transacti-ons on Programming Languages and Systems (TOPLAS),1991, 13(1): 124-149.

[13] Barnes G. A method for implementing lock-free shared-data structures[C]//Proceedings of the fifth annual ACM symposium on Parallel algorithms and architectures. ACM,1993: 261-270.

[14] 譚龍飛. 基于副本的非阻塞自組織鏈表[D]. 天津： 天津大學, 2012.

[15] Korenfeld B. CBTree: A Practical Concurrent Self-Adjusting Search Tree[D]. Tel Aviv, Israel: Tel Aviv Universit-y, 2012.

[16] Kc Clay, Dan Andersen, Paul Hick. The caida anonymized 2011 internet traces[OL]. [2016-07-17]. http://www.caida.org/data/passive/passive_2011_dataset.xml.

NON-BLOCKING SELF-ORGANIZED LINKED LIST BASED ON MTF RULE

Kang Chaofan

(SchoolofComputerScienceandTechnology,TianjinUniversity,Tianjin300000,China)

Self-organized linked list is a special linked list. Comparing with the static linked list, we need to consider that self-organized operation would change the status of the linked list. Therefore, the study of concurrent self-organized list, especially the non-blocking self-organized linked list, is more complex. In recent years, the results of concurrent linked list have been significant, but studies on the linked list algorithms are few and far between. In this context, this paper proposes a lock-free self-organized linked list algorithm based on the move-to-front self-organized rule. The algorithm implements the insertion, deletion and searching operation on the set, and the implementation of the algorithm is lock-free. The experimental results show that the performance of the algorithm is superior to the Harris algorithm in most cases, and has a certain value.

Concurrency Lock-free Self-organized Linked List

2016-10-16。康超凡，碩士生，主研領域：并發數據結構。

TP311.11

A

10.3969/j.issn.1000-386x.2017.07.053