并发基石-AQS与Condition

妖狐艹你老母 2022-02-28 17:26 275阅读 0赞

### 并发基石-AQS与Condition ###

*   *  Condition
     *  AQS
     *   *  Node
         *  执行开始
         *  AQS中的实现

## Condition ##

在前面的博客JUC相关中，已经初略介绍了Condition接口，代表一个条件，可以阻塞、唤醒一个条件队列  
今天来具体讲讲其与AQS（AbstractQueueSynchronizer）的实现源码  
Condition中的加入条件队列，阻塞，唤醒等等操作都是由AbstractQueueSynchronizer或其子类方法完成

## AQS ##

AbstractQueueSynchronizer是java提供的队列同步器，个人理解更贴近一个线程调度的管理者  
首先我们了解其内部类Node，Node既可以代表Condition的一个条件队列（单向链表），也可以代表当前锁资源的同步队列（双向链表）中的一个竞争线程的节点  
先看其结构

### Node ###

static final class Node { 
            /** Marker to indicate a node is waiting in shared mode */
            static final Node SHARED = new Node();
            /** Marker to indicate a node is waiting in exclusive mode */
            static final Node EXCLUSIVE = null;
    
            /** waitStatus value to indicate thread has cancelled */
            static final int CANCELLED =  1;
            /** waitStatus value to indicate successor's thread needs unparking */ static final int SIGNAL = -1; /** waitStatus value to indicate thread is waiting on condition */ static final int CONDITION = -2; /** * waitStatus value to indicate the next acquireShared should * unconditionally propagate */ static final int PROPAGATE = -3; /** * Status field, taking on only the values: * SIGNAL: The successor of this node is (or will soon be) * blocked (via park), so the current node must * unpark its successor when it releases or * cancels. To avoid races, acquire methods must * first indicate they need a signal, * then retry the atomic acquire, and then, * on failure, block. * CANCELLED: This node is cancelled due to timeout or interrupt. * Nodes never leave this state. In particular, * a thread with cancelled node never again blocks. * CONDITION: This node is currently on a condition queue. * It will not be used as a sync queue node * until transferred, at which time the status * will be set to 0. (Use of this value here has * nothing to do with the other uses of the * field, but simplifies mechanics.) * PROPAGATE: A releaseShared should be propagated to other * nodes. This is set (for head node only) in * doReleaseShared to ensure propagation * continues, even if other operations have * since intervened. * 0: None of the above * * The values are arranged numerically to simplify use. * Non-negative values mean that a node doesn't need to
             * signal. So, most code doesn't need to check for particular * values, just for sign. * * The field is initialized to 0 for normal sync nodes, and * CONDITION for condition nodes. It is modified using CAS * (or when possible, unconditional volatile writes). */ volatile int waitStatus; /** * Link to predecessor node that current node/thread relies on * for checking waitStatus. Assigned during enqueuing, and nulled * out (for sake of GC) only upon dequeuing. Also, upon * cancellation of a predecessor, we short-circuit while * finding a non-cancelled one, which will always exist * because the head node is never cancelled: A node becomes * head only as a result of successful acquire. A * cancelled thread never succeeds in acquiring, and a thread only * cancels itself, not any other node. */ volatile Node prev; /** * Link to the successor node that the current node/thread * unparks upon release. Assigned during enqueuing, adjusted * when bypassing cancelled predecessors, and nulled out (for * sake of GC) when dequeued. The enq operation does not * assign next field of a predecessor until after attachment, * so seeing a null next field does not necessarily mean that * node is at end of queue. However, if a next field appears * to be null, we can scan prev's from the tail to
             * double-check.  The next field of cancelled nodes is set to
             * point to the node itself instead of null, to make life
             * easier for isOnSyncQueue.
             */
            volatile Node next;
    
            /**
             * The thread that enqueued this node.  Initialized on
             * construction and nulled out after use.
             */
            volatile Thread thread;
    
            /**
             * Link to next node waiting on condition, or the special
             * value SHARED.  Because condition queues are accessed only
             * when holding in exclusive mode, we just need a simple
             * linked queue to hold nodes while they are waiting on
             * conditions. They are then transferred to the queue to
             * re-acquire. And because conditions can only be exclusive,
             * we save a field by using special value to indicate shared
             * mode.
             */
            Node nextWaiter;
    
