Что такое happens before java

Handling Java Memory Consistency with happens-before relationship

If you are developing multi-threaded applications in Java, you need to have an understanding of how the shared variables are handled inside the memory of Java. One important factor is the happens-before relationship. In order to understand the happens-before relationship in Java, you need to be familiar with the concept of visibility in concurrent programming.

Visibility

If an action in one thread is visible to another thread, then the result of that action can be observed by the second thread.

To understand more on the above statement, let’s have a look at the architecture of a modern shared-memory multiprocessor.

Almost all of the computers today have multiple cores inside their processors, inside their processors, each capable of handling multiple threads of execution. For each of this core, there exist several levels of caches.

The visibility of writing operations on shared variables can cause problems during delays that occur when writing to the main memory due to caching in each core. This can result in another thread reading a stale value (not the last updated value) of the variable.

Let’s consider a situation where two threads perform a read an write operation to the same variable.

In the above example from the book “Effective Java by Joshua Bloch”, there is a background thread (backgroundThread) that will increment the value of “i” until the “stopRequested” boolean becomes true. After starting the thread by the main thread of the program, it sleeps for 1 second and makes the “stopRequested” to true.

What would be the outcome? Ideally, the program should run for 1 second and after the “stopRequested” has become true, the “backgroundThread” should end, terminating the whole program.

But if you run the above on a computer with multiple cores, you will observe that the program keeps on executing without getting terminated. The problem occurs with the write operation on the “stopRequested” variable. There is no guarantee that the change of the value in “stopRequested” variable (from the main thread) becoming visible to the “backgroundThread” that we created. As the write operation to the “stopRequested” variable to true from the main method is invisible to the “backgroundThread”, it will go into an infinite loop.

As the main thread and our “backgroundThread” is running on two different cores inside the processor, the “stopRequested” will be loaded into the cache of the core that executes the “backgroundThread”. The main thread will keep the updated value of the “stopRequested” value in a cache of a different core. Since now the “stopRequested” value resides in two different caches, the updated value may not be visible to the “backgroundThread”.

To avoid these type of memory inconsistencies, Java has introduced the happens-before relationship.

Happens-before relationship

Java defines a happens-before relationship as follows.

Two actions can be ordered by a happens-before relationship. If one action happens-before another, then the first is visible to and ordered before the second.

According to this, if there is a happens-before relationship between a write and read operation, the results of a write by one thread are guaranteed to be visible to a read by another thread. Therefore, we will be able to maintain the memory consistency if we are able to have the happens-before relationship between our actions.

Synchronizing

“Synchronized” keyword is widely used to achieve mutual exclusion among threads. This means that using synchronized keyword we have the ability to limit the access of a particular block of code or a method to only one thread. A single lock is passed around the threads that wish to access a particular synchronized block or a method. Each thread will have wait until the other thread finishes executing the synchronized block/method and release the lock.

However, synchronizing has another important use. It can also be used to achieve a happens-before relationship between code blocks or methods. If there are two synchronized blocks/methods having the same lock, there is a happens-before relationship between the actions inside the synchronization blocks/methods. This is due to the fact that an unlock on an object lock (exiting synchronized block/method) happens before every subsequent acquiring on the same object lock.

Let’s change our initial code to include synchronized methods for read and write operations of the “stopRequested” variable

Since now both read and write operations to the “stopRequested” variable is synchronized, a happens-before relationship has been established between the read/write operations of the “stopRequested” variable enabling the visibility to all the threads. It is important to note that both of the read and write operations need to be synchronized in order to achieve a happens-before relationship.

For situations similar to our example, using the synchronized keyword just to have visibility might not be the optimum solution. Synchronization has a performance impact due to the threads getting blocked while acquiring a lock. Hence, the synchronized keyword is more suitable when mutual exclusiveness (where only one thread is allowed to access a given resource at a time) is required.

For situations which require only visibility, Java has introduced a simple new keyword called “volatile”.

Volatile Fields

A write to a volatile field happens-before every subsequent read of that same field.

