快捷導(dǎo)航

c#高效的線程安全隊(duì)列ConcurrentQueue<T>的實(shí)現(xiàn)

更新時(shí)間：2020年11月26日 10:27:15 作者：流年輕逝

這篇文章主要介紹了c#高效的線程安全隊(duì)列ConcurrentQueue<T>的實(shí)現(xiàn)，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧

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

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

wps_clip_image-30166

1.實(shí)現(xiàn)原理

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

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

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

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

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

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

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

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

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

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

wps_clip_image-5493

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

wps_clip_image-6121

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

二、入隊(duì)操作

wps_clip_image-24139

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

三、出隊(duì)操作

wps_clip_image-3291

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

四、判斷是否為空(IsEmpty)

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

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

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

3. 頭節(jié)點(diǎn)為空而且下一個(gè)節(jié)點(diǎn)不為空返回false，這種情況說(shuō)明隊(duì)列正在擴(kuò)容，所以要自選等待擴(kuò)容完畢時(shí)再次進(jìn)行判斷

五、獲取隊(duì)列內(nèi)元素?cái)?shù)量(Count)

wps_clip_image-31544

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

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

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

您可能感興趣的文章: