公平锁与非公平锁
ReentrantLock默认实现是非公平锁：
所以如果想要实现公平锁，就在构造方法中传入false。
ReentrantLock reentrantLock = new ReentrantLock(false);
来看看非公平锁的实现：首先获取到线程的state，如果state=0，则立马进行compareAndSetState（CAS）操作（其实就是改变state的值），并设置当前线程拥有锁。
final boolean nonfairTryAcquire(int acquires) {
final Thread current = Thread.currentThread();
int c = getState();
if (c == 0) {
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;
}
具体的原理就像下面这样：
线程t1首先拿到了锁（把state改为1），并进行了持续1分钟的操作。在此期间，t2、t3、t4在队列里面排队等待锁。等排到t4的时候，刚好t1释放锁，把state改为0，然后在进行后续释放锁的操作。但是在把state改为0后，线程t5刚好来了，看到了state=0就拿到了锁。但是这样对于等了很久的t2、t3、t4来说公平吗？显然不公平。
我们再来看看公平锁的实现：即使state=0，也不会立马进行CAS操作，还会进行一个hasQueuedPredecessors（判断自己是否需要排队）的判断。
static final class FairSync extends Sync {
private static final long serialVersionUID = -3000897897090466540L;
final void lock() {
acquire(1);
}
/**
* Fair version of tryAcquire. Don't grant access unless
* recursive call or no waiters or is first.
*/
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()) {
int nextc = c + acquires;
if (nextc < 0)
throw new Error("Maximum lock count exceeded");
setState(nextc);
return true;
}
return false;
}
}
hasQueuedPredecessors
hasQueuedPredecessors()是AbstractQueuedSynchronizer类的一个方法。
AQS（AbstractQueuedSynchronizer）类的设计
private transient volatile Node head; // 队首
private transient volatile Node tail; // 队尾
private volatile int state; // 锁状态，加锁成功则为1，重入++1，解锁则为0
Node类的设计
public class Node {
volatile Node prev;
volatile Node next;
volatile Thread thread;
}
AQS当中的队列示意图
hasQueuedPredecessors()方法
// 判断自己要不要排队
public final boolean hasQueuedPredecessors() {
// The correctness of this depends on head being initialized
// before tail and on head.next being accurate if the current
// thread is first in queue.
Node t = tail; // Read fields in reverse initialization order
Node h = head;
Node s;
return h != t &&
((s = h.next) == null || s.thread != Thread.currentThread());
}
【上锁过程重点】
- 锁对象：其实就是ReentrantLock的实例对象
- 自由状态：自由状态表示锁对象没有被别的线程持有，计数器为0
- 计数器：再lock对象中有一个字段state用来记录上锁次数，比如lock对象是自由状态则state为0，如果大于零则表示被线程持有了，当然也有重入那么state则>1
- waitStatus：仅仅是一个状态而已；ws是一个过渡状态，在不同方法里面判断ws的状态做不同的处理，所以ws=0有其存在的必要性
- tail：队列的队尾
- head：队列的对首
- ts：第二个给lock加锁的线程
- tf：第一个给lock加锁的线程
- tc：当前给线程加锁的线程
- tl：最后一个加锁的线程
- tn：随便某个线程 当然这些线程有可能重复，比如第一次加锁的时候tf==tc==tl==tn
- 节点：就是上面的Node类的对象，里面封装了线程，所以某种意义上node就等于一个线程
【不需要排队的两种情况】
- 队列没有初始化，则不需要排队，直接去加锁，但是可能会失败；为什么会失败呢？ 假设两个线程同时来lock，都看到队列没有初始化，都认为不需要排队，都去进行CAS修改计数器；但是肯定有一个会失败，这个时候他就会初始化队列并排队。
- 队列被初始化了，但是当前线程过来加锁，发觉队列当中头结点h就是自己，比如重入，因此不需要排队。
【h != t 判断首不等于尾这里要分三种情况】
- 队列没有初始化，也就是第一个线程来加锁，h和t都是null，&&运算所以后面不执行，直接返回false，但是这个方法取反了，所以会直接去cas加锁。总结起来就是队列没有初始化，没人排队，那么我也不需要排队，直接上锁，直接去看能不能办理业务。
- 如果队列被初始化那么
h!=t则成立，h!=t返回true；但是是&&运算，故而还需要进行后续的判断 ，（有人可能会疑问，比如队列里面只有一个数据，那么头和尾都是同一个，h!=t怎么会成立呢？其实这是第三种情况--队列里面只有一个数据；这里先不考虑，假设现在队列里面有大于1个数据），继续判断把h.next赋值给s；s如果是头的下一个，则表示它是队列当中参与排队的线程而且是排在最前面的；为什么是s最前面不是h嘛？诚然h是队列里面的第一个，但是不是排队的第一个；因为h是持有锁的，但是不参与排队；这个也很好理解，比如你去买火车票，你如果是第一个这个时候售票员已经在给你服务了，你不算排队，你后面的才算排队。然后判断s是否等于空，其实就是判断队列里面是否只有一个数据；假设队列大于1个，那么肯定不成立（s==null---->false），因为大于一个h.next肯定不为空；由于是||运算如果返回false，还要判断s.thread != Thread.currentThread()；这里又分为两种情况：
-
2.1
s.thread != Thread.currentThread()返回true，就是当前线程不等于在排队的第一个线程s。那么这个时候整体结果就是h!=t：true;（s==null false||s.thread != Thread.currentThread() true），方法结果最终返回true，那么去则需要去排队。其实这样符合情理，队列不为空，有人在排队，而且第一个排队的人和现在来参与竞争的人不是同一个，那么你就乖乖去排队。 -
2.2
s.thread != Thread.currentThread()返回false，表示当前来参与竞争锁的线程和第一个排队的线程是同一个线程。那么这个时候整体结果就是h!=t：true; （s==null false||s.thread != Thread.currentThread() false），方法结果最终返回false，那么去则不需要去排队。不需要排队则调用compareAndSetState(0, acquires)去改变计数器尝试上锁；这里又分为两种情况： - 2.2.1 第一种情况加锁成功？有人会问为什么会成功啊，很简单假如这个时候h也就是持有锁的那个线程执行完了，释放锁了，那么肯定成功啊；成功则执行 setExclusiveOwnerThread(current); 然后返回true 。
- 2.2.2 第二种情况加锁失败？有人会问为什么会失败啊。很简单假如这个时候h也就是持有锁的那个线程没执行完，没释放锁，那么肯定失败啊；失败则直接返回false，不会进else if。总结起来就是如果队列被初始化了，而且至少有一个人在排队那么自己也去排队；但是他会去看看那个第一个排队的人是不是自己，如果是自己那么他就去尝试加锁；尝试看看锁有没有释放。
- 队列被初始化了，但是里面只有一个数据，什么情况下才会出现这种情况呢？可能有人会说ts加锁的时候里面就只有一个数据；其实不是，因为队列初始化的时候会虚拟一个h作为头结点，当前线程作为第一个排队的节点， 并且AQS认为h永远是不排队的。为什么这么做呢？假设你不虚拟节点出来那么ts就是h，因为这个时候tf可能没有执行完，ts得不到锁，故而ts其实需要排队的。那么为什么要虚拟为什么ts不直接排在tf之后呢？上面已经时说明白了，tf来上锁的时候队列都没有，它不进队列，故而ts无法排在tf之后，只能虚拟一个null节点出来。那么问题来了，究竟什么时候才会出现队列当中只有一个数据呢？假设原先队列里面有5个人在排队，当前面4个都执行完了，轮到第5个线程得到锁的时候，它会把自己设置成为头部，而尾部又没有，故而队列当中只有一个h就是第5个。至于为什么需要把自己设置成头部；其实已经解释了，因为这个时候第5个线程已经不排队了，它拿到锁了，所以它不参与排队，故而需要设置成为h。所以这个时间内，队列当中只有一个节点。这个时候队列已经初始化了，但是只有一个数据，并且这个数据所代表的线程是持有锁 。
h != t false由于后面是&&运算，故而返回false可以不参与运算，整个方法返回false；不需要排队。
加锁过程总结
如果是第一个线程tf，那么和队列无关，线程直接持有锁。并且也不会初始化队列，如果接下来的线程都是交替执行，那么永远和AQS队列无关，都是直接线程持有锁。
所以在JDK1.6之前，ReentrantLock比synchronized关键字好的地方在于，假设线程都是交替执行，那么ReentrantLock肯定比synchronized关键字快。因为即使只有一个线程（没有高并发的情况下），synchronized关键字都要调用OS函数，性能低下，所以synchronized关键字是重量级锁；而使用ReentrantLock，那么所有代码都是在JDK内部解决的。
如果发生了竞争，比如tf持有锁的过程中T2来lock，那么这个时候就会初始化AQS，初始化AQS的时候会在队列的头部虚拟一个Thread为NULL的Node，因为队列当中的head永远是持有锁的那个node（除了第一次会虚拟一个，其他时候都是持有锁的那个线程锁封装的node），现在第一次的时候持有锁的是tf，而tf不在队列当中所以虚拟了一个node节点。队列当中的除了head之外的所有的node都在park，当tf释放锁之后unpark某个node之后（基本是队列当中的第二个，为什么是第二个呢？前面说过head永远是持有锁的那个node，当有时候也不会是第二个，比如第二个被cancel之后，至于为什么会被cancel，不在我们讨论范围之内，cancel的条件很苛刻，基本不会发生），node被唤醒。假设node是t2，那么这个时候会首先把t2变成head（sethead），在sethead方法里面会把t2代表的node设置为head，并且把node的Thread设置为null，为什么需要设置null？其实原因很简单，现在t2已经拿到锁了，node就不要排队了，那么node对Thread的引用就没有意义了。所以队列的head里面的Thread永远为null。
要注意，并发不一定存在竞争。比如淘宝双十一有1000万并发，你能确定这1000万个线程是一起执行的吗？线程总会有先后顺序。1000个线程当中，可能就2个线程存在竞争。所以交替执行≠竞争。
