入隊(EnQueue) 、出隊(TryDequeue) 、是否為空(IsEmpty)、獲取隊列內(nèi)元素數(shù)量(Count)。

一、ConcurrentQueue內(nèi)部結(jié)構(gòu):

1.實現(xiàn)原理

眾所周知，在普通的非線程安全隊列有兩種實現(xiàn)方式:

1.使用數(shù)組實現(xiàn)的循環(huán)隊列。

2.使用鏈表實現(xiàn)的隊列。

先看看兩種方式的優(yōu)劣：

     .Net Farmework中的普通隊列Queue的實現(xiàn)使用了第一種方式，缺點是當隊列空間不足會進行擴容，擴容的主要實現(xiàn)是開辟一個原始長度2倍的新數(shù)組，然后將原始數(shù)組里面的數(shù)據(jù)復(fù)制到新數(shù)組中，所以當擴容時就會產(chǎn)生不小的內(nèi)存開銷，在并發(fā)的環(huán)境中對性能的影響不可小視。當然在調(diào)用Queue的構(gòu)造函數(shù)時可以指定默認空間的大小，但是一般情況下數(shù)據(jù)量是不可預(yù)測的，選大了會照成空間浪費，選小了會有復(fù)制內(nèi)存的開銷，而且隊列擴容以后需要顯示調(diào)用TrimToSize()方法才能回收掉不使用的內(nèi)存空間。

     第二種鏈表實現(xiàn)方式雖然消除了空間浪費的問題但是又增加了GC的壓力，當入隊時會分配一個新節(jié)點，出隊時要對該節(jié)點進行廢棄，對于大量的出隊入隊操作時該實現(xiàn)方式性能不高。

    綜合以上兩種實現(xiàn)方式，在支持多線程并發(fā)出隊并發(fā)入隊的情況下，ConcurrentQueue使用了分段存儲的概念（如上圖所示），ConcurrentQueue分配內(nèi)存時以段(Segment)為單位，一個段內(nèi)部含有一個默認長度為32的數(shù)組和執(zhí)行下一個段的指針，有個和Head和Tail指針分別指向了起始段和結(jié)束段（這種結(jié)構(gòu)有點像操作系統(tǒng)的段式內(nèi)存管理和頁式內(nèi)存管理策略）。這種分配內(nèi)存的實現(xiàn)方式不但減輕的GC的壓力而且調(diào)用者也不用顯示的調(diào)用TrimToSize()方法回收內(nèi)存（在某段內(nèi)存為空時，會由GC來回收該段內(nèi)存）。

2.Segment(段)內(nèi)部結(jié)構(gòu)

其實對于ConcurrentQueue的操作其實就是對Segment(數(shù)據(jù)段)的操作。

Segment可抽象出如下數(shù)據(jù)結(jié)構(gòu):

Segment內(nèi)部主要方法:

    Segment內(nèi)部和用數(shù)組實現(xiàn)的普通隊列相當，只不過對于入隊和出隊操作使用了原子操作來防止多線程競爭問題，使用隨機退讓等技術(shù)保證活鎖等問題，實現(xiàn)機制和ConcurrentStack差別不大，跟多TryAppend的實現(xiàn)細節(jié)在源碼注釋中已經(jīng)闡述的非常清楚這里就再做不過多的解釋。

二、入隊操作

如上圖所示，入隊操作是在尾部的段中進行，當數(shù)據(jù)進入段內(nèi)失敗時會先進行一個回退操作然后再不斷嘗試直到成功，這里失敗的原因（tail.Append(item)返回false）只有一個就是當該段內(nèi)的空間不夠時正在分配新的段，這段時間內(nèi)會進入該段的元素會失敗。

三、出隊操作

如上圖所示，出隊失敗時返回false 而不是像入隊一樣進行回退操作，因為出隊失敗的原因只有一個就是當隊列內(nèi)所有段的元素為空時，所以出隊設(shè)計成了返回bool值的函數(shù)。

四、判斷是否為空(IsEmpty)

  整個判斷為O(1)的復(fù)雜度 主要有三種情況:

1. 頭節(jié)點（段）不為空返回false

2. 頭節(jié)點為空而且下一個節(jié)點也為空返回true

3. 頭節(jié)點為空而且下一個節(jié)點不為空返回false，這種情況說明隊列正在擴容，所以要自選等待擴容完畢時再次進行判斷

五、獲取隊列內(nèi)元素數(shù)量(Count)

     找到頭節(jié)點的low的位置和尾節(jié)點的high的位置，由于每個段內(nèi)記錄了當前段在隊列中的索引，所以很容易求出整個隊列中元素的數(shù)量。

     跟ConcurrentStack一樣 微軟官方文檔和注釋中也說明：判斷隊列是否為空要使用IsEmpty屬性而不是判斷Count == 0  原因在于GetHeadTailPositions在大量數(shù)據(jù)入隊和出隊的過程中尋找頭尾節(jié)點的位置是比較耗時的操作，要不斷循環(huán)確定頭尾節(jié)點的位置，所以判斷隊列是否為空還是使用IsEmpty屬性。

到此這篇關(guān)于c#高效的線程安全隊列ConcurrentQueue<T>的實現(xiàn)的文章就介紹到這了,更多相關(guān)c# ConcurrentQueue<T>內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！