ReentrantLock 公平锁源码 第1篇

ReentrantLock 1

这篇还是接着ReentrantLock的公平锁,没看过第0篇的可以先去看上一篇https://www.cnblogs.com/sunankang/p/16456342.html
这篇就以问题为导向,先提出问题,然后根据问题去看代码
确保能唤醒排队的线程?

A,B两线程,A线程执行完业务释放锁过程中B线程添加进了链表,如何保证B线程能正常醒来

现在假设A线程走完tryAcuqire后获取到锁,执行业务代码,最后unlock()  tryAcquire代码就不进去看了,上篇讲过了 现在只需关注两个点
lock方法中的acquireQueued 用来park
unlock方法中的release用来unpark
首先来看park的条件是啥

1. public final void acquire(int arg) {
2.     if (!tryAcquire(arg) && acquireQueued(addWaiter(Node.EXCLUSIVE), arg))
3.         selfInterrupt();
4. }

复制代码

进入acquireQueued方法

1. final boolean acquireQueued(final Node node, int arg) {
2.     boolean failed = true;
3.     try {
4.         boolean interrupted = false;
5.         for (;;) {
6.             final Node p = node.predecessor();
7.             if (p == head && tryAcquire(arg)) {
8.                 setHead(node);
9.                 p.next = null; // help GC
10.                 failed = false;
11.                 return interrupted;
12.             }
13.             if (shouldParkAfterFailedAcquire(p, node) &&
14.                 parkAndCheckInterrupt()) //在这里进行的park
15.                 interrupted = true;
16.         }
17.     } finally {
18.         if (failed)
19.             cancelAcquire(node);
20.     }
21. }

复制代码

也就是shouldParkAfterFailedAcquire 如果这个方法返回true,才会去park

1. private static boolean shouldParkAfterFailedAcquire(Node pred, Node node) {
2.     int ws = pred.waitStatus;
3.     if (ws == Node.SIGNAL)
4.         return true;
5.     if (ws > 0) {
6.         do {
7.             node.prev = pred = pred.prev;
8.         } while (pred.waitStatus > 0);
9.         pred.next = node;
10.     } else {
11.         compareAndSetWaitStatus(pred, ws, Node.SIGNAL);
12.     }
13.     return false;
14. }

复制代码

现在假设第一种情况,首次进入这个shouldParkAfterFailedAcquire方法的时候,A线程就进入unlock方法了  那么此时节点状态如下图

1. public final boolean release(int arg) {
2.     if (tryRelease(arg)) {
3.         Node h = head;
4.         //主要看这段代码
5.         if (h != null && h.waitStatus != 0)
6.             unparkSuccessor(h);
7.         return true;
8.     }
9.     return false;
10. }

复制代码

那么h!=null进入,但是头节点的waitStatus还是0,所以不走unpark,A线程结束
A线程结束了谁来唤醒B线程呢? 回到acquireQueued方法

1. final boolean acquireQueued(final Node node, int arg) {
2.     boolean failed = true;
3.     try {
4.         boolean interrupted = false;
5.         for (;;) {
6.             final Node p = node.predecessor();
7.             if (p == head && tryAcquire(arg)) {
8.                 setHead(node);
9.                 p.next = null; // help GC
10.                 failed = false;
11.                 return interrupted;
12.             }
13.             if (shouldParkAfterFailedAcquire(p, node) &&
14.                 parkAndCheckInterrupt())
15.                 interrupted = true;
16.         }
17.     } finally {
18.         if (failed)
19.             cancelAcquire(node);
20.     }
21. }

复制代码

因为第一次进入shouldParkAfterFailedAcquire方法中,最后走到else代码块,我们假设没有发生冲突,修改成功
A线程执行完了unlock,而此时锁的状态值为0,没有被持有的状态,最外层的for(;;)让代码又重新跑了一遍
第二次的时候if (p == head && tryAcquire(arg)) 这个if就会进入,因为现在已经没有其他线程在持有锁了,所以tryAcquire尝试获取锁成功,返回ture

1. private void setHead(Node node) {
2.     head = node;
3.     node.thread = null;
4.     node.prev = null;
5. }

复制代码

在setHead方法中将当前节点,咱们这个例子中也就是B节点,设置为head,之后清空上个引用和当前引用的线程
最后清除上个节点对B节点的引用,此时节点关系如下

而原来的头节点没有任何引用,等待GC即可,也可以看到在代码p.next = null; // help GC  这段旁边写的注释 帮助GC
之后将失败状态设置为false,返回是否被打断的变量,lock方法结束,
现在来假设在shouldParkAfterFailedAcquire方法中修改成功,但此时的A线程还没有走到unlock,当B线程马上要开始走parkAndCheckInterrupt方法开始park的时候,时间片用完的情况

1. final boolean acquireQueued(final Node node, int arg) {
2.     boolean failed = true;
3.     try {
4.         boolean interrupted = false;
5.         for (;;) {
6.             final Node p = node.predecessor();
7.             if (p == head && tryAcquire(arg)) {
8.                 setHead(node);
9.                 p.next = null; // help GC
10.                 failed = false;
11.                 return interrupted;
12.             }
13.             if (shouldParkAfterFailedAcquire(p, node) &&
14.                 //====假设此时B线程在这里=====
15.                 parkAndCheckInterrupt())
16.                 interrupted = true;
17.         }
18.     } finally {
19.         if (failed)
20.             cancelAcquire(node);
21.     }
22. }

