既然文章叫做《一步一步的实现一个reentranklock》，那么我们将从设计一个最简单的锁开始，一步步地深入，最后完整的展示一个reentranklock的设计过程。（未完成）

一个实现锁的最简单的办法

我们知道cas操作是原子的，且自带更新，所以我们其实可以用cas设计一个最简单的自旋锁。方案很简单

简单自旋锁的方案

设置一个公共的变量value，初始化值为a，然后每一个线程的加锁操作都是试图使用cas，校验当前变量值为a，如果为a将其设置为值b，b!=a。失败，就反复重试，直到成功为止。解锁的时候，使用cas校验当前值是否为b，如果是就更新为a。

方案的优缺点

优点

优点很明显，就是这个方案很快的就实现了一个简单的加锁和解锁方案。

缺点

这个锁是自旋锁，自旋本身就是一个耗费性能的操作。更为重要的是，对于解锁方没有控制，一个线程在得到value的时候，如果value已经是b了，该线程确实不能加锁，但是该线程却能强行使用cas，对该共享的变量进行解锁，这是不能接受的，因为一旦代码出现问题，会导致锁的逻辑本身失控。因为一个没有持有锁的线程，居然可以通过解锁来强行获取锁，这本身就是不对的。这个不应该指望使用者保证，而是应该锁本身来保证的。

保证解锁正确的方案

在简单自旋锁的方案中，已经提出了，没有获取锁的线程不应该拥有解锁的能力。解锁的能力，只能开放给拥有锁的线程，所以为了记录当前持有锁的线程，除了value的值之外，我们还需要额外的一个值，用于记录当前拥有锁的线程，在解锁的时候，必须校验，当且仅当是拥有当前锁的线程，才能解锁。
（ps：注意，对于cas的操作值a,b，这里的逻辑应该是对外层隔离的，外层只要有lock和unlock方法就好了。

一个可重入的锁

加锁可重入

一般来说，我们希望锁不仅是独占的，还是可重入的，也就说，已经获取当前锁的线程，还可以继续获取当前的锁。如果我们希望锁是可重入，那么最简单的思路，就是在试图获取锁的时候，判断当前持有锁的线程是否就是当前试图获取锁的线程，如果是就认为获取成功了。这样锁就可以重入了。下面是描述这个过程的伪代码。

if(System.currentThread() == lock.ownerThread()){
  //do something
}else{
  tryAcquireLock();
}

这样的设计，解决了持有锁的线程可以重复获取锁的问题。但是考虑解锁呢。假设我们现在有这么一个场景，线程thread在代码块A中，获取锁l，然后又在B中再一次获取锁l，A,B互相不知道对方的存在，A,B中都有释放锁的逻辑。这样就会导致一个问题，当B快要执行完成的时候，B释放了锁l，本来只想让B自己这部分代码可以继续进行下去，但这个时候A本应该还是锁着的，还没有到需要解锁的地步，这个时候在B中解锁，会导致A中本来是线程thread独占的代码块，被其它线程进入了，破坏了锁的原意。所以单纯判断当前锁的方案是有问题的。

解决办法

B解锁的时候，A不解锁，这个时候允许获取锁是危险的，而当A,B都解锁之后，才尝试获取锁呢，这个时候A,B两边都准备好了，再来的加锁请求都是安全的。为了保证这样的机制，我们需要记录锁被重入的次数， 我们知道java中有一个AtomicInteger类，该类是一个原子的integer类，可以用于保证并发情况下的原子性。假设我们现在有一个AtomicInteger的实例，我们给他命名为state，每当当前线程重入锁一次的时候，就调用AtomicInteger中的incrmentAndGet方法，每次释放锁，就调用decrementAndGet方法。这样的设计，就能记录下当前锁被重入的次数了，只有当所有的锁都被释放的时候，state才会为0，这个时候其它线程再来竞争锁的资源是安全，依循上面的设计就能在原有的设计的基础上，制作出一个可重入的锁了。

我们是否真的需要AtomicInteger

在上面的描述中，我们使用了一个AtomicInteger用于记录锁当前被重入的次数。使用atomicInteger当然没有错，不过我们也不得不承认，相比于普通的int和integer来说，atomicInteger确实是重了一些。一般来说在解决并发的问题的时候，我们倾向于解决一个我们已经解决的并发问题，其实其他问题一样，这种思想在数学里叫做：化归。不过这里我们重新思考一个问题。
在一个线程获取锁成功的前提下，在之后的过程中，是否有其它线程和它争用对state的控制权。仔细一想，其实是没有，因为能使用increment操作的线程，必须是获取到锁的当前线程，所以state，在锁从被某个线程获取到被释放的生命周期中，只能被持有锁的线程修改，既然只有一个线程能修改，就不存在什么并发问题，所以这里state其实根本不需要设计成使AtomicInteger，直接使用普通的int就好了。

