[concurrency-interest] dealing with people that question visibility problems

Peter Veentjer alarmnummer at gmail.com
Wed Feb 21 11:50:02 EST 2007


Hi Greg,

you are using the same example as I have in my post (not completely
finished.. 99%):

++ Spring and visibility problems

<h3>Abstract</h3>
Spring is a great framework, but I expect that some Spring based
applications are  subject to visibility problems (a type of
concurrency problem). This blogentry describes the cause and effects
of this problem, and also how it can be solved.

<h3>Visibility problems</h3>
Most programmers don't have much experience with multi threading and
have a very simplistic view on reality: if a thread makes a change to
a variable, this change directly is visible to all other threads that
access the same variable. This view is called <a
href="http://en.wikipedia.org/wiki/Sequential_consistency">sequential
consistency</a>, but the problem is that no virtual machine
automatically provides this view.

The reason for this apparently faulty behavior is performance. Most
variables are not shared between threads, so no special instructions
(memory barriers) have to be added to make the program sequentially
consistent. If these instructions were automatically added to all
variable accesses, it would greatly reduce performance because a lot
of optimizations would be excluded from being used. To name a few:
<ol>
    <li>
    	usage of super fast local-memory (like caches and cpu-registers).
It also would (greatly) reduce the performance benefits of multi-core
systems because access to main memory would be the bottleneck.
    </li>
    <li>	
    	reordering of instructions to increase the chance of a cache hit.
    </li>
</ol>

The consequence of a visibility problem, is that a value written to a
variable by one thread, doesn't have to be visible in other threads
(maybe never). This could lead to an easy to detect
NullPointerException, but it can also lead to much harder to detect
problems like shown in the following example:

<pre>
public class SomeRunnable implements Runnable{
    private boolean stop = false;

    public void stop(){
	stop = true;
    }

    public void run(){
    	while(!stop){
		System.out.println("hello");
	}
    }
}
</pre>

There are a few reasons why this runnable could fail to stop:
<ol>
	<li>
		stop is not safely published: the thread that executed the run
method, doesn't need to see a change in the stop value. A possible
scenario would be: thread1 (the thread that executed run) is running
on cpu1 (with cache1). Thread2 (the thread that calls stop) is running
on cpu2 (with cache2). When thread1 runs, it needs the value of stop,
sees the initial false value and places it in his cache. When thread2
executes stop, stop is set to true. But it might happen that this
value remains in cache2 for an undetermined time and isn't flushed to
main memory, so thread1 never sees the new value when it happens to
read from main memory. Even if the value is flushed to main memory,
thread1 could still be reading the stale value from cache1.
	</li>
	<li>
		because the access to the stop variable isn't safely published, and
the value doesn't change in the loop, the 'compiler' (JIT, cpu etc)
could decide to replace the variable read by the constant 'true' in
that loop.
	</li>
