这几天看了许多关于 lock-free 和 memory-reordering 的资料,在看到 C++ Concurrency in Action 时候写了一个自己理解的 lock-free 结构。
class LockFreeStack
{
using T = int;
private:
struct Node
{
T val;
Node *next;
};
public:
LockFreeStack() : head(nullptr), length(0){};
void Push(const T &val)
{
Node *new_node = new Node{val, nullptr};
Node *old_head = nullptr;
do
{
old_head = head.load(std::memory_order_release);
} while (!head.compare_exchange_strong(old_head, new_node, std::memory_order_acquire, std::memory_order_acquire));
new_node->next = old_head;
length.fetch_add(1, std::memory_order_relaxed);
}
};
但是和书上不一致:
class lock_free_stack
{
private:
struct node
{
std::shared_ptr<T> data;
node* next;
node(T const& data_):
data(std::make_shared<T>(data_))
{}
};
std::atomic<node*> head;
public:
void push(T const& data)
{
node* const new_node=new node(data); // 1
new_node->next=head.load(); //2
while(!head.compare_exchange_weak(new_node->next,new_node)); //3
}
};
我就很疑惑,他算法中一个线程 A 如果执行到 @2 被休眠,如果其他 push 线程 直接执行 @2 ,@3 ,修改了 head atomic 值,线程 A 不就一直卡死了吗?
1
Reiouf OP 怎么没人捏
|
2
Reiouf OP 我看了 http://15418.courses.cs.cmu.edu/spring2013/article/46 cmu 的一个作业也是在 while 套 cas 如此解决的。
|
3
piaodazhu 2023-05-17 20:38:47 +08:00
第一个在倒数第二三行之间有可能出现暂时的断链情况?
第二个我也感觉有问题。 你发那个链接里第一个代码倒是可以理解的。 |
4
Reiouf OP @piaodazhu 你说的是` new_node->next = old_head;` 在执行之前就被 睡掉了的情况吗?确实可能诶
那我把 new_node->next = old_head; 放到 while 里就完美了 你觉得呢 |
5
C47CH 2023-05-17 21:17:22 +08:00 1
去看了下 compare_exchange_weak 的定义,如果不相等的话会更新 new_node->next 的值,然后继续比较,最后会完成修改。
|
6
DeltaC 2023-05-17 21:44:34 +08:00
打开 Cppreference 的 compare_exchange 正巧就是你这个算法的这个问题。
看了下注释,这和编译器版本有关。 > https://en.cppreference.com/w/cpp/atomic/atomic/compare_exchange |
7
exch4nge 2023-05-17 22:03:25 +08:00 1
贴的第一个代码不对,贴的第二个跟链接里的代码是对的。原因上面 @piaodazhu @C47CH 说了,虽然重复我也说一下。
贴的第一个: - head 已经在 compare exchange 修改了,不过 new_node 的 next 没设置,导致断了 - 用 compare_exchange_weak 就好,不过我不确定你用的 memory order 对不对 - 这里 length 更新会比实际慢,所以会有差异 - while 里的 old_head = head.load(std::memory_order_release); 除了第一次有用外,没什么用,应该放在 do 上面 贴的第二个,解答你的问题。 如果线程 A 如果执行到 @2 被休眠,如果其他 push 线程 直接执行 @2 ,@3 修改了 head atomic 值,线程 A 不就一直卡死了吗? 不会卡死,因为 compare_exchange_weak 会失败,同时会设置 new_node->next 的值。所以是对的。 4L 你的问题:new_node->next = old_head 放到 while 循环里后逻辑是对的。其它问题参考上面的问题列表 |
8
artnowben 2023-05-17 22:11:05 +08:00
lockfree 队列比较实用,DPDK 里面的实现性能非常高,有官方文档介绍。
|
9
piaodazhu 2023-05-18 08:59:50 +08:00
学习了! compare_exchange_weak 和 compare_exchange_strong 还是很不一样的
|
10
Reiouf OP @piaodazhu 我重新看了 cppdocs ,compare_exchange_strong 会在失败的时候置换 expected 值的,他两的差异点在于 week 可能 fail spuriously.
|
12
artnowben 2023-05-18 11:21:27 +08:00
|
13
Reiouf OP C++ concurrency in Actionn 内容真太丰富了,后面看的速度降了好多
|