We can use the “volatile” keyword to make “stopRequested” variable a volatile field creating a happens-before relationship with the write and read operations for “stopRequested”.

However, it is important to keep note that the volatile keyword is not a replacement for synchronized blocks/methods. It will be useful only when achieving visibility for shared variables using a happens-before relationship. We will still have to use the synchronization when we need to achieve mutual exclusiveness between threads.

Consider the below example of a serial number generator

The above code is not thread safe due to lack of atomicity (not happening all read-modify-write operations at once) in the increment operator (++). Various threads can end up in different states (read or write) when executing the following line.

However, making the “nextSerialNumber” volatile will not achieve mutual exclusiveness during the increment operation (as volatile keyword can only be used to achieve visibility). A proper fix would be to make the generateSerialNumber() method synchronized.

Apart from the synchronization and volatility, Java defines several sets of rules for a happens-before relationship. You can find them in detail from the Oracle Docs.

Что такое happens before java

Happens-before is a concept, a phenomenon, or simply a set of rules that define the basis for reordering of instructions by a compiler or CPU. Happens-before is not any keyword or object in the Java language, it is simply a discipline put into place so that in a multi-threading environment the reordering of the surrounding instructions does not result in a code that produces incorrect output.

The definition might seem a bit overwhelming if this is the first time that you have come across this concept. To understand it let’s first learn where does the need for it originates from.

The Java Memory Model which is also referred to as the JMM model defines how the storage and exchange of data take place between threads and the hardware in a single or multithreaded environment.

Some points to keep in mind are as follows:

• Every CPU core has its own set of registers.
• Every CPU core can execute more than one thread at a time.
• Every CPU core has its own set of cache.
• A thread executes on a CPU core but its data is stored and accessed from RAM where the local variables lie inside the “Thread Stack” and the objects lie inside the “Heap.”

The Java Memory Model

The local variables and the references to objects inside a thread are stored in the Thread Stack, whereas the objects themselves are stored inside the Heap. The request for a variable by the thread running on the CPU follows this route RAM -> Cache -> CPU Registers. Similarly, when some processing happens on the variable and its value is updated, the changes go through CPU Register -> Cache -> RAM. Thus while working with multiple threads that share a variable, when one thread updates a shared variable’s value, the update has to be done to the register, then cache, and finally the RAM. And when another thread requires to read that shared variable, it reads the value present in the RAM which travels through the cache and registers. If you look at it at the basic level, if the read-write operations are delayed in such a way that the correct value is not stored in memory before another read-write is performed then it can result in memory consistency errors.

When working with multiple threads, this procedure of storage and retrieval may pose some problems such as:

: The condition where two threads sharing some variable, read and write on it but do not do so in a synchronized manner, resulting in inconsistent values.
• Update Visibility: where the updates made by one thread to a shared variable may not be visible to the other thread because the value has not yet been updated to the RAM.

These problems are solved by the use of synchronized block and volatile variables.

Instruction Reordering

During compilation or during processing, the compiler or the CPU might reorder the instructions to run them in parallel to increase throughput and performance. For example, we have 3 instructions:

The compiler cannot run 1 and 2 in parallel because 2 needs the output of 1, but 1 and 3 can run in parallel because they are independent of each other. So the compiler or the CPU can reorder these instructions in this way:

However, if reordering is performed in a multi-threaded application where threads share some variables then it may cost us the correctness of our program.

Now recall the two problems we talked about in the previous section, the race condition, and the updated visibility. Java provides us with some solutions to handle these types of situations. We are gonna learn what they are, and finally happens-before will be introduced in that section.

Volatile

For a field/variable declared as volatile,

• Every write to the field will be written/flushed directly to the main memory (i.e. bypassing the cache.)
• Every read of that field is read directly from the main memory.

This means that the shared variable count, whenever written-to or read-by a thread, it will always correspond to its most recently written value. This will prevent race condition because now the threads will always use the correct value of a shared variable. Also, the updates to the shared variable will also be visible to all the threads reading it, thus preventing the update visibility problem.

