基于单链表的无界无锁并发队列及入队、出队方法

1.本发明涉及数据结构技术领域，具体涉及基于单链表的无界无锁并发队列及入队、出队方法。


背景技术：

2.基于链表的无锁队列有多种实现方式，其中一种比较常见的是基于单向链表的无锁队列。基于单向链表的无锁队列的主要思想是使用两个指针，一个指向队列的头结点，一个指向队列的尾结点。入队操作是将新结点链接到尾结点的后面，并更新尾指针。出队操作是将头结点的后继结点出队，并更新头指针。为保证头尾指针不为null，避免一些并发问题，即使是一个空的队列，其中也至少会保留一个哨兵节点，其中不保存数据。
3.一个基本的基于链表的无锁队列的实现步骤如下：
4.1.入队操作：
5.·
创建一个新结点，设置其值和next指针为null。
6.·
使用cas操作将尾结点的next指针指向新结点，如果成功，则说明没有其他线程竞争，否则重试。
7.·
使用cas操作将尾指针指向新结点，如果失败，则说明其他线程已经更新了尾指针，
8.不影响结果。
9.2.出队操作：
10.·
获取头结点和头结点的后继结点，如果后继结点为null，则说明队列为空，返回null。
11.·
使用cas操作将头指针指向后继结点，如果成功，则说明没有其他线程竞争，否则重试。
12.·
返回后继结点的值，并释放头结点。
13.然而，在代码实现中，保留一个常空的头节点不是一个很好的做法。在队列非空时，队列的尾指针每次会指向新加入的节点，这种单向更新能够简化无锁队列的实现，提升查询效率。而一旦队列从非空变为空，尾指针将被迫指向头节点，这破坏了尾指针更新的单向性，可能会使得代码实现变得更加复杂。为避免这一问题，部分已有实现选择不保留一个常空的哨兵节点，而是使用数据拷贝的方式传出最后一个节点的值，然而这种做法亦存在问题，如果队列元素本身结构较大，拷贝同样会引入过大开销，导致队列本身性能下降。


技术实现要素：

