关于编程:Datenlord-垃圾回收机制与无锁化编程

垃圾回收机制（GC）对大部分开发者来说应该不生疏，特地是Java开发者或多或少都跟GC打过交道。 GC的长处是实现对堆上调配的内存动静回收，防止内存透露。然而GC的毛病是对性能有肯定影响，特地是stop the world问题，而且GC什么时候回收内存是不确定的，开发者无奈通晓。

在无锁化编程场景下，用Java这种有GC的语言，肯定水平简化了对内存的治理，升高了无锁化编程的难度。无锁化编程，顾名思义，就是不必锁。无锁化编程特指在多线程编程的时候，对线程间共享数据的并发批改不应用锁，而采纳基于硬件提供的原子操作能力来批改共享数据，进而晋升性能，缩小应用锁带来的互斥开销。

最罕用的硬件提供的原子操作是Compare and Swap（简称CAS），编程语言基于硬件提供的原子操作能力封装出CAS库函数调用。先看下C++里的CAS函数调用：

bool __sync_bool_compare_and_swap(    type *ptr, type oldval, type newval, ...);type __sync_val_compare_and_swap(    type *ptr, type oldval, type newval, ...);

这两个函数的性能一样，只是返回值不同。为了简化形容，略去了一些细节（这个细节是对于内存程序，即程序指令在执行时的程序问题，这个问题是无锁化编程是否正确实现的关键问题之一，前面我再专门具体介绍）。第一个CAS函数比拟指针ptr指向的变量，看是不是等于oldval，如果相等就把ptr指向的变量改为newval，并返回true，否则不做任何扭转并返回false。第二个CAS函数也是比拟ptr指向的变量是否等于oldval，如果相等就把该变量改为newval，并返回oldval，如果不等就不做扭转，并返回ptr指向变量的以后值。 C++的CAS函数调用能够保障对ptr指向的变量的批改是原子的，要么更改实现，要么不做更改。

再看下硬件提供的原子操作。比方X86架构提供了一条CAS指令cmpxchg，这条指令在执行时是由硬件保障原子性，不会被打断。其余硬件架构，比方ARM、PowerPC也提供相似的CAS原子操作，然而和X86的实现机制不一样，这里先不开展。编程语言的编译器在X86架构下编译时，会负责把CAS库函数调用编译成基于cmpxchg的机器代码。比方C++的编译器GCC在编译时如果碰到下面两个CAS函数调用，会生成蕴含cmpxchg指令的指标码。

无锁化编程示例：无锁化堆栈（Lock-Free Stack）的Java实现

先来看个简略的无锁化编程的例子，一个无锁化堆栈的Java实现（从网上找了一段现成的代码，没通过编译验证，仅做示例）:

