This is why’s 99th original article

Hi, I’m Why.

No, this picture is not me. The headline says pops is this guy. It happened the other day.


The other day, I found a tech group full of bigs having a heated discussion about happens-before relationships and as-if-serial semantics.

And I looked at the time, it was nearly 23 o ‘clock, the big guys are so roll, then I have to follow the roll, so I looked at their chat records.

And I, as a vegetable chicken, although there is no sense of participation, but feel that the big guys are quite reasonable, argued.

So basically, this is how I went about it:


But as soon as they started talking about Java Concurrent Programming, I was intrigued.

I’ve read the book, and it’s right here, so I can finally get a word in edgewise.

On closer inspection, they refer to section 16.1.4 of the book:


I don’t even know what the word “syncing” means.

So I turned to this stanza and read it.

Since this section is not long and there is no other background except the basic knowledge of happens-before relationship, I take a screenshot of this section to show you:


How did it go? How did everyone feel after watching it?

Don’t even have the patience to finish reading, a feeling in the clouds and fog?

To be honest, that’s what I feel when I read it. I understand every word, but I don’t know what it means when I read it together.

So, the feeling after reading it is:


To find the source code

But don’t panic, the example in this article is FutureTask, one of the basics of concurrent programming that I’m familiar with.

I decided to look in the source code, but I didn’t find the innerSet or innerGet method in the book:


Since I have the source code for JDK 8 here, and this book was released in February 2012:


Since it is a translation, the original book may have been written earlier.

The JDK release timeline shows that the source code is prior to JDK 8:


Sure enough, a big guy told me that the source code in JDK 6 is written like this:


But I don’t think it’s very profitable to work on JDK 6. (Mostly I’m too lazy to download)

So, I was in the JDK 8 source code, found a little bit of clues.

I finally figured out what “with synchronization” means.

And I have to admire Doug Lea’s code, which is: wow.


What exactly is “syncing with help”? Let me tell you more.

paved

In order for the article to proceed smoothly, there must be a foundation of basic knowledge, that is happens-before relationship.

The formal formulation of the happens-before relationship is the JSR 133 specification:

http://www.cs.umd.edu/~pugh/java/memoryModel/jsr133.pdf


If you don’t know what JSR133 is, check out this link.

Java内存模型FAQ（三）JSR133是什么？

Here’s the formal description of the happens-before relationship:


Because this paragraph, especially the words behind the six little black dots, is so important that a miss can be as good as a mile, I dare not easily translate it in the lighthearted style as before.

So I decided to stand on the shoulders of the big guy, respectively “In-depth Understanding of Java Virtual Machine (3rd Edition)”, “Java Concurrent Programming Practice”, “Java concurrent programming art” these three books about this part of the definition and description of the move, we compare.

If you are familiar with this rule, you can skip this section.


Start.

First up is Understanding the Java Virtual Machine (3rd Edition) :

  • Program Order Rule: In a thread, actions written earlier take place before those written later, in Order of control flow. Note that we are talking about the control flow sequence, not the program code sequence, because we have branches, loops, and so on to consider.
  • Monitor Lock Rule: An UNLOCK operation occurs first when a subsequent Lock operation is performed on the same Lock. What must be emphasized here is “the same lock”, and “behind” refers to the sequence of time.
  • Volatile Variable Rule: Writes to a volatile Variable occur first and then reads occur later, again in chronological order.
  • Thread Start Rule: The Start () method of a Thread object precedes every action of the Thread.
  • Thread Termination Rule: All operations ina Thread occur in the Termination detection of this Thread first. We can check whether the Thread has terminated by means of whether the Thread:: Join () method ends or the return value of Thread::isAlive(), etc.
  • Interruption Rule: A call to the interrupt() method occurs when the interrupted Thread code detects that the Interruption has occurred. Thread:interrupted() checks whether the Interruption has occurred.
  • Finalizer Rule: An object’s initialization completes (the end of constructor execution) before its Finalize () method.
  • Transitivity: If operation A precedes operation B and operation B precedes operation C, operation A precedes operation C.

Then came Java Concurrent Programming in Action:

  • Program order rule: If operation A precedes operation B in the program, operation A precedes operation B in the thread.
  • Monitor lock rule: Unlock operations on the monitor lock must be performed before lock operations on the same monitor lock.
  • Rule for volatile Variables: Writes to volatile variables must be performed before reads to them.
  • Thread Start rule: A call to thread.start on a Thread must be executed before any action is performed in that Thread.
  • Thread termination rule: Any operation in a Thread must be performed before another Thread detects that the Thread has terminated, either by returning successfully from thread. join, or by returning false when thread. isAlive is called.
  • Interrupt rule: When a thread calls an interrupt on another thread, it must be executed before the interrupted thread detects the interrupt call (by throwing InterruptedException, or by calling isInterrupted and interrupted).
  • Finalizer rule: An object’s constructor must be executed before starting the object’s finalizer.
  • Transitivity: If operation A is performed before operation B, and operation B is performed before operation C, then operation A must be performed before operation C.