我们是否确实同时需要value和state

在最开始的设计中，value被设计用于表示锁当前是否被持有的状态，而最新加入的state被用于表示当前锁被重入的次数。但是当我们已经有了state的时候，我们还需要value吗？value的要求是，value所表示的集合至少要包含两个不同的值，或者说两个状态，一个代表被持有，另一个表示还未持有。state用于表示锁被重入的次数，0表示没有被重入，也即表示没有线程持有该锁。当有线程获取锁的时候，state加1，每次锁被重入的时候都加1.其实对于state来说，它不仅表示了锁当前被重入的次数，还反映了当前锁是否被线程持有，当state == 0的时候，表示当前锁是空闲的，当state > 0的时候，表示当前锁被某个线程所持有。所以既然state身兼两义，所以站在性能最优的原则上来说，当我们有state的时候，就不再需要value了。

park和unpark

回顾我们之前设计的锁的方案。我们的锁，目前至少拥有了如下的设计

public class SimpleLock {
    private static final Unsafe unsafe = Unsafe.getUnsafe();
    private static final long stateOffset;    
    static {        
        try {
            stateOffset = unsafe.objectFieldOffset(SimpleLock.class.getDeclaredField("state"));
        }catch (Exception e){
            throw new Error(e);
        }
    }
    private int state = 0;
    private Thread ownerThread;
    public boolean lock(){
        Thread currentThread = Thread.currentThread();
        if(currentThread == ownerThread){
            ++state;
            return true;
        }else {
            if(unsafe.compareAndSwapInt(this,stateOffset,0,1)){
                setOwnerThread(currentThread);
                return true;
            }
        }
        return false;
    }
    public void unlock(){
        --state;
    }
    public void setOwnerThread(Thread ownerThread) {
        this.ownerThread = ownerThread;
    }
}

在这个设计下，unsafe和stateOffset主要是为了实现CAS方法，关于他们的更多细节，请自行学习,上面的代码是无法运行的，主要原因在于unsafe要求只能java的标准库才能使用获取该实例。
由于CAS的方法会经常用到，后面的实例中，不会一一写CAS用unsafe实现的细节，我们假设在我们需要CAS的地方，都有这么一个方法，如下

/** cas操作,如果对象object的是期望的except,那么将其更新为newObject,返回成功与否
* @param object 
* @param except 
* @param newObject 
* @return 是否更新成功
*/
private boolean compareAndSet(Object object,Object except,Object newObject);

这里我们的关注点主要在state和ownerThread上。上面这个锁的设计，已经可以达到一个可以使用的可重入锁的需求了。而且也已经去掉了一些多余的数据，比如说value。但是这样的设计依旧不够好。我们来看SimpleLock的一个典型的用法。

SimpleLock simpleLock = new SimpleLock();
while (!simpleLock.lock()){
    System.out.println("获取锁失败,重试");
}
System.out.println("执行业务逻辑");
simpleLock.unlock();

我们可以看到，这个锁对于调用方来说，依旧是个自旋锁，当然我们可以包含掉这部分逻辑，让自旋这部分逻辑对外部透明，但是这依旧改变不了，这个锁需要自旋等待的结果。
自旋等待最大的问题就在于性能耗损严重，不断自旋的过程是对系统cpu资源极大的浪费，当锁被单个线程占用的时间越多，或者当有很多线程都在尝试获取锁的时候，对系统cpu的资源的浪费更是可观。所以我们希望，当一个线程第一次获取锁失败的时候，它可以去休息等待锁释放，而不是不断的自旋，询问锁是否准备好了。而需要实现这个目标，第一个需求就是需要有一个办法，可以让线程进入上述的等待状态。自己设计一个这样的东西无疑是很难的，幸好java在1.5之后，给我们提供了让线程进入等待的一个便捷的方法库java.util.concurrent.locks.LockSupport。

有了LockSupport之后，我们就可以将线程置为阻塞状态了。这样当线程获取失败后，就可以直接将线程置为阻塞，用于节约对资源的消耗了。

阻塞解除的方案

我们有了阻塞，自然就要有唤醒线程的方法，否则线程就会无限等待下去了。既然要唤醒等待的线程，自然的我们的第一个需求，就应该是先设计一个数据结构用于保存阻塞的线程。我们先不纠结集合的具体细节，我们先把它看成一个抽象的集合，我们先来想想这个集合需要满足哪些功能。

这个集合最好FIFO的

我们先来考虑公平锁的情况，公平锁希望的是，锁的获取顺序，是由试图获取锁的时候顺序决定的。所以这个集合如果能是一个先进先出队列，那么就可以满足公平锁的需求了。

队列插入和读取是线程安全的

要一个FIFO的队列很简单，但是现在的情况，却并不是那么简单，因为现在的环境是多线程的，在一个线程插入的同时，另一个线程也可能也在插入或者删除，所以一个困难点，在于如何保证他的线程安全。

