“c++ concurrency in action”一书中拆分引用计数示例的未决问题

q8l4jmvw  于 2023-02-26  发布在  其他
关注(0)|答案(1)|浏览(140)

关于“c++ concurrency in action”一书(第二版)7.2.4节中的清单7.11,我有两个问题,下面是一个代码片段(来自清单7.11),它实现了一个无锁堆栈,带有显式的拆分引用计数机制以避免内存泄漏(我只包含了与我的问题相关的代码)。

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;
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();
        while(!head.compare_exchange_weak(new_node.ptr->next,new_node));
    }
};

引用计数机制基于两个计数器:external_count和internalcount。externalcount 是堆栈节点(类型为 node)的 Package (类型为 * count_node_ptr*)的一部分。internal_count 保留在 node 结构中。

*问题1:push 方法中,为新项创建了一个新的 * count_node_ptr 结构体,最后由 head 指针指向它(为简单起见,假设一次只有一个线程在执行push)。然而, count_node_ptr 结构体是在堆栈上分配的,因此当返回 push() 时,head 应该被假设为悬空指针。我是否遗漏了什么?
**问题2:文中说:“ 一种可能的技术涉及对每个节点使用不是一个而是两个引用计数:一个内部计数和一个外部计数。2这些值的总和就是引用该节点的总次数。3外部计数与指向该节点的指针放在一起,每次读取该指针时,外部计数都会增加。4当读取器完成对该节点的操作时,其减小内部计数。读取指针的简单操作将使外部计数增加1,并在完成时使内部计数减少1。不再需要指针配对(节点不再可以从多线程可访问的位置进行访问),内部计数将增加外部计数减1的值,并丢弃外部计数。一旦内部计数等于零,就不再有对节点的未完成引用,可以安全地删除该节点。"。

我不完全理解这种使用两个计数器的引用计数方案:为什么一个计数器是不够的?每个计数器实际上代表什么?有没有人有这个方案的正式描述的参考(链接)?

vshtjzan

vshtjzan1#

如果你的头只是node pointer,那么在加载时你需要原子加载head,然后原子递增internal_count。在head.load()internal_count.fetch_add(1)之间可能会发生一些事情,所以你需要锁定并接收shared_ptr,而不是lockfree。在node pointer上的简单加载中:

node* old_head=head.load();

您已经使用了指针,但由于internal_count尚未递增,因此不会阻止另一个线程删除它。
在您的示例中,您为node pointer而不是pointer本身使用 Package 器,因此需要一些external_count来安全地访问它。(new_counter),如果old_counter仍然是head,则将head替换为一个atomic CAS中old_counter的增量(拥有)拷贝:

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)); 
   old_counter.external_count=new_counter.external_count;
 }

因此,在increase_head_count之后,您可以安全地访问ptr
原子internal_count您需要防止std::shared_ptr<T> pop()if(head.compare_exchange_strong(old_head,ptr->next))中的线程与else if(ptr->internal_count.fetch_sub(1)==1)中的线程之间的争用

相关问题