• <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
    不卡av一区二区三区| 自线自在国产av| 日韩成人在线观看一区二区三区| 国产精品久久久久久亚洲av鲁大| 国产精品免费视频内射| 俄罗斯特黄特色一大片| 亚洲欧美日韩无卡精品| 老司机在亚洲福利影院| 黑丝袜美女国产一区| 韩国精品一区二区三区| 麻豆久久精品国产亚洲av| 丝袜在线中文字幕| 国产av在哪里看| 亚洲国产看品久久| 国产精品日韩av在线免费观看| 日韩大码丰满熟妇| 一卡2卡三卡四卡精品乱码亚洲| 午夜日韩欧美国产| 日本黄色视频三级网站网址| 欧美黑人精品巨大| 少妇被粗大的猛进出69影院| 男人舔女人的私密视频| 国产日本99.免费观看| 久99久视频精品免费| 99久久国产精品久久久| 午夜亚洲福利在线播放| 亚洲五月天丁香| 国产亚洲精品久久久久5区| 日韩大码丰满熟妇| 美女扒开内裤让男人捅视频| 国产伦在线观看视频一区| 色播在线永久视频| 身体一侧抽搐| 99热只有精品国产| 最近最新免费中文字幕在线| 精品日产1卡2卡| 国产伦在线观看视频一区| 婷婷精品国产亚洲av在线| 国产午夜精品久久久久久| 91国产中文字幕| 欧美中文综合在线视频| 亚洲一区中文字幕在线| 欧美av亚洲av综合av国产av| 精品久久久久久久毛片微露脸| 久久久国产成人免费| 成人18禁高潮啪啪吃奶动态图| 欧美激情久久久久久爽电影| 久久国产精品影院| 女人高潮潮喷娇喘18禁视频| 欧美黑人精品巨大| 久久久久久国产a免费观看| 两性夫妻黄色片| 黄色丝袜av网址大全| 欧美激情久久久久久爽电影| 搡老岳熟女国产| 久久中文字幕人妻熟女| x7x7x7水蜜桃| 国产成人精品久久二区二区免费| 欧美亚洲日本最大视频资源| 亚洲成av片中文字幕在线观看| 久久久久九九精品影院| 国产精品永久免费网站| 曰老女人黄片| 97人妻精品一区二区三区麻豆 | 日韩高清综合在线| 美女扒开内裤让男人捅视频| 日本熟妇午夜| 免费看a级黄色片| 嫩草影院精品99| 美女 人体艺术 gogo| 国产99久久九九免费精品| 亚洲三区欧美一区| 色综合亚洲欧美另类图片| 人成视频在线观看免费观看| 欧美成人免费av一区二区三区| 好看av亚洲va欧美ⅴa在| 免费在线观看影片大全网站| 亚洲国产欧洲综合997久久, | 婷婷精品国产亚洲av在线| 90打野战视频偷拍视频| 国产麻豆成人av免费视频| 脱女人内裤的视频| 国产99白浆流出| 国产精品免费一区二区三区在线| 十八禁人妻一区二区| 黄色丝袜av网址大全| 国产精品98久久久久久宅男小说| 久久精品夜夜夜夜夜久久蜜豆 | 桃红色精品国产亚洲av| 91大片在线观看| 亚洲熟女毛片儿| 免费av毛片视频| 这个男人来自地球电影免费观看| 国产久久久一区二区三区| 亚洲色图av天堂| 99re在线观看精品视频| av视频在线观看入口| 久久精品国产99精品国产亚洲性色| 国产亚洲精品av在线| 伊人久久大香线蕉亚洲五| av有码第一页| 在线观看日韩欧美| 久久青草综合色| 午夜视频精品福利| 99在线人妻在线中文字幕| 嫁个100分男人电影在线观看| 两个人看的免费小视频| 国产午夜福利久久久久久| 1024香蕉在线观看| 18禁裸乳无遮挡免费网站照片 | 日韩精品免费视频一区二区三区| 亚洲黑人精品在线| 国产v大片淫在线免费观看| 欧美绝顶高潮抽搐喷水| 在线观看一区二区三区| 老鸭窝网址在线观看| 国产精品永久免费网站| 一区二区三区激情视频| 免费电影在线观看免费观看| 久久久久久久精品吃奶| 国产亚洲精品久久久久5区| 成人国产综合亚洲| av电影中文网址| 亚洲五月色婷婷综合| 午夜免费成人在线视频| 岛国视频午夜一区免费看| 亚洲精品中文字幕一二三四区| 国产国语露脸激情在线看| 成人18禁高潮啪啪吃奶动态图| 不卡一级毛片| 日韩三级视频一区二区三区| 三级毛片av免费| 国产成人精品久久二区二区免费| 人人妻人人澡欧美一区二区| 国产伦人伦偷精品视频| 婷婷丁香在线五月| 国产精品免费视频内射| 亚洲久久久国产精品| 久久午夜亚洲精品久久| 一级毛片精品| 亚洲成人精品中文字幕电影| 听说在线观看完整版免费高清| 性欧美人与动物交配| 老司机深夜福利视频在线观看| 亚洲国产精品sss在线观看| 嫩草影院精品99| 欧美一级毛片孕妇| 欧美成人午夜精品| 美女高潮喷水抽搐中文字幕| 国产精品美女特级片免费视频播放器 | 国产三级在线视频| 天天添夜夜摸| 成年女人毛片免费观看观看9| 亚洲一区中文字幕在线| 国内精品久久久久久久电影| 亚洲 欧美一区二区三区| 少妇粗大呻吟视频| 露出奶头的视频| 亚洲第一欧美日韩一区二区三区| 老熟妇乱子伦视频在线观看| 国产91精品成人一区二区三区| 午夜精品在线福利| 热re99久久国产66热| 搡老岳熟女国产| 一边摸一边抽搐一进一小说| 精品国产乱子伦一区二区三区| 久久久久久人人人人人| 欧美性猛交╳xxx乱大交人| 国产v大片淫在线免费观看| 国产精品免费视频内射| 亚洲av成人av| 在线看三级毛片| 757午夜福利合集在线观看| 1024香蕉在线观看| 亚洲成人久久爱视频| 中文字幕精品免费在线观看视频| 国产精品久久久久久精品电影 | 国产精品影院久久| 国产成人精品久久二区二区91| 中文字幕最新亚洲高清| 欧美一区二区精品小视频在线| 俄罗斯特黄特色一大片| 亚洲国产精品久久男人天堂| 一区二区三区高清视频在线| 99国产综合亚洲精品| 精品久久久久久成人av| 国产一级毛片七仙女欲春2 | 色老头精品视频在线观看| 欧美黄色片欧美黄色片| 午夜老司机福利片| 又黄又爽又免费观看的视频| 日本精品一区二区三区蜜桃| 97超级碰碰碰精品色视频在线观看| 色老头精品视频在线观看| 亚洲,欧美精品.| 精品熟女少妇八av免费久了| 国产亚洲精品一区二区www| 午夜a级毛片| 男人的好看免费观看在线视频 | 国产精品影院久久| 亚洲国产精品成人综合色| 久久人妻av系列| 国产精品久久久久久亚洲av鲁大| 国产成人精品久久二区二区91| 黑人欧美特级aaaaaa片| 此物有八面人人有两片| 51午夜福利影视在线观看| 亚洲天堂国产精品一区在线| 天天躁夜夜躁狠狠躁躁| 亚洲七黄色美女视频| 91大片在线观看| 大型黄色视频在线免费观看| 91av网站免费观看| 最新美女视频免费是黄的| 亚洲成人久久性| 搡老妇女老女人老熟妇| 国产人伦9x9x在线观看| 久久欧美精品欧美久久欧美| cao死你这个sao货| 欧美最黄视频在线播放免费| 亚洲自拍偷在线| 视频在线观看一区二区三区| 可以在线观看毛片的网站| 亚洲国产精品sss在线观看| 久久精品成人免费网站| 国产99久久九九免费精品| 丁香欧美五月| 国产精华一区二区三区| 国产亚洲精品综合一区在线观看 | 免费女性裸体啪啪无遮挡网站| 成人18禁在线播放| 国产精品综合久久久久久久免费| 亚洲av第一区精品v没综合| 天堂影院成人在线观看| 18禁观看日本| 人成视频在线观看免费观看| 免费一级毛片在线播放高清视频| 男人舔女人下体高潮全视频| 1024手机看黄色片| 亚洲专区字幕在线| 亚洲熟妇中文字幕五十中出| 久久久国产成人精品二区| 国产亚洲精品久久久久久毛片| 欧美日韩中文字幕国产精品一区二区三区| 老司机福利观看| 日韩免费av在线播放| 亚洲七黄色美女视频| 精品国内亚洲2022精品成人| 国内揄拍国产精品人妻在线 | 老汉色∧v一级毛片| 亚洲一码二码三码区别大吗| 热re99久久国产66热| 18禁国产床啪视频网站| 可以免费在线观看a视频的电影网站| 悠悠久久av| 老鸭窝网址在线观看| 一级毛片高清免费大全| 午夜免费成人在线视频| 久久人妻福利社区极品人妻图片| 中文亚洲av片在线观看爽| 亚洲精品在线美女| 国产男靠女视频免费网站| 男女之事视频高清在线观看| 夜夜夜夜夜久久久久| 老司机深夜福利视频在线观看| 巨乳人妻的诱惑在线观看| 国产成人精品无人区| 丰满人妻熟妇乱又伦精品不卡| 精品不卡国产一区二区三区| 1024香蕉在线观看| 久久久国产成人免费| 亚洲国产日韩欧美精品在线观看 | 午夜免费观看网址| tocl精华| 50天的宝宝边吃奶边哭怎么回事| 亚洲欧美日韩无卡精品| 18禁黄网站禁片午夜丰满| 国产视频一区二区在线看| 亚洲精品中文字幕一二三四区| 看片在线看免费视频| 91麻豆精品激情在线观看国产| 性欧美人与动物交配| 天天躁夜夜躁狠狠躁躁| 黄片大片在线免费观看| 免费无遮挡裸体视频| 日韩视频一区二区在线观看| 国产高清videossex| 亚洲专区中文字幕在线| 搡老妇女老女人老熟妇| 久久午夜亚洲精品久久| 女性被躁到高潮视频| 听说在线观看完整版免费高清| 美女扒开内裤让男人捅视频| 村上凉子中文字幕在线| 一级片免费观看大全| 色尼玛亚洲综合影院| 久久婷婷人人爽人人干人人爱| 一本一本综合久久| 欧美乱码精品一区二区三区| 美女高潮到喷水免费观看| 狂野欧美激情性xxxx| 欧美+亚洲+日韩+国产| 免费观看人在逋| 成人18禁在线播放| 国产99白浆流出| 亚洲国产欧美一区二区综合| 免费观看精品视频网站| 国产一卡二卡三卡精品| 成年人黄色毛片网站| 国产精品98久久久久久宅男小说| 满18在线观看网站| 久久 成人 亚洲| 亚洲久久久国产精品| 国产97色在线日韩免费| 午夜福利在线在线| 1024视频免费在线观看| 色老头精品视频在线观看| 天堂动漫精品| 久久国产精品人妻蜜桃| 免费看a级黄色片| 无人区码免费观看不卡| www日本在线高清视频| 国产精品自产拍在线观看55亚洲| 高清在线国产一区| 日韩精品免费视频一区二区三区| 国产极品粉嫩免费观看在线| 欧美日韩黄片免| 日本a在线网址| 欧美日本视频| 国产一卡二卡三卡精品| 女警被强在线播放| 日韩免费av在线播放| 久久精品国产亚洲av高清一级| 精品久久久久久久久久免费视频| 香蕉av资源在线| 日韩一卡2卡3卡4卡2021年| 老熟妇仑乱视频hdxx| 精品国产乱码久久久久久男人| 男男h啪啪无遮挡| 十八禁网站免费在线| 老司机午夜福利在线观看视频| 久久人人精品亚洲av| 禁无遮挡网站| 亚洲三区欧美一区| 日本a在线网址| 国产免费男女视频| 亚洲精品美女久久av网站| 久久热在线av| 成人三级黄色视频| 欧美一级毛片孕妇| 老熟妇仑乱视频hdxx| 欧美zozozo另类| 国产精品乱码一区二三区的特点| 天堂√8在线中文| 欧美一级毛片孕妇| 国产精品综合久久久久久久免费| 中文字幕人妻熟女乱码| 成年版毛片免费区| 国产av不卡久久| 亚洲 欧美一区二区三区| 啦啦啦免费观看视频1| 午夜免费激情av| 又紧又爽又黄一区二区| 成在线人永久免费视频| 国产精品一区二区免费欧美| 国产成年人精品一区二区| 久久久久久亚洲精品国产蜜桃av| 国产亚洲精品久久久久久毛片| 亚洲精品久久国产高清桃花| 熟妇人妻久久中文字幕3abv| 欧美激情 高清一区二区三区| 国产片内射在线| 女人高潮潮喷娇喘18禁视频| 午夜福利在线观看吧| 婷婷精品国产亚洲av| 日韩视频一区二区在线观看| 91老司机精品| 亚洲精品久久成人aⅴ小说| 午夜福利视频1000在线观看| 精品国产超薄肉色丝袜足j| 免费看美女性在线毛片视频| 日韩欧美国产在线观看| 精品乱码久久久久久99久播| 老司机午夜福利在线观看视频| 12—13女人毛片做爰片一| 真人一进一出gif抽搐免费| 两性午夜刺激爽爽歪歪视频在线观看 | 精品国产一区二区三区四区第35| 最近在线观看免费完整版| 日韩精品中文字幕看吧| 国产精品久久久久久人妻精品电影| 精品高清国产在线一区| 久久香蕉国产精品| 久久热在线av| 男女做爰动态图高潮gif福利片| 精品久久久久久久久久久久久 | 亚洲av日韩精品久久久久久密| www.精华液| 国产亚洲精品第一综合不卡| 亚洲精品久久国产高清桃花| 夜夜看夜夜爽夜夜摸| 国产精华一区二区三区| 亚洲精品一卡2卡三卡4卡5卡| 1024视频免费在线观看| 动漫黄色视频在线观看| 母亲3免费完整高清在线观看| 亚洲色图av天堂| 俄罗斯特黄特色一大片| 色婷婷久久久亚洲欧美| 色综合站精品国产| 成人永久免费在线观看视频| 天堂√8在线中文| 免费一级毛片在线播放高清视频| 91麻豆精品激情在线观看国产| 91老司机精品| 日韩欧美一区二区三区在线观看| 亚洲天堂国产精品一区在线| 日韩精品免费视频一区二区三区| 久久亚洲真实| 久久久久久大精品| 午夜福利免费观看在线| 国产熟女午夜一区二区三区| 日韩欧美国产在线观看| 亚洲专区中文字幕在线| 国产欧美日韩一区二区精品| 久久欧美精品欧美久久欧美| 久久久国产成人免费| 欧美一区二区精品小视频在线| 精品久久久久久久末码| www日本在线高清视频| 亚洲五月天丁香| 一本大道久久a久久精品| 日韩av在线大香蕉| 国产黄片美女视频| 俄罗斯特黄特色一大片| 免费无遮挡裸体视频| 日本 欧美在线| 亚洲av五月六月丁香网| 麻豆av在线久日| 老熟妇乱子伦视频在线观看| a在线观看视频网站| 曰老女人黄片| 亚洲熟妇中文字幕五十中出| netflix在线观看网站| 国产av不卡久久| 免费无遮挡裸体视频| 国产亚洲精品综合一区在线观看 | 国产精品久久久久久人妻精品电影| 中出人妻视频一区二区| 大型黄色视频在线免费观看| 老司机午夜十八禁免费视频| 国产黄片美女视频| 最近最新免费中文字幕在线| 久久人妻av系列| 精品国产美女av久久久久小说| 国产在线精品亚洲第一网站| 美女高潮喷水抽搐中文字幕| 一区二区三区国产精品乱码| 亚洲精品粉嫩美女一区| 久久久久精品国产欧美久久久| 国产欧美日韩精品亚洲av| 亚洲天堂国产精品一区在线| 亚洲激情在线av| 精品第一国产精品| 日韩欧美一区视频在线观看| 国产99久久九九免费精品| 国产精品二区激情视频| 久久久久国产一级毛片高清牌| 日韩成人在线观看一区二区三区| 中文字幕最新亚洲高清| 色综合亚洲欧美另类图片| 狂野欧美激情性xxxx| 香蕉av资源在线| 国产片内射在线| 欧美激情极品国产一区二区三区| 脱女人内裤的视频| 黄色视频,在线免费观看| 亚洲中文日韩欧美视频| 欧美激情 高清一区二区三区| 一区二区三区国产精品乱码| 国产精品日韩av在线免费观看| 国产精品乱码一区二三区的特点| 狠狠狠狠99中文字幕| 看免费av毛片| 国产三级黄色录像| 国产精品电影一区二区三区| 男女之事视频高清在线观看| 亚洲午夜精品一区,二区,三区| 欧美成狂野欧美在线观看| 熟女电影av网| av超薄肉色丝袜交足视频| 亚洲成人久久性| 亚洲一卡2卡3卡4卡5卡精品中文| 国产亚洲精品第一综合不卡| 少妇的丰满在线观看| 国产精品免费一区二区三区在线| 午夜久久久久精精品| 男女下面进入的视频免费午夜 | 亚洲欧美精品综合一区二区三区| 久久亚洲真实| 亚洲专区中文字幕在线| 国产精品美女特级片免费视频播放器 | 午夜精品在线福利| 亚洲精品国产区一区二| 国产单亲对白刺激| 亚洲国产看品久久| 亚洲成国产人片在线观看| 18禁国产床啪视频网站| 91老司机精品| 精品免费久久久久久久清纯| 免费在线观看视频国产中文字幕亚洲| 免费看十八禁软件| 国产亚洲精品久久久久久毛片| 男女之事视频高清在线观看| 亚洲中文字幕一区二区三区有码在线看 | 久久久久亚洲av毛片大全| 国产成人一区二区三区免费视频网站| ponron亚洲| 精品欧美一区二区三区在线| 美女免费视频网站| 久久热在线av| 欧美黄色片欧美黄色片| 91麻豆av在线| 亚洲国产精品sss在线观看| 色综合欧美亚洲国产小说| 国内少妇人妻偷人精品xxx网站 | 中文字幕另类日韩欧美亚洲嫩草| 看片在线看免费视频| 免费人成视频x8x8入口观看| 757午夜福利合集在线观看| 精品免费久久久久久久清纯| 不卡一级毛片| 久久午夜亚洲精品久久| 亚洲国产精品999在线| 成人国语在线视频| 久久中文看片网| 国产高清videossex| 亚洲第一青青草原| 久久人妻av系列| 香蕉av资源在线| 女人爽到高潮嗷嗷叫在线视频| 免费观看人在逋| 国产99白浆流出| 欧美色视频一区免费| 天天躁狠狠躁夜夜躁狠狠躁| 国产成人欧美在线观看| 天天躁夜夜躁狠狠躁躁| 国产精品 欧美亚洲| 久久99热这里只有精品18| 99国产精品99久久久久| 一个人免费在线观看的高清视频| 精品少妇一区二区三区视频日本电影| 久久天躁狠狠躁夜夜2o2o| 黄色成人免费大全| 午夜激情福利司机影院| 亚洲精品在线观看二区| 国产av一区在线观看免费| 国产91精品成人一区二区三区| 人人澡人人妻人| 香蕉丝袜av| 精品不卡国产一区二区三区| 99在线视频只有这里精品首页| 国产真人三级小视频在线观看| 日韩大尺度精品在线看网址| 久久久久久大精品| 久久国产精品影院| 亚洲免费av在线视频| 国产成人系列免费观看| 高潮久久久久久久久久久不卡| 亚洲九九香蕉| 曰老女人黄片| 非洲黑人性xxxx精品又粗又长| 久久人人精品亚洲av| 午夜免费鲁丝| 欧美性猛交黑人性爽| 国产亚洲精品av在线| 亚洲成av人片免费观看| 老熟妇仑乱视频hdxx| www.熟女人妻精品国产| 免费av毛片视频| 欧美乱码精品一区二区三区| а√天堂www在线а√下载| 精品电影一区二区在线| 亚洲成国产人片在线观看| 久久精品影院6| 黄色毛片三级朝国网站| 国产三级黄色录像| 在线观看免费视频日本深夜| 制服诱惑二区| 久久精品aⅴ一区二区三区四区| 在线播放国产精品三级| 听说在线观看完整版免费高清| 欧美日本视频| 后天国语完整版免费观看| 成人国产一区最新在线观看| 观看免费一级毛片| 国产午夜精品久久久久久| 精品不卡国产一区二区三区| 久久午夜亚洲精品久久| 亚洲精品久久成人aⅴ小说| 91在线观看av| а√天堂www在线а√下载| 少妇 在线观看| 首页视频小说图片口味搜索| 免费高清视频大片| 欧美绝顶高潮抽搐喷水| 国产麻豆成人av免费视频| 免费在线观看完整版高清| 国产成人精品久久二区二区免费| 国产色视频综合| 国产高清激情床上av| 午夜免费鲁丝| 中国美女看黄片| 久久婷婷成人综合色麻豆| 欧洲精品卡2卡3卡4卡5卡区|