分类： Java
2010-07-16 17:51:27
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 java programming language memory model.
synchronization is implemented using monitors. Each object in Java is associated with a monitor, which a thread can lock or unlock. 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. It is reentrant.
A synchronized method automatically performs a lock action when it is invoked. If the method is static, it locks the monitor associated with the Class object that represents the class in which the method is defined.
The Java programming language neither prevents nor requires detection of deadlock conditions.
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 memory model determines what values can be read at every point in the program. The actions of each thread in isolation must behaves 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 obeys intra-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.
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. In this chapter, we use variable to refer to both fields and array elements. Local variables, formal method parameters or exception handler parameters are never shared between threads and are unaffected by the memory model.
Two accesses to (read of or writes to) the same variable are said to be conflicting if at least one of the accesses is a write.
An inter-thread action is an action performed by one thread that can be detected or directly influenced by another thread. Several kinds of inter-thread action that a program may perform:
1) Read(normal, or non-volatile)
2) Write(normal, or non-volatile)
3) Synchronization actions
a) Volatile read
b) Volatile write
c) Lock
d) Unlock
e) The (synthetic) first and last action of a thread
f) Actions that start a thread or detect that a thread has terminated.
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.
5) Thread divergence action. 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
This specification is only concerned with inter-thread actions. We will usually refer to inter-thread actions more succinctly as simple actions.
An action a is described by a tuple
1) t – the thread peforming the action
2) k – the kind of action
3) v – the variable or monitor involved in the action. For lock actions, v is the monitor being locked; for unlock actions, it is the monitor being unlocked. If the action is read, v is the variable being read. If the action is a write, v is the variable being written.
4) u – an arbitrary unique identifier for the action.
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.
A set of actions is sequentially consistent is all actions occur in a total order(the execution order) that is consistent with program order and furthermore, each read r of a variable v sees the value written by the write w to v such that:
1) w comes before r in the execution order, and
2) there is no other write w’ such that w comes before w’ and w’ come before r in the execution order.
Sequential consistency is a very strong guarantee that is made about visibility and ordering in an execution of a program.
Every execution has a synchronization order. A synchronization order is a total order over all of the synchronization actions of an execution.
Synchronization actions induce the synchronized-with relation on actions, defined as follows:
1) an unlock action on monitor m synchronizes-with all subsequent lock actions on m.
2) a write to a volatile variable v synchronizes-with all subsequent reads of v by any thread.
3) an action that starts a thread synchronizes-with the first action in the thread it starts.
4) the write of the default value to each variable synchronizes-with the first action in every thread.
5) the final action in a thread T1 synchronizes-with any action in another thread T2 that detect that T1 has terminated. T2 may accomplish this by calling T1.isAlive() or T1.join().
6) if thread T1 interrupts thread T2, the interrupt by T1 synchronizes-with any point where any other thread(including T2) determines that T2 has been interrupted.
The source of a synchronizes-with edge is called a release, and the destination is called an acquire.
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.
If we have two actions x and y, we write hb(x,y) to indicate that x happens-before y.
1) if x and y are actions of the same thread and x comes before y in program order, then hb(x,y).
2) there is a happens-before edge from the end of a constructor of an object to the start of a finalizer for that object.
3) if an action x synchronizes-with a following action y, then we also have hb(x,y)
4) if hb(x,y) and hb(y,z), then hb(x,z)
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.
When a program constains two conflicting accesses that are not ordered by a happens-before relationship, it is said to contain a data race.
A program is correctly synchronized if and only if all sequentially consistent executions are free of data races.
A set of actions a is happens-before consistent if for all reads r in A, it is not the case that either hb(r,W(r)), where W(r) is the write action seen by r or that there exists a write w in A such that w.v = r.v and hb(W(r), w) and hb(w,r).
An execution E is described by a tuple
1) P – a program
2) A – a set of actions
3) po – program order, which for each thread t, is a total order over all actions performed by t in A
4) so – synchronization order, which is a total order over all synchronization actions in A.
5) W – a writen-seen function, which for each read r in a, gives W(r), the write action seen by r in E.
6) V – a value-written function, which for each write w in A, gives V(w), the value written by w in E.
7) sw – synchronizes-with, a partial order over synchronization actions.
8) hb – happens-before, a partial order over actions
An execution is happens-before consistent if its set of actions is happens-before consistent.
An execution E=
1) each read sees a write to the same variable in the execution.
2) happens-before order is a partial order.
3) the execution obeys intra-thread consistency.
4) the execution is happens-before consistent
5) the execution obeys synchronization-order consistency
Observable Behavior and Nonterminating Executions
The observable behavior of a program is defined by the finite sets of external actions that the program may perform. We also define a special hang 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.
A thread can be blocked in a variety of circumstances. If a thread is in such a state, Thread.getState will return BLOCKED or WAITING.
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’s final field. The usage model for final fields is a simple one. Set the final fields for an object in that object’s constructor.
For the purposes of the Java programming language memory model, a single write to a non-volatile long or double value is treated as two separate writes: one to each 32-bit half.
Wait actions occur upon invocation of 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.
1) if n is zeor, an IllegalMonitorStateException is thrown.
2) If this is a timed wait and the nanosecs argument is not in the range of 0-999999 or the millisecs argument is negative, an IllegalArgumentException is thrown
3) if thread t is interrupted, an InterruptedException is thrown and t’s interruption status is set to false.
4) otherwise, the following sequence occurs:
a) thread t is added to the wait set of object m, and performs n unlock actions on m
b) 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.
i. a notify action being performed on m in which t is selected for removal from the wait set.
ii. a notifyAll action being performed on m.
iii. an interrupt action being performed on t
iv. if this is a timed wait, an internal action removing t from m’s wait set after the specific time
v. an internal action by the implementation.
c) thread t performs n lock actions on m
d) 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.
Interactions of Waits, Notification and Interruption
If a thread is both notified and interrupted while waiting, it may either:
1) return normally from wait, while still having a pending interrupt(in other words, a call to Thread.interrupted would return true)
2) return from wait by throwing an InterruptedException
Note that if a thread is both interrupted and woken via notify, and that thread returns from wait by throwing an InterruptedException, then some other thread in the wait set must be notified.
Thread.sleep causes the currently executing thread to sleep 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 resumptin of execution will depend on scheduling and the availability of processors on which to execute the thread.
It is important to note that neither Thread.sleep nor Thread.yield have any synchronization semantics. In particular, the compiler does not have to flush writes cached in registers out to share 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.
1. JLS 3nd
2. JVM 2nd
