Fair lock of Java concurrency (1)_ Power node Java college sorting

@H_ 404_ 1 @ basic concepts

In this chapter, we will explain the principle of "thread obtains fair lock"; Before you explain, you need to understand several basic concepts. The following contents are based on these concepts; These concepts may be boring, but from these concepts, we can see some architectures of "Java lock", which is helpful for us to unlock@ H_ 404_ 1@1. AQS -- refers to abstractqueuedsynchronizer class. AQS is an abstract class for managing "locks" in Java. Many public methods of locks are implemented in this class. AQS is a common parent of exclusive locks (for example, reentrantlock) and shared locks (for example, semaphore).

@H_ 404_ 1@2. AQS locks are classified into "exclusive locks" and "shared locks". (01) exclusive lock -- a lock can only be occupied by one thread lock at a point in time. According to the lock acquisition mechanism, it is divided into "fair lock" and "unfair lock". Fair lock means that a thread waiting through CLH obtains a lock fairly according to the first come, first served rule; Instead of a fair lock, when a thread wants to acquire a lock, it will directly acquire the lock regardless of the CLH waiting queue. A typical example of an exclusive lock is reentrantlock. In addition, reentrantreadwritelock Writelock is also an exclusive lock. (02) shared lock -- a lock that can be owned and shared by multiple threads at the same time. Reentrantreadwritelock. In the JUC package Readlock, cyclicbarrier, countdownlatch and semaphore are shared locks. The use and principle of these locks will be described in detail in later chapters.

@H_ 404_ 1@3. CLH queue - Craig, landin, and Hagersten lock queue CLH queue is the thread queue of "waiting for lock" in AQS. In multithreading, in order to protect competing resources from errors caused by multiple threads operating at the same time, we often need to protect these resources through locks. In an exclusive lock, competing resources can only be accessed by one thread lock at a point in time; Other threads need to wait. CLH is the queue that manages these "waiting for locks" threads. CLH is a non blocking FIFO queue. In other words, when inserting or removing a node, it will not block under concurrent conditions, but ensure the atomicity of node insertion and removal through spin lock and CAS.

@H_ 404_ 1@4. CAS function -- compare and swap CAS function is a comparison and exchange function, which is an atomic operation function; That is, the data operated through CAS is atomic. For example, functions such as compareandsethead(), compareandsettail(), compareandsetnext(). Their common feature is that the actions performed by these functions are carried out in an atomic way.

This chapter focuses on how "fair lock" obtains locks. "Fair lock" involves many knowledge points, but generally speaking, it is not particularly difficult; If readers can understand AQS and reentrantlock Java is the general meaning of these two classes, and it is not a problem to understand the principle and mechanism of lock. This chapter is only the author's own understanding of lock. I hope this knowledge can help you understand the acquisition process of "fair lock" and the framework of "lock".

@H_ 404_ 1@reentrantlock data structure

UML class diagram of reentrantlock

As can be seen from the figure:

(01) reentrantlock implements the lock interface. (02) reentrantlock and sync are combinatorial relationships. Reentrantlock contains sync objects; Moreover, sync is a subclass of AQS; More importantly, Sync has two subclasses: fairsync (fair lock) and nonfairsync (non fair lock). Reentrantlock is an exclusive lock. Whether it is a fair lock or an unfair lock depends on whether the sync object is an instance of fairsync or an instance of nonfairsync.

@H_ 404_ 1 @ obtain fair lock (based on jdk1.7.0_40)

Through the previous "example 1" of "Java multithreading series -" JUC lock "02 mutex reentrantlock", we know that the lock is obtained through the lock() function. Next, let's expand the process of obtaining a fair lock with lock ().

@H_ 404_ 1@1. lock()

Lock() in reentrantlock It is implemented in fairsync class of Java. Its source code is as follows:

Note: "current thread" actually obtains the lock through acquire (1).

