• <tr id="yyy80"></tr>
  • <sup id="yyy80"></sup>
  • <tfoot id="yyy80"><noscript id="yyy80"></noscript></tfoot>
  • 99热精品在线国产_美女午夜性视频免费_国产精品国产高清国产av_av欧美777_自拍偷自拍亚洲精品老妇_亚洲熟女精品中文字幕_www日本黄色视频网_国产精品野战在线观看 ?

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

    2017-08-12 15:45:56
    計算機應(yīng)用與軟件 2017年7期
    關(guān)鍵詞:鍵值鏈表線性化

    康 超 凡

    (天津大學(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

    猜你喜歡
    鍵值鏈表線性化
    非請勿進(jìn) 為注冊表的重要鍵值上把“鎖”
    “線性化”在多元不等式證明與最值求解中的應(yīng)用
    基于二進(jìn)制鏈表的粗糙集屬性約簡
    跟麥咭學(xué)編程
    基于反饋線性化的RLV氣動控制一體化設(shè)計
    基于鏈表多分支路徑樹的云存儲數(shù)據(jù)完整性驗證機制
    一鍵直達(dá) Windows 10注冊表編輯高招
    電腦愛好者(2017年9期)2017-06-01 21:38:08
    EHA反饋線性化最優(yōu)滑模面雙模糊滑??刂?/a>
    空間機械臂鎖緊機構(gòu)等效線性化分析及驗證
    鏈表方式集中器抄表的設(shè)計
    電測與儀表(2014年1期)2014-04-04 12:00:22
    高清欧美精品videossex| 三级国产精品片| 亚洲精品日本国产第一区| 少妇熟女欧美另类| 高清在线视频一区二区三区| 久久婷婷青草| 精品酒店卫生间| 三级国产精品欧美在线观看| 黄片无遮挡物在线观看| 97超视频在线观看视频| 超碰av人人做人人爽久久| 欧美xxxx黑人xx丫x性爽| 久久久久精品性色| 欧美高清性xxxxhd video| 久久国产精品男人的天堂亚洲 | 国产爽快片一区二区三区| 精品亚洲成国产av| 日韩在线高清观看一区二区三区| 亚洲经典国产精华液单| 人妻夜夜爽99麻豆av| 国产精品偷伦视频观看了| 日日撸夜夜添| 久久99热这里只频精品6学生| 一区二区三区乱码不卡18| 午夜激情福利司机影院| 最近最新中文字幕大全电影3| 国产又色又爽无遮挡免| 日本-黄色视频高清免费观看| 只有这里有精品99| 国产精品欧美亚洲77777| 深爱激情五月婷婷| 男男h啪啪无遮挡| 中文乱码字字幕精品一区二区三区| 亚洲精品456在线播放app| 老女人水多毛片| 麻豆成人av视频| 一级毛片黄色毛片免费观看视频| 欧美日韩精品成人综合77777| 大片电影免费在线观看免费| 国精品久久久久久国模美| 亚洲国产精品成人久久小说| 高清在线视频一区二区三区| 麻豆成人av视频| 男女免费视频国产| 菩萨蛮人人尽说江南好唐韦庄| 91久久精品国产一区二区三区| av卡一久久| 中文乱码字字幕精品一区二区三区| 日韩一区二区三区影片| 亚洲国产毛片av蜜桃av| 岛国毛片在线播放| 国产黄频视频在线观看| 日本猛色少妇xxxxx猛交久久| 女人十人毛片免费观看3o分钟| 亚洲精品日本国产第一区| 亚洲av不卡在线观看| 久久精品国产亚洲网站| 国产精品麻豆人妻色哟哟久久| 不卡视频在线观看欧美| 只有这里有精品99| 天堂8中文在线网| 精品一区二区三区视频在线| 亚洲人成网站高清观看| 亚洲最大成人中文| 只有这里有精品99| 国产精品爽爽va在线观看网站| av国产久精品久网站免费入址| 国产中年淑女户外野战色| 国产乱人偷精品视频| 尾随美女入室| 日日摸夜夜添夜夜爱| 国产高清有码在线观看视频| 久久人人爽人人片av| videos熟女内射| 国产伦在线观看视频一区| 亚洲,欧美,日韩| 国产高潮美女av| 视频区图区小说| 亚洲精品国产成人久久av| 高清欧美精品videossex| 国产91av在线免费观看| 99国产精品免费福利视频| 在线观看av片永久免费下载| 草草在线视频免费看| 我要看日韩黄色一级片| 国产 精品1| 尤物成人国产欧美一区二区三区| 五月开心婷婷网| av播播在线观看一区| 大片电影免费在线观看免费| 啦啦啦视频在线资源免费观看| 水蜜桃什么品种好| 男女无遮挡免费网站观看| 国产在线免费精品| 亚洲精品,欧美精品| 一级片'在线观看视频| 天天躁日日操中文字幕| 国产精品伦人一区二区| av专区在线播放| 女性生殖器流出的白浆| 国产精品久久久久久久电影| 一区二区av电影网| 黄色怎么调成土黄色| 国产黄色视频一区二区在线观看| 国产免费又黄又爽又色| av.在线天堂| 在线观看一区二区三区| 免费观看性生交大片5| 国产精品99久久99久久久不卡 | 国产欧美亚洲国产| 街头女战士在线观看网站| 一级片'在线观看视频| 18禁裸乳无遮挡免费网站照片| 婷婷色av中文字幕| 熟女av电影| 一级毛片黄色毛片免费观看视频| 少妇人妻久久综合中文| 在线观看免费高清a一片| 在线免费观看不下载黄p国产| 国产 一区 欧美 日韩| 纯流量卡能插随身wifi吗| 亚洲欧美成人精品一区二区| 日日啪夜夜撸| 成人黄色视频免费在线看| 免费大片18禁| 国产精品伦人一区二区| 少妇高潮的动态图| 又粗又硬又长又爽又黄的视频| 国产在视频线精品| 一个人免费看片子| 亚洲国产高清在线一区二区三| 久久精品国产自在天天线| 亚洲精品国产色婷婷电影| 精品久久久精品久久久| av线在线观看网站| .国产精品久久| 久久国产乱子免费精品| 国产精品国产三级国产av玫瑰| 亚洲,一卡二卡三卡| 久久久久性生活片| 亚洲国产毛片av蜜桃av| 人妻夜夜爽99麻豆av| 边亲边吃奶的免费视频| 有码 亚洲区| 一区二区三区免费毛片| av线在线观看网站| 男人添女人高潮全过程视频| 亚洲精品自拍成人| 精品一区在线观看国产| 精品人妻熟女av久视频| 免费看av在线观看网站| 亚洲精华国产精华液的使用体验| 日日啪夜夜撸| 我要看日韩黄色一级片| 99热这里只有是精品在线观看| 日韩一区二区视频免费看| 最近中文字幕2019免费版| 国产一区二区在线观看日韩| 久久97久久精品| 免费黄色在线免费观看| 欧美老熟妇乱子伦牲交| 国产午夜精品久久久久久一区二区三区| 精品久久国产蜜桃| 欧美成人一区二区免费高清观看| 亚洲成人一二三区av| 久久久精品免费免费高清| 插逼视频在线观看| 国产一区二区三区av在线| 99九九线精品视频在线观看视频| 99热6这里只有精品| 成年女人在线观看亚洲视频| 亚洲av中文av极速乱| 多毛熟女@视频| 18禁在线无遮挡免费观看视频| 最近最新中文字幕大全电影3| 国产一区二区三区综合在线观看 | 亚洲伊人久久精品综合| 男男h啪啪无遮挡| 亚洲精品国产av蜜桃| 日韩,欧美,国产一区二区三区| 国产 一区精品| 一级二级三级毛片免费看| 久久精品夜色国产| 亚洲av中文字字幕乱码综合| 亚洲精品国产成人久久av| 国产精品福利在线免费观看| 少妇人妻 视频| 人人妻人人看人人澡| 18禁裸乳无遮挡动漫免费视频| 又大又黄又爽视频免费| 精品人妻视频免费看| av在线观看视频网站免费| 国产一区二区三区综合在线观看 | 亚洲精品aⅴ在线观看| 夫妻性生交免费视频一级片| 亚洲最大成人中文| 成人午夜精彩视频在线观看| 国产v大片淫在线免费观看| 欧美日韩亚洲高清精品| 美女视频免费永久观看网站| 成年av动漫网址| 波野结衣二区三区在线| av天堂中文字幕网| 最新中文字幕久久久久| 亚洲人与动物交配视频| 人妻一区二区av| 欧美日韩视频精品一区| 国语对白做爰xxxⅹ性视频网站| 亚洲欧美日韩另类电影网站 | 午夜激情福利司机影院| videos熟女内射| 亚洲精品aⅴ在线观看| 男女国产视频网站| 久久久久久久大尺度免费视频| 国产精品一区二区三区四区免费观看| 日韩制服骚丝袜av| 亚洲精品国产av成人精品| 亚洲国产毛片av蜜桃av| 黄色一级大片看看| av网站免费在线观看视频| 我的女老师完整版在线观看| 国产精品嫩草影院av在线观看| 男女无遮挡免费网站观看| 亚洲精品自拍成人| 国产高清有码在线观看视频| videos熟女内射| 国产永久视频网站| 国产精品女同一区二区软件| 国产久久久一区二区三区| 人体艺术视频欧美日本| 九色成人免费人妻av| 中文乱码字字幕精品一区二区三区| 赤兔流量卡办理| 欧美精品人与动牲交sv欧美| 国产综合精华液| 特大巨黑吊av在线直播| 久久国产精品大桥未久av | 婷婷色综合大香蕉| 91精品国产国语对白视频| 欧美成人午夜免费资源| 国产女主播在线喷水免费视频网站| 国产视频首页在线观看| 国产在线一区二区三区精| 亚洲欧美一区二区三区黑人 | 高清在线视频一区二区三区| 九九在线视频观看精品| 男女国产视频网站| 久久精品国产a三级三级三级| 大陆偷拍与自拍| 丰满迷人的少妇在线观看| 久久久久久久国产电影| 交换朋友夫妻互换小说| 国产成人免费无遮挡视频| 久久精品国产鲁丝片午夜精品| 男人舔奶头视频| 国精品久久久久久国模美| 在线观看人妻少妇| 插逼视频在线观看| 一级二级三级毛片免费看| 大又大粗又爽又黄少妇毛片口| 22中文网久久字幕| 天天躁日日操中文字幕| 少妇的逼水好多| 亚洲精品自拍成人| 一本一本综合久久| 亚洲国产精品999| 一区二区av电影网| 亚洲精品第二区| 夜夜看夜夜爽夜夜摸| 国产亚洲午夜精品一区二区久久| 极品教师在线视频| 亚洲欧美精品自产自拍| 好男人视频免费观看在线| 男女无遮挡免费网站观看| 黄片无遮挡物在线观看| 中文字幕精品免费在线观看视频 | 夜夜看夜夜爽夜夜摸| 夫妻午夜视频| 蜜桃久久精品国产亚洲av| 夜夜看夜夜爽夜夜摸| 日韩强制内射视频| 在线观看一区二区三区激情| 欧美日韩视频精品一区| 色婷婷久久久亚洲欧美| 成人一区二区视频在线观看| 国产av精品麻豆| 日韩av免费高清视频| 成人二区视频| 成人亚洲精品一区在线观看 | 国产精品爽爽va在线观看网站| 欧美极品一区二区三区四区| 2022亚洲国产成人精品| 丰满少妇做爰视频| 中文资源天堂在线| 久久久久久伊人网av| 精品一区二区三区视频在线| 不卡视频在线观看欧美| 日本猛色少妇xxxxx猛交久久| 97在线人人人人妻| 亚洲美女黄色视频免费看| 精品久久久久久久末码| kizo精华| 18禁裸乳无遮挡动漫免费视频| 免费在线观看成人毛片| 美女脱内裤让男人舔精品视频| 亚洲av.av天堂| 国产片特级美女逼逼视频| 日韩,欧美,国产一区二区三区| 在线观看国产h片| 亚洲精品乱码久久久v下载方式| 身体一侧抽搐| 啦啦啦视频在线资源免费观看| 狠狠精品人妻久久久久久综合| 蜜臀久久99精品久久宅男| 91精品国产国语对白视频| 久久精品熟女亚洲av麻豆精品| 国产一区二区三区av在线| 夜夜骑夜夜射夜夜干| 国产伦精品一区二区三区四那| 亚洲欧美成人综合另类久久久| 午夜激情福利司机影院| 亚洲电影在线观看av| 亚洲av电影在线观看一区二区三区| 国产久久久一区二区三区| 午夜福利高清视频| 亚洲欧美日韩卡通动漫| 久久精品国产a三级三级三级| 午夜福利高清视频| 啦啦啦视频在线资源免费观看| 国产一区有黄有色的免费视频| 寂寞人妻少妇视频99o| 一级毛片久久久久久久久女| 亚洲精品成人av观看孕妇| 国产精品一区二区三区四区免费观看| 精品久久国产蜜桃| av线在线观看网站| 天天躁夜夜躁狠狠久久av| 成人18禁高潮啪啪吃奶动态图 | 嘟嘟电影网在线观看| 久久久久久久久久人人人人人人| 成人漫画全彩无遮挡| 亚洲图色成人| 国产永久视频网站| 中文字幕精品免费在线观看视频 | 亚洲精品亚洲一区二区| 国产成人a∨麻豆精品| 国产欧美日韩精品一区二区| 成人毛片a级毛片在线播放| 黄色怎么调成土黄色| 日韩电影二区| 日韩精品有码人妻一区| 欧美丝袜亚洲另类| av天堂中文字幕网| 成人特级av手机在线观看| 国产爽快片一区二区三区| 国产精品一区二区性色av| 国产黄片视频在线免费观看| 国产欧美日韩精品一区二区| 久久久成人免费电影| 久久精品国产亚洲网站| 欧美日韩一区二区视频在线观看视频在线| 日韩成人av中文字幕在线观看| 欧美高清性xxxxhd video| 久久久亚洲精品成人影院| 国产免费视频播放在线视频| 国产成人午夜福利电影在线观看| 亚洲怡红院男人天堂| 99热6这里只有精品| 插逼视频在线观看| 天美传媒精品一区二区| 免费人成在线观看视频色| 日韩av不卡免费在线播放| 精品久久久精品久久久| 黄色一级大片看看| 少妇裸体淫交视频免费看高清| 老师上课跳d突然被开到最大视频| 亚洲成人中文字幕在线播放| 日韩一区二区三区影片| 久久久久久九九精品二区国产| 91精品伊人久久大香线蕉| a级一级毛片免费在线观看| 日本vs欧美在线观看视频 | 国产视频内射| 国产成人精品久久久久久| 久久6这里有精品| 成年女人在线观看亚洲视频| 草草在线视频免费看| 美女福利国产在线 | 国产av精品麻豆| 免费大片18禁| 国产欧美日韩精品一区二区| 日本vs欧美在线观看视频 | 亚洲综合精品二区| 欧美人与善性xxx| 2018国产大陆天天弄谢| 99热这里只有是精品50| 国产精品av视频在线免费观看| 久久精品夜色国产| 色网站视频免费| 超碰av人人做人人爽久久| tube8黄色片| 少妇人妻一区二区三区视频| 下体分泌物呈黄色| 最近中文字幕2019免费版| 日韩成人av中文字幕在线观看| 亚洲丝袜综合中文字幕| 日本vs欧美在线观看视频 | 91狼人影院| 日本av手机在线免费观看| 国产在线视频一区二区| 成人无遮挡网站| 国产熟女欧美一区二区| 久久久色成人| 国产精品国产三级专区第一集| 国产视频内射| 日韩精品有码人妻一区| 少妇精品久久久久久久| 久久久精品94久久精品| 不卡视频在线观看欧美| 能在线免费看毛片的网站| 午夜福利在线观看免费完整高清在| 亚洲av免费高清在线观看| 高清午夜精品一区二区三区| 久久国内精品自在自线图片| 欧美精品人与动牲交sv欧美| 欧美丝袜亚洲另类| 最黄视频免费看| 少妇人妻精品综合一区二区| 欧美xxⅹ黑人| 亚洲婷婷狠狠爱综合网| 亚洲国产日韩一区二区| 亚洲av电影在线观看一区二区三区| 中文字幕久久专区| 色婷婷av一区二区三区视频| 99久久人妻综合| 国产精品福利在线免费观看| 欧美xxxx性猛交bbbb| 99精国产麻豆久久婷婷| 大片电影免费在线观看免费| 久久久欧美国产精品| 免费久久久久久久精品成人欧美视频 | h视频一区二区三区| 久久久久久久久大av| 欧美日韩亚洲高清精品| 国产黄频视频在线观看| 美女xxoo啪啪120秒动态图| h视频一区二区三区| 精品人妻视频免费看| 在线免费观看不下载黄p国产| 三级国产精品欧美在线观看| 久久韩国三级中文字幕| 人妻一区二区av| 男女国产视频网站| 美女中出高潮动态图| 我的女老师完整版在线观看| 如何舔出高潮| 精华霜和精华液先用哪个| 如何舔出高潮| 26uuu在线亚洲综合色| 婷婷色av中文字幕| 亚洲欧美日韩无卡精品| 国产成人a∨麻豆精品| 国产黄片美女视频| 久久青草综合色| 熟女av电影| 麻豆国产97在线/欧美| 国产成人精品一,二区| 丰满人妻一区二区三区视频av| 一级av片app| 99精国产麻豆久久婷婷| 夜夜骑夜夜射夜夜干| 国产av码专区亚洲av| 有码 亚洲区| 乱码一卡2卡4卡精品| 高清日韩中文字幕在线| 亚洲国产精品国产精品| 菩萨蛮人人尽说江南好唐韦庄| 晚上一个人看的免费电影| 欧美日韩视频精品一区| 蜜桃亚洲精品一区二区三区| 日本与韩国留学比较| 亚洲婷婷狠狠爱综合网| 国产女主播在线喷水免费视频网站| 国产精品久久久久久精品电影小说 | 国产有黄有色有爽视频| 丰满少妇做爰视频| h日本视频在线播放| 在线观看美女被高潮喷水网站| 在线播放无遮挡| 亚洲国产精品一区三区| 色5月婷婷丁香| 久久影院123| 日韩欧美一区视频在线观看 | 国产高清不卡午夜福利| 一区二区三区乱码不卡18| 波野结衣二区三区在线| 一区二区三区免费毛片| 99视频精品全部免费 在线| 国产免费视频播放在线视频| av.在线天堂| 熟女人妻精品中文字幕| 日韩av在线免费看完整版不卡| 国产精品嫩草影院av在线观看| 日产精品乱码卡一卡2卡三| 国产69精品久久久久777片| av在线观看视频网站免费| 亚洲精品成人av观看孕妇| 黄片无遮挡物在线观看| 亚洲美女搞黄在线观看| 日本vs欧美在线观看视频 | 我要看黄色一级片免费的| 国产高清不卡午夜福利| 丰满少妇做爰视频| 大陆偷拍与自拍| 能在线免费看毛片的网站| 精品国产露脸久久av麻豆| 欧美xxxx黑人xx丫x性爽| 亚洲中文av在线| 午夜福利视频精品| 免费人成在线观看视频色| 色哟哟·www| 久热久热在线精品观看| 精品国产三级普通话版| 日日啪夜夜爽| 最近最新中文字幕免费大全7| 伊人久久国产一区二区| 一区二区三区精品91| 精品亚洲成a人片在线观看 | a级毛片免费高清观看在线播放| 人妻 亚洲 视频| 美女主播在线视频| 国产黄色视频一区二区在线观看| freevideosex欧美| 久久精品久久久久久久性| av在线观看视频网站免费| 成人二区视频| 最新中文字幕久久久久| 在线观看人妻少妇| 国产国拍精品亚洲av在线观看| 日韩视频在线欧美| 麻豆国产97在线/欧美| 日韩欧美一区视频在线观看 | 久久精品久久精品一区二区三区| 在线精品无人区一区二区三 | 国产一区有黄有色的免费视频| 国产国拍精品亚洲av在线观看| 男女无遮挡免费网站观看| 欧美国产精品一级二级三级 | 青春草亚洲视频在线观看| 日日摸夜夜添夜夜添av毛片| 青春草亚洲视频在线观看| 新久久久久国产一级毛片| 2022亚洲国产成人精品| 亚洲国产成人一精品久久久| 十分钟在线观看高清视频www | 少妇熟女欧美另类| 久久久久国产精品人妻一区二区| 国产亚洲5aaaaa淫片| 三级国产精品片| 一本—道久久a久久精品蜜桃钙片| 日韩成人伦理影院| 插阴视频在线观看视频| 只有这里有精品99| 免费少妇av软件| 日本爱情动作片www.在线观看| 国产成人精品久久久久久| 中文字幕亚洲精品专区| 日本猛色少妇xxxxx猛交久久| 亚洲经典国产精华液单| a级毛色黄片| 精品午夜福利在线看| 国产在线视频一区二区| 黄色视频在线播放观看不卡| 日韩不卡一区二区三区视频在线| 国产精品人妻久久久久久| 亚洲欧美清纯卡通| 婷婷色综合大香蕉| 午夜视频国产福利| 一本久久精品| 五月伊人婷婷丁香| 国产av一区二区精品久久 | 国产精品不卡视频一区二区| 久久国内精品自在自线图片| 国产一区二区在线观看日韩| 国产午夜精品一二区理论片| 国产免费一区二区三区四区乱码| 国产精品福利在线免费观看| 亚洲三级黄色毛片| 少妇猛男粗大的猛烈进出视频| 2022亚洲国产成人精品| 国产日韩欧美在线精品| 国产av国产精品国产| 午夜日本视频在线| 国产大屁股一区二区在线视频| 久久99热这里只频精品6学生| 日韩人妻高清精品专区| 97在线人人人人妻| 黄色怎么调成土黄色| 久久热精品热| 丝袜喷水一区| 免费观看性生交大片5| 国产精品一区二区性色av| 亚洲精品乱码久久久v下载方式| 成人漫画全彩无遮挡| 两个人的视频大全免费| 伊人久久国产一区二区| 日本av手机在线免费观看| 日韩av不卡免费在线播放| 国产色爽女视频免费观看| 久久国产亚洲av麻豆专区| 一区二区三区精品91| 久久精品熟女亚洲av麻豆精品| 能在线免费看毛片的网站| 婷婷色综合大香蕉| 91精品一卡2卡3卡4卡|