threads.doc.html

A Java virtual machine instruction consists of an opcode specifying the operation to be performed, f

</ul><a name="22258"></a>
<hr><h2>8.7    Rules for <font size=+4><code>volatile</code></font> Variables</h2>
If a variable is declared volatile, then additional constraints apply to the operations 
of each thread. Let <i>T</i><em></em> be a thread and let <i>V</i><i></i> and <i>W</i> be volatile variables.
<p><ul><li>A <i>use</i> operation by <i>T</i><em></em> on <i>V</i><i></i> is permitted only if the previous operation by <i>T</i><em></em> on <i>V</i><i></i> was <i>load</i>, and a <i>load</i> operation by <i>T</i><em></em> on <i>V</i><i></i> is permitted only if the next operation by <i>T</i><em></em> on <i>V</i><i></i> is <i>use</i>. The <i>use</i> operation is said to be "associated" with the <i>read</i> operation that corresponds to the <i>load</i>.<p>
<li>A <i>store</i> operation by <i>T</i><em></em> on <i>V</i><i></i> is permitted only if the previous operation by <i>T</i><em></em> on <i>V</i><i></i> was <i>assign</i>, and an <i>assign</i> operation by <i>T</i><em></em> on <i>V</i><i></i> is permitted only if the next operation by <i>T</i><em></em> on <i>V</i><i></i> is <i>store</i>. The <i>assign</i> operation is said to be "associated" with the <i>write</i> operation that corresponds to the <i>store</i>.<p>
<li>Let action <i>A</i> be a <i>use</i> or <i>assign</i> by thread <i>T</i><em></em> on variable <i>V</i><i></i>, let action <i>F</i> be the <i>load</i> or <i>store</i> associated with <i>A</i>, and let action <i>P</i> be the <i>read</i> or <i>write</i> of <i>V</i><i></i> that corresponds to <i>F</i>. Similarly, let action <i>B</i> be a <i>use</i> or <i>assign</i> by thread <i>T</i><em></em> on variable <i>W</i><i></i>, let action <i>G</i> be the <i>load</i> or <i>store</i> associated with <i>B</i>, and let action <i>Q</i> be the <i>read</i> or <i>write</i> of <i>W</i><i></i> that corresponds to <i>G</i><i></i>. If <i>A</i> precedes <i>B</i>, then <i>P</i> must precede <i>Q</i>. (Less formally: operations on the master copies of volatile variables on behalf of a thread are performed by the main memory in exactly the order that the thread requested.)
</ul><a name="24432"></a>
<hr><h2>8.8    Prescient Store Operations</h2>
If a variable is not declared <code>volatile</code>, then the rules in the previous sections are 
relaxed slightly to allow <i>store</i> operations to occur earlier than would otherwise be 
permitted. The purpose of this relaxation is to allow optimizing compilers to perform
certain kinds of code rearrangement that preserve the semantics of properly 
synchronized programs, but might be caught in the act of performing memory operations
out of order by programs that are not properly synchronized.
<p><a name="24434"></a>
Suppose that a <i>store</i> by <i>T</i> of <i>V</i> would follow a particular <i>assign</i> by <i>T</i> of <i>V</i> according to the rules of the previous sections, with no intervening <i>load</i> or <i>assign</i> by <i>T</i> of <i>V</i>. Then that <i>store</i> operation would send to the main memory the value that the <i>assign</i> operation put into the working memory of thread <i>T</i>. The special rule allows the <i>store</i> operation actually to occur before the <i>assign</i> operation instead, if the following restrictions are obeyed:<p>
<ul><li>If the <i>store</i> operation occurs, the <i>assign</i> is bound to occur. (Remember, these are restrictions on what actually happens, not on what a thread plans to do. No fair performing a <i>store</i> and then throwing an exception before the <i>assign</i> occurs!)<p>
<li>No <i>lock</i> operation intervenes between the relocated <i>store</i> and the <i>assign</i>.<p>
<li>No <i>load</i> of <i>V</i> intervenes between the relocated <i>store</i> and the <i>assign</i>.<p>
<li>No other <i>store</i> of <i>V</i> intervenes between the relocated <i>store</i> and the <i>assign</i>.<p>
<li>The <i>store</i> operation sends to the main memory the value that the <i>assign</i>  operation will put into the working memory of thread <i>T</i>. 
</ul>This last property inspires us to call such an early <i>store</i> operation <i>prescient</i>: it has to 
know ahead of time, somehow, what value will be stored by the <i>assign</i> that it should 
have followed. In practice, optimized compiled code will compute such values early 
(which is permitted if, for example, the computation has no side effects and throws 
no exceptions), store them early (before entering a loop, for example), and keep 
them in working registers for later use within the loop.
<p><a name="22263"></a>
<hr><h2>8.9    Discussion</h2>
Any association between locks and variables is purely conventional. Locking 
any lock conceptually flushes <em>all</em> variables from a thread's working memory, 
and unlocking any lock forces the writing out to main memory of <em>all</em> variables 
that the thread has assigned. That a lock may be associated with a particular 
object or a class is purely a convention. For example, in some applications it 
may be appropriate always to lock an object before accessing any of its instance 
variables; <code>synchronized</code> methods are a convenient way to follow this convention.
In other applications, it may suffice to use a single lock to synchronize 
access to a large collection of objects.
<p><a name="22265"></a>
If a thread uses a particular shared variable only after locking a particular lock and before the corresponding unlocking of that same lock, then the thread will read the shared value of that variable from main memory after the <i>lock</i> operation, if necessary, and will copy back to main memory the value most recently assigned to that variable before the <i>unlock</i> operation. This, in conjunction with the mutual exclusion rules for locks, suffices to guarantee that values are correctly transmitted from one thread to another through shared variables.<p>
<a name="22266"></a>
The rules for volatile variables effectively require that main memory be touched exactly once for each <i>use</i> or <i>assign</i> of a volatile variable by a thread, and that main memory be touched in exactly the order dictated by the thread execution semantics. However, such memory operations are not ordered with respect to <i>read</i> and <i>write</i> operations on nonvolatile variables.<p>
<a name="23865"></a>
<hr><h2>8.10    Example: Possible Swap</h2>
Consider a class that has class variables <code>a</code> and <code>b</code> and methods <code>hither</code> and <code>yon</code>:
<p><blockquote><pre>class Sample {
    int a = 1, b = 2;
    void hither() {
    	a = b;
    }
    void yon() 
    	b = a;
    }
}
</pre></blockquote>Now suppose that two threads are created and that one thread calls <code>hither</code> while 
the other thread calls <code>yon</code>. What is the required set of actions and what are the ordering
constraints?
<p><a name="23877"></a>
Let us consider the thread that calls <code>hither</code>. According to the rules, this thread must perform a <i>use</i> of <code>b</code> followed by an <i>assign</i> of <code>a</code>. That is the bare minimum required to execute a call to the method <code>hither</code>.<p>
<a name="23878"></a>
Now, the first operation on variable <code>b</code> by the thread cannot be <i>use</i>. But it may be <i>assign</i> or <i>load</i>. An <i>assign</i> to <code>b</code> cannot occur because the program text does not call for such an <i>assign</i> operation, so a <i>load</i> of <code>b</code> is required. This <i>load</i> operation by the thread in turn requires a preceding <i>read</i> operation for <code>b</code> by the main memory.<p>
<a name="23879"></a>
The thread may optionally <i>store</i> the value of <code>a</code> after the <i>assign</i> has occurred. If it does, then the <i>store</i> operation in turn requires a following <i>write</i> operation for <code>a</code> by the main memory.<p>
<a name="23880"></a>
The situation for the thread that calls <code>yon</code> is similar, but with the roles of <code>a</code> and <code>b</code> exchanged.<p>
<a name="25448"></a>
The total set of operations may be pictured as follows:<p>
<br><br><img src="Threads.doc.anc.gif">
<br><br>Here an arrow from action <i>A</i> to action <i>B</i> indicates that <i>A</i> must precede <i>B</i>.
<p><a name="24312"></a>
In what order may the operations by the main memory occur? The only constraint is that it is not possible both for the <i>write</i> of <code>a</code> to precede the <i>read</i> of <code>a</code> and for the <i>write</i> of <code>b</code> to precede the <i>read</i> of <code>b</code>, because the causality arrows in the diagram would form a loop so that an action would have to precede itself, which is not allowed. Assuming that the optional <i>store</i> and <i>write</i> operations are to occur, there are three possible orderings in which the main memory might legitimately perform its operations. Let <code>ha</code> and <code>hb</code> be the working copies of <code>a</code> and <code>b</code> for the <code>hither</code> thread, let <code>ya</code> and <code>yb</code> be the working copies for the <code>yon</code> thread, and let <code>ma</code> and <code>mb</code> be the master copies in main memory. Initially <code>ma=1</code> and <code>mb=2</code>. Then the three possible orderings of operations and the resulting states are as follows:<p>
<ul><li><i>write</i> <code>a</code><code><img src="chars/arrwrite.gif"></code><i>read</i> <code>a</code>, <i>read</i> <code>b</code><code><img src="chars/arrwrite.gif"></code><i>write</i> <code>b</code> (then <code>ha=2</code>, <code>hb=2</code>, <code>ma=2</code>, <code>mb=2</code>, <code>ya=2</code>, <code>yb=2</code>)<p>
<li><i>read</i> <code>a</code><code><img src="chars/arrwrite.gif"></code><i>write</i> <code>a</code>, <i>write</i> <code>b</code><code><img src="chars/arrwrite.gif"></code><i>read</i> <code>b</code> (then <code>ha=1</code>, <code>hb=1</code>, <code>ma=1</code>, <code>mb=1</code>, <code>ya=1</code>, <code>yb=1</code>)<p>
<li><i>read</i> <code>a</code><code><img src="chars/arrwrite.gif"></code><i>write</i> <code>a</code>, <i>read</i> <code>b</code><code><img src="chars/arrwrite.gif"></code><i>write</i> <code>b</code> (then <code>ha=2</code>, <code>hb=2</code>, <code>ma=2</code>, <code>mb=1</code>, <code>ya=1</code>, <code>yb=1</code>)
</ul>Thus, the net result might be that, in main memory, <code>b</code> is copied into <code>a</code>, <code>a</code> is copied 
into <code>b</code>, or the values of <code>a</code> and <code>b</code> are swapped; moreover, the working copies of the 
variables might or might not agree. It would be incorrect, of course, to assume that 
any one of these outcomes is more likely than another. This is one place in which the 
behavior of a program is necessarily timing-dependent.
<p><a name="23915"></a>
Of course, an implementation might also choose not to perform the <i>store</i> and <i>write</i> operations, or only one of the two pairs, leading to yet other possible results.<p>
<a name="23916"></a>
Now suppose that we modify the example to use <code>synchronized</code> methods:<p>
<blockquote><pre>class SynchSample {
    int a = 1, b = 2;
    synchronized void hither() {
    	a = b;
    }
    synchronized void yon() 
    	b = a;
    }
}
</pre></blockquote>Let us again consider the thread that calls <code>hither</code>. According to the rules, this 
thread must perform a <i>lock</i> operation (on the instance of class <code>SynchSample</code> on 
which the <code>hither</code> method is being called) before the body of method <code>hither</code> is 
executed. This is followed by a <i>use</i> of <code>b</code> and then an <i>assign</i> of <code>a</code>. Finally, an <i>unlock</i> 
operation on that same instance of <code>SynchSample</code> must be performed after the body 
of method <code>hither</code> completes. That is the bare minimum required to execute a call 
to the method <code>hither</code>.
<p><a name="23927"></a>
As before, a <i>load</i> of <code>b</code> is required, which in turn requires a preceding <i>read</i> operation for <code>b</code> by the main memory. Because the <i>load</i> follows the <i>lock</i> operation, the corresponding <i>read</i> must also follow the <i>lock</i> operation.<p>
<a name="23928"></a>
Because an <i>unlock</i> operation follows the <i>assign</i> of <code>a</code>, a <i>store</i> operation on <code>a</code> is mandatory, which in turn requires a following <i>write</i> operation for <code>a</code> by the main memory. The <i>write</i> must precede the <i>unlock</i> operation.<p>
<a name="25341"></a>
The situation for the thread that calls <code>yon</code> is similar, but with the roles of <code>a</code> and <code>b</code> exchanged.<p>
<a name="25401"></a>
The total set of operations may be pictured as follows:<p>
<a name="25445"></a>
<br><br><img src="Threads.doc.anc1.gif">
<br><br>The <i>lock</i> and <i>unlock</i> operations provide further constraints on the order of operations by the main memory; the <i>lock</i> operation by one thread cannot occur between the <i>lock</i> and <i>unlock</i> operations of the other thread. Moreover, the <i>unlock</i> operations require that the <i>store</i> and <i>write</i> operations occur. It follows that only two sequences are possible:<p>
<ul><li><i>write</i> <code>a</code><code><img src="chars/arrwrite.gif"></code><i>read</i> <code>a</code>, <i>read</i> <code>b</code><code><img src="chars/arrwrite.gif"></code><i>write</i> <code>b</code> (then <code>ha=2</code>, <code>hb=2</code>, <code>ma=2</code>, <code>mb=2</code>,<code> ya=2</code>, <code>yb=2</code>)<p>
<li><i>read</i> <code>a</code><code><img src="chars/arrwrite.gif"></code><i>write</i> <code>a</code>, <i>write</i> <code>b</code><code><img src="chars/arrwrite.gif"></code><i>read</i> <code>b</code> (then <code>ha=1</code>, <code>hb=1</code>, <code>ma=1</code>, <code>mb=1</code>, <code>ya=1</code>, <code>yb=1</code>)
</ul>While the resulting state is timing-dependent, it can be seen that the two threads will 
necessarily agree on the values of <code>a</code> and <code>b</code>.
<p><a name="23974"></a>
<hr><h2>8.11    Example: Out-of-Order Writes</h2>
This example is similar to that in the preceding section, except that one method 
assigns to both variables and the other method reads both variables. Consider a class 
that has class variables <code>a</code> and <code>b</code> and methods <code>to</code> and <code>fro</code>:
<p><blockquote><pre>class Simple {