ReentrantLock:可重入锁，实现与Lock
显示锁：可通过lock和unlock方法进行显示的加锁释放锁
独占锁：同时只能有一个线程持有锁
可重入锁：同一个锁对象，同一个线程可以重入
在ReentrantLock的构造函数中提供了两种公平性选择，非公平的锁（默认）和一个公平的锁，通过FairSync和NonfairSync两个内部类来实现
在公平的锁上，线程将按照它们发出请求的顺序来获得锁，但在非公平的锁上，则允许‘插队’；当一个线程请求非公平的锁时，如果在发出请求的同时该锁的状态变为可用，那么这个线程将跳过队列中所有的等待线程并获得这个锁---java并发编程实战
一，创建锁对象
//true为公平锁，false为非公平锁，无参默认为false Lock lock = new ReentranLock(true);
二，加锁方法lock()
公平锁lock方法
final void lock() {
acquire(1);
}
非公平锁lock方法，先尝试更改锁状态，如果可用，直接获得这个锁
final void lock() {
//先尝试更改锁状态，成功，则作为持有者
if (compareAndSetState(0, 1))
setExclusiveOwnerThread(Thread.currentThread());
else
acquire(1);
}
acquire方法，获取锁，通过轮询、挂起直到获取锁，可响应线程中断
public final void acquire(int arg) {
if (!tryAcquire(arg) &&
acquireQueued(addWaiter(Node.EXCLUSIVE), arg))
selfInterrupt();
}
公平锁的tryAcquire
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;
}
}
//如果当前持有线程就是当前线程，可重入，
else if (current == getExclusiveOwnerThread()) {
//state+1，在释放锁的时候，会state-1，直到减到0，释放锁
int nextc = c + acquires;
//数过大时，超过Integer的最大值，计算结果是负值
if (nextc < 0)
throw new Error("Maximum lock count exceeded");
setState(nextc);
return true;
}
return false;
}
tryAcquire-公平锁
//是否需要插队，返回false则不需要插队
public final boolean hasQueuedPredecessors() {
Node t = tail; //头节点
Node h = head;//尾节点
Node s;
/**
* //这里返回false，则说明需要排队
* 无需排队的情况:
* h==t的情况
* 1:还未初始化的队列，h,t都为null，此时无等待节点;
* 2:队列初始化后，无等待节点的队列。最后一个节点获取到了锁资源，会把此节点设置为头h节点,同时此节点也是尾节点，
* 都指向同一个节点，是相等的（所以，队列一经初始化，头尾节点就不会为空），此时队列无等待节点。
* h!=t 的情况，
* 1:另一个线程未完全初始化时，head被设置有值，h!=null,但是tail还没来得及赋值，tail=null
* h!=t,但是当执行到h.next时，head的next被另一个线程赋值了，此时(s = h.next) == null为false
* 但是，被另一个线程初始化，tail节点持有的线程不会是当前线程，
s.thread != Thread.currentThread())返回true,最终返回true,需要排队
* 2:队列中有等待节点，此时h.next不为null，但是不是当前线程，最终返回true
* 目前只想到这些情况了，不知道还有没有其他情况
*/
return h != t &&
((s = h.next) == null || s.thread != Thread.currentThread());
}
hasQueuedPredecessors
hasQueuedPredecessors
非公平锁的tryAcquire
protected final boolean tryAcquire(int acquires) {
return nonfairTryAcquire(acquires);
}
final boolean nonfairTryAcquire(int acquires) {
final Thread current = Thread.currentThread();
int c = getState();
if (c == 0) {
//区别是这里没了队列状态的判断，!hasQueuedPredecessors()
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;
}
nonfairTryAcquire
如果返回true,则表示获取锁，如果返回false，执行acquireQueued(addWaiter(Node.EXCLUSIVE), arg)，
private Node addWaiter(Node mode) {
//新建节点
Node node = new Node(Thread.currentThread(), mode);
Node pred = tail;
//如果存在尾节点，尝试快速添加到队列中
if (pred != null) {
node.prev = pred;
//尝试设置插入节点为尾节点，
if (compareAndSetTail(pred, node)) {
//设置尾节点关联属性
pred.next = node;
return node;
}
}
//快速添加失败，用enq(node)添加
enq(node);
return node;
}
addWaiter-添加等待节点
快速添加失败，则使用enq(final Node node)方法，通过自旋的方式直到插入队列为止
private Node enq(final Node node) {
//自旋直到添加进去为止
for (;;) {
Node t = tail;
//不存在尾节点，则说明队列还未初始化，因为队列一旦初始化，首尾队列就不会为空
if (t == null) { //进行初始化
//尝试设置头节点
if (compareAndSetHead(new Node()))
//使头尾节点指向同一个节点
tail = head;
} else { //如果队列已经初始化
// 设置插入节点上一个节点为原尾节点
node.prev = t;
//尝试把插入节点设置尾节点
if (compareAndSetTail(t, node)) {
//调整原尾节点关联属性
t.next = node;
return t;
}
}
}
}
enq
enq
添加节点之后 ，执行acquireQueued方法，自旋、挂起，直到获取到锁
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;//
}
//是否应该挂起当前线程，如果需要挂起，挂起，
//结束后返回中断状态，如果已中断，返回true
if (shouldParkAfterFailedAcquire(p, node) &&
parkAndCheckInterrupt())
interrupted = true;
}
} finally {
//如果失败，取消获取锁
if (failed)
cancelAcquire(node);
}
}
acquireQueued
shouldParkAfterFailedAcquire(p, node)，判断是否要挂起当前线程或是接着自旋，以避免刚挂起就获取到锁
private static boolean shouldParkAfterFailedAcquire(Node pred, Node node) {
//上一节点的等待状态
int ws = pred.waitStatus;
//如果是SINNAL(-1)状态，说明需要等待上一个节点释放锁的时候唤醒自己，返回true，挂起
if (ws == Node.SIGNAL)
return true;
if (ws > 0) {//如果上一个节点取消了
do {
node.prev = pred = pred.prev;//就关联上上一个节点，
//直到找到没有被取消的节点，被取消的节点被清除出队列
} while (pred.waitStatus > 0);
pred.next = node;
} else {
//waitStatus must be 0 or PROPAGATE(-3)
//上一个节点等待状态为0，先不考虑PROPAGATE（共享下的状态）
//1:插入节点时，上一个节点（原尾节点）为0;
//2:释放锁时，头节点状态会重置为0
//3:初始化时，头尾节点状态为0
//如果上一个节点是头结点，且状态为0，则可能刚释放完锁，则去自旋尝试获取锁
compareAndSetWaitStatus(pred, ws, Node.SIGNAL);
}
return false;
}
shouldParkAfterFailedAcquire
挂起当前线程，在唤醒的时候，返回并重置中断状态
private final boolean parkAndCheckInterrupt() {
LockSupport.park(this);//挂起休眠，直到获取到许可
return Thread.interrupted(); //返回并重置中断状态
}
parkAndCheckInterrupt
取消节点cancelAcquire
private void cancelAcquire(Node node) {
// Ignore if node doesn't exist
if (node == null)
return;
node.thread = null;
// Skip cancelled predecessors
Node pred = node.prev;
//清除取消节点出队列
while (pred.waitStatus > 0)
node.prev = pred = pred.prev;
Node predNext = pred.next;
node.waitStatus = Node.CANCELLED;
// If we are the tail, remove ourselves.
//如果被取消的是尾节点
if (node == tail && compareAndSetTail(node, pred)) {
//设置取消节点的上一个节点的next为null
compareAndSetNext(pred, predNext, null);
} else {
// 如果上一个节点不是头节点，不是正在或者已经取消的节点，且（waitStatus等于或可以设置成 // Node.SIGNAL状态
int ws;
if (pred != head &&
((ws = pred.waitStatus) == Node.SIGNAL ||
(ws <= 0 && compareAndSetWaitStatus(pred, ws, Node.SIGNAL))) &&
pred.thread != null) {
Node next = node.next;
if (next != null && next.waitStatus <= 0)
compareAndSetNext(pred, predNext, next);//调整节点关联属性
} else {
//尝试唤醒下一个节点
unparkSuccessor(node);
}
node.next = node; // help GC
}
}
cancelAcquire
三，释放锁unlock()
public void unlock() {
sync.release(1);
}
public final boolean release(int arg) {
//释放锁，state-1
if (tryRelease(arg)) {
//state=0, 释放锁完毕
Node h = head;
if (h != null && h.waitStatus != 0)
unparkSuccessor(h);
return true;
}
return false;
}
尝试释放锁
protected final boolean tryRelease(int releases) {
int c = getState() - releases;
//没有获取到锁，就去unlock,抛出异常
if (Thread.currentThread() != getExclusiveOwnerThread())
throw new IllegalMonitorStateException();
boolean free = false;
//因为可重入，所以只有state=0的时候，才表示当前线程完全释放锁了
if (c == 0) {
free = true;
setExclusiveOwnerThread(null);
}
setState(c);
return free;
}
唤醒下一个等待节点
private void unparkSuccessor(Node node) {
int ws = node.waitStatus;
//释放锁后，重置头节点waitStatus状态为0
if (ws < 0)
compareAndSetWaitStatus(node, ws, 0);
//唤醒当前节点下一个没有被取消的节点
Node s = node.next;
//头节点下一个节点为null,或者节点已取消
if (s == null || s.waitStatus > 0) {
s = null;
//从尾节点开始，往前找最接近头节点没有被取消的节点，找到赋值给s
for (Node t = tail; t != null && t != node; t = t.prev)
if (t.waitStatus <= 0)
s = t;
}
if (s != null)
//唤醒线程
LockSupport.unpark(s.thread);
}
四，其它
公平锁不是绝对的公平，a线程先调用了lock方法，b再调用，在CPU调度上，如果b获得了更多的执行时间，那么是有可能先获取锁的。