基于无锁的C#并发队列实现

时间:2021-09-24 17:50:06   收藏:0   阅读:93

https://www.cnblogs.com/liaofan/archive/2008/11/20/1337888.html

https://blog.csdn.net/kuangben2000/article/details/105219688

非原创,转自 以上

 

最近开始学习无锁编程,和传统的基于Lock的算法相比,无锁编程具有其独特的优点,Angel Lucifer的关于无锁编程一文对此有详细的描述。

无锁编程的目标是在不使用Lock的前提下保证并发过程中共享数据的一致性,其主要的实现基础是CAS操作,也就是compare_and_swap,通过处理器提供的指令,可以原子地更新共享数据,并同时监测其他线程的干扰,.Net中的对应实现是InterLocked.CompareExchange函数。

既然不使用Lock,那在无锁编程中要时刻注意的是,代码可能在任意语句中被中断。如果是单个变量,我们可以使用 InterLocked.XXX 保证操作的原子性,但是如果有多个操作要完成的话,简单地组合 InterLocked.XXX 是远远不够的。通常的原则是对函数中用到的共享变量,先在代码开始处用局部变量保存它的内容,在后面更新共享变量时,使用前述变量来判断其是否发生了改变,如果共享变量发生了改变,那么我们可能需要重试,或者在某些可能的情况下,当前线程可以"帮助"其他更新中的线程完成更新。

从上面可以总结出无锁算法的两个基本特征:

1. 无锁算法总是包含一个循环结构,以保证更新失败后重试

2. 无锁算法在更新共享变量时,总是使用CAS和原始值进行比较,以保证没有冲突

下面是按照Michael-Scott算法实现的并发队列,其中的Dequeue算法在IBM的非阻塞算法一文中有详细介绍。代码如下:

技术分享图片
 1技术分享图片public class ConcurrentLinkedQueue<T> 
 2技术分享图片{
 3技术分享图片    private class Node<K>
 4技术分享图片    {
 5技术分享图片        internal K Item;
 6技术分享图片        internal Node<K> Next;
 7技术分享图片
 8技术分享图片        public Node(K item, Node<K> next)
 9技术分享图片        {
10技术分享图片            this.Item = item;
11技术分享图片            this.Next = next;
12技术分享图片        }
13技术分享图片    }
14技术分享图片
15技术分享图片    private Node<T> _head;
16技术分享图片    private Node<T> _tail;
17技术分享图片
18技术分享图片    public ConcurrentLinkedQueue()
19技术分享图片    {
20技术分享图片        _head = new Node<T>(default(T), null);
21技术分享图片        _tail = _head;
22技术分享图片    }
23技术分享图片
24技术分享图片    public bool IsEmpty
25技术分享图片    {
26技术分享图片        get { return (_head.Next == null); }
27技术分享图片    }
28技术分享图片
29技术分享图片    public void Enqueue(T item)
30技术分享图片    {
31技术分享图片        Node<T> newNode = new Node<T>(item, null);
32技术分享图片        while (true)
33技术分享图片        {
34技术分享图片            Node<T> curTail = _tail;
35技术分享图片            Node<T> residue = curTail.Next;
36技术分享图片
37技术分享图片            //判断_tail是否被其他process改变
38技术分享图片            if (curTail == _tail)
39技术分享图片            {
40技术分享图片                //A 有其他process执行C成功,_tail应该指向新的节点
41技术分享图片                if (residue == null) 
42技术分享图片                {
43技术分享图片                    //C 如果其他process改变了tail.next节点,需要重新取新的tail节点
44技术分享图片                    if (Interlocked.CompareExchange<Node<T>>(
45技术分享图片                        ref curTail.Next, newNode, residue) == residue) 
46技术分享图片                    {
47技术分享图片                        //D 尝试修改tail
48技术分享图片                        Interlocked.CompareExchange<Node<T>>(ref _tail, newNode, curTail); 
49技术分享图片                        return;
50技术分享图片                    }
51技术分享图片                }
52技术分享图片                else
53技术分享图片                {
54技术分享图片                    //B 帮助其他线程完成D操作
55技术分享图片                    Interlocked.CompareExchange<Node<T>>(ref _tail, residue, curTail); 
56技术分享图片                }
57技术分享图片            }
58技术分享图片        }
59技术分享图片    }
60技术分享图片
61技术分享图片    public bool TryDequeue(out T result)
62技术分享图片    {
63技术分享图片        Node<T> curHead;
64技术分享图片        Node<T> curTail;
65技术分享图片        Node<T> next;
66技术分享图片        do
67技术分享图片        {
68技术分享图片            curHead = _head;
69技术分享图片            curTail = _tail;
70技术分享图片            next = curHead.Next;
71技术分享图片            if (curHead == _head)
72技术分享图片            {
73技术分享图片                if (next == null)  //Queue为空
74技术分享图片                {
75技术分享图片                    result = default(T);
76技术分享图片                    return false;
77技术分享图片                }
78技术分享图片                if (curHead == curTail) //Queue处于Enqueue第一个node的过程中
79技术分享图片                {
80技术分享图片                    //尝试帮助其他Process完成操作
81技术分享图片                    Interlocked.CompareExchange<Node<T>>(ref _tail, next, curTail); 
82技术分享图片                }
83技术分享图片                else
84技术分享图片                {
85技术分享图片                    //取next.Item必须放到CAS之前
86技术分享图片                    result = next.Item; 
87技术分享图片                    //如果_head没有发生改变,则将_head指向next并退出
88技术分享图片                    if (Interlocked.CompareExchange<Node<T>>(ref _head, 
89技术分享图片                        next, curHead) == curHead)
90技术分享图片                        break;
91技术分享图片                }
92技术分享图片            }
93技术分享图片        }
94技术分享图片        while (true);
95技术分享图片        return true;
96技术分享图片    }
97技术分享图片}
98技术分享图片

根据自己的测试(双核CPU),在轻度和中度争用情况下,无锁算法比基于锁的算法性能好很多,在争用非常严重的情况下(100个并发线程以上/每CPU),基于锁的算法性能开始显示出优势,因为一旦发生争用,基于锁的算法会立刻切换到其他线程,而无锁算法会进入下一次循环,导致CPU的占用。但是如此严重的争用在实际中并不多见,并且可以采用SpinWait的方法加以改进。基于锁的算法在测试中曾经出现过类似死锁的现象,无锁算法则完全没有出过类似问题,另外,处理器核心越多,基于锁的算法效率越差。

 

从上面的算法实现中,可以体会到无锁算法的优势:在并发的多个线程中,总是有线程能够推进,算法总能在有限的循环次数内完成,并且在某些冲突的情况下,一个线程可以“帮助”其他线程完成被中断的工作,这些对提高吞吐量都有很大的作用。

 

原文:https://www.cnblogs.com/akxmhd/p/15305868.html

评论(0
© 2014 bubuko.com 版权所有 - 联系我们:wmxa8@hotmail.com
打开技术之扣,分享程序人生!