Here we will explain the meaning of "1", which is a parameter for setting "lock status". For "exclusive lock", when the lock is in the obtainable state, its state value is 0; When the lock is first acquired by the thread, its status value becomes 1. Because reentrantlock (fair lock / unfair lock) is a reentrant lock, an "exclusive lock" can be acquired by a single thread. The state of the lock will be + 1 every time it is acquired. That is, when acquiring the lock for the first time, set the lock status value to 1 through acquire (1); When acquiring the lock again, set the status value of the lock to 2; And so on This is why the parameter passed in is 1 when obtaining a lock@ H_ 404_ 1 @ reentrant means that a lock can be acquired multiple times by a single thread.

@H_ 404_ 1@2. acquire()

Acquire() is implemented in AQS. Its source code is as follows:

(01) "current thread" first attempts to acquire the lock through tryacquire(). If successful, return directly; If the attempt fails, enter the waiting queue to sort and wait (there may be a thread waiting for the lock in front). (02) if the "current thread" attempt fails, first add the "current thread" to the end of the "CLH queue (non blocking FIFO queue)" through addwaiter (node. Exclusive). The CLH queue is the thread waiting queue. (03) after addwaiter (node. Exclusive) is executed, acquirequeueueueued () will be called to obtain the lock. Because reentrantlock is a fair lock at this time, it will obtain the lock according to the fairness principle. (04) when executing acquirequeueueueueueueueued(), the "current thread" will enter the CLH queue to sleep and wait until it obtains the lock! If the "current thread" is interrupted during sleep waiting, acquirequeueueued will return true. At this time, the "current thread" will call selfinterrupt() to generate an interrupt for itself. As for why you should give yourself an interruption, I'll introduce it later.

The above is a general description of acquire(). Next, we divide the function into four parts to analyze step by step.

@H_ 404_ 1 @ I tryAcquire()

@H_ 404_ 1@1. tryAcquire()

Tryacquire() of fair lock is in reentrantlock It is implemented in fairsync class of Java. The source code is as follows:

Note: according to the code, we can analyze that the function of tryacquire() is to try to obtain the lock. Note that this is just a try! If the attempt is successful, return true; If the attempt fails, false will be returned, and then the lock will be obtained through other methods. Later, we will explain how to obtain the lock step by step when the attempt fails.

@H_ 404_ 1@2. hasQueuedPredecessors()

Hasqueuedpredecessors() is implemented in AQS. The source code is as follows:

Note: through the code, it can be analyzed that hasqueuedpredecessors() determines whether the "current thread" is at the head of the CLH queue to return whether there is a thread waiting longer than the "current thread" in the AQS. The following describes head, tail, and node.

@H_ 404_ 1@ 3. Node source code

Node is the node of CLH queue. Node is implemented in AQS, and its data structure is as follows:

Note: node is the node of CLH queue and represents "thread queue waiting for lock". (01) each node corresponds to a thread. (02) each node will point to the previous node and the next node respectively through prev and next, which represent the previous waiting thread and the next waiting thread respectively. (03) the node saves the waiting status of the thread through waitstatus. (04) node uses nextwaiter to distinguish whether a thread is an "exclusive lock" thread or a "shared lock" thread. If it is an exclusive lock thread, the value of nextwaiter is exclusive; If it is a "shared lock" thread, the value of nextwaiter is shared.

@H_ 404_ 1@ 4. compareAndSetState()

Compareandsetstate() is implemented in AQS. Its source code is as follows:

Note: compareandswapint() is sun misc. A local method in the unsafe class. In this regard, we need to understand that compareandsetstate (expect, update) operates the current thread atomically; If the status of the current thread is expect, set its status to update.

@H_ 404_ 1@5. setExclusiveOwnerThread()

Setexclusiveownerthread() in abstractownablesynchronizer Java. Its source code is as follows:

Note: setexclusiveownerthread() is used to set thread t as the thread that currently owns the exclusive lock.

@H_ 404_ 1@6. getState(),setState()

Both getstate() and setstate() are implemented in AQS. The source code is as follows:

Note: state indicates the state of the lock. For exclusive locks, state = 0 indicates that the lock is available (that is, the lock is not held by any thread lock). Since the exclusive lock in Java is reentrant, the value of state can be > 1.

Summary: the function of tryacquire() is to let the "current thread" try to acquire the lock. True is returned for success and false for failure.

@H_ 404_ 1 @ II addWaiter(Node.EXCLUSIVE)

