At 10 o ‘clock sharp, I arrived at the company, and became the last employee in the whole group.
I was just about to brush my phone to touch the fish when I saw the boss mysteriously walking over.
Boss: Flash ah, you write a tool, based on AQS to achieve a lock, for our group of other development use
Me: Oh OK boss: How soon will you be ready?
Me: is a tool class is it, well this afternoon to you
Boss: Well, hurry up and do it. Everyone is waiting for it
Me: Oh ok
Read the egg: sorted out a very comprehensive Java first-line factory Gaegan interview questions analysis collection is now free to share to read this article Java programmer friends, need to get their own
Dynamic Interview Analysis Collection: Java Basics – Intermediate – Advanced Interview +SSM Framework + Distributed + Performance Optimization + Micro Services + Concurrent Programming + Network + Design Patterns + Data Structures and Algorithms +…
So let’s write a framework
About the lock, I still have a vague understanding, to let the user can obtain the lock, release the lock, to achieve multi-threaded access security. So I quickly wrote out a framework first.
Public void lock() {} public void unlock() {} public void unlock() {}Copy the codeI was halfway through the tooling class, and I laughed at the thought of the entire team of developers using my tools this afternoon.
FlashLock flashLock = new FlashLock(); Public void doSomeThing() {// Obtain the lock, indicating that only one thread is allowed to execute the method flashlock. lock(); try { ... } finally {// Gracefully release the lock in finally flashlock. unlock(); }}Copy the codeAs my colleagues cast strange glances, I came to my senses. Keep thinking, how do I achieve this lock effect in these two methods? Brain a blank ah, ah but the boss just said to be based on AQS, that affirmation this thing can provide some convenience to me, so I searched in Baidu encyclopedia what is AQS
Baidu Baike has not yet included the entry “AQS”
This boss is so lame, give me something I can’t even find in the encyclopedia… I can only search Baidu
The forehead! This seems to be the focus of a Java interview! Wrong boss.
I ordered one, know to call the full name of AQS AbstractQueuedSynchronizer queue type synchronizer (abstract), is a class of a JDK source.
Hi, made a long time is just a class, I have this kind of source code in the world I have god code farmers, also see what article ah, I quickly opened JDK1.8 source code, found this class.
Oh, my God! That’s 2,316 lines! I quickly removed all the comments and found 914 more lines.
Due to be handed in the afternoon, I gave up the idea of not looking at the annotations hard gnaw source, began to look at the annotations…
2: Use AQS to achieve the simplest lock
Provides a framework for implementing blocking locks and related synchronizers (semaphores, events, etc) that rely on first-in-first-out (FIFO) wait queues. This class is designed to be a useful basis for most kinds of synchronizers that rely on a single atomic int value to represent state. Subclasses must define the protected methods that change this state, and which define what that state means in terms of this object being acquired or released.
First it says it’s a framework, and then it says this class is based on an atomic variable, but that’s all principle and I don’t care.
Subclasses must implement methods to change this state and acquire acquired or released locks.
Oh! It looks like I need to inherit it with a subclass, implement some of the methods it specifies, and the parent class will do everything else for me. I immediately realized that the template method used in this design pattern, this is my favorite design pattern, because just by reading the meaning of the template method that needs to be implemented by subclasses, I can make good use of the power of this class.
So I went to see if there were any template methods that needed to be subclassed, and sure enough I found this in the comments.
* To use this class as the basis of a synchronizer, redefine the
* following methods
*
* <li> {@link #tryAcquire}
* <li> {@link #tryRelease}
* <li> {@link #tryAcquireShared}
* <li> {@link #tryReleaseShared}
* <li> {@link #isHeldExclusively}
* </ul>
Copy the codeFind these classes in the source code
protected boolean tryAcquire(int arg) {
throw new UnsupportedOperationException();
}
protected boolean tryRelease(int arg) {
throw new UnsupportedOperationException();
}
protected int tryAcquireShared(int arg) {
throw new UnsupportedOperationException();
}
protected boolean tryReleaseShared(int arg) {
throw new UnsupportedOperationException();
}
protected boolean isHeldExclusively() {
throw new UnsupportedOperationException();
}
Copy the codeThis is the template method left for our subclasses to implement ah, then I write a class to implement them, but how to write…
I was thinking of going to Baidu, when I suddenly found that a small demo based on AQS was given in the note, which was quite long. I understood its meaning, and removed all the ones I did not understand, and wrote a very simple lock
Public class FlashLock public void lock() {sync.acquire(1); } // Unlock public void unlock() {sync.release(1); } private final Sync sync = new Sync(); / / this inner class is inherited and implements AQS but I'm only here to implement two methods private static class Sync extends AbstractQueuedSynchronizer {@ Override public Boolean tryAcquire(int acquires) {return true if (compareAndSetState(0, 1)) {return true; } return false; } @override protected Boolean tryRelease(int releases) {// Release the lock. Ask the reader to consider setState(0); return true; }}}Copy the codeLock and UNLOCK methods are implemented, so I’m going to write some classic test code
Private static long count = 0; Count++ public static void main(String[] args) throws Exception { Th1 = new Thread(()-> add()); Thread th2 = new Thread(()-> add()); // Start two threads th1.start(); th2.start(); Th1.join (); // Wait for both threads to finish. th2.join(); System.out.println(count); } private static ExampleLock ExampleLock = new ExampleLock(); // loop count++, 10000 times private static void add() {examplelock.lock (); for (int i = 0; i < 10000; i++) { count++; } add2(); Examplelock.unlock (); }Copy the codeI tested it several times and found it was 20000. Ha ha, it was done. I quickly told everyone in the group that I had written the new tool. I got a lot of thumbs up from my colleagues and boss.
I couldn’t help laughing again. Out of the office, ready to find a place for lunch.
I have to study the principle of AQS
At 2pm sharp, I was the last person in the office to take a nap…
Xiaoyu: But I have a problem, that is, I use your lock tool, some threads always can not grab the lock, some threads can always grab the lock. Although it is tempting for threads to grab locks, what about a design that equalizes the chances for each thread, or at least prevents one thread from getting the lock all the time? Me: How is this possible, I just write a lock tool, but also can affect other people’s CPU and operating system level mechanism? Yu: Well, think about it. As the company’s most handsome programmer, I believe you.
I this person can not help the girl praise, quickly open the computer screen, staring at my lock code to see
@override public Boolean tryAcquire(int acquires) {if (compareAndSetState(0, acquires)) {return true; } return false; }Copy the codeI noticed that in this code, when attempting to acquire the lock, CAS first grabs the lock and returns true on success. Is there a mechanism I can put in there so that these threads don’t just start grabbing locks at the first opportunity, but take into account the feelings of other threads before deciding whether or not to grab a lock?
I found that I had to look into the internal implementation logic of AQS, the principle, to see if I could get some ideas.
AQS has four attributes, one of which is an inner class Node.
public abstract class AbstractQueuedSynchronizer { private transient volatile Node head; private transient volatile Node tail; private volatile int state; static final class Node {} } static final class Node { // ... Omit some of the volatile Node prev that we don't care about for now; volatile Node next; volatile Thread thread; }Copy the codeCombine that with the highly general notes on AQS from the very beginning
Provides a framework for implementing blocking locks and related synchronizers (semaphores, events, etc) that rely on first-in-first-out (FIFO) wait queues. This class is designed to be a useful basis for most kinds of synchronizers that rely on a single atomic int value to represent state.
As you can easily guess, the inner Node class and its head and tail variables represent a wait queue inside the AQS, while the remaining state variables represent the state of the lock.
A wait queue should be a temporary place where a thread can wait to wake up and try to acquire the lock if it fails to acquire the lock. Prev and Next indicate that Node forms a bidirectional linked list, which facilitates algorithms that need to get a precursor or successor Node.
Great, just by looking at some properties and a comment, I have a guess about the general principle of AQS, which seems quite plausible, so I’ll quickly draw it into a few diagrams to understand it better. (Because this is very important, I won’t keep you guessing, but I’ll just draw the best picture, but I won’t go into too much detail.)
The following figure is an intuitive understanding of AQS most core lines of code, please carefully taste
public final void acquire(int arg) { if (! tryAcquire(arg) && acquireQueued(addWaiter(Node.EXCLUSIVE), arg)) selfInterrupt(); }Copy the code
If you’re not too digested, here’s another chance, so let me get this straight.
First, the state of the initial state AQS =0, indicating that no thread holds the lock. Head and tail are also null, indicating that there are no threads in the wait queue.
The first thread (thread 1) comes in and grabs the lock (state=1) without any thread competing with it.
If thread 1 does not release the lock, thread 2 fails to acquire the lock (execute tryAcquire on your own). After that, AQS does all the rest for you, first join the end of the queue addWaiter (queue is empty, so initialize a placeholder header) and then try to acquire the lock acquireQueue in the loop (note that there is quite a bit of detail here, First of all, only the person whose first node is the head node can try to acquire the lock, that is, only the person at the head of the queue has a chance. In the next loop, the lock acquisition is not always CAS, but the number of times is controlled by a flag. When THE CAS fails twice, the thread suspends park, and then wakes up Unpark after waiting for the thread holding the lock to release the lock. The rest of the details, I hope readers read the source code, not a sentence or two clear).
And then thread 3 comes in, and goes through the same experience as thread 2, except that its precursor is not a header, so it doesn’t get a chance to try to acquire the lock until thread 2 grabs the lock and exits the queue, and its precursor becomes a header.
Thread 1 finally releases the lock (state=0) and at the same time finds the queue header to wake up unpark. The head Node is the Node represented by thread 2, so thread 2 is awakened. If thread 2 is not suspended at this point, it is still trying to acquire the lock. If it is already suspended, thread 2 is woken up, causing it to keep trying to CAS to acquire the lock until it succeeds.
And so, over and over… Do you get the idea?
Well, I understand the principle, to implement a fair lock
Take a closer look at the penultimate picture above.
All right, all right, you’re too lazy to flip it over, I’ll glue it over for you.
Thread 2, which was waiting in the queue, woke up after thread 1 released the lock, but it still needs to grab the lock and may fail to do so.
So if every time thread 2 tries to grab the lock, another new thread takes the lock, then thread 2 never gets a chance to run, and the other threads waiting behind thread 2 never get a chance to run.
Lead to some threads have not run the opportunity, is the new thread every time regardless of whether there is a queue, are directly up to grab the lock.
Good, just small yu put forward the question, I finally have the idea, is to let the new thread grab lock, first ask a, “is there anyone queuing? If there’s a queue, I’ll go to the end of it.”
@override public Boolean tryAcquire(int acquires) {Override public Boolean tryAcquire(int acquires) { AQS will help me put this thread at the end of the queue return false; } if (compareAndSetState(0, 1)) { return true; } return false; }Copy the codeHow do you tell if there is a thread waiting on the queue? I think, AQS so excellent framework must provide a way for the upper level, will not let us go deep into its implementation of the internal, sure enough I found.
public final boolean hasQueuedPredecessors()
Copy the codeAfter optimizing the structure, the final code looks like this
@Override
public boolean tryAcquire(int acquires) {
if (hasQueuedPredecessors() &&
compareAndSetState(0, 1)) {
return true;
}
return false;
}
Copy the codeHa ha, done, hurry to find xiaoyu show off.
And so on…
Then my original way of implementation is gone, there must be others to ask me, EMMM, I expose both ways to everyone, you choose.
I will be the original way of violent lock grab a name, called unfair lock, because the thread grab lock does not queue, pure look at the face. According to xiaoyu needs to achieve the queue lock, I call it fair lock, because as long as there is a thread in the queue, the new will have to obediently queue, can not directly grab.
Public FlashLock(Boolean fair) {sync = fair? new FairSync() : new NonfairSync(); }Copy the codeHa ha, with a lofty name and code implementation, I am happy to find xiaoyu.
The boss requires that the method be reentrant
At 5:30 p.m., I was about to be the first person in the group to have dinner when the boss came running over with a gloomy face.
Boss: flash ah, I use you this tool lead to a thread card dead ah, have been getting less than lock me: hm how can? Boss: The code is sent to you, and you have a look at it!
I opened the locked screen and clicked on the code my boss had sent me
public void doSomeThing2() { flashLock.lock(); doSomeThing2(); flashLock.unlock(); } public void doSomeThing2() { flashLock.lock(); . flashLock.unlock(); }Copy the codeIt suddenly dawned on me that a thread had executed a method, acquired the lock, left the method unfinished, called another method that required the lock, and was stuck forever.
The principle is easy to understand, but it doesn’t seem to be very friendly to use. No wonder the boss is so angry. Is there a way for the same thread to hold the lock and still acquire it (reentrant), only if different threads are mutually exclusive?
Now I use all the variables in AQS, and I don’t see any variables that can record the current thread.
Oh yeah! AQS itself also inherited the AbstractOwnableSynchronizer this class! I quickly found this property in this class!
/**
* The current owner of exclusive mode synchronization.
*/
private transient Thread exclusiveOwnerThread;
Copy the codeFamiliar with the previous routine, I quickly found these two methods again!
protected final void setExclusiveOwnerThread(Thread thread);
protected final Thread getExclusiveOwnerThread();
Copy the codeWhen a thread finds that the lock is occupied, instead of giving up, I simply check to see if I am the thread holding the lock. With previous experience in mind, THIS time I went straight to the final reentrant fair lock code.
@Override public boolean tryAcquire(int acquires) { final Thread current = Thread.currentThread(); int c = getState(); if (c == 0) { if (hasQueuedPredecessors() && compareAndSetState(0, SetExclusiveOwnerThread (current); return true; }} else if (current == getExclusiveOwnerThread()) {setState(c + acquires); return true; } return false; }Copy the code6. Work!
I submitted the final version of the lock code, packed up my stuff and left work, and today was really fruitful.
That’s the end of the story. If you’ve made it this far and fully understood everything above, congratulations, you’ve already mastered the core principles of AQS and implemented a classic lock ReentrantLock based on it. The framework of AQS has been built unconsciously. Both are essential for a Java programmer interview.
It’s just scratching the surface, but if you’re new to these two concepts, the most important thing about this article is that you get a positive first impression of them. I hope the first impression of AQS is not that it’s an abstract queue-type synchronizer, but that it’s just a class with a few template methods to make it easier to implement locks. It’s inaccurate, it’s low, but it’s probably true.