复制代码

此时节点关系如下

A线程的unlock就可以进入unparkSuccessor

1. public final boolean release(int arg) {
2.     if (tryRelease(arg)) {
3.         Node h = head;
4.         if (h != null && h.waitStatus != 0)
5.             unparkSuccessor(h);
6.         return true;
7.     }
8.     return false;
9. }

复制代码

1. private void unparkSuccessor(Node node) {
3.     int ws = node.waitStatus;
4.     if (ws < 0)
5.         compareAndSetWaitStatus(node, ws, 0);
7.     Node s = node.next;
8.     if (s == null || s.waitStatus > 0) {
9.         s = null;
10.         for (Node t = tail; t != null && t != node; t = t.prev)
11.             if (t.waitStatus <= 0)
12.                 s = t;
13.     }
14.     if (s != null)
15.         LockSupport.unpark(s.thread);
16. }

复制代码

那么此时线程A解锁了,线程C调用lock方法

1. private Node enq(final Node node) {
2.     for (;;) {
3.         Node t = tail;
4.         if (t == null) { // Must initialize
5.             if (compareAndSetHead(new Node()))
6.                 //假设线程B走到这里时间片用完,还没来得及设置tail
7.                 tail = head;
8.         } else {
9.             node.prev = t;
10.             if (compareAndSetTail(t, node)) {
11.                 t.next = node;
12.                 return t;
13.             }
14.         }
15.     }
16. }

复制代码

在tryAcquire方法的hasQueuedPredecessors方法中

1. protected final boolean tryAcquire(int acquires) {
2.     final Thread current = Thread.currentThread();
3.     int c = getState();
4.     if (c == 0) {
5.         if (!hasQueuedPredecessors() &&
6.             compareAndSetState(0, acquires)) {
7.             setExclusiveOwnerThread(current);
8.             return true;
9.         }
10.     }
11.     else if (current == getExclusiveOwnerThread()) {
12.         int nextc = c + acquires;
13.         if (nextc < 0)
14.             throw new Error("Maximum lock count exceeded");
15.         setState(nextc);
16.         return true;
17.     }
18.     return false;
19. }

复制代码

此时tail还是null,而head已经被线程B设置了一个空Node,h!=t为true,h也只是一个空Node,所以(s = h.next) == null为true,整体返回true,外层取反为false,退出tryAcquire方法去入队列
那么入队列会破坏队列的初始化或者C线程变成第一个排队的节点吗?,注意咱们现在假设的线程B还没有获取到cpu的调用,还是停在 tail = head;代码执行前
线程C执行addWaiter方法

1. public final boolean hasQueuedPredecessors() {
2.     Node t = tail;
3.     Node h = head;
4.     Node s;
5.     return h != t &&
6.         ((s = h.next) == null || s.thread != Thread.currentThread());
7. }

复制代码

这个时候tail还是空,进入enq方法

1. private Node addWaiter(Node mode) {
2.     Node node = new Node(Thread.currentThread(), mode);
3.     // Try the fast path of enq; backup to full enq on failure
4.     Node pred = tail;
5.     if (pred != null) {
6.         node.prev = pred;
7.         if (compareAndSetTail(pred, node)) {
8.             pred.next = node;
9.             return node;
10.         }
11.     }
12.     enq(node);
13.     return node;
14. }

复制代码

首先第一个判断是会进入的,这个时候tail还是空,但是if (compareAndSetHead(new Node()))方法不会成功,来看看代码

1. private Node enq(final Node node) {
2.     for (;;) {
3.         Node t = tail;
4.         if (t == null) { // Must initialize
5.             if (compareAndSetHead(new Node()))
6.                 tail = head;
7.         } else {
8.             node.prev = t;
9.             if (compareAndSetTail(t, node)) {
10.                 t.next = node;
11.                 return t;
12.             }
13.         }
14.     }
15. }

复制代码

判断的是head为null的时候才会进行修改,所以线程C没有修改成功,那么会一直在for(;;)中循环,直到线程B初始化完空的头节点,也就是执行tail = head;这段代码
如果线程B走完了 tail = head;没来得及进行第二次循环添加B节点的时候,线程A解锁了,线程C进来了呢
还是在tryAcquire方法的hasQueuedPredecessors中

1. protected final boolean tryAcquire(int acquires) {
2.     final Thread current = Thread.currentThread();
3.     int c = getState();
4.     if (c == 0) {
5.         if (!hasQueuedPredecessors() &&
6.             compareAndSetState(0, acquires)) {
7.             setExclusiveOwnerThread(current);
8.             return true;
9.         }
10.     }
11.     else if (current == getExclusiveOwnerThread()) {
12.         int nextc = c + acquires;
13.         if (nextc < 0)
14.             throw new Error("Maximum lock count exceeded");
15.         setState(nextc);
16.         return true;
17.     }
18.     return false;
19. }

复制代码

这个时候第一个h!=t就是false,因为B线程已经将head和tail的引用指向同一个空节点了,返回false

1. public final boolean hasQueuedPredecessors() {
2.     Node t = tail;
3.     Node h = head;
4.     Node s;
5.     return h != t &&
6.         ((s = h.next) == null || s.thread != Thread.currentThread());
7. }

复制代码

C线程直接获取锁去运行代码了,所以ReentrantLock的公平锁其实并不是绝对的公平

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！