Addwaiter (node. Exclusive) is used to create the node node of "current thread", and the lock corresponding to "current thread" recorded in the node is of "exclusive lock" type, and add the node to the end of CLH queue.

@H_ 404_ 1@1.addWaiter ()

Addwaiter() is implemented in AQS. The source code is as follows:

Note: for "fair lock", addwaiter (node. Exclusive) will first create a node. The node type is "exclusive lock" (node. Exclusive). The node is then added to the end of the CLH queue.

@H_ 404_ 1@2. compareAndSetTail()

Compareandsettail() is implemented in AQS. The source code is as follows:

Note: compareandsettail also belongs to CAS function and is implemented through "local method". Compareandsettail (expect, update) operates atomically. Its function is to judge whether the end of the CLH queue is expected. If so, set the end of the queue to update.

@H_ 404_ 1@3. enq()

Enq () is implemented in AQS. The source code is as follows:

Note: the function of enq () is very simple. If the CLH queue is empty, create a new CLH header; Then add node to the end of CLH. Otherwise, add node directly to the end of CLH.

Summary: addwaiter() is used to add the current thread to the CLH queue. This means that the current thread is added to the waiting thread queue waiting to acquire the "lock".

@H_ 404_ 1 @ III acquireQueued()

Previously, we have added the current thread to the CLH queue. The function of acquirequeueueueued() is to execute the thread of CLH queue step by step. If the current thread obtains the lock, it returns; Otherwise, the current thread sleeps until it wakes up and reacquires the lock. Next, let's look at the specific process of acquirequeueueueued ().

@H_ 404_ 1@ 1. acquireQueued()

Acquirequeueueued() is implemented in AQS. The source code is as follows:

Note: the purpose of acquirequeueueueueueueueued() is to obtain locks from the queue.

@H_ 404_ 1@2. shouldParkAfterFailedAcquire()

Shouldparkafterfailedacquire() is implemented in AQS. The source code is as follows:

explain:

(01) for waitstatus, please refer to the following table (the value of waitstatus is in the middle extension). For more information about waitstatus, please refer to the previous node class introduction.

Cancelled [1] - the current thread has been canceled. Signal [- 1] - "subsequent threads of the current thread need to be unpark". Generally, the successor thread of the current thread is blocked, and the current thread is released or cancelled. Therefore, it is necessary to wake up the successor thread of the current thread. Condition [- 2] - the current thread (in condition sleep state) is waiting for condition to wake up. Promote [- 3] - (shared lock) other threads have obtained the "shared lock" [0] - the current thread does not belong to any of the above states.

(02) shouldparkafterfailedacquire() judges whether the "current thread" needs to be blocked through the following rules.

Rule 1: if the status of the predecessor node is signal, it indicates that the current node needs to be unpark (wake up), and then return true. Rule 2: if the status of the predecessor node is cancelled (WS > 0), it indicates that the predecessor node has been cancelled, a valid (non cancelled) node is found through the previous backtracking, and false is returned. Rule 3: if the status of the predecessor node is non signal or non canceled, set the status of the predecessor node to signal and return false. If "rule 1" occurs, that is, the "previous node is signal" state, it means that the "current thread" needs to be blocked. Next, parkandcheckinterrupt() will be called to block the current thread and will not return from parkandcheckinterrupt() until the current thread is awakened first.

@H_ 404_ 1@ 3. parkAndCheckInterrupt())

Parkandcheckinterrupt() is implemented in AQS. The source code is as follows:

Note: parkandcheckinterrupt() is used to block the current thread and return the interrupt status of "after the thread is awakened". It will first pass locksupport Park() blocks the "current thread" and then passes through thread Interrupted() returns the interrupted state of the thread.

Here is how to wake up after a thread is blocked. There are generally two cases: the first case: unpark() wakes up. After the "thread corresponding to the previous node" uses the lock, wake up the current thread through unpark(). Case 2: interrupt wake-up. Other threads interrupt the current thread through interrupt().

Add: the function of park(), unpark() in locksupport() is similar to that of wait(), notify() in object, blocking / waking. Their usage is different. Park(), unpark() is lightweight, while wait(), notify() must first obtain the synchronization lock through synchronized. We will introduce locksupport in the following chapters!

