The author’s knowledge and understanding are limited, mistakes and deficiencies are welcome to point out.
Related articles
- An in-depth rearrangement prelude to the concurrent programming model
- An in-depth tutorial on sequential consistency in concurrent programming models
- An in-depth tutorial on the three concurrent features of the concurrent programming model
Classification of concurrent programming models
In concurrent programming, we need to address two key issues
- How do threads communicate with each other
Threads here refer to active entities that execute concurrently. Communication refers to the mechanism by which threads exchange information. In imperative programming, there are two communication mechanisms between threads: shared memory and message passing.
In the shared memory concurrency model, threads share the common state of the program and communicate implicitly with each other by writing to read the common state in memory.
In the concurrent model of messaging, there is no common state between threads, and threads must communicate explicitly by explicitly sending messages.
- How are threads synchronized
Synchronization is the mechanism that a program uses to control the relative order in which operations occur between different threads.
In the shared memory concurrency model, synchronization is done explicitly. Programmers must explicitly specify that a method or piece of code needs to be executed mutually exclusive between threads.
In the concurrent model of message delivery, synchronization is implicit because the message must be sent before the message is received.
Concurrency in Java is a shared memory model, where communication between Java threads is always implicit (not synchronous, but shared) and the entire communication process is completely transparent to the programmer. Java programmers writing multithreaded programs are likely to encounter all sorts of strange memory visibility problems if they don’t understand how implicit communication between threads works.
Summarize the concurrent programming model with a diagram:
Abstraction of the Java memory model
In Java, all instance fields, static fields, and array elements are stored in heap memory, which is shared between threads. (This article uses the term “shared variables” to refer to instance fields, static fields, and array elements.)
Local variables, method definition parameters (called Formal Method Parameters by the Java language specification), and exception Handler parameters are not shared between threads. They do not have memory visibility issues and are not affected by memory models.
Communication between Java threads is controlled by the Java Memory model (JMM for short in this article), which determines when a write to a shared variable by one thread is visible to another thread. From an abstract point of view, the JMM defines an abstract relationship between threads and main memory:
Shared variables between threads are stored in main memory. Each thread has a private local memory where it can read/write a copy of the shared variable. Local memory is an abstraction of the JMM and does not really exist. It covers caches, write buffers, registers, and other hardware and compiler optimizations.
The Java memory model is abstracted as follows:
Noun explanation:
- Read (read from main memory)
- Load (writes values read from main memory to working memory)
- Use (reading data from working memory to calculate)
- Assign (reassign the calculated value to working memory)
- Store (write working memory data to main storage)
- Write (Assigns store past variable values to variables in main memory)
From the above figure, thread A and thread B must go through the following two steps in order to communicate:
- First, thread A flusher the updated shared variables from local memory A to main memory.
- Thread B then goes into main memory to read the shared variables that thread A has updated previously. The following is a schematic illustration of these two steps:
As shown in the figure above, local memory A and B have copies of the shared variable M in main memory.
So let’s say that at the beginning, all three of these memory m values are 0. When thread A executes, it temporarily stores the updated m value (suppose 1) in its own local memory, A. When thread A and thread B need to communicate, thread A will first refresh the modified M value in its local memory to the main memory, and then the m value in the main memory becomes 1. Thread B then goes to main memory to read thread A’s updated m value, at which point thread B’s local memory m value is also changed to 1.
Taken as A whole, these two steps are essentially thread A sending messages to thread B, and this communication must go through main memory. The JMM provides Java programmers with memory visibility assurance by controlling the interaction between main memory and local memory for each thread.
reorder
To improve performance, compilers and processors often reorder instructions when executing programs. There are three types of reordering:
- Compiler optimized reordering
The compiler can rearrange the execution order of statements without changing the semantics of a single-threaded program.
- Instruction – level parallel reordering
Modern processors use instruction-level Parallelism (ILP) to overlap multiple instructions. If there is no data dependency, the processor can change the execution order of the machine instructions corresponding to the statement.
- Memory system reordering
Because the processor uses caching and read/write buffers, this makes the load and store operations appear to be out of order.
The sequence of instructions from the Java source code to the actual execution goes through one of the following three reorders:
The compiler optimization reordering described above is compiler reordering, instruction level parallel reordering and memory system reordering are processor reordering.
Any of these reorders can cause memory visibility problems in multithreaded programs. For compilers, the JMM’s compiler reordering rules disallow certain types of compiler reordering (not all compiler reordering is prohibited).
For processor reordering, the JMM’s processor reordering rules require the Java compiler to insert memory barriers (Intel calls them Memory fences) of a specific type when generating the sequence of instructions. Memory barrier instructions are used to disallow certain types of handler reordering (not all handler reordering should be disallowed).
The JMM is a language-level memory model that ensures consistent memory visibility for programmers across compilers and processor platforms by disallowing certain types of compiler reordering and processor reordering.
Processor reorder with memory barrier instructions
Modern processors use write buffers to temporarily hold data written to memory. The write buffer keeps the instruction pipeline running and avoids delays when the processor pauses to write data to memory.
At the same time, the footprint on the memory bus can be reduced by flushing the write buffer in a batch manner and merging multiple writes to the same memory address in the write buffer.
For all its benefits, the write buffer on each processor is visible only to the processor in which it resides. This feature has a significant impact on the order in which memory operations are executed: the order in which processor reads/writes to memory may not be the same as the order in which memory reads/writes actually occur! To illustrate, take a look at the following example:
If processors A and B perform memory accesses in parallel, in program order, they might end up with x = y = 0. The specific reasons are shown in the figure below:
Processor A and processor B can simultaneously write the shared variable to their own write buffer (A1, B1), then read another shared variable from memory (A2, B2), and finally flush the dirty data stored in their write cache to memory (A3, B3). When executed in this sequence, the program results in x = y = 0.
In terms of the order in which memory operations actually occur, write A1 is not actually executed until processor A does A3 to flush its own write cache. Although processor A performs memory operations in the order A1->A2, memory operations actually occur in the order A2->A1. At this point, processor A’s memory operations are reordered (processor B’s case is the same as processor A’s, which is not described here).
The point here is that because the write buffer is visible only to its own processor, it can cause the processor to perform memory operations in a different order than the actual memory operations. Because modern processors use write buffers, modern processors allow reordering of write-read operations.
To ensure memory visibility, the Java compiler inserts memory barrier instructions at the appropriate places to generate instruction sequences to prohibit reordering of a particular type of handler. The JMM classifies memory barrier instructions into the following four categories:
| Barrier type | Order sample | instructions |
|---|---|---|
| LoadLoad | Load1; LoadLoad; Load2 | Ensure that Load1 data is loaded after Load2 and Load2. |
| StoreStore | Store1; StoreStore; Store2 | Ensure that Store1 data is visible to other processors (flushed to memory) and stored before Store2 and all subsequent storage instructions. |
| LoadStore | Load1; LoadStore; Store2 | Ensure that Load1 data is loaded before Store2 and all subsequent storage instructions are flushed into memory. |
| StoreLoad | Store1; StoreLoad; Load2 | Ensure that Store1 data becomes visible to other processors (i.e., flush to memory) before loading Load2 and all subsequent load instructions. StoreLoad Barriers will require that all memory access instructions (store and load instructions) prior to the barrier be completed before any memory access instructions after the barrier are executed. |
The StoreLoad barrier type is an “all-in-one” barrier that simultaneously has the effect of the other three barriers. Most modern multiprocessors support this barrier (other types of barriers are not necessarily supported by all processors). Implementing this barrier can be expensive because the current processor usually flusher all the data in the write buffer to memory (buffer fully flush).
happens-before
Starting with JDK5, Java uses the new JSR-133 memory model (this article will focus on the JSR-133 memory model unless otherwise noted). Jsr-133 uses the concept of happens-before to illustrate memory visibility between operations.
In the JMM, if the result of one operation needs to be visible to another, there must be a happens-before relationship between the two operations. The two operations mentioned here can be within a thread or between different threads.
The happens-before rule, which is closely related to programmers, is as follows:
- Program sequence gauge
Every action in a thread happens-before any subsequent action in that thread.
- Monitor lock rule
The unlock of a monitor, happens-before is followed by the lock of the monitor.
- Volatile variable rule
A write to a volatile field is happens-before any subsequent read to the volatile field.
- transitivity
If A happens-before B, and B happens-before C, then A happens-before C.
Note that a happens-before relationship between two operations does not mean that the previous operation must be executed before the latter! Happens-before only requires that the previous action (the result of the execution) be visible to the latter, and that the first is visible to and ordered before the second.
The definition of happens-before is subtle, and we’ll explain why it is later.
The relationship between happens-before and JMM is shown below:
As shown in the figure above, a happens-before rule corresponds to one or more compiler and handler reordering rules. For Java programmers, the happens-before rule is straightforward and prevents them from having to learn complex reordering rules and their implementation in order to understand the memory visibility guarantees provided by the JMM.
conclusion
This article is mainly to clarify some concepts for everyone and do a good foundation for the analysis of subsequent articles. Mainly talked about the
- What are the concurrent programming models
- Java memory model
- Java instruction reordering
- JMM memory barrier
- Happens-before and THE JMM
This article, we focus on understanding these basic concepts, and the schematic diagram can be clarified.