线程不安全的原因

假设我们以最简单的单链表为基础，尝试在单链表的基础上，通过改进来设计一个线程安全的链表。首先，我们来看看为什么单链表不是线程安全的。

初始化环节

首先，一个链表并不是开始就可用的，还需要初始化的过程。当head为null的时候，我们需要对链表做初始化，但是这个初始化对于插入来说应该是透明的，或者说这个链表的初始化逻辑，应该是藏于插入等方法中的，外部应该尽可能的无感知。我们先来看看普通的链表初始化操作在多线程的环境下，会出现的问题

private void initFifo(){
    head = new Node();
    head.setNext(null);
}

• head被重复初始化
• 同一个时间，head被多个线程初始化，而各个线程所看到的head却是不一样的
  所以我们问题解决的重心，应该放在如何保证在head被第一次设置之后，不会被修改。我们知道head的初始值是null，所以问题转换为当head第一次不为null之后，head不会被改变了。
  在解决问题之前，先看看我们现在的工具和武器有什么，很可惜，目前我们只有CAS和LockSupport，LockSupport显然无法帮我解决这个问题。然后CAS刚刚好是可以解决这个问题的，只要我们将期望值设为null就好了，这样head就有且仅能被设置一次了，代码如下所示。

private void initFifoThreadSafe(){
    if(head == null){
        Node myHead = new Node();
        myHead.setNext(null);
        compareAndSet(head,null,myHead);
    }
}

上面的代码解决了head可能在运行的过程被改变的问题，但是不能解决向内存多次申请Node的问题，不过这个问题并不会影响链表的行为，而且java有一套优秀的内存回收机制，我们当然有办法让这个地方只初始化一个Node，但是比起这么一瞬间节约的内存，带来的编码性的复杂性和系统性能的下降，更为令人不能接受。而且更简单,一般来说总是更好的所以在这个问题上，我们可以选择忽略可能存在的一瞬间申请多个Node的问题。

插入环节

初始化的问题解决了，然后我们再来看看插入环节的问题。同样的，我们研究一下，普通的插入策略有哪些线程安全的问题。

initFifoThreadSafe();
Node tail = head;
while (tail.getNext() != null){
    tail = tail.getNext();
}
tail.setNext(node);

在多线程环境下，这段代码存在的问题是

• 我们无法准确的获知，在我们需要插入新的尾的一瞬间之前，当前看到的tail，是否是当前真正的tail。
  很显然，我们无法通过遍历数组来获取当前准确的尾节点，这个时候我们需要的额外的信息是，向我们表明当前的tail是什么。针对这个问题，我们可以添加一个指向tail的节点，每次添加通过cas更新它，以此来保证，我们可见的tail是当前的tail。代码如下。

private void addNodeThreadSafe(Node node){
    while (true){
        Node oldTail = tail;
        if(compareAndSet(tail,oldTail,node)){
            oldTail.setNext(node);
            break;
        }
    }
}

删除环节/出队列

对于公平锁来说，由于是先进先出的，所以出队列的，只能是头结点。照常我们先来看看，普通的pop操作有什么问题。

private Node pop(){
    Node node = head;
    head = head.getNext();
    return node;
}

普通的pop操作在并发的环境下，一个重要的问题，是当你试图获取head的时候，可能当前head已经被改变了。所以需要控制，方案和之前大同小异。如下所示

private Node popThreadSafe(){
    while (true){
        Node tempHead = head;
        Node node = tempHead.getNext();
        if(compareAndSet(head,tempHead,node)){
            return node;
        }
    }
}

注意，在node出队列的时候，我们还需要知道node入队列的时候的对应的线程，所以node的构造函数，应该如下所示。

public Node(){
    thread = Thread.currentThread();
}

截止到现在，我们已经得到了一个比较完整的公平锁。我们目前得到的代码，如下所示。

/**
 * 一个携带线程信息的Node节点
**/
public class Node {
    private Node next;
    private Node previous;
    private Thread thread;
    public Node(){
        thread = Thread.currentThread();
    }
}

/**
 * 线程安全的FIFO队列
 */
public class ThreadSafeFifo {
    private Node head;
    private Node tail;
    private void addNodeThreadSafe(Node node){
        while (true){
            Node oldTail = tail;
            if(compareAndSet(tail,oldTail,node)){
                oldTail.setNext(node);
                break;
            }
        }
    }
    private void initFifoThreadSafe(){
        if(head == null){
            Node myHead = new Node();
            myHead.setNext(null);
            compareAndSet(head,null,myHead);
        }
    }
    private Node popThreadSafe(){
        while (true){
            Node tempHead = head;
            Node node = tempHead.getNext();
            if(compareAndSet(head,tempHead,node)){
                return node;
            }
        }
    }
}

(截止2016/04/26未完成）