Java SE >Java SE Specifications >Java Language Specification
Table of Contents
While most of the discussion in the preceding chapters is concerned only with the behavior of code as executed a single statement or expression at a time, that is, by a singlethread, the Java Virtual Machine can support many threads of execution at once. These threads independently execute code that operates on values and objects residing in a shared main memory. Threads may be supported by having many hardware processors, by time-slicing a single hardware processor, or by time-slicing many hardware processors.
Threads are represented by theThread class. The only way for a user to create a thread is to create an object of this class; each thread is associated with such an object. A thread will start when thestart() method is invoked on the correspondingThread object.
The behavior of threads, particularly when not correctly synchronized, can be confusing and counterintuitive. This chapter describes the semantics of multithreaded programs; it includes rules for which values may be seen by a read of shared memory that is updated by multiple threads. As the specification is similar to thememory models for different hardware architectures, these semantics are known as theJava programming language memory model. When no confusion can arise, we will simply refer to these rules as "the memory model".
These semantics do not prescribe how a multithreaded program should be executed. Rather, they describe the behaviors that multithreaded programs are allowed to exhibit. Any execution strategy that generates only allowed behaviors is an acceptable execution strategy.
The Java programming language provides multiple mechanisms for communicating between threads. The most basic of these methods issynchronization, which is implemented usingmonitors. Each object in Java is associated with a monitor, which a thread canlock orunlock. Only one thread at a time may hold a lock on a monitor. Any other threads attempting to lock that monitor are blocked until they can obtain a lock on that monitor. A threadt may lock a particular monitor multiple times; each unlock reverses the effect of one lock operation.
Thesynchronized statement (§14.19) computes a reference to an object; it then attempts to perform a lock action on that object's monitor and does not proceed further until the lock action has successfully completed. After the lock action has been performed, the body of thesynchronized statement is executed. If execution of the body is ever completed, either normally or abruptly, an unlock action is automatically performed on that same monitor.
Asynchronized method (§8.4.3.6) automatically performs a lock action when it is invoked; its body is not executed until the lock action has successfully completed. If the method is an instance method, it locks the monitor associated with the instance for which it was invoked (that is, the object that will be known asthis during execution of the body of the method). If the method isstatic, it locks the monitor associated with theClass object that represents the class in which the method is defined. If execution of the method's body is ever completed, either normally or abruptly, an unlock action is automatically performed on that same monitor.
The Java programming language neither prevents nor requires detection of deadlock conditions. Programs where threads hold (directly or indirectly) locks on multiple objects should use conventional techniques for deadlock avoidance, creating higher-level locking primitives that do not deadlock, if necessary.
Other mechanisms, such as reads and writes ofvolatile variables and the use of classes in thejava.util.concurrent package, provide alternative ways of synchronization.
Every object, in addition to having an associated monitor, has an associatedwait set. A wait set is a set of threads.
When an object is first created, its wait set is empty. Elementary actions that add threads to and remove threads from wait sets are atomic. Wait sets are manipulated solely through the methodsObject.wait,Object.notify, andObject.notifyAll.
Wait set manipulations can also be affected by the interruption status of a thread, and by theThread class's methods dealing with interruption. Additionally, theThread class's methods for sleeping and joining other threads have properties derived from those of wait and notification actions.
Wait actions occur upon invocation ofwait(), or the timed formswait(long millisecs) andwait(long millisecs, int nanosecs).
A call ofwait(long millisecs) with a parameter of zero, or a call ofwait(long millisecs, int nanosecs) with two zero parameters, is equivalent to an invocation ofwait().
A threadreturns normally from a wait if it returns without throwing anInterruptedException.
Let threadt be the thread executing thewait method on objectm, and letn be the number of lock actions byt onm that have not been matched by unlock actions. One of the following actions occurs:
Ifn is zero (i.e., threadt does not already possess the lock for targetm), then anIllegalMonitorStateException is thrown.
If this is a timed wait and thenanosecs argument is not in the range of0-999999 or themillisecs argument is negative, then anIllegalArgumentException is thrown.
If threadt is interrupted, then anInterruptedException is thrown andt's interruption status is set to false.
Otherwise, the following sequence occurs:
Threadt is added to the wait set of objectm, and performsn unlock actions onm.
Threadt does not execute any further instructions until it has been removed fromm's wait set. The thread may be removed from the wait set due to any one of the following actions, and will resume sometime afterward:
Anotify action being performed onm in whicht is selected for removal from the wait set.
If this is a timed wait, an internal action removingt fromm's wait set that occurs after at leastmillisecs milliseconds plusnanosecs nanoseconds elapse since the beginning of this wait action.
An internal action by the implementation. Implementations are permitted, although not encouraged, to perform "spurious wake-ups", that is, to remove threads from wait sets and thus enable resumption without explicit instructions to do so.
Notice that this provision necessitates the Java coding practice of usingwait only within loops that terminate only when some logical condition that the thread is waiting for holds.
Each thread must determine an order over the events that could cause it to be removed from a wait set. That order does not have to be consistent with other orderings, but the thread must behave as though those events occurred in that order.
For example, if a threadt is in the wait set form, and then both an interrupt oft and a notification ofm occur, there must be an order over these events. If the interrupt is deemed to have occurred first, thent will eventually return fromwait by throwingInterruptedException, and some other thread in the wait set form (if any exist at the time of the notification) must receive the notification. If the notification is deemed to have occurred first, thent will eventually return normally fromwait with an interrupt still pending.
If threadt was removed fromm's wait set in step 2 due to an interrupt, thent's interruption status is set to false and thewait method throwsInterruptedException.
Notification actions occur upon invocation of methodsnotify andnotifyAll.
Let threadt be the thread executing either of these methods on objectm, and letn be the number of lock actions byt onm that have not been matched by unlock actions. One of the following actions occurs:
Ifn is zero, then anIllegalMonitorStateException is thrown.
This is the case where threadt does not already possess the lock for targetm.
Ifn is greater than zero and this is anotify action, then ifm's wait set is not empty, a threadu that is a member ofm's current wait set is selected and removed from the wait set.
There is no guarantee about which thread in the wait set is selected. This removal from the wait set enablesu's resumption in a wait action. Notice, however, thatu's lock actions upon resumption cannot succeed until some time aftert fully unlocks the monitor form.
Ifn is greater than zero and this is anotifyAll action, then all threads are removed fromm's wait set, and thus resume.
Notice, however, that only one of them at a time will lock the monitor required during the resumption of wait.
Interruption actions occur upon invocation ofThread.interrupt, as well as methods defined to invoke it in turn, such asThreadGroup.interrupt.
Lett be the thread invokingu.interrupt, for some threadu, wheret andu may be the same. This action causesu's interruption status to be set to true.
Additionally, if there exists some objectm whose wait set containsu, thenu is removed fromm's wait set. This enablesu to resume in a wait action, in which case this wait will, after re-lockingm's monitor, throwInterruptedException.
Invocations ofThread.isInterrupted can determine a thread's interruption status. Thestatic methodThread.interrupted may be invoked by a thread to observe and clear its own interruption status.
The above specifications allow us to determine several properties having to do with the interaction of waits, notification, and interruption.
If a thread is both notified and interrupted while waiting, it may either:
The thread may not reset its interrupt status and return normally from the call towait.
Similarly, notifications cannot be lost due to interrupts. Assume that a sets of threads is in the wait set of an objectm, and another thread performs anotify onm. Then either:
Note that if a thread is both interrupted and woken vianotify, and that thread returns fromwait by throwing anInterruptedException, then some other thread in the wait set must be notified.
Thread.sleep causes the currently executing thread to sleep (temporarily cease execution) for the specified duration, subject to the precision and accuracy of system timers and schedulers. The thread does not lose ownership of any monitors, and resumption of execution will depend on scheduling and the availability of processors on which to execute the thread.
It is important to note that neitherThread.sleep norThread.yield have any synchronization semantics. In particular, the compiler does not have to flush writes cached in registers out to shared memory before a call toThread.sleep orThread.yield, nor does the compiler have to reload values cached in registers after a call toThread.sleep orThread.yield.
For example, in the following (broken) code fragment, assume thatthis.done is a non-volatile boolean field:
while (!this.done) Thread.sleep(1000);
The compiler is free to read the fieldthis.done just once, and reuse the cached value in each execution of the loop. This would mean that the loop would never terminate, even if another thread changed the value ofthis.done.
Amemory model describes, given a program and an execution trace of that program, whether the execution trace is a legal execution of the program. The Java programming language memory model works by examining each read in an execution trace and checking that the write observed by that read is valid according to certain rules.
The memory model describes possible behaviors of a program. An implementation is free to produce any code it likes, as long as all resulting executions of a program produce a result that can be predicted by the memory model.
This provides a great deal of freedom for the implementor to perform a myriad of code transformations, including the reordering of actions and removal of unnecessary synchronization.
Example 17.4-1. Incorrectly Synchronized Programs May Exhibit Surprising Behavior
The semantics of the Java programming language allow compilers and microprocessors to perform optimizations that can interact with incorrectly synchronized code in ways that can produce behaviors that seem paradoxical. Here are some examples of how incorrectly synchronized programs may exhibit surprising behaviors.
Consider, for example, the example program traces shown inTable 17.4-A. This program uses local variablesr1 andr2 and shared variablesA andB. Initially,A == B == 0.
Table 17.4-A. Surprising results caused by statement reordering - original code
| Thread 1 | Thread 2 |
|---|---|
1:r2 = A; | 3:r1 = B; |
2:B = 1; | 4:A = 2; |
It may appear that the resultr2 == 2 andr1 == 1 is impossible. Intuitively, either instruction 1 or instruction 3 should come first in an execution. If instruction 1 comes first, it should not be able to see the write at instruction 4. If instruction 3 comes first, it should not be able to see the write at instruction 2.
If some execution exhibited this behavior, then we would know that instruction 4 came before instruction 1, which came before instruction 2, which came before instruction 3, which came before instruction 4. This is, on the face of it, absurd.
However, compilers are allowed to reorder the instructions in either thread, when this does not affect the execution of that thread in isolation. If instruction 1 is reordered with instruction 2, as shown in the trace inTable 17.4-B, then it is easy to see how the resultr2 == 2 andr1 == 1 might occur.
Table 17.4-B. Surprising results caused by statement reordering - valid compiler transformation
| Thread 1 | Thread 2 |
|---|---|
B = 1; | r1 = B; |
r2 = A; | A = 2; |
To some programmers, this behavior may seem "broken". However, it should be noted that this code is improperly synchronized:
there is a write in one thread,
a read of the same variable by another thread,
and the write and read are not ordered by synchronization.
This situation is an example of adata race (§17.4.5). When code contains a data race, counterintuitive results are often possible.
Several mechanisms can produce the reordering inTable 17.4-B. A Just-In-Time compiler in a Java Virtual Machine implementation may rearrange code, or the processor. In addition, the memory hierarchy of the architecture on which a Java Virtual Machine implementation is run may make it appear as if code is being reordered. In this chapter, we shall refer to anything that can reorder code as acompiler.
Another example of surprising results can be seen inTable 17.4-C. Initially,p == q andp.x == 0. This program is also incorrectly synchronized; it writes to shared memory without enforcing any ordering between those writes.
Table 17.4-C. Surprising results caused by forward substitution
| Thread 1 | Thread 2 |
|---|---|
r1 = p; | r6 = p; |
r2 = r1.x; | r6.x = 3; |
r3 = q; | |
r4 = r3.x; | |
r5 = r1.x; |
One common compiler optimization involves having the value read forr2 reused forr5: they are both reads ofr1.x with no intervening write. This situation is shown inTable 17.4-D.
Table 17.4-D. Surprising results caused by forward substitution
| Thread 1 | Thread 2 |
|---|---|
r1 = p; | r6 = p; |
r2 = r1.x; | r6.x = 3; |
r3 = q; | |
r4 = r3.x; | |
r5 = r2; |
Now consider the case where the assignment tor6.x in Thread 2 happens between the first read ofr1.x and the read ofr3.x in Thread 1. If the compiler decides to reuse the value ofr2 for ther5, thenr2 andr5 will have the value0, andr4 will have the value3. From the perspective of the programmer, the value stored atp.x has changed from0 to3 and then changed back.
The memory model determines what values can be read at every point in the program. The actions of each thread in isolation must behave as governed by the semantics of that thread, with the exception that the values seen by each read are determined by the memory model. When we refer to this, we say that the program obeysintra-thread semantics. Intra-thread semantics are the semantics for single-threaded programs, and allow the complete prediction of the behavior of a thread based on the values seen by read actions within the thread. To determine if the actions of threadt in an execution are legal, we simply evaluate the implementation of threadt as it would be performed in a single-threaded context, as defined in the rest of this specification.
Each time the evaluation of threadt generates an inter-thread action, it must match the inter-thread actiona oft that comes next in program order. Ifa is a read, then further evaluation oft uses the value seen bya as determined by the memory model.
This section provides the specification of the Java programming language memory model except for issues dealing withfinal fields, which are described in§17.5.
The memory model specified herein is not fundamentally based in the object-oriented nature of the Java programming language. For conciseness and simplicity in our examples, we often exhibit code fragments without class or method definitions, or explicit dereferencing. Most examples consist of two or more threads containing statements with access to local variables, shared global variables, or instance fields of an object. We typically use variables names such asr1 orr2 to indicate variables local to a method or thread. Such variables are not accessible by other threads.
Memory that can be shared between threads is calledshared memory orheap memory.
All instance fields,static fields, and array elements are stored in heap memory. In this chapter, we use the termvariable to refer to both fields and array elements.
Local variables (§14.4), formal method parameters (§8.4.1), and exception handler parameters (§14.20) are never shared between threads and are unaffected by the memory model.
Two accesses to (reads of or writes to) the same variable are said to beconflicting if at least one of the accesses is a write.
Aninter-thread action is an action performed by one thread that can be detected or directly influenced by another thread. There are several kinds of inter-thread action that a program may perform:
Synchronization actions, which are:
Actions that start a thread or detect that a thread has terminated (§17.4.4).
External Actions. An external action is an action that may be observable outside of an execution, and has a result based on an environment external to the execution.
Thread divergence actions (§17.4.9). A thread divergence action is only performed by a thread that is in an infinite loop in which no memory, synchronization, or external actions are performed. If a thread performs a thread divergence action, it will be followed by an infinite number of thread divergence actions.
Thread divergence actions are introduced to model how a thread may cause all other threads to stall and fail to make progress.
This specification is only concerned with inter-thread actions. We do not need to concern ourselves with intra-thread actions (e.g., adding two local variables and storing the result in a third local variable). As previously mentioned, all threads need to obey the correct intra-thread semantics for Java programs. We will usually refer to inter-thread actions more succinctly as simplyactions.
An actiona is described by a tuple <t,k,v,u >, comprising:
v - the variable or monitor involved in the action.
For lock actions,v is the monitor being locked; for unlock actions,v is the monitor being unlocked.
If the action is a (volatile or non-volatile) read,v is the variable being read.
If the action is a (volatile or non-volatile) write,v is the variable being written.
An external action tuple contains an additional component, which contains the results of the external action as perceived by the thread performing the action. This may be information as to the success or failure of the action, and any values read by the action.
Parameters to the external action (e.g., which bytes are written to which socket) are not part of the external action tuple. These parameters are set up by other actions within the thread and can be determined by examining the intra-thread semantics. They are not explicitly discussed in the memory model.
In non-terminating executions, not all external actions are observable. Non-terminating executions and observable actions are discussed in§17.4.9.
Among all the inter-thread actions performed by each threadt, theprogram order oft is a total order that reflects the order in which these actions would be performed according to the intra-thread semantics oft.
A set of actions issequentially consistent if all actions occur in a total order (the execution order) that is consistent with program order, and furthermore, each readr of a variablev sees the value written by the writew tov such that:
Sequential consistency is a very strong guarantee that is made about visibility and ordering in an execution of a program. Within a sequentially consistent execution, there is a total order over all individual actions (such as reads and writes) which is consistent with the order of the program, and each individual action is atomic and is immediately visible to every thread.
If a program has no data races, then all executions of the program will appear to be sequentially consistent.
Sequential consistency and/or freedom from data races still allows errors arising from groups of operations that need to be perceived atomically and are not.
If we were to use sequential consistency as our memory model, many of the compiler and processor optimizations that we have discussed would be illegal. For example, in the trace inTable 17.4-C, as soon as the write of3 top.x occurred, subsequent reads of that location would be required to see that value.
Every execution has asynchronization order. A synchronization order is a total order over all of the synchronization actions of an execution. For each threadt, the synchronization order of the synchronization actions (§17.4.2) int is consistent with the program order (§17.4.3) oft.
Synchronization actions induce thesynchronized-with relation on actions, defined as follows:
An unlock action on monitormsynchronizes-with all subsequent lock actions onm (where "subsequent" is defined according to the synchronization order).
A write to a volatile variablev (§8.3.1.4)synchronizes-with all subsequent reads ofv by any thread (where "subsequent" is defined according to the synchronization order).
An action that starts a threadsynchronizes-with the first action in the thread it starts.
The write of the default value (zero,false, ornull) to each variablesynchronizes-with the first action in every thread.
Although it may seem a little strange to write a default value to a variable before the object containing the variable is allocated, conceptually every object is created at the start of the program with its default initialized values.
The final action in a threadT1synchronizes-with any action in another threadT2 that detects thatT1 has terminated.
T2 may accomplish this by callingT1.isAlive() orT1.join().
If threadT1 interrupts threadT2, the interrupt byT1synchronizes-with any point where any other thread (includingT2) determines thatT2 has been interrupted (by having anInterruptedException thrown or by invokingThread.interrupted orThread.isInterrupted).
The source of asynchronizes-with edge is called arelease, and the destination is called anacquire.
Two actions can be ordered by ahappens-before relationship. If one actionhappens-before another, then the first is visible to and ordered before the second.
If we have two actionsx andy, we writehb(x, y) to indicate thatx happens-before y.
Ifx andy are actions of the same thread andx comes beforey in program order, thenhb(x, y).
There is ahappens-before edge from the end of a constructor of an object to the start of a finalizer (§12.6) for that object.
If an actionxsynchronizes-with a following actiony, then we also havehb(x, y).
Thewait methods of classObject (§17.2.1) have lock and unlock actions associated with them; theirhappens-before relationships are defined by these associated actions.
It should be noted that the presence of ahappens-before relationship between two actions does not necessarily imply that they have to take place in that order in an implementation. If the reordering produces results consistent with a legal execution, it is not illegal.
For example, the write of a default value to every field of an object constructed by a thread need not happen before the beginning of that thread, as long as no read ever observes that fact.
More specifically, if two actions share ahappens-before relationship, they do not necessarily have to appear to have happened in that order to any code with which they do not share ahappens-before relationship. Writes in one thread that are in a data race with reads in another thread may, for example, appear to occur out of order to those reads.
Thehappens-before relation defines when data races take place.
A set of synchronization edges,S, issufficient if it is the minimal set such that the transitive closure ofS with the program order determines all of thehappens-before edges in the execution. This set is unique.
It follows from the above definitions that:
An unlock on a monitorhappens-before every subsequent lock on that monitor.
A write to avolatile field (§8.3.1.4)happens-before every subsequent read of that field.
A call tostart() on a threadhappens-before any actions in the started thread.
All actions in a threadhappen-before any other thread successfully returns from ajoin() on that thread.
The default initialization of any objecthappens-before any other actions (other than default-writes) of a program.
When a program contains two conflicting accesses (§17.4.1) that are not ordered by a happens-before relationship, it is said to contain adata race.
The semantics of operations other than inter-thread actions, such as reads of array lengths (§10.7), executions of checked casts (§5.5,§15.16), and invocations of virtual methods (§15.12), are not directly affected by data races.
Therefore, a data race cannot cause incorrect behavior such as returning the wrong length for an array.
A program iscorrectly synchronized if and only if all sequentially consistent executions are free of data races.
If a program is correctly synchronized, then all executions of the program will appear to be sequentially consistent (§17.4.3).
This is an extremely strong guarantee for programmers. Programmers do not need to reason about reorderings to determine that their code contains data races. Therefore they do not need to reason about reorderings when determining whether their code is correctly synchronized. Once the determination that the code is correctly synchronized is made, the programmer does not need to worry that reorderings will affect his or her code.
A program must be correctly synchronized to avoid the kinds of counterintuitive behaviors that can be observed when code is reordered. The use of correct synchronization does not ensure that the overall behavior of a program is correct. However, its use does allow a programmer to reason about the possible behaviors of a program in a simple way; the behavior of a correctly synchronized program is much less dependent on possible reorderings. Without correct synchronization, very strange, confusing and counterintuitive behaviors are possible.
We say that a readr of a variablev is allowed to observe a writew tov if, in thehappens-before partial order of the execution trace:
Informally, a readr is allowed to see the result of a writew if there is nohappens-before ordering to prevent that read.
A set of actionsA ishappens-before consistent if for all readsr inA, whereW(r) is the write action seen byr, it is not the case that eitherhb(r, W(r)) or that there exists a writew inA such thatw.v =r.v andhb(W(r), w) andhb(w, r).
In ahappens-before consistent set of actions, each read sees a write that it is allowed to see by thehappens-before ordering.
Example 17.4.5-1. Happens-before Consistency
For the trace inTable 17.4.5-A, initiallyA == B == 0. The trace can observer2 == 0 andr1 == 0 and still behappens-before consistent, since there are execution orders that allow each read to see the appropriate write.
Table 17.4.5-A. Behavior allowed by happens-before consistency, but not sequential consistency.
| Thread 1 | Thread 2 |
|---|---|
B = 1; | A = 2; |
r2 = A; | r1 = B; |
Since there is no synchronization, each read can see either the write of the initial value or the write by the other thread. An execution order that displays this behavior is:
1: B = 1;3: A = 2;2: r2 = A; // sees initial write of 04: r1 = B; // sees initial write of 0
Another execution order that is happens-before consistent is:
1: r2 = A; // sees write of A = 23: r1 = B; // sees write of B = 12: B = 1;4: A = 2;
In this execution, the reads see writes that occur later in the execution order. This may seem counterintuitive, but is allowed byhappens-before consistency. Allowing reads to see later writes can sometimes produce unacceptable behaviors.
An executionE is described by a tuple <P, A, po, so, W, V, sw, hb >, comprising:
po - program order, which for each threadt, is a total order over all actions performed byt inA
so - synchronization order, which is a total order over all synchronization actions inA
W - a write-seen function, which for each readr inA, givesW(r), the write action seen byr inE.
V - a value-written function, which for each writew inA, givesV(w), the value written byw inE.
sw - synchronizes-with, a partial order over synchronization actions
Note that the synchronizes-with and happens-before elements are uniquely determined by the other components of an execution and the rules for well-formed executions (§17.4.7).
An execution ishappens-before consistent if its set of actions ishappens-before consistent (§17.4.5).
We only consider well-formed executions. An executionE = <P, A, po, so, W, V, sw, hb > is well formed if the following are true:
Each read sees a write to the same variable in the execution.
All reads and writes of volatile variables are volatile actions. For all readsr inA, we haveW(r) inA andW(r).v =r.v. The variabler.v is volatile if and only ifr is a volatile read, and the variablew.v is volatile if and only ifw is a volatile write.
The happens-before order is a partial order.
The happens-before order is given by the transitive closure of synchronizes-with edges and program order. It must be a valid partial order: reflexive, transitive and antisymmetric.
The execution obeys intra-thread consistency.
For each threadt, the actions performed byt inA are the same as would be generated by that thread in program-order in isolation, with each writew writing the valueV(w), given that each readr sees the valueV(W(r)). Values seen by each read are determined by the memory model. The program order given must reflect the program order in which the actions would be performed according to the intra-thread semantics ofP.
The execution ishappens-before consistent (§17.4.6).
The execution obeys synchronization-order consistency.
For all volatile readsr inA, it is not the case that eitherso(r, W(r)) or that there exists a writew inA such thatw.v =r.v andso(W(r), w) andso(w, r).
We usef|d to denote the function given by restricting the domain off tod. For allx ind,f|d(x) =f(x), and for allx not ind,f|d(x) is undefined.
We usep|d to represent the restriction of the partial orderp to the elements ind. For allx,y ind,p(x,y) if and only ifp|d(x,y). If eitherx ory are not ind, then it is not the case thatp|d(x,y).
A well-formed executionE = <P, A, po, so, W, V, sw, hb > is validated bycommitting actions fromA. If all of the actions inA can be committed, then the execution satisfies the causality requirements of the Java programming language memory model.
Starting with the empty set asC0, we perform a sequence of steps where we take actions from the set of actionsA and add them to a set of committed actionsCi to get a new set of committed actionsCi+1. To demonstrate that this is reasonable, for eachCi we need to demonstrate an executionE containingCi that meets certain conditions.
Formally, an executionE satisfies the causality requirements of the Java programming language memory model if and only if there exist:
Sets of actionsC0,C1, ... such that:
IfA is finite, then the sequenceC0,C1, ... will be finite, ending in a setCn =A.
IfA is infinite, then the sequenceC0,C1, ... may be infinite, and it must be the case that the union of all elements of this infinite sequence is equal toA.
Well-formed executionsE1, ..., whereEi = <P, Ai, poi, soi, Wi, Vi, swi, hbi >.
Given these sets of actionsC0, ... and executionsE1, ... , every action inCi must be one of the actions inEi. All actions inCi must share the same relative happens-before order and synchronization order in bothEi andE. Formally:
The values written by the writes inCi must be the same in bothEi andE. Only the reads inCi-1 need to see the same writes inEi as inE. Formally:
All reads inEi that are not inCi-1 must see writes that happen-before them. Each readr inCi -Ci-1 must see writes inCi-1 in bothEi andE, but may see a different write inEi from the one it sees inE. Formally:
Given a set of sufficient synchronizes-with edges forEi, if there is a release-acquire pair that happens-before (§17.4.5) an action you are committing, then that pair must be present in allEj, wherej≥i. Formally:
Letsswi be theswi edges that are also in the transitive reduction ofhbi but not inpo. We callsswi thesufficient synchronizes-with edges forEi. Ifsswi(x, y) andhbi(y, z) andz inCi, thenswj(x, y) for allj≥i.
If an actiony is committed, all external actions that happen-beforey are also committed.
Ify is inCi,x is an external action andhbi(x, y), thenx inCi.
Example 17.4.8-1. Happens-before Consistency Is Not Sufficient
Happens-before consistency is a necessary, but not sufficient, set of constraints. Merely enforcing happens-before consistency would allow for unacceptable behaviors - those that violate the requirements we have established for programs. For example, happens-before consistency allows values to appear "out of thin air". This can be seen by a detailed examination of the trace inTable 17.4.8-A.
Table 17.4.8-A. Happens-before consistency is not sufficient
| Thread 1 | Thread 2 |
|---|---|
r1 = x; | r2 = y; |
if (r1 != 0) y = 1; | if (r2 != 0) x = 1; |
The code shown inTable 17.4.8-A is correctly synchronized. This may seem surprising, since it does not perform any synchronization actions. Remember, however, that a program is correctly synchronized if, when it is executed in a sequentially consistent manner, there are no data races. If this code is executed in a sequentially consistent way, each action will occur in program order, and neither of the writes will occur. Since no writes occur, there can be no data races: the program is correctly synchronized.
Since this program is correctly synchronized, the only behaviors we can allow are sequentially consistent behaviors. However, there is an execution of this program that is happens-before consistent, but not sequentially consistent:
r1 = x; // sees write of x = 1y = 1;r2 = y; // sees write of y = 1x = 1;
This result is happens-before consistent: there is no happens-before relationship that prevents it from occurring. However, it is clearly not acceptable: there is no sequentially consistent execution that would result in this behavior. The fact that we allow a read to see a write that comes later in the execution order can sometimes thus result in unacceptable behaviors.
Although allowing reads to see writes that come later in the execution order is sometimes undesirable, it is also sometimes necessary. As we saw above, the trace inTable 17.4.5-A requires some reads to see writes that occur later in the execution order. Since the reads come first in each thread, the very first action in the execution order must be a read. If that read cannot see a write that occurs later, then it cannot see any value other than the initial value for the variable it reads. This is clearly not reflective of all behaviors.
We refer to the issue of when reads can see future writes ascausality, because of issues that arise in cases like the one found inTable 17.4.8-A. In that case, the reads cause the writes to occur, and the writes cause the reads to occur. There is no "first cause" for the actions. Our memory model therefore needs a consistent way of determining which reads can see writes early.
Examples such as the one found inTable 17.4.8-A demonstrate that the specification must be careful when stating whether a read can see a write that occurs later in the execution (bearing in mind that if a read sees a write that occurs later in the execution, it represents the fact that the write is actually performed early).
The memory model takes as input a given execution, and a program, and determines whether that execution is a legal execution of the program. It does this by gradually building a set of "committed" actions that reflect which actions were executed by the program. Usually, the next action to be committed will reflect the next action that can be performed by a sequentially consistent execution. However, to reflect reads that need to see later writes, we allow some actions to be committed earlier than other actions that happen-before them.
Obviously, some actions may be committed early and some may not. If, for example, one of the writes inTable 17.4.8-A were committed before the read of that variable, the read could see the write, and the "out-of-thin-air" result could occur. Informally, we allow an action to be committed early if we know that the action can occur without assuming some data race occurs. InTable 17.4.8-A, we cannot perform either write early, because the writes cannot occur unless the reads see the result of a data race.
For programs that always terminate in some bounded finite period of time, their behavior can be understood (informally) simply in terms of their allowable executions. For programs that can fail to terminate in a bounded amount of time, more subtle issues arise.
The observable behavior of a program is defined by the finite sets of external actions that the program may perform. A program that, for example, simply prints "Hello" forever is described by a set of behaviors that for any non-negative integeri, includes the behavior of printing "Hello"i times.
Termination is not explicitly modeled as a behavior, but a program can easily be extended to generate an additional external actionexecutionTermination that occurs when all threads have terminated.
We also define a specialhang action. If behavior is described by a set of external actions including ahang action, it indicates a behavior where after the external actions are observed, the program can run for an unbounded amount of time without performing any additional external actions or terminating. Programs can hang if all threads are blocked or if the program can perform an unbounded number of actions without performing any external actions.
A thread can be blocked in a variety of circumstances, such as when it is attempting to acquire a lock or perform an external action (such as a read) that depends on external data.
An execution may result in a thread being blocked indefinitely and the execution's not terminating. In such cases, the actions generated by the blocked thread must consist of all actions generated by that thread up to and including the action that caused the thread to be blocked, and no actions that would be generated by the thread after that action.
To reason about observable behaviors, we need to talk about sets of observable actions.
IfO is a set of observable actions for an executionE, then setO must be a subset ofE's actions,A, and must contain only a finite number of actions, even ifA contains an infinite number of actions. Furthermore, if an actiony is inO, and eitherhb(x, y) orso(x, y), thenx is inO.
Note that a set of observable actions are not restricted to external actions. Rather, only external actions that are in a set of observable actions are deemed to be observable external actions.
A behaviorB is an allowable behavior of a programP if and only ifB is a finite set of external actions and either:
There exists an executionE ofP, and a setO of observable actions forE, andB is the set of external actions inO (If any threads inE end in a blocked state andO contains all actions inE, thenB may also contain ahang action); or
There exists a setO of actions such thatB consists of ahang action plus all the external actions inO and for allk≥ |O |, there exists an executionE ofP with actionsA, and there exists a set of actionsO' such that:
Note that a behaviorB does not describe the order in which the external actions inB are observed, but other (internal) constraints on how the external actions are generated and performed may impose such constraints.
Fields declared final are initialized once, but never changed under normal circumstances. The detailed semantics offinal fields are somewhat different from those of normal fields. In particular, compilers have a great deal of freedom to move reads offinal fields across synchronization barriers and calls to arbitrary or unknown methods. Correspondingly, compilers are allowed to keep the value of afinal field cached in a register and not reload it from memory in situations where a non-final field would have to be reloaded.
final fields also allow programmers to implement thread-safe immutable objects without synchronization. A thread-safe immutable object is seen as immutable by all threads, even if a data race is used to pass references to the immutable object between threads. This can provide safety guarantees against misuse of an immutable class by incorrect or malicious code.final fields must be used correctly to provide a guarantee of immutability.
An object is considered to becompletely initialized when its constructor finishes. A thread that can only see a reference to an object after that object has been completely initialized is guaranteed to see the correctly initialized values for that object'sfinal fields.
The usage model forfinal fields is a simple one: Set thefinal fields for an object in that object's constructor; and do not write a reference to the object being constructed in a place where another thread can see it before the object's constructor is finished. If this is followed, then when the object is seen by another thread, that thread will always see the correctly constructed version of that object'sfinal fields. It will also see versions of any object or array referenced by thosefinal fields that are at least as up-to-date as thefinal fields are.
Example 17.5-1. final Fields In The Java Memory Model
The program below illustrates howfinal fields compare to normal fields.
class FinalFieldExample { final int x; int y; static FinalFieldExample f; public FinalFieldExample() { x = 3; y = 4; } static void writer() { f = new FinalFieldExample(); } static void reader() { if (f != null) { int i = f.x; // guaranteed to see 3 int j = f.y; // could see 0 } } }The classFinalFieldExample has afinalint fieldx and a non-finalint fieldy. One thread might execute the methodwriter and another might execute the methodreader.
Because thewriter method writesfafter the object's constructor finishes, thereader method will be guaranteed to see the properly initialized value forf.x: it will read the value3. However,f.y is notfinal; thereader method is therefore not guaranteed to see the value4 for it.
Example 17.5-2. final Fields For Security
final fields are designed to allow for necessary security guarantees. Consider the following program. One thread (which we shall refer to as thread 1) executes:
Global.s = "/tmp/usr".substring(4);
while another thread (thread 2) executes
String myS = Global.s; if (myS.equals("/tmp"))System.out.println(myS);String objects are intended to be immutable and string operations do not perform synchronization. While theString implementation does not have any data races, other code could have data races involving the use ofString objects, and the memory model makes weak guarantees for programs that have data races. In particular, if the fields of theString class were notfinal, then it would be possible (although unlikely) that thread 2 could initially see the default value of0 for the offset of the string object, allowing it to compare as equal to "/tmp". A later operation on theString object might see the correct offset of4, so that theString object is perceived as being "/usr". Many security features of the Java programming language depend uponString objects being perceived as truly immutable, even if malicious code is using data races to passString references between threads.
Leto be an object, andc be a constructor foro in which afinal fieldf is written. Afreeze action onfinal fieldf ofo takes place whenc exits, either normally or abruptly.
Note that if one constructor invokes another constructor, and the invoked constructor sets afinal field, the freeze for thefinal field takes place at the end of the invoked constructor.
For each execution, the behavior of reads is influenced by two additional partial orders, the dereference chaindereferences() and the memory chainmc(), which are considered to be part of the execution (and thus, fixed for any particular execution). These partial orders must satisfy the following constraints (which need not have a unique solution):
Dereference Chain: If an actiona is a read or write of a field or element of an objecto by a threadt that did not initializeo, then there must exist some readr by threadt that sees the address ofo such thatrdereferences(r, a).
Memory Chain: There are several constraints on the memory chain ordering:
Ifr is a read that sees a writew, then it must be the case thatmc(w, r).
Ifr anda are actions such thatdereferences(r, a), then it must be the case thatmc(r, a).
Ifw is a write of the address of an objecto by a threadt that did not initializeo, then there must exist some readr by threadt that sees the address ofo such thatmc(r, w).
Given a writew, a freezef, an actiona (that is not a read of afinal field), a readr1 of thefinal field frozen byf, and a readr2 such thathb(w, f),hb(f, a),mc(a, r1), anddereferences(r1, r2), then when determining which values can be seen byr2, we considerhb(w, r2). (Thishappens-before ordering does not transitively close with otherhappens-before orderings.)
Note that thedereferences order is reflexive, andr1 can be the same asr2.
For reads offinal fields, the only writes that are deemed to come before the read of thefinal field are the ones derived through thefinal field semantics.
A read of afinal field of an object within the thread that constructs that object is ordered with respect to the initialization of that field within the constructor by the usualhappens-before rules. If the read occurs after the field is set in the constructor, it sees the value thefinal field is assigned, otherwise it sees the default value.
In some cases, such as deserialization, the system will need to change thefinal fields of an object after construction.final fields can be changed via reflection and other implementation-dependent means. The only pattern in which this has reasonable semantics is one in which an object is constructed and then thefinal fields of the object are updated. The object should not be made visible to other threads, nor should thefinal fields be read, until all updates to thefinal fields of the object are complete. Freezes of afinal field occur both at the end of the constructor in which thefinal field is set, and immediately after each modification of afinal field via reflection or other special mechanism.
Even then, there are a number of complications. If afinal field is initialized to a constant expression (§15.28) in the field declaration, changes to thefinal field may not be observed, since uses of thatfinal field are replaced at compile time with the value of the constant expression.
Another problem is that the specification allows aggressive optimization offinal fields. Within a thread, it is permissible to reorder reads of afinal field with those modifications of afinal field that do not take place in the constructor.
Example 17.5.3-1. Aggressive Optimization offinal Fields
class A { final int x; A() { x = 1; } int f() { return d(this,this); } int d(A a1, A a2) { int i = a1.x; g(a1); int j = a2.x; return j - i; } static void g(A a) { // uses reflection to change a.x to 2 } }In thed method, the compiler is allowed to reorder the reads ofx and the call tog freely. Thus,new A().f() could return-1,0, or1.
An implementation may provide a way to execute a block of code in afinal-field-safe context. If an object is constructed within afinal-field-safe context, the reads of afinal field of that object will not be reordered with modifications of thatfinal field that occur within thatfinal-field-safe context.
Afinal-field-safe context has additional protections. If a thread has seen an incorrectly published reference to an object that allows the thread to see the default value of afinal field, and then, within afinal-field-safe context, reads a properly published reference to the object, it will be guaranteed to see the correct value of thefinal field. In the formalism, code executed within afinal-field-safe context is treated as a separate thread (for the purposes offinal field semantics only).
In an implementation, a compiler should not move an access to afinal field into or out of afinal-field-safe context (although it can be moved around the execution of such a context, so long as the object is not constructed within that context).
One place where use of afinal-field-safe context would be appropriate is in an executor or thread pool. By executing eachRunnable in a separatefinal-field-safe context, the executor could guarantee that incorrect access by oneRunnable to a objecto will not removefinal field guarantees for otherRunnables handled by the same executor.
Normally, a field that isfinal andstatic may not be modified. However,System.in,System.out, andSystem.err arestaticfinal fields that, for legacy reasons, must be allowed to be changed by the methodsSystem.setIn,System.setOut, andSystem.setErr. We refer to these fields as beingwrite-protected to distinguish them from ordinaryfinal fields.
The compiler needs to treat these fields differently from otherfinal fields. For example, a read of an ordinaryfinal field is "immune" to synchronization: the barrier involved in a lock or volatile read does not have to affect what value is read from afinal field. Since the value of write-protected fields may be seen to change, synchronization events should have an effect on them. Therefore, the semantics dictate that these fields be treated as normal fields that cannot be changed by user code, unless that user code is in theSystem class.
One consideration for implementations of the Java Virtual Machine is that every field and array element is considered distinct; updates to one field or element must not interact with reads or updates of any other field or element. In particular, two threads that update adjacent elements of a byte array separately must not interfere or interact and do not need synchronization to ensure sequential consistency.
Some processors do not provide the ability to write to a single byte. It would be illegal to implement byte array updates on such a processor by simply reading an entire word, updating the appropriate byte, and then writing the entire word back to memory. This problem is sometimes known asword tearing, and on processors that cannot easily update a single byte in isolation some other approach will be required.
Example 17.6-1. Detection of Word Tearing
The following program is a test case to detect word tearing:
public class WordTearing extends Thread { static final int LENGTH = 8; static final int ITERS = 1000000; static byte[] counts = new byte[LENGTH]; static Thread[] threads = new Thread[LENGTH]; final int id; WordTearing(int i) { id = i; } public void run() { byte v = 0; for (int i = 0; i < ITERS; i++) { byte v2 = counts[id]; if (v != v2) { System.err.println("Word-Tearing found: " + "counts[" + id + "] = "+ v2 + ", should be " + v); return; } v++; counts[id] = v; } } public static void main(String[] args) { for (int i = 0; i < LENGTH; ++i) (threads[i] = new WordTearing(i)).start(); } }This makes the point that bytes must not be overwritten by writes to adjacent bytes.
For the purposes of the Java programming language memory model, a single write to a non-volatilelong ordouble value is treated as two separate writes: one to each 32-bit half. This can result in a situation where a thread sees the first 32 bits of a 64-bit value from one write, and the second 32 bits from another write.
Writes and reads of volatilelong anddouble values are always atomic.
Writes to and reads of references are always atomic, regardless of whether they are implemented as 32-bit or 64-bit values.
Some implementations may find it convenient to divide a single write action on a 64-bitlong ordouble value into two write actions on adjacent 32-bit values. For efficiency's sake, this behavior is implementation-specific; an implementation of the Java Virtual Machine is free to perform writes tolong anddouble values atomically or in two parts.
Implementations of the Java Virtual Machine are encouraged to avoid splitting 64-bit values where possible. Programmers are encouraged to declare shared 64-bit values asvolatile or synchronize their programs correctly to avoid possible complications.