本文共 3002 字，大约阅读时间需要 10 分钟。

简介

最近学习《CPP concurrency in action》的一些总结，文中的图片与程序皆是引用于该书。

*数据结构并发编程中，内存回收一直是一个头疼的问题。下面简单介绍使用引用计数的方式，进行内存回收。

背景：

以最简单的数据结构——栈为例，进行在设计无锁的线程安全栈结构时，借助的是原子操作和内存顺序特性实现。栈结构设计，其本质就是对结点node指针进行操作，push()操作只有内存分配问题，较为简单；但是进行pop()操作存在内存回收问题，就没有想象中那么简单了。这里详细介绍pop()操作，步骤可分为如下5歩：

• 1.读取当前head指针的值；
• 2.读取head->next；
• 3.设置head为head->next；
• 4.通过索引node，返回data数据；
• 5.删除node结点。

一、简单版无锁pop()设计（存在内存泄露）

如果不考虑内存泄露，在多线程环境下， 使用compare_exchange_weak()就能够设置出优雅的程序：

其实就是根据上面的5歩进行的，首先读取head的值，while()循环是重点：判断是否有其他线程更新了head值。若有，则将old_head更新为最新的head值，并返回false；否则，将head值设置为old_head->next；最后一句就是通过引用返回结点数据。

很明显，这儿存在内存泄露，没有对删除的old_head结点进行内存回收。

二、自定义引用计数内存回收机制

为什么在多线程中，对内存的回收就不简单了呢？

主要是如果当前线程正删除一个结点，进行内存回收，而同时另外一个线程对该结点进行访问，这就会出现未定义行为。所以在内存回收的时候，需要保证所有线程都不会再访问该结点，这样才能安全删除结点，进行内存回收。 所谓的引用计数，就是添加一个计数器threads_in_pop，并且将变量声明为原子类型；每次调用pop()操作，thread_in_pop计数器就加一，表示调用pop操作的线程数。如果只有当前线程（即thread_in_pop=1），那么表示结点可以安全的删除；否则，就将该结点插入到待删除结点链表nodes_to_delete中，进行等待安全删除。 下面是实现程序：

class lock_free_stack{private:    std::atomic
   
     threads_in_pop;    void try_reclaim(node* old_head);public:   //pop()操作实现函数    std::shared_ptr
    
      pop()    {        ++threads_in_pop;        node* old_head=head.load();        while(old_head &&              !head.compare_exchange_weak(old_head,old_head->next));        std::shared_ptr
     
       res;        if(old_head)        {            res.swap(old_head->data);        }        try_reclaim(old_head);  //尝试回收内存        return res;    }private:    std::atomic
      
        to_be_deleted;    static void delete_nodes(node* nodes)    {        while(nodes)        {            node* next=nodes->next;            delete nodes;            nodes=next;        }    }    void try_reclaim(node* old_head)    {        if(threads_in_pop==1)        {    //声明一个新结点获取以前待删除节点列表            node* nodes_to_delete=to_be_deleted.exchange(nullptr);                         if(!--threads_in_pop)  //注意这儿的检测            {                delete_nodes(nodes_to_delete);            }            else if(nodes_to_delete)            {               //存在多个线程更新to_be_deleted结点               //将提取出的待删除列表，重新插入到待删除列表中                chain_pending_nodes(nodes_to_delete);              }            delete old_head;        }        else        {            chain_pending_node(old_head);            --threads_in_pop;        }    }    void chain_pending_nodes(node* nodes)    {        node* last=nodes;        while(node* const next=last->next)        {            last=next;        }        chain_pending_nodes(nodes,last);    }    void chain_pending_nodes(node* first,node* last)    {        last->next=to_be_deleted;        while(!to_be_deleted.compare_exchange_weak(last->next,first) );    }    void chain_pending_node(node* n)    {        chain_pending_nodes(n,n);    }};
      
     
    
   

注意：上述程序中对thread_in_pop的两次检测，因为在声明待删链表过程可能存在其他的线程调用pop操作，从而更新数据，所以在实际删除前，需要再次检测。若只有一个这将待删链表节点，全部回收，若不是将节点加入到之前的待删链表中；若thread_in_pop第一次检测时不等于1，即已经有多个线程进行了调用，那么就直接将old_head插入到待删链表中即可。

待删列表其实是一个栈结构，先入后出结构。

最后，内存回收还有使用shared_ptr智能指针、风险指针的方式，可以查看该书籍第七章。

转载地址：http://esjmb.baihongyu.com/