There are some more important points that the volatile dictates:

• At the time you write to a volatile variable, all the non-volatile variables that are visible to that thread will also get written/flushed to the main memory, i.e. their most recent values will be stored in the RAM along with the volatile variable.
• At the time you read a volatile variable, all the non-volatile variables that are visible to that thread will also get refreshed from the main memory, i.e. their most recent values will be assigned to them.

This is called the visibility guarantee of a volatile variable.

All of this looks and works fine, unless the CPU decides to reorder your instructions, resulting in incorrect execution of your application. Lets understand what we mean. Consider this piece of a program:

Implementation:

The below code in the illustration depicts as conveyed in simpler words is as follows:

• Inputs a fresh assignment submitted by a student
• And then collects that fresh assignment.

Our goal is that each time “only a freshly prepared assignment is collected. So proposing the sample code for the same as follows:

illustration:

• The method submitAssignment() is used by a thread Thread1, which accepts an assignment submitted by a student in the field assign, then increases the count of assignments submitted, and then flips the newAssignment variable to true.
• The method collectAssignment() is used by a thread Thread2, which waits until a new assignment has been submitted, when the value of newAssignment becomes true, it stores the submitted assignment into a variable ‘collectedAssgn’, increasing the count of assignments collected and flips the newAssignment to false, since no pending assignments are left. Finally, it returns the collected assignment.

Now, the volatile variable newAssignment acts as a shared variable between Thread1 and Thread2 which are running concurrently. And since all the other variables are visible to each of the threads along with newAssignment itself, the read-write operations will be done directly using the main memory.

If we focus on the submitAssignment() method, statements 1, 2, and 3 are independent of each other, since no statement makes use of the other statement, hence your CPU might think “Why not reorder them?” for whatever reasons that it may provide better performance. So let us assume the CPU reordered the three statements in this way:

Now think for a second, what our goal was, it was to collect a new fresh assignment each time, but now due to statement 3 updating the newAssignment to true even before the new assgn has been stored in the assgn, the while loop in the Thread2 will now be exited and there is a possibility that Thread2’s instructions execute before the remaining instructions of Thread1, resulting in an older value object of Assignment being submitted. Even though the values are being retrieved directly from the main memory, it is useless if the instructions are executed in the wrong order in this case.

This is the point where even though the visibility of the variables is guaranteed, the reordering of the instructions may lead to incorrect execution. And therefore, Java introduced the happens-before guarantee, with regards to the visibility of volatile variables.

Happens-Before in Volatile

Happens-Before states about reordering. It is as follows:

• When reordering any write to a variable that happened before a write to a volatile, will remain before the write to the volatile variable.
• When reordering any read of a volatile variable that is located before read of some non-volatile or volatile variable, is guaranteed to happen before any of the subsequent reads.

In context to the above example, the first point is relevant. Any write to a variable (Statements 1 and 2) that happened before a write to a volatile (Statement 3), will remain before the write to the volatile variable. This means that reordering of Statement 3 before 1 and 2 is prohibited. This in turn guarantees that newAssignment is only set to true once the new value of Assignment is assigned to ‘assgn’. This is called happens-before visibility guarantee of volatile. Also, statements 1 and 2 may be reordered among themselves as long as they are not being reordered after statement 3.

Synchronization Block

In the case of a synchronization block in Java:

• When a thread enters a synchronization block, the thread will refresh the values of all variables that are visible to the thread at that time from the main memory.
• When a thread exits a synchronization block, the values of all those variables will be written to the main memory.

Happens-Before in Synchronization Block

In case of synchronization block, happens before states that for reordering:

• Any write to a variable that happens before the exit of a synchronization block is guaranteed to remain before the exit of a synchronization block.
• Entrance to a synchronization block that happens before a read of a variable, is guaranteed to remain before any of the reads to the variables that follow the entrance of a synchronized block.

Now getting deeper to the roots of the happens-before relationship in java. Let us consider a scenario to understand it in better terms.

Illustration:

If one action ‘x’ is visible to and ordered before another action ‘y’, then there is a happens-before relationship between the two actions indicated by hb(x, y).

• If x and y are actions of the same thread and x comes before y in program order, then hb(x, y).
• There is a happens-before edge from the end of a constructor of an object to the start of a finalizer for that object.
• If an action x synchronizes with the following action y, then we also have hb(x, y).
• If hb(x, y) and hb(y, z), then hb(x, z).

Note: It is important to know that if we have hb(x, y) then it does not necessarily mean that x always occurs in the implementation before y, as long as the execution produces correct results, reordering of such actions is legal.

Some more rules laid out regarding synchronization state that are as follows:

# Java Memory Model

If this class is used is a single-threaded application, then the observable behavior will be exactly as you would expect. For instance:

As far as the "main" thread can tell, the statements in the main() method and the doIt() method will be executed in the order that they are written in the source code. This is a clear requirement of the Java Language Specification (JLS).

Now consider the same class used in a multi-threaded application.

What will this print?

In fact, according to the JLS it is not possible to predict that this will print:

• You will probably see a few lines of 0, 0 to start with.
• Then you probably see lines like N, N or N, N + 1 .
• You might see lines like N + 1, N .
• In theory, you might even see that the 0, 0 lines continue forever 1 .

1 — In practice the presence of the println statements is liable to cause some serendipitous synchronization and memory cache flushing. That is likely to hide some of the effects that would cause the above behavior.

So how can we explain these?

# Reordering of assignments

One possible explanation for unexpected results is that the JIT compiler has changed the order of the assignments in the doIt() method. The JLS requires that statements appear to execute in order from the perspective of the current thread. In this case, nothing in the code of the doIt() method can observe the effect of a (hypothetical) reordering of those two statement. This means that the JIT compiler would be permitted to do that.

Why would it do that?

On typical modern hardware, machine instructions are executed using a instruction pipeline which allows a sequence of instructions to be in different stages. Some phases of instruction execution take longer than others, and memory operations tend to take a longer time. A smart compiler can optimize the instruction throughput of the pipeline by ordering the instructions to maximize the amount of overlap. This may lead to executing parts of statements out of order. The JLS permits this provided that not affect the result of the computation from the perspective of the current thread.

# Effects of memory caches

A second possible explanation is effect of memory caching. In a classical computer architecture, each processor has a small set of registers, and a larger amount of memory. Access to registers is much faster than access to main memory. In modern architectures, there are memory caches that are slower than registers, but faster than main memory.

A compiler will exploit this by trying to keep copies of variables in registers, or in the memory caches. If a variable does not need to be flushed to main memory, or does not need to be read from memory, there are significant performance benefits in not doing this. In cases where the JLS does not require memory operations to be visible to another thread, the Java JIT compiler is likely to not add the "read barrier" and "write barrier" instructions that will force main memory reads and writes. Once again, the performance benefits of doing this are significant.

# Proper synchronization

So far, we have seen that the JLS allows the JIT compiler to generate code that makes single-threaded code faster by reordering or avoiding memory operations. But what happens when other threads can observe the state of the (shared) variables in main memory?

The answer is, that the other threads are liable to observe variable states which would appear to be impossible . based on the code order of the Java statements. The solution to this is to use appropriate synchronization. The three main approaches are:

• Using primitive mutexes and the synchronized constructs.
• Using volatile variables.
• Using higher level concurrency support; e.g. classes in the java.util.concurrent packages.

But even with this, it is important to understand where synchronization is needed, and what effects that you can rely on. This is where the Java Memory Model comes in.

# The Memory Model

The Java Memory Model is the section of the JLS that specifies the conditions under which one thread is guaranteed to see the effects of memory writes made by another thread. The Memory Model is specified with a fair degree of formal rigor, and (as a result) requires detailed and careful reading to understand. But the basic principle is that certain constructs create a "happens-before" relation between write of a variable by one thread, and a subsequent read of the same variable by another thread. If the "happens before" relation exists, the JIT compiler is obliged to generate code that will ensure that the read operation sees the value written by the write.

