synchronized实现原理及ReentrantLock源码

synchronized

synchronized的作用范围

public class SynchronizedTest {
    // 实例方法，方法访问标志ACC_SYNCHRONIZED,锁对象是对象实例
    public synchronized void test1(){}
    // 静态方法，方法访问标志ACC_SYNCHRONIZED,锁对象是MetaSpace中的Class
    // 相当于类的全局锁，会锁住所有调用该方法的线程
    public synchronized static void test2(){}

    public void test3() {
        //同步代码块，在代码块前增加monitorenter指令，代码块后增加monitorexit指令
        SynchronizedTest synchronizedTest = new SynchronizedTest();
        synchronized (synchronizedTest) {}
        // 类锁，效果等同于锁静态方法。代码块前后增加monitorenter、monitorexit指令
        synchronized (SynchronizedTest.class) {}
    }
}

可jclasslib查看Acc_SYNCHRONIZED标志和monitorenter、monitorexit指令

test1 方法：

Access flags： 0x0021[public synchronized]

test2 方法：

Access flags： 0x0029[public static synchronized]

test3方法Code操作码：

 0 new #2 <com/java/study/jvm/SynchronizedTest>
 3 dup
 4 invokespecial #3 <com/java/study/jvm/SynchronizedTest.<init>>
 7 astore_1
 8 aload_1
 9 dup
10 astore_2
11 monitorenter
12 aload_2
13 monitorexit
14 goto 22 (+8)
17 astore_3
18 aload_2
19 monitorexit
20 aload_3
21 athrow
22 ldc #2 <com/java/study/jvm/SynchronizedTest>
24 dup
25 astore_2
26 monitorenter
27 aload_2
28 monitorexit
29 goto 39 (+10)
32 astore 4
34 aload_2
35 monitorexit
36 aload 4
38 athrow
39 return

synchronized实现

核心组件

Wait Set：哪些调用 wait方法被阻塞的线程被放置在这里
Contention List：竞争队列，所有请求锁的线程首先被放在这个竞争队列中
Entry List： Contention List 中那些有资格成为候选资源的线程被移动到 Entry List 中
OnDeck：任意时刻，最多只有一个线程正在竞争锁资源，该线程被成为 OnDeck
Owner：当前已经获取到所资源的线程被称为 Owner
!Owner：当前释放锁的线程

图示过程：

synchronized实现原理及ReentrantLock源码-LMLPHP

解释：

JVM 每次从队列的尾部取出一个数据用于锁竞争候选者（OnDeck），但是并发情况下，ContentionList 会被大量的并发线程进行 CAS 访问，为了降低对尾部元素的竞争， JVM 会将一部分线程移动到 EntryList 中作为候选竞争线程。
Owner 线程会在 unlock 时，将 ContentionList 中的部分线程迁移到 EntryList 中，并指定EntryList 中的某个线程为 OnDeck 线程（一般是最先进去的那个线程）。
Owner 线程并不直接把锁传递给 OnDeck 线程，而是把锁竞争的权利交给 OnDeck，OnDeck 需要重新竞争锁。这样虽然牺牲了一些公平性，但是能极大的提升系统的吞吐量，在JVM 中，也把这种选择行为称之为“竞争切换”。
OnDeck 线程获取到锁资源后会变为 Owner 线程，而没有得到锁资源的仍然停留在 EntryList中。如果 Owner 线程被 wait 方法阻塞，则转移到 WaitSet 队列中，直到某个时刻通过 notify或者 notifyAll 唤醒，会重新进去 EntryList 中。
处于 ContentionList、 EntryList、 WaitSet 中的线程都处于阻塞状态，该阻塞是由操作系统来完成的（Linux 内核下采用 pthread_mutex_lock 内核函数实现的）。
Synchronized 是非公平锁。 Synchronized 在线程进入 ContentionList 时，等待的线程会先尝试自旋获取锁，如果获取不到就进入 ContentionList，这明显对于已经进入队列的线程是不公平的，还有一个不公平的事情就是自旋获取锁的线程还可能直接抢占 OnDeck 线程的锁资源。
参考： https://blog.csdn.net/zqz_zqz/article/details/70233767
每个对象都有个 monitor 对象，加锁就是在竞争 monitor 对象，代码块加锁是在前后分别加上 monitorenter 和 monitorexit 指令来实现的，方法加锁是通过一个标记位来判断的
synchronized 是一个重量级操作，需要调用操作系统相关接口，性能是低效的，有可能给线程加锁消耗的时间比有用操作消耗的时间更多。
Java1.6， synchronized 进行了很多的优化，有适应自旋、锁消除、锁粗化、轻量级锁及偏向锁等，效率有了本质上的提高。在之后推出的 Java1.7 与 1.8 中，均对该关键字的实现机理做了优化。引入了偏向锁和轻量级锁。都是在对象头中有标记位，不需要经过操作系统加锁。
锁可以从偏向锁升级到轻量级锁，再升级到重量级锁。这种升级过程叫做锁膨胀；
JDK 1.6 中默认是开启偏向锁和轻量级锁，可以通过-XX:-UseBiasedLocking 来禁用偏向锁

