AbstractQueuedSynchronizer（AQS）粗解
Synchronizers至少需要包括两个方法，acquire（阻塞当前线程直到它能拿到执行许可），release（释放资源）。而AQS针对这两个方法的设计思想，相当简单与直接。
acquire方法伪代码如下：
while (synchronization state does not allow acquire) { enqueue current thread if not already queued;
possibly block current thread;
}
dequeue current thread if it was queued
release方法伪代码如下：
update synchronization state; if (state may permit a blocked thread to acquire)
unblock one or more queued threads;
而要实现上面两个方法的，需要如下三个模块的支持：
- Atomically managing synchronization state
- Blocking and unblocking threads
- Maintaining queues
Synchronization State
AbstractQueuedSynchronizer类用了一个32位的int类型来维护同步状态，并暴露出getState,setState,compareAndSetState这些方法来获取、更新同步状态，当然这需要java.util.concurrent.atomic包的支持。为什么用32位的？Restricting synchronization state to a 32bit int was a pragmaticdecision. While JSR166 also provides atomic operations on 64bitlong fields, these must still be emulated using internal locks onenough platforms that the resulting synchronizers would notperform well. In the future, it seems likely that a second baseclass, specialized for use with 64bit state (i.e., with long controlarguments), will be added. However, there is not now acompelling reason to include it in the package. Currently, 32 bitssuffice for most applications. Only one java.util.concurrentsynchronizer class, CyclicBarrier, would require more bitsto maintain state, so instead uses locks (as do most higher-levelutilities in the package).（翻译出来就是一句话，实践出真知）
Concrete classes based on AbstractQueuedSynchronizermust define methods tryAcquire and tryRelease in termsof these exported state methods in order to control the acquireand release operations. The tryAcquire method must returntrue if synchronization was acquired, and the tryReleasemethod must return true if the new synchronization state mayallow future acquires. These methods accept a single intargument that can be used to communicate desired state; forexample in a reentrant lock, to re-establish the recursion countwhen re-acquiring the lock after returning from a condition wait.Many synchronizers do not need such an argument, and so justignore it.
Blocking
Until JSR166, there was no Java API available to block andunblock threads for purposes of creating synchronizers that arenot based on built-in monitors. The only candidates wereThread.suspend and Thread.resume, which areunusable because they encounter an unsolvable race problem: Ifan unblocking thread invokes resume before the blockingthread has executed suspend, the resume operation will haveno effect.（现成java api里没有可用的东西，这里的现成当然是指java.util.concurrent之前）
The java.util.concurrent.locks package includes a LockSupport class with methods that address this problem. Method LockSupport.park blocks the current thread unless or untila LockSupport.unpark has been issued. (Spurious wakeupsare also permitted.) Calls to unpark are not "counted", somultiple unparks before a park only unblock a single park.Additionally, this applies per-thread, not per-synchronizer. Athread invoking park on a new synchronizer might returnimmediately because of a "leftover" unpark from a previoususage. However, in the absence of an unpark, its nextinvocation will block. While it would be possible to explicitlyclear this state, it is not worth doing so. It is more efficient toinvoke park multiple times when it happens to be necessary.
Queues
The heart of the framework(AQS) is maintenance of queues of blockedthreads, which are restricted here to FIFO queues. Thus, theframework does not support priority-based synchronization.
These days, there is little controversy that the most appropriatechoices for synchronization queues are non-blocking data structures that do not themselves need to be constructed usinglower-level locks. And of these, there are two main candidates:variants of Mellor-Crummey and Scott (MCS) locks, andvariants of Craig, Landin, and Hagersten (CLH) locks.Historically, CLH locks have been used only in spinlocks.However, they appeared more amenable than MCS for use in the synchronizer framework because they are more easily adapted to handle cancellation and timeouts, so were chosen as a basis. The resulting design is far enough removed from the original CLH structure to require explanation.（这里采用了CLH锁，因为它比MCS更容易实现取消、超时等操作）
Among the advantages of CLH locks are that enqueuing anddequeuing are fast, lock-free, and obstruction free (even undercontention, one thread will always win an insertion race so willmake progress); that detecting whether any threads are waiting isalso fast (just check if head is the same as tail); and thatrelease status is decentralized, avoiding some memorycontention.
In the original versions of CLH locks, there were not even linksconnecting nodes. In a spinlock, the pred variable can be heldas a local. However, Scott and Scherer[10] showed that byexplicitly maintaining predecessor fields within nodes, CLHlocks can deal with timeouts and other forms of cancellation: If anode"s predecessor cancels, the node can slide up to use theprevious node"s status field.
The main additional modification needed to use CLH queues forblocking synchronizers is to provide an efficient way for onenode to locate its successor. In spinlocks, a node need onlychange its status, which will be noticed on next spin by itssuccessor, so links are unnecessary. But in a blockingsynchronizer, a node needs to explicitly wake up (unpark) itssuccessor.
An AbstractQueuedSynchronizer queue node contains anext link to its successor. But because there are no applicabletechniques for lock-free atomic insertion of double-linked listnodes using compareAndSet, this link is not atomically set aspart of insertion; it is simply assigned:pred.next = node;after the insertion. This is reflected in all usages. The next linkis treated only as an optimized path. If a node"s successor doesnot appear to exist (or appears to be cancelled) via its next field,it is always possible to start at the tail of the list and traversebackwards using the pred field to accurately check if therereally is one.
A second set of modifications is to use the status field kept ineach node for purposes of controlling blocking, not spinning. Inthe synchronizer framework, a queued thread can only returnfrom an acquire operation if it passes the tryAcquire methoddefined in a concrete subclass; a single "released" bit does notsuffice. But control is still needed to ensure that an active threadis only allowed to invoke tryAcquire when it is at the head ofthe queue; in which case it may fail to acquire, and (re)block.This does not require a per-node status flag because permissioncan be determined by checking that the current node"spredecessor is the head. And unlike the case of spinlocks, thereis not enough memory contention reading head to warrantreplication. However, cancellation status must still be present inthe status field.
The queue node status field is also used to avoid needless calls topark and unpark. While these methods are relatively fast asblocking primitives go, they encounter avoidable overhead in theboundary crossing between Java and the JVM runtime and/or OS.Before invoking park, a thread sets a "signal me" bit, and thenrechecks synchronization and node status once more beforeinvoking park. A releasing thread clears status. This savesthreads from needlessly attempting to block often enough to beworthwhile, especially for lock classes in which lost time waitingfor the next eligible thread to acquire a lock accentuates othercontention effects. This also avoids requiring a releasing threadto determine its successor unless the successor has set the signalbit, which in turn eliminates those cases where it must traversemultiple nodes to cope with an apparently null next field unlesssignalling occurs in conjunction with cancellation. Perhaps the main difference between the variant of CLH locksused in the synchronizer framework and those employed in otherlanguages is that garbage collection is relied on for managingstorage reclamation of nodes, which avoids complexity andoverhead. However, reliance on GC does still entail nulling oflink fields when they are sure to never to be needed. This cannormally be done when dequeuing. Otherwise, unused nodeswould still be reachable, causing them to be uncollectable.Some further minor tunings, including lazy initialization of theinitial dummy node required by CLH queues upon firstcontention, are described in the source code documentation in theJ2SE1.5 release. Omitting such details, the general form of the resultingimplementation of the basic acquire operation (exclusive,noninterruptible, untimed case only) is:
if (!tryAcquire(arg)) { node = create and enqueue new node;
pred = node"s effective predecessor;
while (pred is not head node || !tryAcquire(arg)) {
if (pred"s signal bit is set)
park();
else
compareAndSet pred"s signal bit to true;
pred = node"s effective predecessor;
}
head = node;
}
And the release operation is:
if (tryRelease(arg) && head node"s signal bit is set) { compareAndSet head"s signal bit to false;
unpark head"s successor, if one exists
}
The number of iterations of the main acquire loop depends, ofcourse, on the nature of tryAcquire. Otherwise, in theabsence of cancellation, each component of acquire and release isa constant-time O(1) operation, amortized across threads,disregarding any OS thread scheduling occuring within park. Cancellation support mainly entails checking for interrupt ortimeout upon each return from park inside the acquire loop. Acancelled thread due to timeout or interrupt sets its node statusand unparks its successor so it may reset links. With cancellation,determining predecessors and successors and resetting status mayinclude O(n) traversals (where n is the length of the queue).Because a thread never again blocks for a cancelled operation,links and status fields tend to restabilize quickly.
Condition Queues
The synchronizer framework provides a ConditionObject class for use by synchronizers that maintain exclusives ynchronization and conform to the Lock interface. Any numberof condition objects may be attached to a lock object, providing classic monitor-style await, signal, and signalAll operations, including those with timeouts, along with some inspection and monitoring methods.
The ConditionObject class enables conditions to be efficiently integrated with other synchronization operations,again by fixing some design decisions. This class supports only Java-style monitor access rules in which condition operations are legal only when the lock owning the condition is held by thecurrent thread . Thus, a ConditionObject attached to a ReentrantLock acts inthe same way as do built-in monitors (via Object.wait etc),differing only in method names, extra functionality, and the fact that users can declare multiple conditions per lock.A ConditionObject uses the same internal queue nodes assynchronizers, but maintains them on a separate condition queue.The signal operation is implemented as a queue transfer from the condition queue to the lock queue, without necessarily waking upthe signalled thread before it has reacquired its lock.
The basic await operation is:
create and add new node to condition queue;
release lock;
block until node is on lock queue;
re-acquire lock;
And the signal operation is:
transfer the first node from condition queue to lock queue;
Because these operations are performed only when the lock is held, they can use sequential linked queue operations (using a nextWaiter field in nodes) to maintain the condition queue.The transfer operation simply unlinks the first node from the condition queue, and then uses CLH insertion to attach it to the lock queue.
The main complication in implementing these operations is dealing with cancellation of condition waits due to timeouts or Thread.interrupt. A cancellation and signal occuring at approximately the same time encounter a race whose outcome conforms to the specifications for built-in monitors. As revised inJSR133, these require that if an interrupt occurs before a signal,then the await method must, after reacquiring the lock, throw InterruptedException. But if it is interrupted after asignal, then the method must return without throwing an exception, but with its thread interrupt status set.
To maintain proper ordering, a bit in the queue node statusrecords whether the node has been (or is in the process of being)transferred. Both the signalling code and the cancelling code tryto compareAndSet this status. If a signal operation loses this race,it instead transfers the next node on the queue, if one exists. If acancellation loses, it must abort the transfer, and then await lockre-acquisition. This latter case introduces a potentiallyunbounded spin. A cancelled wait cannot commence lock re-acquisition until the node has been successfully inserted on thelock queue, so must spin waiting for the CLH queue insertioncompareAndSet being performed by the signalling thread tosucceed. The need to spin here is rare, and employs aThread.yield to provide a scheduling hint that some otherthread, ideally the one doing the signal, should instead run. Whileit would be possible to implement here a helping strategy for thecancellation to insert the node, the case is much too rare to justifythe added overhead that this would entail. In all other cases, thebasic mechanics here and elsewhere use no spins or yields, whichmaintains reasonable performance on uniprocessors
以上是 AbstractQueuedSynchronizer（AQS）粗解 的全部内容， 来源链接： utcz.com/z/514346.html
