Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Java > Question whether a problem with race conditions exists in this case

Reply
Thread Tools

Question whether a problem with race conditions exists in this case

 
 
Saxo
Guest
Posts: n/a
 
      12-14-2011
I have a class Node as displayed below that holds a new value and the
previous value. Which one applies is determined by the value of
useNewValue. In my application there is a list of such nodes where for
each node the current value is replaced with a new one. The new values
should become effective for the entire list all >at once< through an
atomic change of useNewValue in every node. For that purpose, when the
new value is set, for every node in the list the same AtomicBoolean
instance is passed on to setNewValue(...), which is stored in
useNewValueParam. When the commit is done, the value of this instance
of AtomicBoolean is changed to true (this way the thread doing the
commit does not have to enter the synchronized block as all the other
threads calling aNode.get) and thus the new value of every node
becomes visible at once to every thread calling aNode.get().

public class Node {

AtomicBoolean useNewValue = new AtomicBoolean(false);
private Object newValue = null;
private Object previousValue = null;
private Object lock = new Object();

public Object get() {
synchronized(lock) {
if(useNewValue.get()) // 1
return newValue; // 2
return previousValue; // 3
}
}

public void setNewValue(Object newValue, AtomicBoolean
useNewValueParam) {
synchronized(lock) {
if(this.useNewValue.get())
previousValue = this.newValue;
this.newValue = newValue;
// useNewValueParam is allways set to false when setNewValue is
called
this.useNewValue = useNewValueParam;
}
}
}

At the same time there is never more than one thread iterating over
the node list calling setNewValue. This is made sure through
serialization of threads that want to iterate over the list calling
setNewValue. Serialization of threads is a bit crude, but not relevant
at the moment for the discussion of the problem described here.

My question is now whether this approach is free of race conditions or
starvation issues if implemented as described above. I have some
doubts whether everything is fine here as useNewValue is changed by
the commit thread by reference without entering synchronized(lock)
{ ... }. So is everything still fine if a context switch happens
between line 1 and 2 or between line 1 and 3? It would be for sure if
the commit thread entered the synchronized(lock) { ... } block, but it
does not (changing to the new values all at once wouldn't be possible
otherwise).

I would be thankful if someone could look over this and tell me her/
his opinion.

Thanks al lot, Oliver
 
Reply With Quote
 
 
 
 
Andreas Leitgeb
Guest
Posts: n/a
 
      12-14-2011
