国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

為什么ConcurrentHashMap是弱一致的

CarterLi / 2125人閱讀

摘要:是我們一直擁有的,即我們有,。中的迭代器中的迭代器主要包括方法。在遍歷過程中,如果已經遍歷的數組上的內容變化了,迭代器不會拋出異常。這就是迭代器弱一致的表現。總結的弱一致性主要是為了提升效率,是一致性與效率之間的一種權衡。

本文將用到Java內存模型的happens-before偏序關系(下文將簡稱為hb)以及ConcurrentHashMap的底層模型相關的知識。happens-before相關內容參見:JLS §17.4.5. Happens-before Order、深入理解Java內存模型以及Happens before;ConcurrentHashMap的詳細介紹以及底層原理見深入分析ConcurrentHashMap。本文將從ConcurrentHashMap的get,clear,iterator(entrySet、keySet、values方法)三個方法來分析它們的弱一致問題。

ConcurrentHashMap#get

get方法是弱一致的,是什么含義?可能你期望往ConcurrentHashMap底層數據結構中加入一個元素后,立馬能對get可見,但ConcurrentHashMap并不能如你所愿。換句話說,put操作將一個元素加入到底層數據結構后,get可能在某段時間內還看不到這個元素,若不考慮內存模型,單從代碼邏輯上來看,卻是應該可以看得到的。

下面將結合代碼和java內存模型相關內容來分析下put/get方法(本文中所有ConcurrentHashMap相關的代碼均來自hotspot1.6.0_18)。put方法我們只需關注Segment#put,get方法只需關注Segment#get,在繼續之前,先要說明一下Segment里有兩個volatile變量:counttable;HashEntry里有一個volatile變量:value
Segment#put

V put(K key, int hash, V value, boolean onlyIfAbsent) {
    lock();
    try {
        int c = count;
        if (c++ > threshold) // ensure capacity
            rehash();
        HashEntry[] tab = table;
        int index = hash & (tab.length - 1);
        HashEntry first = tab[index];
        HashEntry e = first;
        while (e != null && (e.hash != hash || !key.equals(e.key)))
            e = e.next;

        V oldValue;
        if (e != null) {
            oldValue = e.value;
            if (!onlyIfAbsent)
                e.value = value;
        }
        else {
            oldValue = null;
            ++modCount;
            tab[index] = new HashEntry(key, hash, first, value);
            count = c; // write-volatile
        }
        return oldValue;
    } finally {
        unlock();
    }
}

Segment#get

V get(Object key, int hash) {
    if (count != 0) { // read-volatile
        HashEntry e = getFirst(hash);
        while (e != null) {
            if (e.hash == hash && key.equals(e.key)) {
                V v = e.value;
                if (v != null)
                    return v;
                return readValueUnderLock(e); // recheck
            }
            e = e.next;
        }
    }
    return null;
}

我們如何確定線程1放入某個變量的值是否對線程2可見?文章開頭提到的JLS鏈接中有說到,當a hb c時,a對c可見,那么我們接下來我們只要尋找put和get之間所有可能的執行軌跡上的hb關系。要找出hb關系,我們需要先找出與hb相關的Action。為方便,這里將兩段代碼放到了一張圖片上。

可以注意到,同一個Segment實例中的put操作是加了鎖的,而對應的get卻沒有。根據hb關系中的線程間Action類別,可以從上圖中找出這些Action,主要是volatile讀寫和加解鎖,也就是圖中畫了橫線的那些。

put操作可以分為兩種情況,一是key已經存在,修改對應的value;二是key不存在,將一個新的Entry加入底層數據結構。

key已經存在的情況比較簡單,即if (e != null)部分,前面已經說過HashEntry的value是個volatile變量,當線程1給value賦值后,會立馬對執行get的線程2可見,而不用等到put方法結束。

key不存在的情況稍微復雜一些,新加一個Entry的邏輯在else中。那么將new HashEntry賦值給tab[index]是否能立刻對執行get的線程可見呢?我們只需分析寫tab[index]與讀取tab[index]之間是否有hb關系即可。

假設執行put的線程與執行get的線程的軌跡是這樣的

執行put的線程 執行get的線程
⑧tab[index] = new HashEntry(key, hash, first, value)
②count = c
③if (count != 0)
⑨HashEntry e = getFirst(hash);

