ReentrantLock的继承与组合
公平锁-加锁成功
公平锁-加锁失败
公平锁-释放锁
公平锁小结
非公平锁-加锁成功
非公平锁-加锁两次插队
ReentrantLock的继承与组合
ReentrantLock继承，组合。ReentrantLock实现了Lock接口，持有Sync实例，Sync的抽象父类是AbstractQueuedSynchronizer（以下称为AQS）AQS继承自AbstractOwnableSynchronizer（以下称之为AOS）AOS中只有一个成员变量Thread，当前持有锁的线程。
Sync有两个实现分别为NonfairSync非公平锁，FairSync公平锁。无参构造器默认为非公平锁，可以通过有参构造使用公平锁。
class ReentrantLock implements Lock, java.io.Serializable{
private final Sync sync;
abstract static class Sync extends AbstractQueuedSynchronizer{}
static final class NonfairSync extends Sync{}
static final class FairSync extends Sync{}
}
public abstract class AbstractQueuedSynchronizer extends AbstractOwnableSynchronizer implements java.io.Serializable{}
public abstract class AbstractOwnableSynchronizer implements java.io.Serializable{
private transient Thread exclusiveOwnerThread;
}
public ReentrantLock() {
sync = new NonfairSync();
}
public ReentrantLock(boolean fair) {
sync = fair ? new FairSync() : new NonfairSync();
}
公平锁-加锁成功
加锁代码，先看公平锁，假设现在只有一条线程获取锁，还原获取锁成功的步骤。
public void lock() {
sync.lock();
}
final void lock() {
acquire(1);//AQS中
}
//AQS中
public final void acquire(int arg) {
if (!tryAcquire(arg) &&
acquireQueued(addWaiter(Node.EXCLUSIVE), arg))
selfInterrupt();
}
protected final boolean tryAcquire(int acquires) {//入参1，尝试获取锁操作。
final Thread current = Thread.currentThread();//当前线程。
int c = getState();//AQS中的变量，默认为0，表示锁未被占用。
if (c == 0) {//能进来说明当前锁未被占用。
if (!hasQueuedPredecessors() &&
compareAndSetState(0, acquires)) {
setExclusiveOwnerThread(current);//把当前线程设置到AOS中，占有锁成功。
return true;//返回成功。
}
}
else if (current == getExclusiveOwnerThread()) {//getExclusiveOwnerThread从AOS中获取当前持有锁的线程是不是当前线程。
int nextc = c + acquires;//重入锁+1。
if (nextc < 0)
throw new Error("Maximum lock count exceeded");
setState(nextc);//设置锁占用标记。
return true;//返回成功。
}
return false;//返回失败。
}
//AQS
public final boolean hasQueuedPredecessors() {
Node t = tail; //将获取锁的线程封装到Node中，在AQS中有尾部，头部两个链表指针。
Node h = head;
Node s;
//h!=t表示链表有元素，h.next==null表示链表中只有一个元素,链表中唯一的元素不是当前线程。
return h != t &&((s = h.next) == null || s.thread != Thread.currentThread());
}
//AQS
protected final boolean compareAndSetState(int expect, int update) {
//CAS操作。成员变量state为1，不了解Unsafe的可以看上一篇博客。
return unsafe.compareAndSwapInt(this, stateOffset, expect, update);
}
//AOS
protected final void setExclusiveOwnerThread(Thread thread) {
exclusiveOwnerThread = thread;//设置当前线程为独占线程
}
公平锁-加锁失败
还原锁获取失败的步骤。
final void lock() {
acquire(1);
}
public final void acquire(int arg) {
//tryAcquire返回false取反为true。执行&&后操作，Node EXCLUSIVE = null。这是Node内部类中的成员变量。
//addWaiter将当前阻塞线程设置到Node链表中
if (!tryAcquire(arg) && acquireQueued(addWaiter(Node.EXCLUSIVE), arg))
selfInterrupt();
}
protected final boolean tryAcquire(int acquires) {
final Thread current = Thread.currentThread();
int c = getState();//有线程持有锁当前state！=0
if (c == 0) {
if (!hasQueuedPredecessors() &&
compareAndSetState(0, acquires)) {
setExclusiveOwnerThread(current);
return true;
}
}
else if (current == getExclusiveOwnerThread()) {//持有锁的线程不是当前线程
int nextc = c + acquires;
if (nextc < 0)
throw new Error("Maximum lock count exceeded");
setState(nextc);
return true;
}
return false;
}
private Node addWaiter(Node mode) {
//Node(Thread thread, Node mode) {this.nextWaiter = mode;this.thread = thread;}
//构造一个Node对象，入参为当前线程和一个空的Node，空的Node为下一个阻塞线程。
Node node = new Node(Thread.currentThread(), mode);
Node pred = tail;//获取阻塞链表中最后一个节点。
if (pred != null) {//如果尾部节点存在
node.prev = pred;//将尾部节点设置为新节点的prev。
//private final boolean compareAndSetTail(Node expect, Node update) {return unsafe.compareAndSwapObject(this, tailOffset, expect, update);}
// CAS操作，将新节点设置为tail.这个操作是可能失败的。例如有其他线程创建了newNode替换了tail。
if (compareAndSetTail(pred, node)) {
pred.next = node;//如果CAS操作成功，将新节点设置为上一个尾部节点的next
return node;//返回新的tail
}
}
enq(node);//添加失败或尾部节点为null后会走这里。
return node;
}
private Node enq(final Node node) { for (;;) {//自旋操作,两个操作 1 如果阻塞链表中没有线程阻塞，则创建一个空的Node当作head和tail，此时阻塞队列中已经有了head不过是哑节点。再次自旋将node设置为tail。或者直接走else Node t = tail;//获取尾部节点 if (t == null) { //如果尾部节点==null表示当前阻塞链表中已经没有阻塞的线程了。
//private final boolean compareAndSetHead(Node update) {return unsafe.compareAndSwapObject(this, headOffset, null, update);}
//CAS操作，new Node()然后设置该Node为head if (compareAndSetHead(new Node())) tail = head;//head赋值到tail } else {//如果阻塞链表中有线程。 node.prev = t;将当前tail赋值给Node的prev if (compareAndSetTail(t, node)) {//CAS设置当前线程为tail t.next = node;//设置node为原tail的next return t;//返回当前tail。 } } } }
final boolean acquireQueued(final Node node, int arg) {//传入当前线程的阻塞节点和1
boolean failed = true;//失败标记
try {
boolean interrupted = false;//中断信号
for (;;) {//自旋操作
//final Node predecessor() throws NullPointerException {Node p = prev;if (p == null){throw new NullPointerException();}else {return p;}}
//获取当前阻塞节点的上一个Node。无论走不走enq方法当前阻塞节点的prev都不可能为null。
final Node p = node.predecessor();
if (p == head && tryAcquire(arg)) {//prev是head表示当前Node的上一个就是哑节点，则可以再次执行tryAcquire(1)尝试获取锁。
//private void setHead(Node node) {head = node;node.thread = null;node.prev = null;}
setHead(node);//如果获取锁成功则将当前节点设置为head,这个操作其实也是把当前已经获取到锁的节点设置为哑节点。
p.next = null; //设置原来的哑节点的next为null此操作为了GC释放内存。
failed = false;
return interrupted;//返回false
}
//如果当前节点的上一个不是哑节点或者当前节点抢占锁失败。shouldParkAfterFailedAcquire(p,n)起码要走两次。
//parkAndCheckInterrupt()将线程阻塞。
if (shouldParkAfterFailedAcquire(p, node) && parkAndCheckInterrupt()){
interrupted = true;
}
}
} finally {
if (failed)//如果失败则执行这里，目前还看不出什么情况下会走这里。
cancelAcquire(node);
}
}
private static boolean shouldParkAfterFailedAcquire(Node pred, Node node) {
//获取上一个Node的状态。此处的状态有
//CANCELLED= 1 表示线程已经取消
//SIGNAL= -1 线程的后续线程需要阻塞
//CONDITION= -2 表示线程正在处于等待
//PROPAGATE= -3 表示该线程以及后续线程进行无条件传播
int ws = pred.waitStatus;//这里是判断上一个节点的status.默认为0
if (ws == Node.SIGNAL)//一个节点创建后默认是0也就是说要想走到if起码要走一次compareAndSetWatiStatus(p,w,s);
return true;//如果已经是-1则返回true
if (ws > 0) {
do {
node.prev = pred = pred.prev;//如果pred的状态大于0则表示非正常状态，则需要将当前Node.prev指向上一个的上一个，这个操作是循环的。直到排除所有非正常状态的节点。
} while (pred.waitStatus > 0);
pred.next = node;
} else {//第一次为0需要执行CAS操作将状态更改为-1，这里也是设置上一个节点的status。
compareAndSetWaitStatus(pred, ws, Node.SIGNAL);
}
return false;
}
private final boolean parkAndCheckInterrupt() {//目前先不考虑线程被中断的情况。
LockSupport.park(this);//阻塞当前线程
return Thread.interrupted();//阻塞结束后，返回线程中断状态。
}
公平锁-释放锁
释放锁操作
public void unlock() {
sync.release(1);
}
public final boolean release(int arg) {//AQS
if (tryRelease(arg)) {//释放锁的操作是由Sync做的。
Node h = head;
if (h != null && h.waitStatus != 0)//如果阻塞链表中的head!=null并且head这个哑节点的waitStatus!=0才会执行。
unparkSuccessor(h);
return true;
}
return false;
}
protected final boolean tryRelease(int releases) {//ReentrantLock.Sync
int c = getState() - releases;//获取state冲入次数然后-1
if (Thread.currentThread() != getExclusiveOwnerThread())//如果持有锁的线程不是当前线程则报错。从AOS中获取
throw new IllegalMonitorStateException();
boolean free = false;
if (c == 0) {//如果冲入次数==0则表示释放锁成功。
free = true;
setExclusiveOwnerThread(null);//将AOS中的线程置为null
}
setState(c);//设置重入数量
return free;//只有重入次数为0，才会返回true
}
private void unparkSuccessor(Node node) {//接收head节点
//拿到head的status正常情况是-1
int ws = node.waitStatus;
if (ws < 0)
compareAndSetWaitStatus(node, ws, 0);//设置head的status为0
//拿到哑节点的下一个节点
Node s = node.next;
if (s == null || s.waitStatus > 0) {//如果哑节点的下一个节点是无效节点。
s = null;//将无效节点设置为null
//从链表的尾部开始找status是-1的节点。直到找到null，然后取最后一个有效节点为s.
for (Node t = tail; t != null && t != node; t = t.prev)
if (t.waitStatus <= 0)
s = t;
}
if (s != null)//在这里释放next节点。也就是从parkAndCheckInterrupt()方法中继续执行。
LockSupport.unpark(s.thread); }
公平锁小结
公平锁小结。
以下线程执行前提为顺序执行。
线程1 t1 获取锁
1 获取ReentrantLock中的state是0，表示锁无占用
1 队列内head和tail都是null，CAS设置state成功。设置当前线程到AOS，获取锁成功
2 state不是0，判断持有锁的线程如果是当前线程则表示同一个线程多次重入，修改state。
线程2 t2 获取锁
1 获取ReentrantLock中的state不是0.AOS中持有锁的线程也不是当前线程，获取锁失败。
2 获取 Node mode = Node.EXCLUSIVE其实该节点是null,用于作为线程Node的next。
3 addWaiter()接收mode.
1 创建新的阻塞节点，封装了t2，Node t2Node = new Node(ct,mode);
2 获取tail节点。tail节点为null。
(进入enq自旋,接收node)
1 获取tail为null，创建一个Node new Node()；为哑节点。
2 CAS将哑节点设置为head,然后赋值给tail.
1 获取tail!=null，设置node.prev为哑节点。
2 CAS将t2Node设置为tail,将哑节点.next设置为t2Node然后返回。
3 返回t2Node。这个node.prev是一个哑节点。
4 acquireQueued()接收封装了t2Node和1
5 自旋操作
1 获取t2Node.prev==head，head就是哑节点,然后尝试获取锁失败。
2 进入shouldParkAfterFailedAcquire传入哑节点和t2Node
3 判断哑节点的status不是-1也不大于0当前哑节点的status为0
4 CAS设置哑节点的status为-1，返回false.
重复1，2步骤
3 判断哑节点的status是-1返回true。
4 进入parkAndCheckInterrupt方法阻塞t2线程。
线程3 t3 获取锁
1 获取ReentrantLock中的state不是0.AOS中持有锁的线程也不是当前线程，获取锁失败。
2 获取 Node mode = Node.EXCLUSIVE其实该节点是null,用于作为线程Node的next。
3 addWaiter()接收mode.
1 创建新的阻塞节点，封装了t3，Node t3Node = new Node(ct,mode);
2 获取tail节点。tail节点为t2Node
3 设置t3Node.prev=t2Node
4 CAS设置t3Node为tail。设置t2Node.next为t3Node。返回t3的node
4 acquireQueued()接收封装了t3Node和1
5 自旋操作
1 获取t3Node.prev是t2Node并不是哑节点head。
2 进入shouldParkAfterFailedAcquire传入t2Node和t3Node
3 判断t2的status不是-1也不大于0，当前t2的status是0
4 CAS设置t2Node中status为-1，返回false.
重复1，2
3 判断t2的status是-1返回true
4 进入parkAndCheckInterrupt方法阻塞t3线程。
线程1 t1 释放锁
1 执行tryRelease(1)，重入次数state-1.
2 判断释放锁的线程是否是AOS中持有锁的线程，如果不是则抛出异常。
3 判断state==0,true,AOS持有锁的线程设置为null.
4 设置state为0，返回true。
5 获取head哑节点，!=null,并且status==-1。哑节点的status是t2线程设置为-1的
6 进入unparkSuccessor接收哑节点。
7 CAS将哑节点的status设置为0.
8 获取哑节点.next。此处可能会循环获取，因为哑节点.next指向的Node.status可能不是-1.
这种情况将从队列的尾部开始寻找距离哑节点最近的一个-1节点。按照上边的流程当前哑节点.next是t2线程
9 unpark释放t2线程。
线程2 被唤醒
1 线程2从parkAndCheckInterrupt方法内唤醒。返回中断状态为false
2 继续执行acquireQueued方法，自旋中
1 获取t2Node.prev，当前t2Node.prev为head也就是哑节点
2 tryAcquire(1)尝试获取锁
3 获取当前线程，获取state重入次数为0
4 执行hasQueuedPredecessors(),tail为t3,head为哑节点。h!=t h.next.thread==当前线程
5 CAS设置state为1，设置AOS中的当前持有锁线程为t2.返回true
6 设置t2Node为head,t2Node.prev为null,t2Node.thread=null
7 设置哑节点.next=null，释放GC
8 线程2继续执行
线程2 释放锁
1 执行tryRelease(1)，重入次数state-1.
2 判断释放锁的线程是否是AOS中持有锁的线程，如果不是则抛出异常。
3 判断state==0,true,AOS持有锁的线程设置为null.
4 设置state为0，返回true。
5 获取head节点，当前hean为t2Node,status是-1，t2Node的status是t3Node设置的。
6 进入unparkSuccessor接收t2Node
7 CAS将t2Node.status设置为0
8 获取t2Node.next为t3Node。当前t3Node.status是0
9 unpark释放t3线程。
线程3 被唤醒
1 线程3从parkAndCheckInterrupt方法内唤醒。返回中断状态为false
2 继续执行acquireQueued方法，自旋中
1 获取t3Node.prev,当前t2Node.prev为t2Node,也就是head
2 tryAcquire(1)尝试获取锁
3 获取当前线程，获取state重入次数为0
4 执行hasQueuedPredecessors()，tail为t2Node,head为t2Node.h!=t, h.next.thread==当前线程
5 CAS设置state为1，设置AOS中的当前持有锁线程为t3.返回true
6 设置t3Node为head。t3Node.prev=null,t3Node.thread=null
7 t2Node.next=null,释放GC
8 线程3继续执行
线程3 释放锁
1 执行tryRelease(1)，重入次数state-1.
2 判断释放锁的线程是否是AOS中持有锁的线程，如果不是则抛出异常。
3 判断state==0,true,AOS持有锁的线程设置为null.
4 设置state为0，返回true。
5 获取head节点，当前head为t3Node
6 head节点status状态是0无需进入unparkSuccessor，head节点status为0表示不需要唤醒其他线程，也没有其他线程。
非公平锁-加锁成功
final void lock() {
if (compareAndSetState(0, 1))//插队操作，不管队列中有没有阻塞线程，直接CAS抢夺锁。
setExclusiveOwnerThread(Thread.currentThread());//抢夺成功，将当前线程设置到AOS中
else
acquire(1);//抢占失败
}
public final void acquire(int arg) {//AQS中
if (!tryAcquire(arg) &&
acquireQueued(addWaiter(Node.EXCLUSIVE), arg))
selfInterrupt();
}
protected final boolean tryAcquire(int acquires) {
return nonfairTryAcquire(acquires);//父类Sync的方法
}
final boolean nonfairTryAcquire(int acquires) {//入参1
final Thread current = Thread.currentThread();//当前线程
int c = getState();//获取重入锁次数
if (c == 0) {//如果重入锁次数==0表示当前锁没有线程持有
if (compareAndSetState(0, acquires)) {//插队，CAS修改state
setExclusiveOwnerThread(current);//AOS设置持有锁的线程
return true;//返回成功
}
}
else if (current == getExclusiveOwnerThread()) {//锁已经被持有并且是当前线程
int nextc = c + acquires;//重入次数+1
if (nextc < 0) //小于0报错
throw new Error("Maximum lock count exceeded");
setState(nextc);//设置重入次数
return true;//返回失败
}
return false;//返回失败
}
非公平锁-加锁两次插队
第一次插队再lock()方法内，公平锁会执行acquire(1)尝试获取锁，而非公平锁则直接CAS尝试修改状态，如果修改成功直接拿到锁。
公平锁尝试获取锁
非公平锁尝试获取锁
公平锁再tryAcquire时多做了一步hasQueuedPredecessors判断，这个方法期望返回false因为只有返回了false取反才可以继续执行CAS操作。
返回false的情况
1 head==tail直接返回false，这种情况表示等待队列中没有线程等待。
2 head!=tail说明等待队列中有Node，如果有Node，这个Node.next==null也可以，表示Node是哑节点。
3 如果head!=tail，Node.next!=null，并且Node.next.thread还不是当前线程那就必须返回true了，表示等待队列的下一个Node不是当前线程。
综合以上三条，非公平锁第二次插队在于不管阻塞队列中有没有线程再等待，它都会直接CAS。