The Art of Concurrent Programming in Java, in which the author adds the qualifier “The happens-before rule is relevant to programmers” :

  • Procedure order rule: For every action in a thread, happens-before any subsequent action in that thread.
  • Monitor lock rule: a lock is unlocked, happens-before a lock is subsequently locked.
  • Volatile variable rule: Writes to a volatile field, happens-before any subsequent reads to that volatile field.
  • Transitivity: If A happens-before B, and B happens-before C, then A happens-before C.

That is: thread start rules, thread kill rules, interrupt rules, object kill rules are insensitive to development, and there is no room for messing around with these rules.

When you compare the descriptions of the same event in these three books, it may be a little more impressive.

It’s essentially the same thing, just a slightly different description.

In addition, I think I need to add a very important point, which is a very important word action that appears in many places in the original paper:


So what is action?

For this slightly vague definition, the fifth point at the beginning of the paper mentions the specific meaning:

In this section we define in more detail some of the informal concepts we have presented. In this section, we will define some of our informal concepts in more detail.

The seven concepts in the paper are described in detail, which are:

  • Shared variables/Heap memory

  • Inter-thread Actions

  • Program Order

  • Intra-thread semantics

  • Synchronization Actions

  • Synchronization Order

  • Happens-Before and Synchronizes-With Edges

In my personal understanding, action in happens-before mainly refers to the following three concepts:




Inter-thread Actions, intra-thread Actions, and Synchronization Actions.

Locking, unlocking, reading and writing to volatile variables, starting a thread, and detecting whether a thread has terminated are all synchronous actions.

Inter-thread actions are relative to intra-thread actions. For example, when a thread reads or writes a local variable, that is, a variable assigned on the stack, it is not perceived by other threads. This is an in-thread action. Interthread actions such as reads and writes to global variables, that is, variables allocated in the heap, are perceived by other threads.

In addition, if you look at the inter-Thread Actions where I underlined them, the description is pretty much the same as synchronous Actions. I understand that most inter-thread actions are synchronous actions.

So you read a book called HotSpot in The Deep Understanding of the Java Virtual Machine, which has a slightly different description of the happens-before, starting with the qualification that “All synchronized actions…” :

1) All synchronized actions (locking, unlocking, reading and writing volatile variables, thread start, thread completion) are coded in the same order as the execution order, also known as the synchronization order. 1.1) For the same Monitor in the synchronization action, unlocking occurs before locking. 1.2) The same volatile variable write precedes the read. 1.3) The thread start operation is the first operation of the thread, and no previous operation can occur. 1.4) When thread T2 finds that thread T1 has completed or connected to thread T1, the last operation of T1 precedes all operations of T2. 1.5) If thread T1 interrupts thread T2, the T1 breakpoint precedes the operation of any thread that determines that T2 is interrupted. Write default values to variables before the first operation of the thread; Object initialization completes before the first operation of finalize(). 2) If A occurs before B and B occurs before C, then it can be determined that A occurs before C. 3) Volatile writes precede volatile reads.

Originally, I wanted to mention the happens-before description in Ideas for Java Programming.

As a result, I went through the section on concurrency in the book, and it turned out:

No, yes, write!

Well, I suppose it’s possible that the divine book was written before the release of JSR133 in 2004?

As a result, the English version was released in 2006, which the author intentionally omitted, and he only mentions Java Concurreny in Practice in 21.11.1:


Java Concurreny in Practice is Java Concurrent Programming in Action.

For a book that is so well known in the Java world, it is a slight pity that there is no mention of happens-before.

But on second thought, although the status of this book is very high, but the positioning is actually entry-level, did not mention this piece of knowledge is relatively normal.

Another interesting thing is this:


In Understanding the Java Virtual Machine (3rd edition), Monitor is translated as “pipe process”, and the other two translations are “Monitor”.

So what exactly is a “pipeline”?


Harm? That’s the same thing.

Synchronized in Java is an implementation of a pipe procedure.

FutureTask in JDK 8

With so much foreshadowing ahead, you should not forget what I want to share in this article, right?

That’s the use of the “with synchronization” thing in FutureTask.


This is a screenshot of the FutureTask source code in JDK 8, focusing on the two sections I’ve framed.

  • State is volatile.
  • Outcome the comment following the outcome variable.

Focus on this note:

non-volatile, protected by state reads/writes

You see, the outcome encapsulates a FutureTask return, which could be a normal return or an exception in the task.

The simplest and most common application scenario is that the main thread submits a task to the thread pool via submit, and the return value is FutureTask:


What will you do next?

Call FutureTask’s get method in the main thread to get the return value of the task?

What happens now is that the thread in the thread pool writes to the outcome, and the main thread calls the GET method to read the outcome?

In this scenario, is it normal to add a volatile to the outcome to ensure visibility?

So why isn’t volatile here?

You just smack it yourself.

Everything that follows revolves around this topic.

Here we go.

