preface

  • This is a sequel to the first two
    • AQS and already
    • AQS and ReentrantReadWriteLock

General structure of AQS

  • The reentrant and reentrant read and write locks explained earlier are all about blocking queues.
  • There is no mention of another important aspect of AQS: wait queues, also known as conditional queues.
  • AQS have Node objects that serve two purposes: to form a wait queue and a blocking queue.
  • Queues although Node is similar to a linked list, the JDK comments only use the word queues, so they are called queues because they tend to be FIFO.

Take newCondition in ReentrantLock as an example

Take the trouble to read JDK source code

NewCondition () method

About the status of nodes in AQS

  • The value of the status field can only be: SIGNAL: The successor node of this node is (or will be) blocked (through park), so the current node must unpark the successor node before releasing or canceling. To avoid contention, fetching methods must first indicate that they need a signal, then retry atomic fetching, and then block on failure. CANCELLED: This object was CANCELLED due to timeout or interruption. The node will never leave this state. In particular, the thread that cancels the node never blocks again. CONDITION: This object is currently in the CONDITION queue. It will not be used as a synchronization queue node until transmission, at which point the state will be set to 0. (Using this value here is unrelated to other uses of the field, but simplifies the mechanism.) PROPAGATE: A releaseShared should PROPAGATE to other nodes. This is set in doReleaseShared (for head nodes only) to ensure that propagation continues even if other operations have intervened. 0: None of the above is for simplification, the values are arranged numerically. Non-negative means that nodes do not need to signal their successors. Therefore, most code doesn’t need to check for specific values, just symbols. For normal synchronous nodes, this field is initialized to 0, and for conditional nodes, it is initialized to CONDITION. It modifies using CAS (or, where possible, unconditionally volatile writes).

Implementation of the await method

Nothing is actually done, but the wait queue is created and the decision is interrupted in the wait.

Implementation of the signal method

summary

About the relationship between AQs and synchronized keywords:

  1. Synchronized keyword in the underlying c++ implementation, there are two important data structures (collections) : waitSet and EntryList.
  2. WaitSet holds thread objects (wrapped as C++ Node objects) that call the wait method of object.
  3. EntryList holds thread objects that are stuck in a blocked state and need to get monitor.
  4. When a thread is notified, it is moved from waitSet to EntryList.
  5. After entering EntryList, the thread still has to compete with other threads for monitor objects.
  6. If it does, the thread has the lock on the object, and it can execute the corresponding synchronization code in an exclusive manner.
  1. There are two kinds of queues in AQS, the conditional queue on the Condition object and the blocking queue of AQS itself.
  2. Each object in the two queues is a Node instance (which encapsulates the thread object), along with the state of the Node.
  3. When a thread in the Condition queue is signaled by another thread, it is moved from the Condition queue to the blocking queue of the AQS.
  4. Node objects in AQS blocking queues are essentially two-way linked lists.
  5. When acquiring the AQS lock, the threads entering the blocking queue attempt to acquire it in the order in which they are in the queue.
  6. When a thread in the AQS blocking queue acquires the lock, it indicates that the thread can execute normally.
  7. A thread stuck in a blocked state still needs to enter the kernel state of the operating system and enter the blocked state (implemented by the Park method).

WaitSet corresponds to AQS wait queues, which can be multiple and do not interfere with each other. EntryList corresponds to the blocking queue of AQS.