Saxo <(E-Mail Removed)> wrote:
> public class Node {
> AtomicBoolean useNewValue = new AtomicBoolean(false);
> private Object newValue = null;
> private Object previousValue = null;
> private Object lock = new Object();


I think, you would at least have to declare these volatile.
Otherwise, a different thread might e.g. still see an old
value in newValue, after the AtomicBoolean's value changes
to true.

 
Reply With Quote
 
 
 
 
Lew
Guest
Posts: n/a
 
      12-14-2011
On Wednesday, December 14, 2011 9:53:37 AM UTC-8, Andreas Leitgeb wrote:
> Saxo <(E-Mail Removed)> wrote:
> > public class Node {
> > AtomicBoolean useNewValue = new AtomicBoolean(false);
> > private Object newValue = null;
> > private Object previousValue = null;
> > private Object lock = new Object();

>
> I think, you would at least have to declare these volatile.


Nope, they use 'synchronized'. 'volatile' wouldn't work anyway, because these
have to change together, so they must use 'synchronized'.

> Otherwise, a different thread might e.g. still see an old
> value in newValue, after the AtomicBoolean's value changes
> to true.


--
Lew
 
Reply With Quote
 
Daniel Pitts
Guest
Posts: n/a
 
      12-14-2011
On 12/14/11 9:07 AM, Saxo wrote:
> I have a class Node as displayed below that holds a new value and the
> previous value.

[snip]
>
> public class Node {
>
> AtomicBoolean useNewValue = new AtomicBoolean(false);
> private Object newValue = null;
> private Object previousValue = null;
> private Object lock = new Object();
>
> public Object get() {
> synchronized(lock) {
> if(useNewValue.get()) // 1
> return newValue; // 2
> return previousValue; // 3
> }
> }
>
> public void setNewValue(Object newValue, AtomicBoolean
> useNewValueParam) {
> synchronized(lock) {
> if(this.useNewValue.get())
> previousValue = this.newValue;
> this.newValue = newValue;
> // useNewValueParam is allways set to false when setNewValue is
> called

If it is always false, why pass it in at all? I don't believe this comment.
> this.useNewValue = useNewValueParam;
> }
> }
> }

Don't use tabs on usenet, it makes formatting bonkers. Use 2 to 4
spaces for indenting.

Since you have a lock here, you don't need to use an AtomicBoolean.
Even so, you're not using the AtomicBoolean as expected. The field for
it should be final, and you call "set(value)" on it, rather than replace
it with another AtomicBoolean instance. That defeats the purpose.

>
> At the same time there is never more than one thread iterating over
> the node list calling setNewValue. This is made sure through
> serialization of threads that want to iterate over the list calling
> setNewValue. Serialization of threads is a bit crude, but not relevant
> at the moment for the discussion of the problem described here.

The threads are all serialized because of the synchronize(lock).
>
> My question is now whether this approach is free of race conditions or
> starvation issues if implemented as described above. I have some
> doubts whether everything is fine here as useNewValue is changed by
> the commit thread by reference without entering synchronized(lock)
> { ... }. So is everything still fine if a context switch happens
> between line 1 and 2 or between line 1 and 3? It would be for sure if
> the commit thread entered the synchronized(lock) { ... } block, but it
> does not (changing to the new values all at once wouldn't be possible
> otherwise).

synchronized(lock) prevents more than one thread from being inside *any*
synchronized(lock) block at *any* given time, so you will never have a
setter and getter running at the same time. This code will "work", but
is still not great quality.
>
> I would be thankful if someone could look over this and tell me her/
> his opinion.

Unrelated, it might be useful to use Generics here. I don't know much
of your use-case, but I'll demonstrate how it might be used. There are
actually two ways I would suggest doing this, depending on the frequency
of sets vs gets. If they are about equal, or sets are more frequent, I
suggest this class:

public class Node<V> {
private boolean useNew;
private V previousValue;
private V value;
private final Object lock = new Object();

public V getValue() {
synchronize(lock) {
return useNew ? value : previousValue;
}
}

public void setValue(V value, boolean useNew) {
synchronize(lock) {
previousValue = getValue();
this.value = value;
this.useNew = useNew;
}
}
}

If the sets are somewhat infrequent, I suggest the following class. It
will allow much faster access by multiple threads for getValue(). It
does have a small amount of overhead when setting the value.

public class Node<V> {
private volatile State<V> state = new State<V>(null, null, true);
private final Object setLock = new Object();

public V getValue() {
// volatile allows us to safely read a value.
return state.getValue();
}

public V setValue(V newValue, boolean useNew) {
// we need to serialize access here, otherwise we might get the
// wrong previous value.
synchronized(setLock) {
state = new State<V>(state.value, newValue, useNew);
}
}

// Note, this <V> is independent of the <V> in Node.
private static class State<V> {
private final V previousValue;
private final V newValue;
private volatile boolean V useNew;
public State(V previousValue, V newValue, boolean useNew) {
this.previousValue = previousValue;
this.newValue = newValue;
this.useNew = useNew;
}
public V getValue() {
return useNew ? newValue : previousValue;
}
}
}

 
Reply With Quote
 
Daniel Pitts
Guest
Posts: n/a
 
      12-14-2011
On 12/14/11 10:44 AM, Lew wrote:
> On Wednesday, December 14, 2011 9:53:37 AM UTC-8, Andreas Leitgeb wrote:
>> Saxo<(E-Mail Removed)> wrote:
>>> public class Node {
>>> AtomicBoolean useNewValue = new AtomicBoolean(false);
>>> private Object newValue = null;
>>> private Object previousValue = null;
>>> private Object lock = new Object();

>>
>> I think, you would at least have to declare these volatile.

>
> Nope, they use 'synchronized'. 'volatile' wouldn't work anyway, because these
> have to change together, so they must use 'synchronized'.

There are other ways to atomically change multiple "fields". See my
other post.
>> Otherwise, a different thread might e.g. still see an old
>> value in newValue, after the AtomicBoolean's value changes
>> to true.

True if the only change was to add volatile and remove synchronized.


 
Reply With Quote
 
Lew
Guest
Posts: n/a
 
      12-14-2011
Saxo wrote:
> I have a class Node as displayed below that holds a new value and the


First, good job with your SSCCE (http://sscce.org/). That was a well thought-
out and complete job.

Second, _never_ use TAB characters in code posts except in literals. To
indent, use two or four spaces per indent level. Two tends to fit better in
forum posts.

> previous value. Which one applies is determined by the value of
> useNewValue. In my application there is a list of such nodes where for
> each node the current value is replaced with a new one. The new values
> should become effective for the entire list all >at once< through an
> atomic change of useNewValue in every node. For that purpose, when the
> new value is set, for every node in the list the same AtomicBoolean
> instance is passed on to setNewValue(...), which is stored in
> useNewValueParam. When the commit is done, the value of this instance
> of AtomicBoolean is changed to true (this way the thread doing the
> commit does not have to enter the synchronized block as all the other
> threads calling aNode.get) and thus the new value of every node
> becomes visible at once to every thread calling aNode.get().
>
> public class Node {
>
> AtomicBoolean useNewValue = new AtomicBoolean(false);


A 'volatile boolean' should do here. Actually, a non-'volatile' variable will be just fine:

boolean useNewValue;

No need to set to 'false' what is already set to 'false'.

Why did you declare it package-private?

> private Object newValue = null;


Why do you redundantly set this to 'null'?

> private Object previousValue = null;
> private Object lock = new Object();


Why not use the instance itself as the lock?

> public Object get() {
> synchronized(lock) {
> if(useNewValue.get()) // 1
> return newValue; // 2
> return previousValue; // 3
> }
> }
>
> public void setNewValue(Object newValue, AtomicBoolean
> useNewValueParam) {


It is ridiculous to pass an 'AtomicBoolean'. You just need a 'boolean'.

> synchronized(lock) {
> if(this.useNewValue.get())
> previousValue = this.newValue;
> this.newValue = newValue;
> // useNewValueParam is allways set to false when setNewValue is
> called


That's patently untrue.

What the heck do you mean by this comment? I cannot make sense of it.

> this.useNewValue = useNewValueParam;


You write a very confusing logic here. Is 'useNewValueParam' (terrible name, BTW) meant to affect the next time the accessor is called?

If so, you've pretty much thrown all your concurrency out the window. Any number of 'set' calls could occur, each flipping your boolean the other way, and you'll never know whether it's going to land butter side up.

If all you care about is that each reader see the correct current state whatever it may be after whatever number of setters, then fine.

Regardless, you need to document the heck out of what you intend to do withthis parameter. What the heck are you even trying to accomplish?

> }
> }
> }
>
> My question is now whether this approach is free of race conditions or
> starvation issues if implemented as described above. I have some


You over-implemented it by a mile.

Use just one lock.

> doubts whether everything is fine here as useNewValue is changed by
> the commit thread by reference without entering synchronized(lock)
> { ... }. So is everything still fine if a context switch happens
> between line 1 and 2 or between line 1 and 3? It would be for sure if
> the commit thread entered the synchronized(lock) { ... } block, but it
> does not (changing to the new values all at once wouldn't be possible
> otherwise).


You have synchronized those lines. They are all in the same critical section. All accesses are covered by the same lock (plus several other unnecessary ones). You're good.

Except for how you coded it, that is.

Use the instance itself as the monitor, unless you really, really need a separate one. It would be kind to maintainers to comment your implementationchoice, and that in turn forces you to have a darned good reason.

Throwing a crapload of locks at a problem willy-nilly is superstitious programming. That is not effective. Don't do it.

*Think* about what you're doing. What references have you checked to improve your ability to reason about concurrent programming?

Seriously, which ones have you read?

I really am asking.

Brian Goetz's _Java Concurrency in Practice_ is an excellent resource.

You synchronize each block of reads (accesses) with the same monitor that you use for each block of writes (mutations). You have the same actors in each block, no more, no less. In your example, you have three. And insteadof 'Object', consider using generics.

public class Node<V> // off the top of my head, not even compiled
{
private V value;
private V previous;

private boolean useCurrent;

synchronized public V getValue()
{
return useCurrent? value : previous;
}

synchronized public void setValue(V value, boolean useCurrent)
{
previous = this.value;
this.value = value;
this.useCurrent = useCurrent;
}
}

This code will not behave the same as yours, but I presumptuously concludedthat your code did the wrong thing. Either way, you can see how simple you should make it. It should be quite straightforward to reason about how this code will work.

--
Lew
 
Reply With Quote
 
Saxo
Guest
Posts: n/a
 
      12-14-2011
On Dec 14, 6:53*pm, Andreas Leitgeb <(E-Mail Removed)>
wrote:
> Saxo <(E-Mail Removed)> wrote:
> > public class Node {
> > * *AtomicBoolean useNewValue = new AtomicBoolean(false);
> > * *private Object newValue = null;
> > * *private Object previousValue = null;
> > * *private Object lock = new Object();

>
> I think, you would at least have to declare these volatile.
> Otherwise, a different thread might e.g. still see an old
> value in newValue, after the AtomicBoolean's value changes
> to true.


Yes, good point. Thanks! The commit thread that changes useNewValue on
commit from false to true by reference from outside the synchronized
block does not enter the synchronized block. Therefore, the contents
of these values might still be cached for threads calling get().
 
Reply With Quote
 
Saxo
Guest
Posts: n/a
 
      12-14-2011
On Dec 14, 7:53*pm, Daniel Pitts
<(E-Mail Removed)> wrote:

> If it is always false, why pass it in at all? I don't believe this comment.> * * * * * * * * * *this.useNewValue = useNewValueParam;


It is passed in so that the visibility change from previousValue to
newValue can be done with a single atomic change of useNewValue by
reference from outside the synchronized block for all nodes in the
list at once. This is also the reason why boolean wouldn't work as not
accessible by reference and why it has to be aAtomicBoolean as the
commit thread changing the value of useNewValue does not enter the
synchronized block.


>
> The threads are all serialized because of the synchronize(lock).


This is true for all threads calling aNode.get(), but not for the
single commit thread that changes useNewValue atomically by reference
from outside the synchronized block.
 
Reply With Quote
 
Saxo
Guest
Posts: n/a
 
      12-14-2011
On Dec 14, 8:04*pm, Lew <(E-Mail Removed)> wrote:
> Saxo wrote:
>
> > * public void setNewValue(Object newValue, AtomicBoolean
> > useNewValueParam) {

>
> It is ridiculous to pass an 'AtomicBoolean'. *You just need a 'boolean'..


Well, no. useNewValue is changed by reference. That's why it has to
been an object. When it is changed it is not protected by the
synchronized block since it is changed by reference from the commit
threas.

> > * * synchronized(lock) {
> > * * if(this.useNewValue.get())
> > * * * previousValue = this.newValue;
> > * * * this.newValue = newValue;
> > * * * // useNewValueParam is allways set to false when setNewValue is
> > called

>
> That's patently untrue.
>
> What the heck do you mean by this comment? *I cannot make sense of it.
>
> > * * * this.useNewValue = useNewValueParam;

>


This way the single AtomicBoolean object is passed that will be
changed from false to true by reference, so that all new values become
visible for any thread calling aNode.get() "at once".

> You write a very confusing logic here. *Is 'useNewValueParam' (terriblename, BTW) meant to affect the next time the accessor is called?
>
> If so, you've pretty much thrown all your concurrency out the window. *Any number of 'set' calls could occur, each flipping your boolean the otherway, and you'll never know whether it's going to land butter side up.


Yes, that is why there is only a single commit thread at any time that
calls setNewValue and changes useNewValue. This is explained in my
initial post in the second block counting from below: "At the same
time there is never more than one thread iterating over the node list
calling setNewValue. This is made sure through serialization of
threads.

My initial post is quite a long read. I know ...

> Throwing a crapload of locks at a problem willy-nilly is superstitious programming. *That is not effective. *Don't do it.
>
> *Think* about what you're doing. *What references have you checked to improve your ability to reason about concurrent programming?
>
> Seriously, which ones have you read?
>
> I really am asking.


This is really funny and made me laugh. Thanks .

Regards, Oliver

 
Reply With Quote
 
Andreas Leitgeb
Guest
Posts: n/a
 
      12-14-2011
Lew <(E-Mail Removed)> wrote:
> On Wednesday, December 14, 2011 9:53:37 AM UTC-8, Andreas Leitgeb wrote:
>> Saxo <(E-Mail Removed)> wrote:
>> > public class Node {
>> > AtomicBoolean useNewValue = new AtomicBoolean(false);
>> > private Object newValue = null;
>> > private Object previousValue = null;
>> > private Object lock = new Object();

>> I think, you would at least have to declare these volatile.

> Nope, they use 'synchronized'.


You're right on that... I didn't look at the rest carefully
enough.

> 'volatile' wouldn't work anyway, because these
> have to change together, so they must use 'synchronized'.


I thought, that was the whole point of the code: first store
the new value in a separate var, then later do the switchover.
I even think, that the synchronized blocks would be redundant,
if the fields were volatile. Afterall, there wasn't any
check-and-set or similar combined operation involved.

From examples posted here during the last few years, I've come
to think, that one just cannot really understand concurrency
and memory-barriers. If one thinks he does, then he either
missed the hairier bits, or just doesn't (perhaps rightly so)
believe them.

>> Otherwise, a different thread might e.g. still see an old
>> value in newValue, after the AtomicBoolean's value changes
>> to true.


Doesn't volatile imply: "really look at what's in the field,
rather than what is in local CPU's cache" ?

 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
How to prevent from race conditions to share data between many process and thread in python mars Python 6 02-07-2007 08:52 AM
copyfile avoiding overwrites and race conditions manuelg@gmail.com Python 2 06-19-2006 06:29 PM
VHDL - processes, race conditions, & Verilog Taras_96 VHDL 7 04-05-2005 01:01 AM
race conditions/pulse width The Weiss Family VHDL 6 10-19-2004 02:47 PM
Mega Pixel race is like the Mhz Race Hugo Drax Digital Photography 7 01-12-2004 11:07 AM



Advertisments