Tag: aba

Lock Free堆栈实现的想法 – 目前已经破解

我想出了一个想法，我试图实现一个无锁堆栈，不依赖引用计数来解决ABA问题，并且还正确处理内存回收。 它在概念上与RCU类似，并且依赖于两个特征：将列表条目标记为已删除，以及跟踪阅读器遍历列表。 前者很简单，它只使用指针的LSB。 后者是我对实现无限制无锁堆栈的方法的“聪明”尝试。 基本上，当任何线程试图遍历列表时，一个primefaces计数器（list.entries）会递增。 遍历完成后，第二个计数器（list.exits）递增。 节点分配由push处理，释放由pop处理。 推送和弹出操作与天真无锁堆栈实现非常相似，但必须遍历标记为删除的节点才能到达未标记的条目。 因此推送基本上就像链表插入一样。 pop操作类似地遍历列表，但它使用atomic_fetch_or将节点标记为在遍历时被删除，直到它到达未标记的节点。 遍历0个或更多标记节点的列表后，弹出的线程将尝试CAS堆栈的头部。 至少有一个并发弹出的线程将成功，在此之后，进入堆栈的所有读者将不再看到以前标记的节点。 成功更新列表的线程然后加载primefaceslist.entries，并基本上自旋加载atomic.exits，直到该计数器最终超过list.entries。 这应该意味着列表的“旧”版本的所有读者都已完成。 然后，该线程只是释放它从列表顶部交换的标记节点列表。 因此，弹出操作的含义应该（我认为）可能没有ABA问题，因为释放的节点不会返回到可用的指针池，直到所有使用它们的并发读取器完成，显然内存回收问题由于同样的原因，处理也是如此。 所以，无论如何，这是理论，但我仍然在实施上摸不着头脑，因为它目前无法正常工作（在multithreading情况下）。 似乎我在免费问题之后得到了一些写作，但是我在查找问题时遇到了麻烦，或者我的假设可能存在缺陷而且无法正常工作。 无论是概念还是调试代码的方法，都会非常感谢任何见解。 这是我当前（损坏的）代码（使用gcc -D_GNU_SOURCE -std = c11 -Wall -O0 -g -pthread -o list list.c编译）： #include #include #include #include #include #include #include #include #define NUM_THREADS 8 #define NUM_OPS (1024 * 1024) typedef uint64_t list_data_t; typedef struct list_node_t { struct […]