14.为了解决上述现有技术中存在的问题，本发明拟提供了基于单链表的无界无锁并发队列及入队、出队方法，拟解决现有基于单链表的队列无法保证尾指针更新的单向性，且需对节点内容的数据进行拷贝影响队列执行性能的问题。
15.基于单链表的无界无锁并发队列，队列中设有dumb节点，在队列仅剩最后一个元
素且需要对该元素进行出队时，入队一个dumb节点，并将原有节点出队，在队列为空时dumb节点将作为哨兵节点存在。
16.优选的，所述队列中用于链接链表节点的指针分为两部分，前半部分为更新计数，后半部分为地址部分，指向下一个节点的地址，并且此结构将作为一个数值类型进行存储。
17.基于单链表的无界无锁并发队列的入队方法，包括两步cas操作，第一步是将新节点添加至尾指针指向的节点的后继上，如果失败即重试；第二步是将尾指针更新至新插入的节点上，这一步无需重试，可由其他线程代为完成。
18.基于单链表的无界无锁并发队列的出队方法，若队列中有两个以上的节点，将头节点出队即可；若队列中仅剩一个节点，则检查此节点有无内容；若有，则入队一个dumb节点，并将原有节点出队；若无，返回null，表示此队列为空。
19.基于单链表的无界无锁并发队列的入队方法，包括如下步骤：
20.第一步：获取tail_指向的节点tail；
21.第二步：获取tail的后继节点next；
22.第三步：判断尾指针是否没有变动，即tail_是否等于tail，若不等于则返回第一步，若等于则判断next是否为空；
23.第四步：若next不为空说明有其他线程添加了新节点，使用一个cas操作将tail_时戳+1，指针修改为新节点；若为空则将新元素时戳修改为tail的时戳，后继指针赋null，再使用一个cas操作将tail的时戳+1，后继指针修改为新节点；
24.第五步：若后继指针修改为新节点修改成功则使用一个cas操作将tail_时戳+1，指针修改为新节点；若修改失败则返回第一步。
25.基于单链表的无界无锁并发队列的出队方法，包括如下步骤：
26.第一步：获得head_指向的节点head；
27.第二步：获得tail_指向的节点tail；
28.第三步：获得head的后继next；
29.第四步：判断头指针是否没有变动即head_是否等于head，若是进行下一步，若否返回第一步；
30.第五步：判断队列是否为空，即head是否等于tail，若等于则进行下一步，若否则使用一个cas操作将head_时戳+1，指针修改为next，若修改成功则返回head节点则流程结束，若修改失败则返回第一步；
31.第六步：检查head的后继是否为null，若是则进行下一步，若否则说明有新节点入队，更新tail_即使用一个cas操作将tail_时戳+1，指针修改为新节点，而后返回第一步；
32.第七步：检查head是否为dumb节点，若是则说明队列无元素可返回，返回null而后结束，若否则说明当前队列只有一个元素，创建一个dumb节点入队下一轮将此节点出队，而后返回第一步。
33.本发明的有益效果包括：
34.1、本发明能够解决现有单链表无锁队列实现中提到的问题，既保证了尾指针更新的单向性，又无需进行对节点内容的数据拷贝，一定程度上提升了队列的执行性能。
35.2、在实际使用场景中，本发明相比c++boost::lockfree::queue即目前主流的无锁队列实现，性能存在较大提升，在使用本发明实现的mpmc(多生产者多消费者)queue，分
别进行每核一定数量级(n)的入队和出队操作，在不同n取值下，性能最终要优于boost库队列约30％左右。
附图说明
36.图1为实施例1基于单链表的无界无锁并发队列的结构。
37.图2为实施例1基于单链表的无界无锁并发队列的链表节点指针结构。
38.图3为实施例1涉及基于单链表的无界无锁并发队列的入队方法。
39.图4为实施例1涉及基于单链表的无界无锁并发队列的出队方法。
40.图5为实施例1涉及现有技术与本发明性能对比图。
具体实施方式
41.为使本技术实施例的目的、技术方案和优点更加清楚，下面将结合本技术实施例中附图，对本技术实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅是本技术一部分实施例，而不是全部的实施例。因此，以下对在附图中提供的本技术的实施例的详细描述并非旨在限制要求保护的本技术的范围，而是仅仅表示本技术的选定实施例。基于本技术的实施例，本领域技术人员在没有做出创造性劳动的前提下所获得的所有其他实施例，都属于本技术保护的范围。
42.实施例1
43.下面结合附图1-2对基于单链表的无界无锁并发队列的具体实施例做详细的说明；
44.基于单链表的无界无锁并发队列，队列中设有dumb节点，在队列仅剩最后一个元素且需要对该元素进行出队时，入队一个dumb节点，并将原有节点出队，在队列为空时dumb节点将作为哨兵节点存在。所述队列中用于链接链表节点的指针分为两部分，前半部分为更新计数，后半部分为地址部分，指向下一个节点的地址，并且此结构将作为一个数值类型进行存储。
45.本发明与现有技术相比，能够保证尾指针更新的单向性，并且不论何种场景，尾指针始终会被更新至新入队的节点，这样做将大大简化队列的实现。
46.同时，与现有技术相比，本发明不存在拷贝开销。原有方案若希望保证尾指针更新的单向性，在最后一个节点出队时，需要将其内容拷贝至哨兵节点，并将哨兵节点出队，这种做法不但引入了拷贝开销，还在底层改变了数据的存放地址，这对队列的使用者并不友好，本发明的设计可以较好地解决这些问题。
47.在此之上，为避免出现aba问题，本发明选择在指针中引入更新计数。具体而言，用于链接链表节点的指针(或称为铆接点)将分为两部分，前半部分为更新计数(或称时戳)，后半部分为地址部分，指向下一个节点的地址，如图1所示。此结构将作为一个数值类型进行存储，仅需要一次cas操作即可完成更新。
48.实施例2
49.下面结合附图3对基于单链表的无界无锁并发队列的入队方法的具体实施例做详细的说明；
50.基于单链表的无界无锁并发队列的入队方法，对于入队方法，主要完成两步cas操
作，第一步是将新节点添加至尾指针指向的节点的后继上，如果失败即重试；第二步是将尾指针更新至新插入的节点上，这一步无需重试，可由其他线程代为完成。
51.具体包括如下步骤：
52.第一步：获取tail_指向的节点tail；
53.第二步：获取tail的后继节点next；
54.第三步：判断尾指针是否没有变动，即tail_是否等于tail，若不等于则返回第一步，若等于则判断next是否为空；
55.第四步：若next不为空说明有其他线程添加了新节点，使用一个cas操作将tail_时戳+1，指针修改为新节点；若为空则将新元素时戳修改为tail的时戳，后继指针赋null，再使用一个cas操作将tail的时戳+1，后继指针修改为新节点；
56.第五步：若后继指针修改为新节点修改成功则使用一个cas操作将tail_时戳+1，指针修改为新节点；若修改失败则返回第一步。
57.实施例3
58.下面结合附图4对基于单链表的无界无锁并发队列的出队方法的具体实施例做详细的说明；
59.基于单链表的无界无锁并发队列的出队方法，若队列中有两个以上的节点，将头节点出队即可；若队列中仅剩一个节点，则检查此节点有无内容。若有，则入队一个dumb节点，并将原有节点出队；若无，返回null，表示此队列为空；
60.具体包括如下步骤：
61.第一步：获得head_指向的节点head；
62.第二步：获得tail_指向的节点tail；
63.第三步：获得head的后继next；
64.第四步：判断头指针是否没有变动即head_是否等于head，若是进行下一步，若否返回第一步；
65.第五步：判断队列是否为空，即head是否等于tail，若等于则进行下一步，若否则使用一个cas操作将head_时戳+1，指针修改为next，若修改成功则返回head节点则流程结束，若修改失败则返回第一步；
66.第六步：检查head的后继是否为null，若是则进行下一步，若否则说明有新节点入队，更新tail_即使用一个cas操作将tail_时戳+1，指针修改为新节点，而后返回第一步；
67.第七步：检查head是否为dumb节点，若是则说明队列无元素可返回，返回null而后结束，若否则说明当前队列只有一个元素，创建一个dumb节点入队下一轮将此节点出队，而后返回第一步。
68.在实际使用场景中，本发明相比c++boost::lockfree::queue(目前主流的无锁队列实现)，性能存在较大提升。在48逻辑核场景下，对boost::lockfree::queue，以及使用本发明实现的队列mpmc(多生产者多消费者)queue，分别进行每核一定数量级(n)的入队和出队操作，在不同n取值下，单次出入队操作时延如图5所示；由于c++boost库封装的复杂性较高，初始化开销相对较大，在测试数据量较小时，可观察到本发明性能明显优于boost库的队列。随着测试数据量增大，这种效应被稀释了，但仍可观察到本发明性能明显优于boost库队列。在测试中，本发明的性能相对较为稳定，在1000ns附近波动，而随着测试数据量继
续增大，boost库的队列性能也将渐渐趋于一个固定值。通过计算可知，本发明的性能最终要优于boost库约30％左右。
69.以上所述实施例仅表达了本技术的具体实施方式，其描述较为具体和详细，但并不能因此而理解为对本技术保护范围的限制。应当指出的是，对于本领域的普通技术人员来说，在不脱离本技术技术方案构思的前提下，还可以做出若干变形和改进，这些都属于本技术的保护范围。

