c#高效的线程安全队列ConcurrentQueue<T>的实现

入队(EnQueue) 、出队(TryDequeue) 、是否为空(IsEmpty)、获取队列内元素数量(Count)。

一、ConcurrentQueue内部结构:

1.实现原理

众所周知，在普通的非线程安全队列有两种实现方式:

1.使用数组实现的循环队列。

2.使用链表实现的队列。

先看看两种方式的优劣：

.Net Farmework中的普通队列Queue的实现使用了第一种方式，缺点是当队列空间不足会进行扩容，扩容的主要实现是开辟一个原始长度2倍的新数组，然后将原始数组里面的数据复制到新数组中，所以当扩容时就会产生不小的内存开销，在并发的环境中对性能的影响不可小视。当然在调用Queue的构造函数时可以指定默认空间的大小，但是一般情况下数据量是不可预测的，选大了会照成空间浪费，选小了会有复制内存的开销，而且队列扩容以后需要显示调用TrimToSize()方法才能回收掉不使用的内存空间。

第二种链表实现方式虽然消除了空间浪费的问题但是又增加了GC的压力，当入队时会分配一个新节点，出队时要对该节点进行废弃，对于大量的出队入队操作时该实现方式性能不高。

综合以上两种实现方式，在支持多线程并发出队并发入队的情况下，ConcurrentQueue使用了分段存储的概念（如上图所示），ConcurrentQueue分配内存时以段(Segment)为单位，一个段内部含有一个默认长度为32的数组和执行下一个段的指针，有个和Head和Tail指针分别指向了起始段和结束段（这种结构有点像操作系统的段式内存管理和页式内存管理策略）。这种分配内存的实现方式不但减轻的GC的压力而且调用者也不用显示的调用TrimToSize()方法回收内存（在某段内存为空时，会由GC来回收该段内存）。

2.Segment(段)内部结构

其实对于ConcurrentQueue的操作其实就是对Segment(数据段)的操作。

Segment可抽象出如下数据结构:

Segment内部主要方法:

Segment内部和用数组实现的普通队列相当，只不过对于入队和出队操作使用了原子操作来防止多线程竞争问题，使用随机退让等技术保证活锁等问题，实现机制和ConcurrentStack差别不大，跟多TryAppend的实现细节在源码注释中已经阐述的非常清楚这里就再做不过多的解释。

二、入队操作

如上图所示，入队操作是在尾部的段中进行，当数据进入段内失败时会先进行一个回退操作然后再不断尝试直到成功，这里失败的原因（tail.Append(item)返回false）只有一个就是当该段内的空间不够时正在分配新的段，这段时间内会进入该段的元素会失败。

三、出队操作

如上图所示，出队失败时返回false 而不是像入队一样进行回退操作，因为出队失败的原因只有一个就是当队列内所有段的元素为空时，所以出队设计成了返回bool值的函数。

四、判断是否为空(IsEmpty)

整个判断为O(1)的复杂度 主要有三种情况:

1. 头节点（段）不为空返回false

2. 头节点为空而且下一个节点也为空返回true

3. 头节点为空而且下一个节点不为空返回false，这种情况说明队列正在扩容，所以要自选等待扩容完毕时再次进行判断

五、获取队列内元素数量(Count)

找到头节点的low的位置和尾节点的high的位置，由于每个段内记录了当前段在队列中的索引，所以很容易求出整个队列中元素的数量。

跟ConcurrentStack一样 微软官方文档和注释中也说明：判断队列是否为空要使用IsEmpty属性而不是判断Count == 0  原因在于GetHeadTailPositions在大量数据入队和出队的过程中寻找头尾节点的位置是比较耗时的操作，要不断循环确定头尾节点的位置，所以判断队列是否为空还是使用IsEmpty属性。