            /**
             * Returns true if node is waiting in shared mode.
             */
            final boolean isShared() { 
                return nextWaiter == SHARED;
            }
    		...
    	}

Node中保存有竞争锁的线程对象  
prev属性代表同步队列中的上一个节点  
next属性代表同步队列中的下一个节点  
nextWaiter属性，如果Node处于条件队列中，则nextWaiter指向条件队列中的下一个Node  
nextWaiter属性，如果Node处于同步队列中，则nextWaiter代表同步模式，SHARE和EXCLUSIVE  
因为条件队列中的都是互斥，所以不需要保存该mode

### 执行开始 ###

首先Condition调用了await方法

final int fullyRelease(Node node) { 
    	boolean failed = true;
    	try { 
    		int savedState = getState();
    		if (release(savedState)) { 
    			failed = false;
    			return savedState;
    		} else { 
    			throw new IllegalMonitorStateException();
    		}
    	} finally { 
    		if (failed)
    			node.waitStatus = Node.CANCELLED;
    	}
    }
     public final void await() throws InterruptedException { 
                if (Thread.interrupted())
                    throw new InterruptedException();
                Node node = addConditionWaiter();
                int savedState = fullyRelease(node);
                int interruptMode = 0;
                while (!isOnSyncQueue(node)) { 
                    LockSupport.park(this);
                    if ((interruptMode = checkInterruptWhileWaiting(node)) != 0)
                        break;
                }
                if (acquireQueued(node, savedState) && interruptMode != THROW_IE)
                    interruptMode = REINTERRUPT;
                if (node.nextWaiter != null) // clean up if cancelled
                    unlinkCancelledWaiters();
                if (interruptMode != 0)
                    reportInterruptAfterWait(interruptMode);
            }
    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);
            }
        }
    	 private static boolean shouldParkAfterFailedAcquire(Node pred, Node node) { 
            int ws = pred.waitStatus;
            if (ws == Node.SIGNAL)
                /*
                 * This node has already set status asking a release
                 * to signal it, so it can safely park.
                 */
                return true;
            if (ws > 0) { 
                /*
                 * Predecessor was cancelled. Skip over predecessors and
                 * indicate retry.
                 */
                do { 
                    node.prev = pred = pred.prev;
                } while (pred.waitStatus > 0);
                pred.next = node;
            } else { 
                /*
                 * waitStatus must be 0 or PROPAGATE.  Indicate that we
                 * need a signal, but don't park yet.  Caller will need to
                 * retry to make sure it cannot acquire before parking.
                 */
                compareAndSetWaitStatus(pred, ws, Node.SIGNAL);
            }
            return false;
        }
    	private Node addConditionWaiter() { 
    	Node t = lastWaiter;
    	// If lastWaiter is cancelled, clean out.
    	if (t != null && t.waitStatus != Node.CONDITION) { 
    		unlinkCancelledWaiters();
    		t = lastWaiter;
    	}
    	Node node = new Node(Thread.currentThread(), Node.CONDITION);
    	if (t == null)
    		firstWaiter = node;
    	else
    		t.nextWaiter = node;
    	lastWaiter = node;
    	return node;
    	}
    	private void unlinkCancelledWaiters() { 
    	Node t = firstWaiter;
    	Node trail = null;
    	while (t != null) { 
    		Node next = t.nextWaiter;
    		if (t.waitStatus != Node.CONDITION) { 
    			t.nextWaiter = null;
    			if (trail == null)
    				firstWaiter = next;
    			else
    				trail.nextWaiter = next;
    			if (next == null)
    				lastWaiter = trail;
    		}
    		else
    			trail = t;
    		t = next;
    	}
    }

