《c++并发编程》中无锁栈的实现为什么要用双引用计数器

2024-04-13 13:12

本文主要是介绍《c++并发编程》中无锁栈的实现为什么要用双引用计数器,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

背景

《c++并发编程》中,实现无锁栈用了引用计数技术。原因是,pop方法要删除栈顶中的节点,然而,由于1.读取栈顶指针->2.根据栈顶指针访问栈顶节点、获取栈顶节点所保存的数据以及下一个节点指针next_node->3.更新栈顶指针为next_node->4.删除栈顶节点这4个 步骤不能做到原子,所以可能出现下面情况,线程A执行完步骤1后,在执行步骤2之前,线程B一口气执行完步骤1-4,把节点删除了,然后线程A执行步骤2,就是一个空悬指针解引用的错误,因为线程A并不知道他要访问的节点,已经被线程B删除了。为了不让这中情况发生,需要使用引用计数技术,每有一个指针指向一个某个对象,这个对象的引用计数就+1。当指向一个对象的指针不再指向它时,它的引用计数就-1。当它的引用计数减少为0时,把他减为0的线程,要负责删除这个节点。所以,只要还有一个指针在指涉一个对象,这个对象就不会被删除。换句话说,就是让线程B知道线程A中有一个指针在指向它所弹出的节点,使得他不执行步骤4。

在《c++并发编程》实现引用计数用了两个计数器,一个计数器在节点内部,成为内部计数器。一个被称为外部计数器的计数器与指针绑定成结构体counted_node_ptr。栈顶指针的类型从原生指针修改为counted_node_ptr。每当有线程通过载入head指针,外部计数器+1。每当线程不再有指涉某个节点的指针,内部计数器-1,内部计数器+外部计数器=节点的实际引用计数,当它为0时,删除节点,数据结构如下图。(上上句话就是我写这篇博客的原因,我花了好长时间才想通为什么要这么做,为什么要搞内外引用计数器,为什么不合并每个计数器,后面我会讲,但现在,先让我把书本的做法介绍完)
在这里插入图片描述
当有线程要弹出数据时,它首先读取head指针(栈顶指针),存到线程局部变量local_head中并让head中的外部计数器+1,这个过程可以做到原子,接着它让local_head的计数器也变为和head中的计数器一样。然后,它通过local_head访问节点。如果它不能弹出节点(判定条件是:local_head与head不相同,也即有其他线程在本线程把head载入到local_head之后,修改了head指针),本线程载入的local_head作废),就把节点的内部计数器-1(本线程马上就不会指向这个节点的指针了)。如果节点的内部计数器因此变为了0(也即他原本为1),则本线程删除这个节点。否则,啥也不做(此时内部计数器可能为负数)。如果它能够弹出数据(判定条件是:old_head仍然与head相同,也即没有其他线程在本线程把head载入到local_head之后,修改head指针),则它把head指针修改为head.ptr->next。注意,判定并修改可以做到原子。然后,local_head的外部计数器-1(因为head指针已经不在指向这个节点),再让local_head的外部计数器-1(因为 local_head也准备不指向这个节点了,实际写代码时,让local_head减2就行,我分开讲是为了说清楚减的2是哪两个1)。然后,把local_head的计数器的值加到内部计数器。如果内部计数器因此变为0,也即他原本为local_head的外部计数器的相反数。则本线程负责把节点删除,否则,不删除节点。

为什么要两个计数器,一个可以吗?

如果一个可以,那考虑这个计数器放再哪里。放在节点内部吗?不行,因为计数器是为了解决空悬指针解引用,如果他放在节点内部,那访问计数器必须先访问节点。考虑下面场景:线程A读取head指针,存到local_head中,还没来得及通过local_head访问节点内部的引用计数器,让他加1,线程B率先访问到了节点引用计数器,让计数器+1。然后弹出节点,退出前,让计数器-1。发现计数器因此变成了0。删除节点。然后线程A才开始通过local_head访问节点内部引用计数器并试图让节点内部计数器+1。但是,节点已经被删除了,又出现了空悬指针解引用。所以,如果一个计数器可行,它只能在节点外面。那放在哪里呢?这个计数器需要让所有线程都能直接访问到(节点不属于所有线程能直接访问到的数据,它只能通过head指针间接访问)。它应该和head指针(所有线程都能直接访问)有相同的地位。参考外部指针,把计数器和head指针合2为1使得读head指针和计数器+1有机会原子进行(否则,读head指针和让计数器+1必定有时间间隙,不可能原子进行,因为他们属于两个不同的变量)。只有一个计数器,那么理论很直观。每有一个指向head节点的指针,就让计数器+1,当指针不再指向这个节点时,让它-1。理想很美好,现实怎么实现呢?
看看下面步骤
线程A载入head 到 local_head(类型为counted_node_ptr)。如果head没有变化,就让head的计数器+1。然后local_head也加1,此时他们head和local_head的计数器都为2。这些步骤都发生在访问节点之前,如果本线程确实要访问local_head指向的节点,由于计数器变为了2,所以节点肯定不会被删除。它之后可以安全地访问local_head指向的节点。但它还没来得及访问,线程B这时候载入head到local_head中,并让head计数器和local_head计数器都变为了3。(它看到head指针为3,就知道,此时除了它自己,还有另一个线程在访问head节点。),它把head指针修改为了head.ptr->next。这时候,head的计数器变为了1,因此此时head指针指向的对象改变了,而那个对象目前只有head指针一个指针在指向它。线程B检查local_head的计数器,让local_head的计数器-2。也即让local_head的计数器变为了1。由于计数器不为0,所以它没有删除节点。它完成了巩工作,pop函数退出。此时线程A安全地访问它的local_head所指向的节点,发现local_head和head已经不一样,所有它放弃弹出这节点。它让local_head的计数器-1,使得local_head的计数器变为了1,由于不为0,所以没有删除节点。这样,这个节点永远都不会被删除了。问题出在哪里呢?计数器应该是节点关联的,它应该存在节点内部,一个节点应该只有一个计数器,但这里,我们无法把计数器放在节点的内部,而放在节点的外部,又需要和head指针拼在一起使得他们读head指针和让计数器+1能够原子进行。这样,就会产生多个计数器,head指针和每个进程各有一个计数器。每个线程让计数器-1,别的进程是不可见的。这就是问题所在。
所以,一个计数器是不行的,除非我们可以让所有的节点有且只有一个计数器,就像shared_ptr那样,可惜,shared_ptr无法做到和读head指针无锁但原子地进行。

双引用计数器的原理是什么

外部计数器:为了线程读读head指针时,知道除了它自己,还有几个线程和自己读取了相同的head。一个线程退出时,如果它修改了head指针它减去自己知道的有2个指针不再指向那个节点,得出一个值x。x就是在它的视角看来,他退出后,还有x个线程在指向这个节点,把这个值加上节点内部计数器,就像是通知这个节点,你的任务已经完成了,但是,由于在我看来,还有x个线程在指向你,除非他们都不再指向你了(内部计数器的值为外部计数器的值的相反数),否则我不能删除你。如果它没有修改head指针,它让节点内部计数器-1,就像告诉节点,我已经不再指向你了,如果你现在没有被其他人引用的话(内部计数器为1),我就删除你,否则,我只是通知你。你后面可以告诉别人我不再引用你了。
内部计数器:有多少个指针在引用自己。但更新滞后,并不是每有一个指针指向它,它就立刻更新。
外部计数器更新及时,但不为所有线程所见,内部计数器为所有线程所见,但更新不及时,他们按照协议相互配合,才能正确工作。

这篇关于《c++并发编程》中无锁栈的实现为什么要用双引用计数器的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/900229

相关文章

SpringBoot3实现Gzip压缩优化的技术指南

《SpringBoot3实现Gzip压缩优化的技术指南》随着Web应用的用户量和数据量增加,网络带宽和页面加载速度逐渐成为瓶颈,为了减少数据传输量,提高用户体验,我们可以使用Gzip压缩HTTP响应,... 目录1、简述2、配置2.1 添加依赖2.2 配置 Gzip 压缩3、服务端应用4、前端应用4.1 N

SpringBoot实现数据库读写分离的3种方法小结

《SpringBoot实现数据库读写分离的3种方法小结》为了提高系统的读写性能和可用性,读写分离是一种经典的数据库架构模式,在SpringBoot应用中,有多种方式可以实现数据库读写分离,本文将介绍三... 目录一、数据库读写分离概述二、方案一:基于AbstractRoutingDataSource实现动态

Python FastAPI+Celery+RabbitMQ实现分布式图片水印处理系统

《PythonFastAPI+Celery+RabbitMQ实现分布式图片水印处理系统》这篇文章主要为大家详细介绍了PythonFastAPI如何结合Celery以及RabbitMQ实现简单的分布式... 实现思路FastAPI 服务器Celery 任务队列RabbitMQ 作为消息代理定时任务处理完整

揭秘Python Socket网络编程的7种硬核用法

《揭秘PythonSocket网络编程的7种硬核用法》Socket不仅能做聊天室,还能干一大堆硬核操作,这篇文章就带大家看看Python网络编程的7种超实用玩法,感兴趣的小伙伴可以跟随小编一起... 目录1.端口扫描器:探测开放端口2.简易 HTTP 服务器:10 秒搭个网页3.局域网游戏:多人联机对战4.

Java枚举类实现Key-Value映射的多种实现方式

《Java枚举类实现Key-Value映射的多种实现方式》在Java开发中,枚举(Enum)是一种特殊的类,本文将详细介绍Java枚举类实现key-value映射的多种方式,有需要的小伙伴可以根据需要... 目录前言一、基础实现方式1.1 为枚举添加属性和构造方法二、http://www.cppcns.co

使用Python实现快速搭建本地HTTP服务器

《使用Python实现快速搭建本地HTTP服务器》:本文主要介绍如何使用Python快速搭建本地HTTP服务器,轻松实现一键HTTP文件共享,同时结合二维码技术,让访问更简单,感兴趣的小伙伴可以了... 目录1. 概述2. 快速搭建 HTTP 文件共享服务2.1 核心思路2.2 代码实现2.3 代码解读3.

MySQL双主搭建+keepalived高可用的实现

《MySQL双主搭建+keepalived高可用的实现》本文主要介绍了MySQL双主搭建+keepalived高可用的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,... 目录一、测试环境准备二、主从搭建1.创建复制用户2.创建复制关系3.开启复制,确认复制是否成功4.同

Java实现文件图片的预览和下载功能

《Java实现文件图片的预览和下载功能》这篇文章主要为大家详细介绍了如何使用Java实现文件图片的预览和下载功能,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... Java实现文件(图片)的预览和下载 @ApiOperation("访问文件") @GetMapping("

Java并发编程必备之Synchronized关键字深入解析

《Java并发编程必备之Synchronized关键字深入解析》本文我们深入探索了Java中的Synchronized关键字,包括其互斥性和可重入性的特性,文章详细介绍了Synchronized的三种... 目录一、前言二、Synchronized关键字2.1 Synchronized的特性1. 互斥2.

使用Sentinel自定义返回和实现区分来源方式

《使用Sentinel自定义返回和实现区分来源方式》:本文主要介绍使用Sentinel自定义返回和实现区分来源方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Sentinel自定义返回和实现区分来源1. 自定义错误返回2. 实现区分来源总结Sentinel自定