</ol>
Visibility problems can lead to hard to detect errors and
unpredictable behavior, and you definitely want to keep them out of
your system. And betting on the <a
href="http://en.wikipedia.org/wiki/Memory_coherence">Memory
Coherence</a> of a computer, is asking for trouble (the application
also wouldn't platform independant).

<h3>Spring applications and visibility problems</h3>
I expect that a lot of Spring applications are subject to visibility
problems. If you look at singleton beans for example (dao's,
controllers, managers etc), these beans often are shared by many
threads, to name a few:
<ul>
    <li>threads from the servlet container</li>
    <li>threads from remoting middleware</li>
    <li>threads from jmx</li>
    <li>threads from triggers or other internal threads</li>
</ul>

Take a look at the following example:
<pre>
public class EmployeeManagerImpl implements EmployeeManager{

    private EmployeeDao employeeDao;

    public setEmployeeDao(EmployeeDao employeeDao){
        this.employeeDao = employeeDao;
    }

    public void fire(long employeeId){
        Employee employee = employeeDao.load(employeeId);
        employee.fire();
    }
}
</pre>

And the bean configuration that belongs to it:
<pre>
    &lt;bean id=&quot;employeeManager&quot;
class=&quot;EmployeeManagerImpl&quot;&gt;
        &lt;property name=&quot;employeeDao&quot;
ref=&quot;employeeDao&quot;/&gt;
    &lt;/bean&gt;
</pre>

The visibility problem here, is that employeeDao, set by the thread
that constructed the employeeManager, isn't safely published and
doesn't have to be visible in other threads. If one of those threads
calls the fire method on the EmployeeManagerImpl, it could lead to a
NullPointerException because that thread still sees a null value for
the employeeDao.

The problem can be solved in a few ways:
<ol>
    <li>
        make employeeDao volatile. Although it sounds quite strange,
because the employeeDao is not going to change after it has been set,
volatile variables are always safely published. Personally I don't
like this solution much because it is misleading (the value is never
going to change after the object has been constructed) and it also
reduces performance (the variable always has to be read from main
memory instead of local memory).
    </li>
    <li>
        make employeeDao final, because final variables also are
safely published. The problem with final variables is that they only
can be set by constructor based Dependency Injection (DI) and Spring
promotes setter based DI. Personally I prefer constructor based DI,
because it is a lot easier to guarantee class invariants. Although
those setters only are visible in an implementing class, and not in
the interface, I still don't feel happy about because it also makes
classes harder to understand. But constructor based DI isn't perfect
either; I guess most of us have struggled with large constructors.
    </li>
</ol>

<h3>Problem not that bad?</h3>
Before going into detail why the problems maybe are not that bad, I
need to explain the new Memory Model found in Java 5 and higher (<a
href="http://jcp.org/aboutJava/communityprocess/review/jsr133/index.html">JSR-133</a>)
(pointer to footnote). The model describes under what kinds of
conditions a variable will be visible in other threads.
<p/>
The model is expressed in terms of actions:
<ol>
	<li>
		read/writes to normal/volatile/final variables
	</li>
	<li>
		lock acquire/release
	</li>
	<li>
		thread start/join
	</li>
</ol>
<p/>
The model also contains a set of happens-before rules between actions.
If a happens-before rule applies between action1 and action2, then all
changes made by action1 are visible in action2. Examples of
happens-before rules are:
<ol>
	<li>
		Program Order rule: Each action in a thread happens-before every
action in that thread that comes later in the program order. It is
important to realize that normal variable reads/writes, can be
reordered as long as they keep the 'within-thread as-if-serial
semantics semantics': the reordering should not be visible inside the
thread.
	</li>
	<li>
		Volatile variable rule. A write to a volatile variable
happens-before every subsequent read of that same variable (that is
why making the employeeDao volatile works).
	</li>
	<li>
		Monitor lock rule. An unlock on a monitor lock happens-before every
subsequent lock on that same monitor lock. (The same goes for the the
new <a href="http://java.sun.com/j2se/1.5.0/docs/api/java/util/concurrent/locks/Lock.html">Lock</a>
found in Java 5.
	</li>
	<li>
		Transitivity rule. If action1 happens-before action2, and action2
happens-before action3, then action1 happens-before action3.
	</li>
</ol>

<h3>Safe handoff</h3>
These elementary happens-before rules can be used to check if there is
a happens-before relation between two actions. Take a look at the
following example:
<pre>
int a=0;
volatile boolean b=0;

void initialize(){
	a=console.readInteger();		
	b=console.readBoolean();
}

void print(){
	print(b);
	print(a);
}
</pre>

A possible ordering of actions could be:
<table border="1">
	<tr><td>action</td><td>thread 1</td><td>thread 2</td></tr>	
	<tr><td>action1</td><td>normalwrite(a)</td><td></td></tr>
	<tr><td>action2</td><td>volatilewrite(b)</td><td></td></tr>
	<tr><td>action3</td><td></td><td>volatileread(b)</td></tr>
	<tr><td>action4</td><td></td><td>normalread(a)</td></tr>
</table>
Because action1 happens-before action2 (program order) and because
action2 happens-before action3 (monitor lock rule) and because action3
happens before action4 (program order), action1 happens before action4
(remember that the happens before rules are transitive). This means
that the change in action1, is visible in action4. This technique is
called 'safe handoff' (aka 'piggybacking on synchronization').
Safe handoff uses the safe publication of a variable X (in this case
b), to safely publish all unsafely-published-variables that are
changed before X (in this case a).

<h4>Safe handoff in Spring</h4>
The Spring applicationcontext also provides safe handoff (in Java 5
and higher): after a bean is created, it is placed in a synchronized
map. When it is needed, it is retrieved from that synchronized map.
But instead of using the 'volatile variable' rule, it uses the
'monitor lock' rule.

The following table shows a very simplified ordering of actions
(variable 'X' is mapentry.ref):
<table border="1">
	<tr><td>action</td><td>thread 1</td><td>thread 2</td></tr>	
	<tr><td></td><td><i>construction of the employeeManager</i></td><td></td></tr>	
	<tr><td>action1</td><td>normalwrite(employeeDao)</td><td></td></tr>	
	<tr><td></td><td><i>employeeManager is placed in the
applicationcontext</i></td><td></td></tr>
	<tr><td>action2</td><td>lock(applicationcontext)</td><td></td></tr>
	<tr><td>action3</td><td>normalwrite(mapentry.ref)</td><td></td></tr>
	<tr><td>action4</td><td>unlock(applicationcontext)</td><td></td></tr>
	<tr><td></td><td></td><td><i>employeeManager is read from the
applicationcontext</i></td></tr>
	<tr><td>action5</td><td></td><td>lock(applicationcontext)</td></tr>
	<tr><td>action6</td><td></td><td>normalread(mapentry.ref)</td></tr>
	<tr><td>action7</td><td></td><td>unlock(applicationcontext)</td></tr>
	<tr><td></td><td></td><td><i>employeeManager fire method is
called</i></td></tr>
	<tr><td>action8</td><td></td><td>normalread(employeeDao)</td></tr>
</table>
This means that there is a happens before relation between action1 and
action8, so the value set in the employeeDao (action1), is visible
when it is read by another thread (action8). That is why standard
Spring singletons don't have visibility problems.

<h3>Conclusion</h3>
I'm glad that standard singleton beans aren't subject to visibility
problems (under Java 5 and higher), but I don't think it is the
correct way to deal with concurrency control in Spring:
<ol>
	<li>
		objects can't be safely used in a different environment. So your
objects are tied to the Spring framework to make them work correct.
	</li>
	<li>
		the save handoff behavior is not guaranteed by Spring, and it only
works under Java 5 and higher. The behavior is undefined in older
JVM's.
	</li>
</ol>
It also gives a dangerous feeling of security. If objects are used in
a multi threaded environment, you <b>have</b> to make your objects
thread safe. You can't assume everything will work out, because
eventually it will come back to you. Especially with the increase in
number of local memories (introduced by multi core machines) and the
now clearly defined Memory Model, the chance of problems (caused by
unsafe code) will increase. Hoping that nothing falls over, while the
specs are clear (although not for the faint hearted), is in my opinion
not a professional way to develop software.

<p/>
Footnote:
If you want a more in depth explanation of the new Java Memory Model,
I suggest <a href="http://www.amazon.com/Java-Concurrency-Practice-Brian-Goetz/dp/0321349601">'Java
Concurrency in Practice'</a> from Brian Goets, Tim Peierls, Joshua
Bloch, Joseph Bowbeer, David Holmes and Doug Lea, or check out the
following website <a
href="http://www.cs.umd.edu/~pugh/java/memoryModel">The Java Memory
Model</a>
<p/>



On 2/21/07, Gregg Wonderly <gergg at cox.net> wrote:
> Peter Veentjer wrote:
> > Does someone have experience with dealing with this situation?
>
> On a single core systems, and prior to JDK 1.5 (and some 1.4) simple (incorrect)
> code such as
>
> public class MyThread implements Runnable {
>      private boolean done;
>      public void shutdown() {
>         done = true;
>      }
>
>      public void run() {
>          while( !done ) {
>              ...
>          }
>      }
> }
>
> will work just fine.  Now days, you will have visibility problems with changes
> in the value of "done".  I recently had a conversation with a research professor
> who said that his current mantra is that all class fields must either be "final"
> or "volatile".  If a field doesn't have one of those qualifiers on it, it will
> be problematic and the overhead of volatile is far less of a concern than
> incorrect code.
>
> There are probably a million or more ways to demonstrate visibility problems for
> the inexperienced to learn from.  Maybe someone can create a nice set of
> graphical demos that show the problem literally.
>
> Gregg Wonderly
>



More information about the Concurrency-interest mailing list