Memory Model
A memory 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.
Non Shared Variables (Stack)
What is stored on the thread's stack is:
the method's local variables,
the method's parameters,
the method's return address etc so that the CPU knows where to go when the call returns, and (possibly)
Shared Variables (Heap)
- Memory that can be shared between threads is called shared memory or heap memory.
- All instance fields, static fields and array elements are stored in heap memory.
- Local variables (§14.4), formal method parameters (§8.4.1) or exception handler parameters are never shared between threads and are unaffected by the memory model.
Actions
another thread.
There are several kinds of inter-thread action that a program may perform:
- Read (normal, or non-volatile). Reading a variable.
- Write (normal, or non-volatile). Writing a variable.
- Synchronization actions, which are:
- Volatile read. A volatile read of a variable.
- Volatile write. A volatile write of a variable.
- Lock. Locking a monitor
- Unlock. Unlocking a monitor.
- The (synthetic) first and last action of a thread
- Actions that start a thread or detect that a thread has terminated, as described in §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
Programs and Program Order
- Among all the inter-thread actions performed by each thread t, the program order of t is a total order that reflects the order in which these actions would be performed according to the intra-thread semantics of t.
- 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.
Synchronization Order
The source of a synchronizes-with edge is called a release, and the destination is called an acquire.
Happens-before Order
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.
It should be noted that the presence of a happens-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.
More specifically, if two actions share a happens-before relationship, they do not necessarily have to appear to have happened in that order to any code with which they do not share a happens-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.
• An unlock on a monitor happens-before every subsequent lock on that monitor.
• A write to a volatile field (§8.3.1.4) happens-before every subsequent read of that field.
• A call to start() on a thread happens-before any actions in the started thread.
• All actions in a thread happen-before any other thread successfully returns from a
join() on that thread.
• The default initialization of any object happens-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 a data race.
Semantics of Final Fields
The semantics for final fields are as follows. Let o be an object, and c be a constructor for o in which f is written. A freeze action on a final field f of o takes place when c exits, either normally or abruptly.
More...
Non-atomic Treatment of double and long - Some implementations may find it convenient to divide a single write action on a 64-bit long or double value into two write actions on adjacent 32 bit values.
Chapter 17 of the Java Language Specification defines the happens-before relation on memory operations such as reads and writes of shared variables. The results of a write by one thread are guaranteed to be visible to a read by another thread only if the write operation happens-before the read operation. The synchronized and volatile constructs, as well as the Thread.start() and Thread.join() methods, can form happens-before relationships. In particular:
Each action in a thread happens-before every action in that thread that comes later in the program's order.
An unlock (synchronized block or method exit) of a monitor happens-before every subsequent lock (synchronized block or method entry) of that same monitor. And because the happens-before relation is transitive, all actions of a thread prior to unlocking happen-before all actions subsequent to any thread locking that monitor.
A write to a volatile field happens-before every subsequent read of that same field. Writes and reads of volatile fields have similar memory consistency effects as entering and exiting monitors, but do not entail mutual exclusion locking.
A call to start on a thread happens-before any action in the started thread.
All actions in a thread happen-before any other thread successfully returns from a join on that thread.
Wait Sets and Notification
Wait - A thread returns normally from a wait if it returns without throwing an InterruptedException.
Let thread t be the thread executing the wait method on object m, and let n be the number of lock actions by t on m that have not been matched by unlock actions. One of the following actions occurs.
1. Thread t is added to the wait set of object m, and performs n unlock actions on m.
2. Thread t does not execute any further instructions until it has been removed from m'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.
- A notify action being performed on m in which t is selected for removal from the wait set.
- A notifyAll action being performed on m.
- An interrupt action being performed on t.
- If this is a timed wait, an internal action removing t from m's wait set that occurs after at least millisecs milliseconds plus nanosecs 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'' -- 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 using wait only within loops that terminate only when some logical condition that the thread is waiting for holds.
3. Thread t performs n lock actions on m.
4. If thread t was removed from m's wait set in step 2 due to an interrupt, t's interruption
status is set to false and the wait method throws InterruptedException.
Notification
- If n is zero an IllegalMonitorStateException is thrown. This is the case where thread t does not already possess the lock for target m.
- If n is greater than zero and this is a notify action, then, if m's wait set is not empty, a thread u that is a member of m'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 enables u's resumption in a wait action. Notice however, that u's lock actions upon resumption cannot succeed until some time after t fully unlocks the monitor for m.
- If n is greater than zero and this is a notifyAll action, then all threads are removed from m'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
Interruptions
Let t be the thread invoking u.interrupt, for some thread u, where t and u may be the same. This action causes u's interruption status to be set to true.
Additionally, if there exists some object m whose wait set contains u, u is removed from m's wait set. This enables u to resume in a wait action, in which case this wait will, after re-locking m's monitor, throw InterruptedException.
Invocations of Thread.isInterrupted can determine a thread's interruption status. The static method Thread.interrupted may be invoked by a thread to observe and clear its own interruption status
The thread may not reset its interrupt status and return normally from the call to wait.
Similarly, notifications cannot be lost due to interrupts. Assume that a set s of threads is in the wait set of an object m, and another thread performs a notify on m. Then either
- at least one thread in s must return normally from wait, or
- all of the threads in s must exit wait by throwing InterruptedException
Sleep and Yield
Thread.sleep - causes the currently executing thread to sleep (temporarily cease execution) for the specified duration.
The thread does not lose ownership of any monitors.
Thread.yield - A hint to the scheduler that the current thread is willing to yield its current use of a processor. The scheduler is free to ignore this hint.
Thread.sleep nor Thread.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 to Thread.sleep or Thread.yield, nor does the compiler have to reload values cached in registers after a call to Thread.sleep or Thread.yield.
From another link ---
http://shipilev.net/blog/2014/jmm-pragmatics/
Part I. Access Atomicity
Most platforms, however, do guarantee atomicity for up to 32-bit accesses. This is why we have a compromise in JMM which relaxes the atomicity guarantees for 64-bit values. Of course, there are still ways to enforce atomicity for 64-bit values, e.g. by pessimistically acquiring the lock on update and read, but that will come at a cost, and so we provide an escape hatch: users put volatile where they need atomicity, and VM and hardware work together to preserve it, no matter what the costs are.
since volatile is overloaded with two meanings: a) access atomicity; and b) memory ordering — you cannot get one without getting the other as baggage
Part II. Word Tearing
If two variables are distinct, then the actions on them should also be distinct, and should not be affected by the actions on adjacent elements. How can this example break? Quite simple: if our hardware cannot access a distinct array element, it will be forced to read several elements, modify one element in the bunch, and then put the entire bunch back.
If two threads are doing the same dance on their separate elements, it might happen that another thread stores its own steps back to memory, overwriting an element updated by the first thread.
Compromise - One bit boolean is store as a 8bit-byte wasting space.
Part III: SC-DRF
SC = Sequential Consistency
Sequential consistency does not mean the operations were executed in a particular total order! (The stronger strict consistency provides that). It is only important that the result is indistinguishable from some execution which has the total order of operations. We call executions like these sequentially consistent executions, and their results are called sequentially consistent results.
Program Order
Intra-thread consistency is the very first execution filter, which most people do implicitly in their heads when dealing with JMM. You may notice at this point that JMM is a non-constructive model: we don’t build up the solution inductively, but rather take the entire realm of executions, and filter out those interesting to us.
Synchronization Order
In weak memory models, we don’t order all the actions, we only impose a hard order on a few limited primitives. In the JMM, those primitives are wrapped in their respective Synchronization Actions.
Synchronization Actions are
1. volatile read, volatile write
2. lock monitor, unlock monitor
3. (Synthetic) first & last actions in a Thread
4. actions detecting the thread had terminated - Thread.join(), Thrad.interrupted()
5. actions that start the thread
SO-PO consistency
If you take an arbitrary program, no matter how many races it contains, and sprinkle enough volatile-s around that program, it will eventually become sequentially consistent, i.e. all the outcomes of the program would be explained by some SC execution. This is because you will eventually hit a critical moment when all the important program actions turn into synchronization actions, and become totally ordered.
Happens-Before
We need something to connect the thread states, something which will drag the non-SA values along. SO is not usable for that, because it is not clear when and how it drags the state along. So, we need a clear-cut suborder of SO which describes the data flow. We call this suborder synchronizes-with order (SW).
if we construct the union of PO and SW orders, and then transitively close that union, we get the derived order: Happens-Before (HB). HB in this sense acquires both inter-thread and intra-thread semantics. PO leaks the information about sequential actions within each thread into HB, and SW leaks when the state "synchronizes". HB is partial order, and allows for construction of equivalent executions with reordered actions.
Sequentially Consistent - Data Race Free
This is what SC-DRF is all about: if we have no races in the program — that is, all reads and writes are ordered either by SO or HB — then the outcome of this program can be explained by some sequentially consistent execution. There is a formal proof for SC-DRF properties, but we will use intuitive understanding as to why this should be true.
Happens-Before: Publication
The source of a synchronizes-with edge is called "release", and the destination is called "acquire". HB contains SW, and therefore, HB spanning different threads also starts at "release", and ends at "acquire".
Release can be thought of as the operation which releases all the preceding state updates into the wild, and acquire is the paired operation which receives those updates. So, after a successful acquire, we can see all the updates preceding the paired release.
Because of the constructions we laid out before, it only works if acquire/release happened on the same variable, and we actually saw the written value
Lock Coarsening - Include non synchronised instructions inside the synchronised lock - as this is allowed by the JMM.
Part IV: Out of Thin Air
Optimisations reordering issues
Part V: Finals
There is a freeze action at the end of the constructor.
The freeze action freezes the field values. final values ??
No comments:
Post a Comment