@H_ 404_ 1@ 4. Try acquire() again

After understanding the shouldparkafterfailedacquire() and parkandcheckinterrupt() functions. We then analyze the for loop part of acquirequeueueueueueued ().

explain:

(01) through node Predecessor() gets the predecessor node. Predecessor () is the successor node that returns node. If you have any doubts about this, you can see the following introduction to node class.

(02) P = = head & & tryacquire (ARG) first, judge whether the "predecessor node" is a CHL header. If so, try to acquire the lock through tryacquire(). In fact, the purpose of this is to "let the current thread obtain the lock", but why do you need to judge P = = head first? Understanding this is very important to understand the mechanism of "fair lock", because the reason for doing so is to ensure fairness! (a) Earlier, in shouldparkafterfailedacquire(), we judge whether the "current thread" needs to be blocked; (b) Then, if the "current thread" is blocked, parkandcheckinterrupt() will be called to block the thread. When the thread is unblocked, we will return the interrupt state of the thread. The reason why the thread is blocked may be that "the thread is interrupted" or "other threads call the unpark() function of the thread". (c) Back to P = = head. If the current thread is awakened because other threads call the unpark() function, the thread that awakens it should be the thread corresponding to its predecessor node (you will see this later in the process of "releasing the lock"). OK, it is the previous node that calls unpark() to wake up the current thread! At this point, it is easy to understand P = = head: the current successor node is the head node of the CLH queue and it releases the lock; It's the current node's turn to acquire the lock. Then, the current node obtains the lock through tryacquire(); If successful, set the current node as the head node through sethead (node) and return. In short, if "the predecessor node calls unpark() to wake up the current thread" and "the predecessor node is the CLH header", P = = head is satisfied, that is, the fairness principle is met. Otherwise, if the current thread wakes up because the thread is interrupted, it is obviously not fair. This is why P = = head is to ensure fairness!

Summary: the function of acquirequeueueueued() is that the "current thread" will block and wait according to the fairness principle until the lock is obtained; And returns whether current thread has been interrupted during waiting.

@H_ 404_ 1 @ IV selfInterrupt()

Selfinterrupt() is implemented in AQS. The source code is as follows:

Note: the code of selfinterrupt () is very simple, that is, the "current thread" generates an interrupt by itself. But why? This must be analyzed in conjunction with acquirequeueueueueueueued(). If the current thread has been interrupted in acquirequeueueueueued(), execute selfinterrupt(); Otherwise, it will not be executed.

In acquirequeueueueued (), even if the thread is awakened by an interrupt in the blocking state, it obtains the CPU execution right; However, if there are other threads waiting for locks in front of the thread, the thread still cannot obtain the lock according to the principle of fairness. It will block again! The thread blocks again until the thread is awakened by the thread lock waiting for the lock in front of it; The thread will acquire the lock and "really execute"! That is, before the thread "successfully acquires the lock and actually executes", its interrupt will be ignored and the interrupt flag will be cleared! Because in parkandcheckinterrupt(), we call thread. When the thread is in the interrupt state interrupted()。 This function is different from the isinterrupted() function of thread. Isinterrupted() only returns the interrupt state, while interrupted() also clears the interrupt state after returning the current interrupt state. Because the previous interrupt state has been cleared, you need to call selfinterrupt() to regenerate an interrupt!

Summary: the function of selfinterrupt() is to generate an interrupt by the current thread itself.

@H_ 404_ 1 @ summary

Looking back at the acquire () function, its ultimate goal is to acquire the lock!

(01) first try to acquire the lock through tryacquire(). If successful, return directly; If the attempt fails, acquire the lock through acquirequeueueueueued(). (02) if the attempt fails, the "current thread" will be added to the end of the "CLH queue" through addwaiter(); Then call acquireQueued (), sort in the CLH queue, wait for the lock, in the process, the thread is dormant. It does not return until the lock is acquired. If it is interrupted during sleep waiting, call selfinterrupt() to generate an interrupt by itself.

The above is the whole content of this article. I hope it will be helpful to your study, and I hope you can support programming tips.