import java.util.concurrent.atomic.*;import net.jcip.annotations.*;/*** ConcurrentStack** @author Brian Goetz and Tim Peierls*/@ThreadSafepublic class ConcurrentStack <E> {    AtomicReference<Node<E>> top =        new AtomicReference<Node<E>>(); // 栈顶    public void push( E item ) {        Node<E> newNode = new Node<E>( item );        Node<E> curTop;        do {            curTop = top.get();            newNode.next = curTop;                  // CAS调用批改栈顶        } while ( !top.compareAndSet(                curTop, newNode ) );    }    public E pop() {        Node<E> curTop;        Node<E> newTop;        do {            curTop = top.get();            if ( curTop == null ) {                return null; // 堆栈为空            }            newTop = curTop.next;                    // CAS调用批改栈顶        } while ( !top.compareAndSet(                curTop, newTop ) );                        return curTop.item;    }    private static class Node <E> {        public final E item;        public Node<E> next;        public Node( E item ) {            this.item = item;        }    }}

从代码能够看出，这个栈的实现齐全没有用锁，栈顶top是以后堆栈顶端节点的原子援用AtomicReference，每次出栈（pop）入栈（push）的时候，调用AtomicReference的compareAndSet办法来试图批改栈顶top。因为有可能有多个线程竞争拜访这个无锁化堆栈，即有可能有多个线程同时对栈顶进行批改，或同时pop、或同时push，或同时pop和push， CAS的原子性保障了多个线程并发调用compareAndSet办法批改栈顶top时，仅有一个线程的调用能批改胜利，其余线程的调用不胜利，所以pop和push操作里要用循环的形式反复调用compareAndSet办法试图批改栈顶top，直到胜利返回。

从这个例子能够看出无锁化编程的一个显著特点，对共享数据的批改要多次重试CAS操作。尽管CAS调用基于硬件提供的原子能力，然而CAS调用的代价也不小。比方在X86多处理器架构下运行下面的无锁化堆栈，每次CAS办法调用会运行cmpxchg指令，这个指令使得多个处理器缓存里的栈顶top生效，导致多个处理器要从新从内存加载top。如果频繁调用CAS试图批改共享数据，将导致处理器缓存里的共享数据频繁生效，这个对性能的影响也不小。所以千万不要滥用CAS调用。

无锁化编程示例：无锁化堆栈的C++实现

下面用Java实现无锁化堆栈，还是比较简单的，几十行代码就实现了。那用C++来实现无锁化堆栈会不会也很简略呢？先看上面的无锁化堆栈C++实现片段（为了简化形容，还是省略了内存程序的细节，代码没通过编译验证，仅做示例）：

#include <atomic>struct Node {    void* data;    std::atomic< Node * > next;};std::atomic<Node *> top; // 栈顶top.store( nullptr ); // 初始化栈顶为空指针bool push( Node* new_node ) {    Node * cur_top = top.load();    while ( true ) {        new_node->next.store( cur_top );                // CAS调用批改栈顶        if ( top.compare_exchange_weak(                cur_top, new_node )) {            return true;        }    }}Node * pop() {    while ( true ) {        Node * cur_top = top.load();        if ( cur_top == nullptr ) {            return nullptr; // 堆栈为空        }        Node * next = cur_top->next.load();                // CAS调用批改栈顶        if ( top.compare_exchange_weak(                cur_top, next )) {            return cur_top;        }    }}

看上去C++的无锁化堆栈实现跟Java版本简直统一，栈顶top也是原子类型，然而这个C++实现有问题。思考如下应用无锁化堆栈的C++代码片段：

Node * new_node = new Node();new_node.data = ...;push( new_node );...Node * pop_node = pop();if ( pop_node ) {    // 生产出栈节点    ...    // 不能保障没有其余线程在拜访pop_node，    // 此处不应该delete    delete pop_node;}

入栈的每个节点都是new进去的，所以可能感觉想当然出栈之后的每个节点在生产过过当前要被delete掉。然而思考多线程并发拜访的场景，比方有两个线程同时调用出栈pop函数，假设这两个线程同时读取到以后栈顶cur_top = top.load();，之后其中一个线程被抢占，另一个线程调用pop胜利取出栈顶节点，并且生产完之后delete掉，这时之前被抢占的线程复原执行，判断cur_top不为空，而后读取cur_top的下一个节点next = cur_top->next.load();, 然而cur_top曾经被另一个线程delete掉了，cur_top曾经变成野指针了，一旦读取就会导致非法内存拜访使得程序解体。

那为什么Java版本的实现就没有问题呢？是因为GC的缘故。Java里没有显式的delete操作，所有的内存回收是GC主动实现的。回到下面两个线程并发调用出栈pop函数的场景，如果用Java实现，当两个线程都读取到以后栈顶的援用，其中一个线程被抢占，另一个线程出栈调用胜利，并实现生产出栈节点，此时Java的GC并不会回收出栈节点，因为GC发现出栈节点仍有被其余线程援用。所以Java版本的无锁化编程是内存平安的。

对没有垃圾回收机制的语言做无锁化编程的思考

从下面无锁化堆栈的例子能够看出，Java的GC肯定水平简化了无锁化编程，因为不必思考内存回收的问题，Java的GC会平安的回收内存，只是不能确定Java的GC什么时候回收内存。比照没有GC的语言，显然没有GC使无锁化编程变得复杂，因为实现的时候不得不自行思考内存平安回收的问题。这个问题相当于是在用C++这类没有GC的语言做无锁化编程的时候，要自行实现一个GC，专门解决无锁化编程场景下的内存回收问题，并保障内存平安同时避免内存透露。

针对这个问题曾经有一些成型的算法，最简略的办法是Reference Counter（然而RC性能十分差，不实用，因而不做思考），简单些的办法诸如Hazard pointer，Epoch-Based Reclamation或Quiescent State-Based Reclamation。这些办法大都能够看做是一种确定型GC，更精确的说是绝对Java的GC而言，这些办法执行内存回收的时刻是确定的（只是不同算法的具体内存回收触发逻辑不同）。这种确定型GC的思路是，仅针对无锁化编程这种特定场景实现GC，升高无锁化编程的难度，而不是作为通用型GC，这比起Java的GC来说就简略多了。因而，确定型GC相比Java的GC，一方面缩小复杂度从而大大降低对程序性能的影响，另一方面因其内存回收的确定性所以避免stop the world问题呈现。当然对开发者而言确定型GC也是是通明的，开发者无需关怀内存何时回收。限于篇幅，具体的细节这里先不开展，后续我再具体介绍这些确定型内存回收算法。

对没有GC的语言，比方C++，曾经有一些针对无锁化编程的内存回收算法的实现，比方libcds，更进一步，libcds还实现了无锁化堆栈、无锁化队列、无锁化哈希表等等。所以对于开发者而言，不须要反复造轮子，能够间接应用这些已有的实现来简化无锁化编程。

作者 | 王璞