到此这篇关于c#高效的线程安全队列ConcurrentQueue<T>的实现的文章就介绍到这了,更多相关c# ConcurrentQueue<T>内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • C#获取进程或线程相关信息的方法

    本文实例讲述了C#获取进程或线程相关信息的方法.分享给大家供大家参考.具体实现方法如下: using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Diagnostics; namespace ConsoleApp { class ProcessDo { /// <summary> /// 获取进程相关信息 /// </summary> pub

  • C#多线程等待所有子线程结束的示例

    在使用多线程过程中,可能会遇到在一些情况下必须等待子线程全部执行结束后主线程才进行下一步, 做法如下: //在使用多线程过程中,可能会遇到在一些情况下必须等待子线程全部执行结束后主线程才进行下一步,做法如下 List<ManualResetEvent> manualEvents = new List<ManualResetEvent>();//创建线程等待集合 for (int i = 0; i < 64; i++) //WaitHandles 的数目必须少于或等于 64 个

  • C# 多线程处理List数据的示例代码

    代码思路 将要处理的数据放到ConcurrentQueue中,然后开启多个线程去处理数据,处理完成后,再到队列中获取下一个待处理数据. ConcurrentQueue 表示线程安全的先进先出 (FIFO) 集合,属于 System.Collections.Concurrent 命名空间下的一个数据结构 直接上代码 /// <summary> /// 多线程处理数据(无返回值) /// </summary> /// <typeparam name="T"&g

  • C#网络编程基础之进程和线程详解

    C#网络编程基础之进程和线程详解

    在C#的网络编程中,进程和线程是必备的基础知识,同时也是一个重点,所以我们要好好的掌握一下. 一:概念 首先我们要知道什么是"进程",什么是"线程",好,查一下baike. 进程:是一个具有一定独立功能的程序关于某个数据集合的一次活动.它是操作系统动态执行的基本单元, 在传统的操作系统中,进程既是基本的分配单元,也是基本的执行单元. 线程:是"进程"中某个单一顺序的控制流. 关于这两个概念,大家稍微有个印象就行了,防止以后被面试官问到. 二:进程

  • 详解C#多线程编程之进程与线程

    一. 进程 简单来说,进程是对资源的抽象,是资源的容器,在传统操作系统中,进程是资源分配的基本单位,而且是执行的基本单位,进程支持并发执行,因为每个进程有独立的数据,独立的堆栈空间.一个程序想要并发执行,开多个进程即可. Q1:在单核下,进程之间如何同时执行? 首先要区分两个概念--并发和并行 并发:并发是指在一段微小的时间段中,有多个程序代码段被CPU执行,宏观上表现出来就是多个程序能"同时"执行. 并行:并行是指在一个时间点,有多个程序段代码被CPU执行,它才是真正的同时执行. 所

  • c# 如何实现不同进程之间的通信

    进程之间的通信是为了解决不同进程之间的数据传输问题,这样可以让不同程序交互数据.实现进程通信的方式:1.剪切板:2.COM:3.内存映射文件:4.WCF 1.剪切板Clipboard在进程间传送对象 剪切板是一个供应用程序使用的公有区域.在.NET中定一个了一个DataFormats类,此类包含一些静态字段,定义了剪切板中可以存放的数据类型.使用Clipboard类可以向剪切板中放入数据. 如将文字放入剪切板,使用方法SetDataObject即可:Clipboard.SetDataObject

  • C#获取所有进程的方法

    在使用C#进行相关编程的时候,有时候我们需要获取系统相关的进程信息.那么在C#中如何获取系统的所有进程那?下面请跟小编一起来操作. 1.首先新建一个控制台程序,这里主要是为了方便演示,控制台程序相对比较简单,如下图所示: 2.然后导入进程相关的操作类,主要是diagnostics,如下图所示 3.然后我们调用Process类的GetProcesses方法,获取系统所以进程,注意是一个数组,图下图所示: 4.我们来看一下Process的相关解释说明,把鼠标放上去,看到如下图所示的内容 5.接下来我

  • 如何在C# 中查找或结束程序域中的主、子进程

    有时候,我们的程序需要启动一些子进程,如嵌入的图形程序. 当启动一个进程后,获得这个进程信息Process,然后其内部在某个时刻启动了一个子进程,这个时候就涉及程序域和进程树的概念.当我们通过非正常操作的方式结束前面获得的进程信息Process时(如Kill掉),可能并没有实际结束子进程.因为当有主进程启动了子进程后,所有的进程实际上是被放在程序域中运行的(winform的Program文件中的Application域中),而结束的仅仅是域中的某个进程.当然,如果我们正常推出主进程,实际上App

  • c# 进程和线程的区别与联系

    引入线程是为了减少程序在并发执行时所付出的时空开销. 属性: 轻型实体.它不拥有系统资源,只是有一点必不可少的.能保证独立运行的资源. 独立调度和分派的基本单位.在多线程OS中,线程是独立运行的基本单位,因而也是独立调度和分派的基本单位,但由于线程很轻,故线程的切换非常迅速且开销小. 可并发执行.在一个进程中的多个线程之间可以并发执行,甚至允许在一个进程中的所有线程都能并发执行:同样,不同进程中的线程也能并发执行. 共享进程资源.在同一个进程中的各个线程都可以共享该进程所拥有的资源,这首先表现在

  • c# 进程之间的线程同步

    Mutex类.Event类.SemaphoreSlim类和ReaderWriterLockSlim类等提供了多个进程之间的线程同步.  1.WaitHandle 基类 WaitHandle抽象类,用于等待一个信号的设置.可以根据其派生类的不同,等待不同的信号.异步委托的BeginInvoke()方法返回一个实现了IAsycResult接口的对象.使用IAsycResult接口可以用AsycWaitHandle属性访问WaitHandle基类.在调用WaitOne()方法时,线程会等待接收一个和等

随机推荐