在" C++ Concurrency in Action"一书中,作者给出了使用危险指针实现无锁堆栈数据结构的示例.部分代码如下:
std::shared_ptr<T> pop()
{
std::atomic<void*>& hp=get_hazard_pointer_for_current_thread();
node* old_head=head.load();
node* temp;
do
{
temp=old_head;
hp.store(old_head);
old_head=head.load();
} while(old_head!=temp);
// ...
}
描述说
您必须在
while循环中执行此操作,以确保node在读取旧head指针和危险指针设置之间未删除.在此窗口期间,没有其他线程知道您正在访问此特定节点.幸运的是,如果head要删除旧 节点,head它本身必须已更改,因此您可以检查并保持循环,直到您知道head指针仍然具有您设置危险指针的相同值.
我认为代码存在缺陷,因为head节点受ABA问题的影响.即使值head保持不变,它最初指向的节点也可能已被删除.head分配了一个新节点,该节点恰好具有与前一个节点相同的地址值.
我已经在练习书和维基百科中调查了并发中的 ABA 问题，我已经阅读了以下帖子
据我了解，ABA 问题的根本原因是在算法中我们检查与以前相同的状态，但算法暗示该状态未受影响。
堆栈数据结构示例：
要将元素添加到堆栈，我们使用以下算法：
create new stack node(save to `newNode` variable)
while(true) {
oldHead = stack.get();
newNode.next = oldHead; // point_1
if(stack.compareAndSet(oldhead, newNode)) { // atomically replace head if now head same as was in start of iteration
break;
}
}
导致 ABA 问题的步骤：
初始状态
a->b->c // a-head, c- tail.
线程_1 尝试向d堆栈添加值，操作系统在compareAndSet操作前挂起线程（point_1）
Thread_2 然后执行 pop（Thread_1 仍然挂起）
b->c // b-head, c- tail.
Thread_3 然后执行 pop（Thread_1 仍然挂起）
c // c-head, c- tail.
Thread_4 然后执行 …
我提出了一个想法,我试图实现一个无锁堆栈,不依赖于引用计数来解决ABA问题,并且还正确处理内存回收.它在概念上与RCU类似,并且依赖于两个特征:将列表条目标记为已删除,以及跟踪阅读器遍历列表.前者很简单,它只使用指针的LSB.后者是我对实现无限制无锁堆栈的方法的"聪明"尝试.
基本上,当任何线程试图遍历列表时,一个原子计数器(list.entries)会递增.遍历完成后,第二个计数器(list.exits)递增.
节点分配由push处理,释放由pop处理.
推送和弹出操作与天真无锁堆栈实现非常相似,但必须遍历标记为删除的节点才能到达未标记的条目.因此推送基本上就像链表插入一样.
pop操作类似地遍历列表,但它使用atomic_fetch_or将节点标记为在遍历时被删除,直到它到达未标记的节点.
遍历0个或更多标记节点的列表后,弹出的线程将尝试CAS堆栈的头部.至少有一个并发弹出的线程将成功,在此之后,进入堆栈的所有读者将不再看到以前标记的节点.
成功更新列表的线程然后加载原子list.entries,并基本上自旋加载atomic.exits,直到该计数器最终超过list.entries.这应该意味着列表的"旧"版本的所有读者都已完成.然后,该线程只是释放它从列表顶部交换的标记节点列表.
因此,弹出操作的含义应该(我认为)可能没有ABA问题,因为释放的节点不会返回到可用的指针池,直到所有使用它们的并发读取器完成,显然内存回收问题由于同样的原因,处理也是如此.
所以,无论如何,这是理论,但我仍然在实现上摸不着头脑,因为它目前无法正常工作(在多线程情况下).似乎我在免费问题之后得到了一些写作,但是我在查找问题时遇到了麻烦,或者我的假设可能存在缺陷而且无法正常工作.
无论是概念还是调试代码的方法,都会非常感谢任何见解.
这是我当前(损坏的)代码(使用gcc -D_GNU_SOURCE -std = c11 -Wall -O0 -g -pthread -o list list.c编译):
#include <pthread.h>
#include <stdatomic.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdlib.h>
#include <sys/resource.h>
#include <stdio.h>
#include <unistd.h>
#define NUM_THREADS 8
#define NUM_OPS (1024 * 1024)
typedef uint64_t list_data_t;
typedef struct list_node_t {
struct list_node_t * _Atomic next;
list_data_t data;
} list_node_t;
typedef struct {
list_node_t * _Atomic head;
int64_t _Atomic size;
uint64_t _Atomic entries;
uint64_t _Atomic exits;
} list_t; …