来 self 之前问题的答案: Pointers in c++ after delete
很明显,使用指向“已删除”内存(特别是复制它们)的指针值会导致 c++11 中的 undef 行为,以及 c++14 中的实现定义行为。
Antomy Williams 在他的书“C++ concurrency in action”中提出了下一个带有引用计数的无锁堆栈:
#include <atomic>
#include <memory>
template<typename T>
class lock_free_stack
{
private:
struct node;
struct counted_node_ptr
{
int external_count;
node* ptr;
};
struct node
{
std::shared_ptr<T> data;
std::atomic<int> internal_count;
counted_node_ptr next;
node(T const& data_):
data(std::make_shared<T>(data_)),
internal_count(0)
{}
};
std::atomic<counted_node_ptr> head;
void increase_head_count(counted_node_ptr& old_counter)
{
counted_node_ptr new_counter;
do
{
new_counter=old_counter;
++new_counter.external_count;
}
while(!head.compare_exchange_strong(
old_counter,new_counter,
std::memory_order_acquire,
std::memory_order_relaxed));
old_counter.external_count=new_counter.external_count;
}
public:
~lock_free_stack()
{
while(pop());
}
void push(T const& data)
{
counted_node_ptr new_node;
new_node.ptr=new node(data);
new_node.external_count=1;
new_node.ptr->next=head.load(std::memory_order_relaxed)
while(!head.compare_exchange_weak(
new_node.ptr->next,new_node,
std::memory_order_release,
std::memory_order_relaxed));
}
std::shared_ptr<T> pop()
{
counted_node_ptr old_head=
head.load(std::memory_order_relaxed);
for(;;)
{
increase_head_count(old_head);
node* const ptr=old_head.ptr;
if(!ptr)
{
return std::shared_ptr<T>();
}
if(head.compare_exchange_strong(
old_head,ptr->next,std::memory_order_relaxed))
{
std::shared_ptr<T> res;
res.swap(ptr->data);
int const count_increase=old_head.external_count-2;
if(ptr->internal_count.fetch_add(
count_increase,std::memory_order_release)==-count_increase)
{
delete ptr;
}
return res;
}
else if(ptr->internal_count.fetch_add(
-1,std::memory_order_relaxed)==1)
{
ptr->internal_count.load(std::memory_order_acquire);
delete ptr;
}
}
}
};
我担心功能
void increase_head_count(counted_node_ptr& old_counter)
{
counted_node_ptr new_counter;
do
{
new_counter=old_counter;
++new_counter.external_count;
}
while(!head.compare_exchange_strong(
old_counter,new_counter,
std::memory_order_acquire,
std::memory_order_relaxed));
old_counter.external_count=new_counter.external_count;
}
看来,new_counter=old_counter;可以在 old_counter.ptr 被另一个线程删除时执行。
那么,有人可以确认或拒绝,这个堆栈实现在 c++11 中是完全不正确的吗?
最佳答案
我认为实现还有其他问题: 让我们假设两个线程在一个非空的无锁堆栈上工作:
- 线程A在代码行之后调用push()添加一个新节点 new_node.ptr->next=head.load(std::memory_order_relaxed);已经 执行完毕,线程A进入休眠状态;
- 线程 B 在代码行之后调用 pop() 删除旧节点 增加_head_count(old_head);已经执行,线程B进入 sleep ;
- 线程A继续运行,发现头节点的外部引用计数不为1,但会忽略该信息,将新节点作为新头加入栈中;
- 线程B继续运行,head.compare_exchange_strong()会失败,执行ptr->internal_count.fetch_add(-1, std::memory_order_relaxed),导致旧head的外部引用计数指针还是2,但是内部引用计数是-1。
- 所以无锁堆栈被破坏了!
谁能帮忙看看是不是真的有问题?
关于c++ - 带引用计数的无锁堆栈,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/44186686/