技术特征：
1.基于单链表的无界无锁并发队列，其特征在于，队列中设有dumb节点，在队列仅剩最后一个元素且需要对该元素进行出队时，入队一个dumb节点，并将原有节点出队，在队列为空时dumb节点将作为哨兵节点存在。2.根据权利要求1所述的基于单链表的无界无锁并发队列，其特征在于，所述队列中用于链接链表节点的指针分为两部分，前半部分为更新计数，后半部分为地址部分，指向下一个节点的地址，并且此结构将作为一个数值类型进行存储。3.基于单链表的无界无锁并发队列的入队方法，其特征在于，包括两步cas操作，第一步是将新节点添加至尾指针指向的节点的后继上，如果失败即重试；第二步是将尾指针更新至新插入的节点上，这一步无需重试，可由其他线程代为完成。4.基于单链表的无界无锁并发队列的出队方法，其特征在于，若队列中有两个以上的节点，将头节点出队即可；若队列中仅剩一个节点，则检查此节点有无内容；若有，则入队一个dumb节点，并将原有节点出队；若无，返回null，表示此队列为空。5.根据权利要求3所述的基于单链表的无界无锁并发队列的入队方法，其特征在于，包括如下步骤：第一步：获取tail_指向的节点tail；第二步：获取tail的后继节点next；第三步：判断尾指针是否没有变动，即tail_是否等于tail，若不等于则返回第一步，若等于则判断next是否为空；第四步：若next不为空说明有其他线程添加了新节点，使用一个cas操作将tail_时戳+1，指针修改为新节点；若为空则将新元素时戳修改为tail的时戳，后继指针赋null，再使用一个cas操作将tail的时戳+1，后继指针修改为新节点；第五步：若后继指针修改为新节点修改成功则使用一个cas操作将tail_时戳+1，指针修改为新节点；若修改失败则返回第一步。6.根据权利要求4所述的基于单链表的无界无锁并发队列的出队方法，其特征在于，包括如下步骤：第一步：获得head_指向的节点head；第二步：获得tail_指向的节点tail；第三步：获得head的后继next；第四步：判断头指针是否没有变动即head_是否等于head，若是进行下一步，若否返回第一步；第五步：判断队列是否为空，即head是否等于tail，若等于则进行下一步，若否则使用一个cas操作将head_时戳+1，指针修改为next，若修改成功则返回head节点则流程结束，若修改失败则返回第一步；第六步：检查head的后继是否为null，若是则进行下一步，若否则说明有新节点入队，更新tail_即使用一个cas操作将tail_时戳+1，指针修改为新节点，而后返回第一步；第七步：检查head是否为dumb节点，若是则说明队列无元素可返回，返回null而后结束，若否则说明当前队列只有一个元素，创建一个dumb节点入队下一轮将此节点出队，而后返回第一步。

技术总结
本发明公开基于单链表的无界无锁并发队列及入队、出队方法，涉及数据结构技术领域，拟解决现有基于单链表的队列无法保证尾指针更新的单向性，且需对节点内容的数据进行拷贝影响队列执行性能的问题；本发明在基于单链表的无锁队列中设有dumb节点，在队列仅剩最后一个元素且需要对该元素进行出队时，入队一个dumb节点，并将原有节点出队，在队列为空时dumb节点将作为哨兵节点存在；本发明能够解决现有单链表无锁队列实现中提到的问题，既保证了尾指针更新的单向性，又无需进行对节点内容的数据拷贝，提升了队列的执行性能。提升了队列的执行性能。提升了队列的执行性能。


技术研发人员：聂晓文 黄麒之
受保护的技术使用者：电子科技大学
技术研发日：2023.05.10
技术公布日：2023/7/27