康 超 凡

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

?

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

康 超 凡

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

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

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

0 引 言

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

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

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

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

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

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

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

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

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

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

1 算法設(shè)計(jì)

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

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

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

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

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

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

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

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

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

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

表2 search方法

表3 contains方法

表4 insert方法

表5 remove方法

表6 enlist方法

1.1 搜索操作

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

search方法在遍歷鏈表過(guò)程中，會(huì)遇到以下情況：

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

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

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

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

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

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

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

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

1.2 查找操作

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

1.3 刪除操作

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

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

1.4 插入操作

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

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

1.5 結(jié)點(diǎn)加入操作

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

2 正確性證明

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

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

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

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

2.1 算法的可線性化性

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

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

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

定義基于MTF無(wú)鎖自組織鏈表的可線性化點(diǎn)為：

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

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

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

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

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

2.2 算法的無(wú)鎖特性

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

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

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

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

3 組織鏈表的性能分析

3.1 實(shí)驗(yàn)環(huán)境與實(shí)驗(yàn)內(nèi)容

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

本實(shí)驗(yàn)中共實(shí)現(xiàn)了三個(gè)算法：

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

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

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

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

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

3.2 實(shí)驗(yàn)結(jié)果與實(shí)驗(yàn)分析

根據(jù)操作比例和鍵值范圍的不同取值，實(shí)驗(yàn)共分為9組，每組實(shí)驗(yàn)運(yùn)10次，每次運(yùn)行5秒鐘，最終結(jié)果取平均值。實(shí)驗(yàn)結(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%)

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

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

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

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

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

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

4 結(jié) 語(yǔ)

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

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

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

針對(duì)并發(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?？党玻T士生，主研領(lǐng)域：并發(fā)數(shù)據(jù)結(jié)構(gòu)。

TP311.11

A

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