简单捋一下await的逻辑，首先创建一个Node到等待队列里，然后释放资源  
接着不断循环判断是否已经在同步队列里了，不在则挂起线程直到被UnPark  
当处于同步队列里且被唤醒后就会调用请求资源的方法  
不断的自旋尝试获取锁，如果处于头节点则获取得到资源，恢复执行后续代码  
如果他不是同步队列的头节点，则判断他在同步队列里的前驱节点  
如果前驱节点也处于请求释放的状态，因为总是唤醒前面的节点，所以这个节点这时候就可以安全的挂起  
如果前驱节点处于取消状态，则不断清理被前驱取消的节点，直到第一个处于非取消状态的节点，将该节点作为当前结点的前驱  
剩下的waitstatus中-2代表在条件队列已经不需要考虑，只剩下0（初始状态需要请求）和-3（读写锁的读锁请求到共享资源时，标记为该状态代表可以执行）  
就把前驱节点更改为请求释放signal的状态  
最后把所有已经不是条件等待状态的node移出队列

如果调用了signal方法

public final void signal() { 
                if (!isHeldExclusively())
                    throw new IllegalMonitorStateException();
                Node first = firstWaiter;
                if (first != null)
                    doSignal(first);
            }
    private void doSignal(Node first) { 
    	do { 
    		if ( (firstWaiter = first.nextWaiter) == null)
    			lastWaiter = null;
    		first.nextWaiter = null;
    	} while (!transferForSignal(first) &&
    			 (first = firstWaiter) != null);
    }    
    final boolean transferForSignal(Node node) { 
            /*
             * If cannot change waitStatus, the node has been cancelled.
             */
            if (!compareAndSetWaitStatus(node, Node.CONDITION, 0))
                return false;
    
            /*
             * Splice onto queue and try to set waitStatus of predecessor to
             * indicate that thread is (probably) waiting. If cancelled or
             * attempt to set waitStatus fails, wake up to resync (in which
             * case the waitStatus can be transiently and harmlessly wrong).
             */
            Node p = enq(node);
            int ws = p.waitStatus;
            if (ws > 0 || !compareAndSetWaitStatus(p, ws, Node.SIGNAL))
                LockSupport.unpark(node.thread);
            return true;
        }
    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;
                    }
                }
            }
        }
     public final void await() throws InterruptedException { 
                if (Thread.interrupted())
                    throw new InterruptedException();
                Node node = addConditionWaiter();
                int savedState = fullyRelease(node);
                int interruptMode = 0;
                while (!isOnSyncQueue(node)) { 
                    LockSupport.park(this);
                    if ((interruptMode = checkInterruptWhileWaiting(node)) != 0)
                        break;
                }
                if (acquireQueued(node, savedState) && interruptMode != THROW_IE)
                    interruptMode = REINTERRUPT;
                if (node.nextWaiter != null) // clean up if cancelled
                    unlinkCancelledWaiters();
                if (interruptMode != 0)
                    reportInterruptAfterWait(interruptMode);
            }
    final int fullyRelease(Node node) { 
    	boolean failed = true;
    	try { 
    		int savedState = getState();
    		if (release(savedState)) { 
    			failed = false;
    			return savedState;
    		} else { 
    			throw new IllegalMonitorStateException();
    		}
    	} finally { 
    		if (failed)
    			node.waitStatus = Node.CANCELLED;
    	}
    }
    public final boolean release(int arg) { 
            if (tryRelease(arg)) { 
                Node h = head;
                if (h != null && h.waitStatus != 0)
                    unparkSuccessor(h);
                return true;
            }
            return false;
        }
    private void unparkSuccessor(Node node) { 
    	/*
    	 * If status is negative (i.e., possibly needing signal) try
    	 * to clear in anticipation of signalling.  It is OK if this
    	 * fails or if status is changed by waiting thread.
    	 */
    	int ws = node.waitStatus;
    	if (ws < 0)
    		compareAndSetWaitStatus(node, ws, 0);
    
    	/*
    	 * Thread to unpark is held in successor, which is normally
    	 * just the next node.  But if cancelled or apparently null,
    	 * traverse backwards from tail to find the actual
    	 * non-cancelled successor.
    	 */
    	Node s = node.next;
    	if (s == null || s.waitStatus > 0) { 
    		s = null;
    		for (Node t = tail; t != null && t != node; t = t.prev)
    			if (t.waitStatus <= 0)
    				s = t;
    	}
    	if (s != null)
    		LockSupport.unpark(s.thread);
    }