tab變量是一個普通的變量,雖然給它賦值的是volatile的table。另外,雖然引用類型(數組類型)的變量table是volatile的,但table中的元素不是volatile的,因此⑧只是一個普通的寫操作;count變量是volatile的,因此②是一個volatile寫;③很顯然是一個volatile讀;⑨中getFirst方法中讀取了table,因此包含一個volatile讀。

根據Synchronization Order,對同一個volatile變量,有volatile寫 hb volatile讀。在這個執行軌跡中,時間上②在③之前發生,且②是寫count,③是讀count,都是針對同一個volatile變量count,因此有② hb ③;又因為⑧和②是同一個線程中的,③和⑨是同一個線程中的,根據Program Order,有⑧ hb ②,③ hb ⑨。目前我們有了三組關系了⑧ hb ②,② hb ③,③ hb ⑨,再根據hb關系是可傳遞的(即若有x hb y且y hb z,可得出x hb z),可以得出⑧ hb ⑨。因此,如果按照上述執行軌跡,⑧中寫入的數組元素對⑨中的讀取操作是可見的。

再考慮這樣一個執行軌跡:

|執行put的線程|執行get的線程|
|-|-|
|⑧tab[index] = new HashEntry(key, hash, first, value)||
||③if (count != 0)|
②count = c||
||⑨HashEntry e = getFirst(hash);|

這里只是變換了下執行順序。每條語句的volatile讀寫含義同上,但它們之間的hb關系卻改變了。Program Order是我們一直擁有的,即我們有⑧ hb ②,③ hb ⑨。但這次對volatile的count的讀時間上發生在對count的寫之前,我們無法得出② hb ⑨這層關系了。因此,通過count變量,在這個軌跡上是無法得出⑧ hb ⑨的。那么,存不存在其它可替換關系,讓我們仍能得出⑧ hb ⑨呢?

我們要找的是,在⑧之后有一條語句或指令x,在⑨之前有一條語句或指令y,存在x hb y。這樣我們可以有⑧ hb x,x hb y, y hb ⑨。就讓我們來找一下是否存在這樣的x和y。圖中的⑤、⑥、⑦、①存在volatile讀寫,但是它們在⑧之前,因此對確立⑧ hb ⑨這個關系沒有用處;同理,④在⑨之后,我們要找的是⑨之前的,因此也對這個問題無益。前面已經分析過了②,③之間沒法確立hb關系。

在⑧之后,我們發現一個unlock操作,如果能在⑨之前找到一個lock操作,那么我們要找的x就是unlock,要找的y就是lock,因為Synchronization Order中有unlock hb lock的關系。但是,很不幸運,⑨之前沒有lock操作。因此,對于這樣的軌跡,是沒有⑧ hb
⑨關系的,也就是說,如果某個Segment實例中的put將一個Entry加入到了table中,在未執行count賦值操作之前有另一個線程執行了同一個Segment實例中的get,來獲取這個剛加入的Entry中的value,那么是有可能取不到的!

此外,如果getFirst(hash)先執行,tab[index] = new HashEntry(key, hash, first, value)后執行,那么,這個get操作也是看不到put的結果的。

正是因為get操作幾乎所有時候都是一個無鎖操作(get中有一個readValueUnderLock調用,不過這句執行到的幾率極小),使得同一個Segment實例上的put和get可以同時進行,這就是get操作是弱一致的根本原因。Java
API中對此有一句簡單的描述:

  

Retrievals reflect the results of the most recently completed
update operations holding upon their onset.

也就是說API上保證get操作一定能看到已完成的put操作。已完成的put操作肯定在get讀取count之前對count做了寫入操作。因此,也就是我們第一個軌跡分析的情況。

ConcurrentHashMap#clear

clear方法很簡單,看下代碼即知。

public void clear() {
    for (int i = 0; i < segments.length; ++i)
        segments[i].clear();
}

因為沒有全局的鎖,在清除完一個segments之后,正在清理下一個segments的時候,已經清理segments可能又被加入了數據,因此clear返回的時候,ConcurrentHashMap中是可能存在數據的。因此,clear方法是弱一致的。

ConcurrentHashMap中的迭代器

ConcurrentHashMap中的迭代器主要包括entrySet、keySet、values方法。它們大同小異,這里選擇entrySet解釋。當我們調用entrySet返回值的iterator方法時,返回的是EntryIterator,在EntryIterator上調用next方法時,最終實際調用到了HashIterator.advance()方法,看下這個方法:

final void advance() {
    if (nextEntry != null && (nextEntry = nextEntry.next) != null)
        return;

    while (nextTableIndex >= 0) {
        if ( (nextEntry = currentTable[nextTableIndex--]) != null)
            return;
    }

    while (nextSegmentIndex >= 0) {
        Segment seg = segments[nextSegmentIndex--];
        if (seg.count != 0) {
            currentTable = seg.table;
            for (int j = currentTable.length - 1; j >= 0; --j) {
                if ( (nextEntry = currentTable[j]) != null) {
                    nextTableIndex = j - 1;
                    return;
                }
            }
        }
    }
}

這個方法在遍歷底層數組。在遍歷過程中,如果已經遍歷的數組上的內容變化了,迭代器不會拋出ConcurrentModificationException異常。如果未遍歷的數組上的內容發生了變化,則有可能反映到迭代過程中。這就是ConcurrentHashMap迭代器弱一致的表現。

總結

ConcurrentHashMap的弱一致性主要是為了提升效率,是一致性與效率之間的一種權衡。要成為強一致性,就得到處使用鎖,甚至是全局鎖,這就與Hashtable和同步的HashMap一樣了。


via ifeve.com

文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。

轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/64041.html

相關文章

  • java中ConcurrentHashMap使用及在Java 8中沖突方案

    摘要:中的使用及在中的沖突方案引言簡稱是在作為的替代選擇新引入的,是包的重要成員。為了解決在頻繁沖突時性能降低的問題,中使用平衡樹來替代鏈表存儲沖突的元素。目前,只有和會在頻繁沖突的情況下使用平衡樹。 java中ConcurrentHashMap的使用及在Java 8中的沖突方案 1、引言 ConcurrentHashMap(簡稱CHM)是在Java 1.5作為Hashtable的替代選擇新...

    kun_jian 評論0 收藏0
  • Java多線程之線程安全與異步執行

    摘要:同步包裝器任何集合類使用同步包裝器都會變成線程安全的,會將集合的方法使用鎖加以保護,保證線程的安全訪問。線程池中的線程執行完畢并不會馬上死亡,而是在池中準備為下一個請求提供服務。 多線程并發修改一個數據結構,很容易破壞這個數據結構,如散列表。鎖能夠保護共享數據結構,但選擇線程安全的實現更好更容易,如阻塞隊列就是線程安全的集合。 線程安全的集合 Vector和HashTable類提供了線...

    taoszu 評論0 收藏0
  • ConcurrentHashMap探究

    摘要:是線程安全,性能出色的的線程安全實現,相比較他是線程安全的,相比較他的性能優勢非常明顯。的源碼其實很簡單,和的結構一致,但是每一個方法都是用來修飾,以保證操作是線程安全的。這樣在多線程的情況下,只有一個線程獲取鎖操作中的數據。 ConcurrentHashMap ConcurrentHashMap是線程安全,性能出色的Map的線程安全實現,相比較HashMap他是線程安全的,相比較Ha...

    zombieda 評論0 收藏0
  • ConcurrentHashMap學習

    摘要:與和是一一對應的,對充當鎖的角色,每當對數組的數據進行修改時,首先要獲取對應的鎖解決散列沖突的方式是采用分離鏈表法分散鏈表法使用鏈表解決沖突,將散列值相同的元素都保存到一個鏈表中。負載因子,默認為。 一、為什么要用ConcurrentHashMap? 1、HashMap線程不安全,并且進行put操作會導致死循環(由于HashMap的Entry鏈表形成環形數據結構,Entry下的next...

    mayaohua 評論0 收藏0
  • 通俗方式理解動態類型,靜態類型;強類型,弱類型

    摘要:不允許隱式轉換的是強類型,允許隱式轉換的是弱類型。拿一段代碼舉例在使用調用函數的時候會先生成一個類模板運行時生成,執行的時候會生成類模板,執行的時候會生成類模板。 0 x 01 引言 今天和一個朋友討論 C++ 是強類型還是弱類型的時候,他告訴我 C++ 是強類型的,他和我說因為 C++ 在寫的時候需要 int,float 等等關鍵字去定義變量,因此 C++ 是強類型的,我告訴他 C+...

    周國輝 評論0 收藏0

發表評論

0條評論

最新活動
閱讀需要支付1元查看
<