Armed with this, it is possible to reason about memory coherency in a Java program, and decide whether this will be predictable and consistent for all execution platforms.

# Happens-before relationships

(The following is a simplified version of what the Java Language Specification says. For a deeper understanding, you need to read the specification itself.)

Happens-before relationships are the part of the Memory Model that allow us to understand and reason about memory visibility. As the JLS says (JLS 17.4.5

"Two actions can be ordered by a happens-before relationship. If one action happens-before another, then the first is visible to and ordered before the second."

What does this mean?

# Actions

The actions that the above quote refers to are specified in JLS 17.4.2

(opens new window) . There are 5 kinds of action listed defined by the spec:

• Volatile read: Reading a volatile variable.
• Volatile write: Writing a volatile variable.
• Lock. Locking a monitor
• Unlock. Unlocking a monitor.
• The (synthetic) first and last actions of a thread.
• Actions that start a thread or detect that a thread has terminated.

External Actions. An action that has a result that depends on the environment in which the program.

Thread divergence actions. These model the behavior of certain kinds of infinite loop.

# Program Order and Synchronization Order

These two orderings ( JLS 17.4.3

(opens new window) ) govern the execution of statements in a Java

Program order describes the order of statement execution within a single thread.

Synchronization order describes the order of statement execution for two statements connected by a synchronization:

# Happens-before Order

(opens new window) ) is what determines whether a memory write is guaranteed to be visible to a subsequent memory read.

More specifically, a read of a variable v is guaranteed to observe a write to v if and only if write(v) happens-before read(v) AND there is no intervening write to v . If there are intervening writes, then the read(v) may see the results of them rather than the earlier one.

The rules that define the happens-before ordering are as follows:

In addition, various classes in the Java standard libraries are specified as defining happens-before relationships. You can interpret this as meaning that it happens somehow, without needing to know exactly how the guarantee is going to be met.

# Happens-before reasoning applied to some examples

We will present some examples to show how to apply happens-before reasoning to check that writes are visible to subsequent reads.

# Single-threaded code

As you would expect, writes are always visible to subsequent reads in a single-threaded program.

By Happens-Before Rule #1:

1. The write(a) action happens-before the write(b) action.
2. The write(b) action happens-before the read(a) action.
3. The read(a) action happens-before the read(a) action.

By Happens-Before Rule #4:

1. write(a) happens-before write(b) AND write(b) happens-before read(a) IMPLIES write(a) happens-before read(a) .
2. write(b) happens-before read(a) AND read(a) happens-before read(b) IMPLIES write(b) happens-before read(b) .

1. The write(a) happens-before read(a) relation means that the a + b statement is guaranteed to see the correct value of a .
2. The write(b) happens-before read(b) relation means that the a + b statement is guaranteed to see the correct value of b .

# Behavior of ‘volatile’ in an example with 2 threads