默认唤醒条件队列从头节点开始往后找到的第一个处于非取消状态的节点  
把其加入同步队列，并更改状态  
如果更改失败说明这其间该节点被取消了，则返回失败继续往后寻找节点唤醒  
如果更改成功，则判断同步队列的前驱节点的状态，如果该节点被取消了则唤醒当前新加入的线程53  
原因是进入同步队列时，只有作为头节点才会立即请求资源  
否则，同步队列里只有释放资源时才会再次Unpark同步队列下一个线程  
因此防止前面的节点未获取到资源就取消导致后续没有调起下一个Unpark  
最好最安全的方法是如果前驱节点突然取消了，unPark一下  
这样即使还有别的线程在占用资源，他也会在获取资源失败后再次进入park

### AQS中的实现 ###

添加节点，默认添加到尾部

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;
                }
            }
            enq(node);
            return node;
        }

条件队列的移除上面已经分析了，那同步队列的呢?

现在我们回到一开始await被signal唤醒后自旋请求资源的地方来看请求资源的方法

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);
            }
        }
    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; // predNext is the apparent node to unsplice. CASes below will // fail if not, in which case, we lost race vs another cancel // or signal, so no further action is necessary. Node predNext = pred.next; // Can use unconditional write instead of CAS here. // After this atomic step, other Nodes can skip past us. // Before, we are free of interference from other threads. node.waitStatus = Node.CANCELLED; // If we are the tail, remove ourselves. if (node == tail && compareAndSetTail(node, pred)) { compareAndSetNext(pred, predNext, null); } else { // If successor needs signal, try to set pred's next-link
                // so it will get one. Otherwise wake it up to propagate.
                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
            }
        }
    	 final Node predecessor() throws NullPointerException { 
                Node p = prev;
                if (p == null)
                    throw new NullPointerException();
                else
                    return p;
            }
    	//---默认Sync使用不公平，此处作为示例	
    	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;
            }

当请求资源时什么情况执行finally  
1.前驱节点为null，空指针异常failed变量为初始值true，此时取消资源会把自己移除出同步队列（因为头指针是特殊标记，不代表实际请求资源的Node）  
—在插入同步队列时，如果没有头指针会自动初始化一个头指针，所以第一个插入的节点不会有问题  
2.该节点的前驱节点是头节点，则当前结点获取到资源，并把自己设置为头指针，failed变量标记为false（因为新的头指针不需要删除，这样就把旧的头节点出队了）  
3.超出资源限制的请求数量，throw new Error(“Maximum lock count exceeded”)，取消该node  
cancelAcquire方法会将当前结点标记为取消状态，并且迭代移除当前结点的已取消的前驱节点知道第一个非取消状态的节点  
主要操作是  
1.当前是尾节点，删除当前结点更新尾节点  
2.前驱节点不是头节点（因为头节点是标记节点要特殊处理），删除当前结点  
3.前驱节点是头节点，调用unParkSuccess去唤起后一个线程（因为他没有获取到资源又是第一个节点不执行release）

而被标记为取消的节点在shouldParkAfterFailedAcquire中会被删除  
因为Park下一个节点，他不是head下的第一个节点所以他会请求失败并执行shouldParkAfterFailedAcquire

private static boolean shouldParkAfterFailedAcquire(Node pred, Node node) { 
            int ws = pred.waitStatus;
            if (ws == Node.SIGNAL)
                /*
                 * This node has already set status asking a release
                 * to signal it, so it can safely park.
                 */
                return true;
            if (ws > 0) { 
                /*
                 * Predecessor was cancelled. Skip over predecessors and
                 * indicate retry.
                 */
                do { 
                    node.prev = pred = pred.prev;
                } while (pred.waitStatus > 0);
                pred.next = node;
            } else { 
                /*
                 * waitStatus must be 0 or PROPAGATE.  Indicate that we
                 * need a signal, but don't park yet.  Caller will need to
                 * retry to make sure it cannot acquire before parking.
                 */
                compareAndSetWaitStatus(pred, ws, Node.SIGNAL);
            }
            return false;
        }

更多文章，请搜索公众号歪歪梯Club  
![更多资料，请搜索公众号编程宝可梦][20200521183346518.jpg]

[20200521183346518.jpg]: /images/20220227/d5cf8f2c86194e6e98cd5d1f611f9f22.png