ReentrantLock

ReentrantLock初始化时，会new一个同步类（默认非公平NonfairSync，当传入公平参数fair=true时，则new公平类FairSync）；而FairSync 和NonfairSync都继承ReentrantLock中内部类Sync，Sync则继承同步器AbstractQueuedSynchronizer。UML图如下（https://www.cnblogs.com/zhimingyang/p/5702752.html 截取）：

synchronized实现原理及ReentrantLock源码-LMLPHP

Lock流程图(非公平锁示例)

synchronized实现原理及ReentrantLock源码-LMLPHP

源码

ReentrantLock$NonfairSync#lock(),当state为0，即compareAndSetState(0, 1)为true时，获得锁；否则进行下一步
ReentrantLock$NonfairSync#acquire() ——> AbstractQueuedSynchronizer#acquire() --> ReentrantLock$NonfairSync#tryAcquire() -->
ReentrantLock$Sync#nonfairTryAcquire(), 第2次尝试获取锁
在上面acquire方法中，还会调用addWaiter方法，将一个排他锁加入队列

public class ReentrantLock implements Lock, java.io.Serializable {

    abstract static class Sync extends AbstractQueuedSynchronizer {
        final boolean nonfairTryAcquire(int acquires) {
            final Thread current = Thread.currentThread();
            int c = getState();
            if (c == 0) {
                //第2次尝试获取锁
                if (compareAndSetState(0, acquires)) {
                    setExclusiveOwnerThread(current);
                    return true;
                }
            }
            else if (current == getExclusiveOwnerThread()) {
                int nextc = c + acquires;
                if (nextc < 0) // overflow
                    throw new Error("Maximum lock count exceeded");
                setState(nextc);
                return true;
            }
            return false;
        }
    }

    static final class NonfairSync extends Sync {

        final void lock() {
            // 可不进入队列，直接抢锁
            if (compareAndSetState(0, 1))
                setExclusiveOwnerThread(Thread.currentThread());
            else
                acquire(1);
        }

        protected final boolean tryAcquire(int acquires) {
            return nonfairTryAcquire(acquires);
        }
    }
}