First, across the board, there are only two writes to the outcome variable:


Set and setException, and the logic and principle of these two places are actually the same. So I’m just going to analyze the set method.

Next, look at the read operation on the outcome variable, which is the only place, the get method:


The caveat is Java. Util. Concurrent. FutureTask# get (long, Java. Util. Concurrent. TimeUnit) method and the principle of the get method is consistent, also won’t do too much reading.

So we focused on these three methods:


The get method calls the report method. Let’s merge the two methods:


Is there anything wrong here?

Then, we really only care about when the outcome is returned, and everything else is interference to me, so we turn the get above into pseudocode:


When S is NORMAL, outcome is returned. Is there anything wrong with that pseudocode?

Let’s look at the set method again:


(实 习) COMPLETING the state (实 习) from NEW (实 习) to the (实 习) state (实 习), CAS (实 习)

Then, after a third line of code, outcome= V, the state is changed to NORMAL.

He had spent those years well, but in fact, the transition from NEW to NORMAL is fleeting.

Or even, like, useless?

So, in order to do my reasoning well, I have decided to use inverse proof, assuming that we do not need this COMPLETING state, then our set method will look like this:


After simplification, this is the pseudocode for the final set:


So we put the pseudo-code for get/set together:


And here, finally, all the groundwork is done.

Welcome to declassification.

First, if the value read at ④ is NORMAL, then the value read at ③ must have already been executed.

Why is that?

Because s is modified by volatile, according to the happens-before relationship:

Rule for volatile Variables: Writes to volatile variables must be performed before reads to them.

Therefore, we can conclude that the code labeled ③ executes before the code labeled ④.

And according to the order of procedure rule, namely:

In a thread, operations written earlier take place before operations written later, in control flow order. Note that we are talking about the control flow sequence, not the program code sequence, because we have branches, loops, and so on to consider.

② happens-before ③ happens-before ④ happens-before ⑤

And according to the transitivity rule, namely:

If operation A precedes operation B and operation B precedes operation C, it follows that operation A precedes operation C.

② happens-before ⑤.

While ② is the writing of the outcome variable, ⑤ is the reading of the outcome variable.

Although the variable that is written and read is not volatile, it is synchronized using the happens-before relationship of the S variable modified by volatile.

That is, write before read.

This is called syncing with help.

Did you get a whiff of it?


Don’t worry, I’m talking about those conditions well.

Going back to the pseudo-code for the set method, I haven’t said anything about that.

Can we agree that while ① and ③ are both operations on volatile variables, they are not thread-safe?

So, this is where we use CAS for thread safety.

So the program looks like this:


Thus, the thread-safety problem is solved. But there are other problems.

The first problem is that the meaning of the program has changed:

From “S becomes NORMAL only after the outcome assignment is complete” to “s is assigned only after the outcome assignment is NORMAL”.

However, this problem is not within the scope of my discussion in this article, and it will be solved eventually, so let’s look at another problem, which is the one I want to discuss.

What’s the problem?

That was Outcome’s “help sync” strategy failed.

Because if we solve thread-safety problems in this way, the program looks something like this when we take the CAS operation apart:


From the happens-before relationship, we can only infer that:

② happens-before ④ happens-before ⑤.

So, we can’t get ③ happens-before ⑤, so we can’t use synchronization.

At this point, what if it was us?

It’s easy. Just add volatile to the outcome. There’s no need for so much weird reasoning.

But Doug Lea is Doug Lea. How low is volatile?

This is possible with synchronization, but not thread-safe:

protected void set(V v) {

    if (s==NEW) {

        outcome = v;

        s=NORMAL;

    }

}

Copy the code

So, how about this:

protected void set(V v) {

    if (s==NEW) {

        s=COMPLETING;

        outcome = v;

        s=NORMAL;

    }

}

Copy the code

COMPLETING those variables is also writing about S, and the outcome can be “synchronized”.

The CAS optimization looks like this:

protected void set(V v) {

    if (compareAndSet(s, NEW, COMPLETING)){

        outcome = v;

        s=NORMAL;

    }

}

Copy the code

Introducing a fleeting COMPLETING state can not only make the outcome variable volatile, but also establish the happens-before relationship, so as to achieve the purpose of “using synchronization”.

The apparently unassuming and dispensable state of COMPLETING things turns out to be a deliberate product of code optimisation.

Gotta say, Pops, this code:

Really is “SAO”, learn not to come, learn not to come.


In addition, I wrote a previous article on FutureTask that described another BUG:

The BUG Doug Lea wrote in the J.U.C. package has been found again.

It was mentioned in this article:


The Don said he “wrote it on purpose,” but was there a background “with the help of synchronization” behind it?

I don’t know, but I feel like I have a “dream linkage” feeling.

Well, this article is to share here.

Congratulations, you’ve learned another lesson that you’ll almost never use in your life.

See you later.

One last word

If you find something wrong, you can put it up in the comments section and I will correct it.

Thank you for reading, I insist on original, very welcome and thank you for your attention.