We will use the following example code to explore some implications of the Memory Model for `volatile.

First, consider the following sequence of statements involving 2 threads:

1. A single instance of VolatileExample is created; call it ve ,
2. ve.update(1, 2) is called in one thread, and
3. ve.observe() is called in another thread.

By Happens-Before Rule #1:

1. The write(a) action happens-before the volatile-write(a) action.
2. The volatile-read(a) action happens-before the read(b) action.

By Happens-Before Rule #2:

1. The volatile-write(a) action in the first thread happens-before the volatile-read(a) action in the second thread.

By Happens-Before Rule #4:

1. The write(b) action in the first thread happens-before the read(b) action in the second thread.

In other words, for this particular sequence, we are guaranteed that the 2nd thread will see the update to the non-volatile variable b made by the first thread. However, it is should also be clear that if the assignments in the update method were the other way around, or the observe() method read the variable b before a , then the happens-before chain would be broken. The chain would also be broken if volatile-read(a) in the second thread was not subsequent to the volatile-write(a) in the first thread.

When the chain is broken, there is no guarantee that observe() will see the correct value of b .

# Volatile with three threads

Suppose we to add a third thread into the previous example:

1. A single instance of VolatileExample is created; call it ve ,
2. Two threads call update :
3. ve.update(1, 2) is called in one thread,
4. ve.update(3, 4) is called in the second thread,

To analyse this completely, we need to consider all of the possible interleavings of the statements in thread one and thread two. Instead, we will consider just two of them.

Scenario #1 — suppose that update(1, 2) precedes update(3,4) we get this sequence:

In this case, it is easy to see that there is an unbroken happens-before chain from write(b, 3) to read(b) . Furthermore there is no intervening write to b . So, for this scenario, the third thread is guaranteed to see b as having value 3 .

Scenario #2 — suppose that update(1, 2) and update(3,4) overlap and the ations are interleaved as follows:

Now, while there is a happens-before chain from write(b, 3) to read(b) , there is an intervening write(b, 1) action performed by the other thread. This means we cannot be certain which value read(b) will see.

(Aside: This demonstrates that we cannot rely on volatile for ensuring visibility of non-volatile variables, except in very limited situations.)

# How to avoid needing to understand the Memory Model

The Memory Model is difficult to understand, and difficult to apply. It is useful if you need to reason about the correctness of multi-threaded code, but you do not want to have to do this reasoning for every multi-threaded application that you write.

If you adopt the following principals when writing concurrent code in Java, you can largely avoid the need to resort to happens-before reasoning.

The general principle is to try to use Java’s built-in concurrency libraries rather than "rolling your own" concurrency. You can rely on them working, if you use them properly.

1 — Not all objects need to be thread safe. For example, if an object or objects is thread-confined (i.e. it is only accessible to one thread), then its thread-safety is not relevant.

# Remarks

The Java Memory Model is the section of the JLS that specifies the conditions under which one thread is guaranteed to see the effects of memory writes made by another thread. The relevant section in recent editions is "JLS 17.4 Memory Model" (in Java 8

There was a major overhaul of the Java Memory Model in Java 5 which (among other things) changed the way that volatile worked. Since then, the memory model been essentially unchanged.

Управление потоками. Ключевое слово volatile и метод yield()

Мы рассмотрели уже много методов класса Thread , но есть один важный, который будет для тебя новым. Это метод yield(). С английского переводится как «уступать». И это ровно то, что метод делает! Когда мы вызываем метод yield у потока, он фактически говорит другим потокам: «Так, ребята, я никуда особо не тороплюсь, так что если кому-то из вас важно получить время процессора — берите, мне не срочно». Вот простой пример того, как это работает: Мы последовательно создаем и запускаем три потока — Thread-0 , Thread-1 и Thread-2 . Thread-0 запускается первым и сразу уступает место другим. После него запускается Thread-1 , и тоже уступает. После — запускается Thread-2 , который тоже уступает. Больше потоков у нас нет, и после того, как Thread-2 последним уступил свое место, планировщик потоков смотрит: «Так, новых потоков больше нет, кто у нас там в очереди? Кто уступал свое место последним, перед Thread-2 ? Кажется, это был Thread-1 ? Окей, значит пусть он и выполняется». Thread-1 выполняет свою работу до конца, после чего планировщик потоков продолжает координацию: «Окей, Thread-1 выполнился. Есть у нас кто-то еще в очереди?». В очереди есть Thread-0: он уступал свое место сразу до Thread-1. Теперь дело дошло до него, и он выполняется до конца. После чего планировщик заканчивает координацию потоков: «Ладно, Thread-2, ты уступил место другим потокам, они все уже отработали. Ты уступал место последним, так что теперь твоя очередь». После этого отрабатывает до конца поток Thread-2. Вывод в консоль будет выглядеть так: Thread-0 уступает свое место другим Thread-1 уступает свое место другим Thread-2 уступает свое место другим Thread-1 закончил выполнение. Thread-0 закончил выполнение. Thread-2 закончил выполнение. Планировщик потоков, конечно, может запустить потоки в другом порядке (например, 2-1-0 вместо 0-1-2), но сам принцип неизменный.