public abstract class AbstractQueuedSynchronizer
    extends AbstractOwnableSynchronizer
    implements java.io.Serializable {

    public final void acquire(int arg) {
        // 步骤3，加入等待队列，默认排他锁
        if (!tryAcquire(arg) &&
            acquireQueued(addWaiter(Node.EXCLUSIVE), arg))
            selfInterrupt();
    }

而继续addWaiter、enq和acquireQueued则是实现以下图示过程：
synchronized实现原理及ReentrantLock源码-LMLPHP

    private Node addWaiter(Node mode) {
        Node node = new Node(Thread.currentThread(), mode);
        // Try the fast path of enq; backup to full enq on failure
        Node pred = tail;
        if (pred != null) {
            node.prev = pred;
            if (compareAndSetTail(pred, node)) {
                pred.next = node;
                return node;
            }
        }
        //前置节点为null的临界条件，第一个线程进入等待队列
        enq(node);
        return node;
    }

前置节点为null的临界条件，第一个线程进入等待队列，进行初始化

    private Node enq(final Node node) {
        for (;;) {
            Node t = tail;
            if (t == null) { // Must initialize
                //队列初始化
                if (compareAndSetHead(new Node()))
                    tail = head;
            } else {
                //双向链表添加元素
                node.prev = t;
                if (compareAndSetTail(t, node)) {
                    t.next = node;
                    return t;
                }
            }
        }
    }

    final boolean acquireQueued(final Node node, int arg) {
        boolean failed = true;
        try {
            boolean interrupted = false;
            for (;;) {
                final Node p = node.predecessor();
                if (p == head && tryAcquire(arg)) {
                    setHead(node);
                    p.next = null; // help GC
                    failed = false;
                    return interrupted;
                }
                if (shouldParkAfterFailedAcquire(p, node) &&
                    parkAndCheckInterrupt())
                    interrupted = true;
            }
        } finally {
            if (failed)
                cancelAcquire(node);
        }
    }

node属性值介绍：
synchronized实现原理及ReentrantLock源码-LMLPHP
对应源码：

public abstract class AbstractQueuedSynchronizer
    extends AbstractOwnableSynchronizer
    implements java.io.Serializable {
    static final class Node {

        static final Node EXCLUSIVE = null;
        static final int CANCELLED =  1;
        static final int SIGNAL    = -1;
        static final int CONDITION = -2;
        static final int PROPAGATE = -3;

        volatile int waitStatus;
        volatile Node prev;
        volatile Node next;
        volatile Thread thread;
        Node nextWaiter;

        final boolean isShared() {
            return nextWaiter == SHARED;
        }

        final Node predecessor() throws NullPointerException {
            Node p = prev;
            if (p == null)
                throw new NullPointerException();
            else
                return p;
        }

        Node() {    // Used to establish initial head or SHARED marker
        }

        Node(Thread thread, Node mode) {     // Used by addWaiter
            this.nextWaiter = mode;
            this.thread = thread;
        }

        Node(Thread thread, int waitStatus) { // Used by Condition
            this.waitStatus = waitStatus;
            this.thread = thread;
        }
    }
}

重入锁的实现

重入锁的可重复进入在以下代码中实现(非公平锁示例，公平锁代码一样)：

c > 0, 即有锁，并且获取锁的线程就是当前线程，则将state加1，并更新

final boolean nonfairTryAcquire(int acquires) {
    final Thread current = Thread.currentThread();
    int c = getState();
    if (c == 0) {
        ...
    }
    // c > 0
    else if (current == getExclusiveOwnerThread()) {
        int nextc = c + acquires;
        if (nextc < 0) // overflow
            throw new Error("Maximum lock count exceeded");
        setState(nextc);
        return true;
    }
    return false;
}

公平锁和非公平锁

第一处不公平地方(lock方法)：

非公平锁lock时，如果发现没有锁了，即state为0，可以不管队列，直接compareAndSetState，如果获取true了(抢到锁)，直接获得锁，不用进同步器中的队列。
而公平锁没有此逻辑。

static final class NonfairSync extends Sync {

    final void lock() {
        // 可不进入队列，直接抢锁
        if (compareAndSetState(0, 1))
            setExclusiveOwnerThread(Thread.currentThread());
        else
            acquire(1);
    }
}

static final class FairSync extends Sync {
    final void lock() {
        acquire(1);
    }
}

第二处不公平的地方(tryAcquire)：

非公平锁tryAcquire方法会调用Sync#nonfairTryAcquire()，当state为0，发现锁被释放时，可直接抢锁
公平锁则必须满足!hasQueuedPredecessors()条件，也即必须同步器中队列没有线程在等待，才去获取锁

static final class NonfairSync extends Sync {
    protected final boolean tryAcquire(int acquires) {
        return nonfairTryAcquire(acquires);
    }
}

abstract static class Sync extends AbstractQueuedSynchronizer {
    final boolean nonfairTryAcquire(int acquires) {
        final Thread current = Thread.currentThread();
        int c = getState();
        if (c == 0) {
            //发现锁被释放时，可直接抢锁
            if (compareAndSetState(0, acquires)) {
                setExclusiveOwnerThread(current);
                return true;
            }
        }
        ...
    }
}

公平锁

static final class FairSync extends Sync {
    protected final boolean tryAcquire(int acquires) {
        final Thread current = Thread.currentThread();
        int c = getState();
        if (c == 0) {
            // 必须同步器中队列没有线程在等待，才去获取锁
            if (!hasQueuedPredecessors() &&
                compareAndSetState(0, acquires)) {
                setExclusiveOwnerThread(current);
                return true;
            }
        }
        ...
    }
}

第三处不公平地方，加入队列时，前置节点是头节点：

    final boolean acquireQueued(final Node node, int arg) {
        boolean failed = true;
        try {
            boolean interrupted = false;
            for (;;) {
                final Node p = node.predecessor();
                if (p == head && tryAcquire(arg)) {
                ...
                }
            }
    }

曹自标