康 超 凡

(天津大學(xué)計算機科學(xué)與技術(shù)學(xué)院 天津 300000)

?

基于MTF規(guī)則的非阻塞自組織鏈表

康 超 凡

(天津大學(xué)計算機科學(xué)與技術(shù)學(xué)院 天津 300000)

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

并發(fā) 無鎖 自組織 鏈表

0 引 言

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

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

在當(dāng)前的多核處理器時代，并發(fā)程序與傳統(tǒng)的串行程序相比，更能充分發(fā)揮多核處理器的優(yōu)勢。近些年來，并發(fā)程序設(shè)計問題成為人們重點研究和討論的問題。

數(shù)據(jù)結(jié)構(gòu)是程序設(shè)計的基礎(chǔ)與核心，鏈表是一種常見的數(shù)據(jù)結(jié)構(gòu)，為了發(fā)揮多處理器的優(yōu)勢，并發(fā)鏈表的設(shè)計與實現(xiàn)，具有重要的意義。根據(jù)不同的同步機制，并發(fā)鏈表可以分為阻塞鏈表和非阻塞鏈表。

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

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

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

自組織鏈表是一種非常具有實用價值的數(shù)據(jù)結(jié)構(gòu)，將自組織鏈表應(yīng)用于并發(fā)環(huán)境下，可以充分發(fā)揮多核處理器的優(yōu)勢，獲得更好的執(zhí)行性能。阻塞方式的實現(xiàn)簡單，但是加鎖的方法使算法難以實現(xiàn)高并行性；非阻塞方式與阻塞方式相比具有更好的可靠性和健壯性。Herlihy[11-13]等證明了使用CAS操作原語能夠?qū)崿F(xiàn)任何非阻塞數(shù)據(jù)結(jié)構(gòu)，但是這種通用構(gòu)造的方法實現(xiàn)較為復(fù)雜，并且效率不高。因此，對于實現(xiàn)非阻塞自組織鏈表算法，需要更加精細(xì)的設(shè)計。

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

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

1 算法設(shè)計

本文實現(xiàn)了一個基于MTF規(guī)則的無鎖自組織鏈表算法。鏈表的結(jié)構(gòu)如表1所示。

表1 無鎖MTF自組織鏈表結(jié)構(gòu)及初始化

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

算法實現(xiàn)了鏈表的查找、刪除和插入方法。這三個方法的主要思想是在鏈表的頭部插入相應(yīng)的操作結(jié)點，然后調(diào)用search方法向后進(jìn)行鏈表的遍歷。同時在遍歷的過程中對朋友結(jié)點進(jìn)行監(jiān)聽。search方法是查找、刪除和插入操作的基礎(chǔ)和核心部分。

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

數(shù)據(jù)結(jié)點: state=DAT&result=FND

查找結(jié)點: state=DAT &result=UNK

刪除結(jié)點: state=REM&result=UNK

插入結(jié)點:數(shù)據(jù)結(jié)點+刪除結(jié)點

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

表2 search方法

表3 contains方法

表4 insert方法

表5 remove方法

表6 enlist方法

1.1 搜索操作

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

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

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

(2) 搜索到狀態(tài)為INV的結(jié)點，此結(jié)點表示已經(jīng)被邏輯刪除，對其進(jìn)行物理刪除，并繼續(xù)向后遍歷。

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

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

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

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

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

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

1.2 查找操作

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

1.3 刪除操作

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

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

1.4 插入操作

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

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

1.5 結(jié)點加入操作

enlist方法是向鏈表頭部插入操作結(jié)點的方法。該方法輸入?yún)?shù)包括first結(jié)點和last結(jié)點，enlist方法首先將last結(jié)點指向head指向的結(jié)點，然后使用CAS操作扭轉(zhuǎn)head指針指向first結(jié)點。方法反復(fù)執(zhí)行這一過程直至CAS操作成功。調(diào)用enlist方法將操作結(jié)點插入到鏈表頭部這一過程是無鎖的，當(dāng)有多個線程同時執(zhí)行這一操作時，至少有一個線程的CAS操作能夠成功執(zhí)行并返回。

2 正確性證明

并發(fā)對象的行為可以用安全性和活性來描述，也稱為正確性和演進(jìn)性[3]，安全性是指算法實現(xiàn)了一個抽象數(shù)據(jù)結(jié)構(gòu)，活性指的是算法的演進(jìn)性保證，包括阻塞特性和非阻塞特性。

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

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

本文將在2.1節(jié)和2.2節(jié)分別對算法的可線性化性和無鎖特性進(jìn)行說明。

2.1 算法的可線性化性

要證明算法實現(xiàn)的數(shù)據(jù)結(jié)構(gòu)對應(yīng)一個順序?qū)ο蟮目删€性化實現(xiàn)，只需要找到一個可線性化點。

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

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

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

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

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

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

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

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

2.2 算法的無鎖特性

該算法提供的關(guān)于鏈表的插入、刪除和查找操作都是先創(chuàng)建相應(yīng)的操作結(jié)點，并調(diào)用enlist方法將操作結(jié)點加入到鏈表的頭部，接下來再進(jìn)行search操作。

線程調(diào)用enlist方法將操作結(jié)點加入到鏈表頭部的過程需要循環(huán)調(diào)用CAS操作，直到操作成功。當(dāng)有多個線程同時執(zhí)行操作結(jié)點的加入，CAS操作可以保證至少有一個線程可以插入成功，因此這一個過程是無鎖的。

search方法對鏈表中的結(jié)點進(jìn)行遍歷，并物理刪除已經(jīng)被邏輯刪除的結(jié)點，search對結(jié)點的遍歷最長會遍歷到鏈表的尾部，而且鏈表是無環(huán)的，因此遍歷操作必然會在有限步驟內(nèi)完成。

綜上所述，該算法的實現(xiàn)是無鎖的。

3 組織鏈表的性能分析

3.1 實驗環(huán)境與實驗內(nèi)容

實驗是在4核8線程64位計算機上運行，計算機內(nèi)存為8 GB，操作系統(tǒng)為Microsoft Windows 10，Java版本為1.8，算法在MyEclipse下用Java實現(xiàn)。

本實驗中共實現(xiàn)了三個算法：

Harris：Harris-Michael實現(xiàn)的無鎖有序的鏈表算法，鏈表中結(jié)點按升序排列；

MTFList：本文實現(xiàn)的基于MTF規(guī)則的無鎖自組織鏈表算法；

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

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

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

3.2 實驗結(jié)果與實驗分析

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié) 語

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

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

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

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

[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]. 天津： 天津大學(xué), 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。康超凡，碩士生，主研領(lǐng)域：并發(fā)數(shù)據(jù)結(jié)構(gòu)。

TP311.11

A

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