Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.java.programmer > #10728 > unrolled thread

Question whether a problem with race conditions exists in this case

Back to article view | Back to comp.lang.java.programmer

Contents

  Question whether a problem with race conditions exists in this case Saxo <saxo123@gmx.de> - 2011-12-14 09:07 -0800
    Re: Question whether a problem with race conditions exists in this case Andreas Leitgeb <avl@gamma.logic.tuwien.ac.at> - 2011-12-14 17:53 +0000
      Re: Question whether a problem with race conditions exists in this case Lew <lewbloch@gmail.com> - 2011-12-14 10:44 -0800
        Re: Question whether a problem with race conditions exists in this case Daniel Pitts <newsgroup.nospam@virtualinfinity.net> - 2011-12-14 10:54 -0800
        Re: Question whether a problem with race conditions exists in this case Andreas Leitgeb <avl@gamma.logic.tuwien.ac.at> - 2011-12-14 21:15 +0000
          Re: Question whether a problem with race conditions exists in this case Tom Anderson <twic@urchin.earth.li> - 2011-12-15 14:58 +0000
            Re: Question whether a problem with race conditions exists in this case Saxo <saxo123@gmx.de> - 2011-12-15 08:40 -0800
            Re: Question whether a problem with race conditions exists in this case Gene Wirchenko <genew@ocis.net> - 2011-12-15 11:55 -0800
              Re: Question whether a problem with race conditions exists in this case Tom Anderson <twic@urchin.earth.li> - 2011-12-16 14:06 +0000
                Re: Question whether a problem with race conditions exists in this case Gene Wirchenko <genew@ocis.net> - 2011-12-16 10:09 -0800
      Re: Question whether a problem with race conditions exists in this case Saxo <saxo123@gmx.de> - 2011-12-14 11:47 -0800
    Re: Question whether a problem with race conditions exists in this case Daniel Pitts <newsgroup.nospam@virtualinfinity.net> - 2011-12-14 10:53 -0800
      Re: Question whether a problem with race conditions exists in this case Saxo <saxo123@gmx.de> - 2011-12-14 11:54 -0800
        Re: Question whether a problem with race conditions exists in this case Daniel Pitts <newsgroup.nospam@virtualinfinity.net> - 2011-12-15 16:38 -0800
          Re: Question whether a problem with race conditions exists in this case Saxo <saxo123@gmx.de> - 2011-12-15 23:01 -0800
            Re: Question whether a problem with race conditions exists in this case Daniel Pitts <newsgroup.nospam@virtualinfinity.net> - 2011-12-16 09:34 -0800
              Re: Question whether a problem with race conditions exists in this case Saxo <saxo123@gmx.de> - 2011-12-17 11:55 -0800
                Re: Question whether a problem with race conditions exists in this case Saxo <saxo123@gmx.de> - 2011-12-19 05:33 -0800
    Re: Question whether a problem with race conditions exists in this case Lew <lewbloch@gmail.com> - 2011-12-14 11:04 -0800
      Re: Question whether a problem with race conditions exists in this case Saxo <saxo123@gmx.de> - 2011-12-14 12:32 -0800
        Re: Question whether a problem with race conditions exists in this case markspace <-@.> - 2011-12-14 14:13 -0800
          Re: Question whether a problem with race conditions exists in this case Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-12-14 17:44 -0500
            Re: Question whether a problem with race conditions exists in this case Saxo <saxo123@gmx.de> - 2011-12-14 14:50 -0800
              Re: Question whether a problem with race conditions exists in this case markspace <-@.> - 2011-12-14 15:26 -0800
        Re: Question whether a problem with race conditions exists in this case Lew <lewbloch@gmail.com> - 2011-12-15 01:34 -0800
      Re: Question whether a problem with race conditions exists in this case Andreas Leitgeb <avl@gamma.logic.tuwien.ac.at> - 2011-12-14 21:38 +0000
    Re: Question whether a problem with race conditions exists in this case Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-12-14 16:26 -0500
      Re: Question whether a problem with race conditions exists in this case Saxo <saxo123@gmx.de> - 2011-12-14 13:57 -0800
        Re: Question whether a problem with race conditions exists in this case Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-12-14 18:05 -0500
          Re: Question whether a problem with race conditions exists in this case Saxo <saxo123@gmx.de> - 2011-12-14 23:25 -0800
            Re: Question whether a problem with race conditions exists in this case Saxo <saxo123@gmx.de> - 2011-12-14 23:28 -0800
        Re: Question whether a problem with race conditions exists in this case Tom Anderson <twic@urchin.earth.li> - 2011-12-15 14:44 +0000
          Re: Question whether a problem with race conditions exists in this case Lew <lewbloch@gmail.com> - 2011-12-16 08:27 -0800
            Re: Question whether a problem with race conditions exists in this case Daniel Pitts <newsgroup.nospam@virtualinfinity.net> - 2011-12-16 09:41 -0800
              Re: Question whether a problem with race conditions exists in this case Tom Anderson <twic@urchin.earth.li> - 2011-12-16 18:51 +0000
            Re: Question whether a problem with race conditions exists in this case Tom Anderson <twic@urchin.earth.li> - 2011-12-16 18:50 +0000
      Re: Question whether a problem with race conditions exists in this case Saxo <saxo123@gmx.de> - 2011-12-14 14:13 -0800
        Re: Question whether a problem with race conditions exists in this case Lew <lewbloch@gmail.com> - 2011-12-14 16:55 -0800

Page 1 of 2  [1] 2  Next page →

#10728 — Question whether a problem with race conditions exists in this case

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

[toc] | [next] | [standalone]

#10731

Saxo <saxo123@gmx.de> 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.

[toc] | [prev] | [next] | [standalone]

#10734

On Wednesday, December 14, 2011 9:53:37 AM UTC-8, Andreas Leitgeb wrote:
> Saxo <sax...@gmx.de> 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

[toc] | [prev] | [next] | [standalone]

#10736

On 12/14/11 10:44 AM, Lew wrote:
> On Wednesday, December 14, 2011 9:53:37 AM UTC-8, Andreas Leitgeb wrote:
>> Saxo<sax...@gmx.de>  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.

[toc] | [prev] | [next] | [standalone]

#10743

Lew <lewbloch@gmail.com> wrote:
> On Wednesday, December 14, 2011 9:53:37 AM UTC-8, Andreas Leitgeb wrote:
>> Saxo <sax...@gmx.de> 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" ?

[toc] | [prev] | [next] | [standalone]

#10776

On Wed, 14 Dec 2011, Andreas Leitgeb wrote:

> 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.

Really?

I have come to think that to understand concurrency and the effects of 
memory barriers, one must think *strictly* and *only* in terms of 
happens-before relationships, as specified by the JLS. The whole of 
section 17.4 is relevant, with 17.4.5 being the heart of the matter:

http://java.sun.com/docs/books/jls/third_edition/html/memory.html#17.4

The rules for working out happens-before relationships are simple. At 
least, the fundamental idea is simple; the details of exactly when a 
relationship arises are less simple, but if you know the few most 
important ones, you will be fine most of the time. *Every Java programmer 
should know these rules*.

To paraphrase the JLS slightly, they are:

1. If x and y are actions of the same thread and x comes before y in 
program order, then x happens before y

('actions' mostly means reads and writes on memory, and a few other, less 
important things; 'program order' means the order of actions within a 
single thread)

2. If x happens before y, and y happens before z, then x happens before z

3. The release of a lock happens before any subsequent acquisition of that 
lock

4. A write to a volatile variable happens before any subsequent read of 
that variable

There are further rules about interruption, thread birth and death, and 
object initialisation, but they are significantly less important. I still 
think everyone ought to know them, but i will understand if they don't (i 
don't know the ones about interruption and thread lifecycle off the top of 
my head!).

From these rules, you can work out if there is a happens-before 
relationship between any two actions. Doing so is not necessarily trivial, 
but it is no more complex than, say, solving a sudoku problem. It's a 
question of applying the rules, and trying to find a chain of 
happens-before relationships. If you can't find one, you conclude one 
doesn't exist.

You don't need to know any more about memory barriers than that. The 
effects of memory barriers are as required by these rules.

tom

-- 
And the future is certain, give us time to work it out

[toc] | [prev] | [next] | [standalone]

#10777

All right, think a found a solution for my initial problem, which was
context switches bewtween lines 1,2,3:

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

Solution for the new Node class looks like this (hope it works out
well with indentation and line breaks):

package test.switchover;

import java.util.concurrent.atomic.AtomicBoolean;

public class SwitchableValue
{

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

    public SwitchableValue() {
      super();
    }

    public SwitchableValue(Object currentValue) {
      super();
      this.newValue = currentValue;
    }

    public void set(Object newValue, AtomicBoolean useNewValue, Object
switchOverLock) {
      synchronized (lock) {
        assert useNewValue.get() == false;
        this.switchOverLock = switchOverLock;
        this.useNewValue = useNewValue;
        this.previousValue = this.newValue;
        this.newValue = newValue;
      }
    }

    public Object get() {
        synchronized (lock) {
          if(switchOverLock == null) {
            // optimization to avoid 2 nested synchronized blocks
when
            // not switching over to the new value, which is mostly
the case
            return newValue;
	  }
        synchronized (switchOverLock) {
          // do the switch over, the if-then-else block should be
without
          // any problems caused by context switches in between as
done
          // from within the switchOverLock
          if(useNewValue.get()) {
            switchOverLock = null;
            useNewValue = null;
            return newValue;
          }
          return previousValue;
        }
      }
    }
}


Here is some code to run a test case:

package test.switchover;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.concurrent.atomic.AtomicBoolean;

public class SwitchOverTest {


  public static void main(String[] args)
  {
    final int maxValues = 100;
    List<Runnable> pollingRunnables = new ArrayList<Runnable>();
    final List<SwitchableValue> values = new
ArrayList<SwitchableValue>();
    final AtomicBoolean proceed = new AtomicBoolean(true);
    for (int i = 0; i < maxValues; i++) {
      final int j = i;
      values.add(new SwitchableValue(new Integer(i)));
      pollingRunnables.add(new Runnable() {
      int pos = j;
      public void run() {
      while(proceed.get()) {
      System.out.println("Value of runnable " + pos + ": " +
values.get(pos).get());
        try {
          Thread.sleep(1000);
        } catch (InterruptedException e) { }
      }
    });
  }

  Iterator<Runnable> it = pollingRunnables.iterator();
  while(it.hasNext()) {
    new Thread(it.next()).start();
  }

  try {
    Thread.sleep(2000);
  } catch (InterruptedException e) { }

  Object switchOverLock = new Object();
  AtomicBoolean useNewValue = new AtomicBoolean(false);

  for (int i = 0; i < maxValues; i++) {
    values.get(i).set(i + 1, useNewValue, switchOverLock);
  }

  synchronized (switchOverLock) {
    try {
      System.out.println("Now all output to the console is suspended,
because the switchOverLock is held by the commit thread.");
      System.out.println("Waiting for 4 seconds to be able to read the
message...");
      Thread.sleep(4000);
      System.out.println("All output to the console is resumed and the
values are all incremented by 1.");
      System.out.println("Waiting for 4 seconds to be able to read the
message...");
      Thread.sleep(4000);
    } catch (InterruptedException e) { }
    useNewValue.compareAndSet(false, true);
  }

  try {
    Thread.sleep(2000);
  } catch (InterruptedException e) { }

  System.out.println("stopping ...");
  proceed.compareAndSet(true, false);

  try {
    Thread.sleep(1000);
  } catch (InterruptedException e) { }

  System.out.println("done.");
  }
}

Cheers, Oliver

[toc] | [prev] | [next] | [standalone]

#10781

On Thu, 15 Dec 2011 14:58:04 +0000, Tom Anderson
<twic@urchin.earth.li> wrote:

[snip]

>The rules for working out happens-before relationships are simple. At 
>least, the fundamental idea is simple; the details of exactly when a 
>relationship arises are less simple, but if you know the few most 
>important ones, you will be fine most of the time. *Every Java programmer 
>should know these rules*.
>
>To paraphrase the JLS slightly, they are:
>
>1. If x and y are actions of the same thread and x comes before y in 
>program order, then x happens before y
>
>('actions' mostly means reads and writes on memory, and a few other, less 
>important things; 'program order' means the order of actions within a 
>single thread)

     Is this actually the case?  IIRC, C has an as-if rule.  An
implementation can break the rules if it can be guaranteed that the
result will be the same as if the rules were followed.

[snip]

Sincerely,

Gene Wirchenko

[toc] | [prev] | [next] | [standalone]

#10798

On Thu, 15 Dec 2011, Gene Wirchenko wrote:

> On Thu, 15 Dec 2011 14:58:04 +0000, Tom Anderson
> <twic@urchin.earth.li> wrote:
>
> [snip]
>
>> The rules for working out happens-before relationships are simple. At
>> least, the fundamental idea is simple; the details of exactly when a
>> relationship arises are less simple, but if you know the few most
>> important ones, you will be fine most of the time. *Every Java programmer
>> should know these rules*.
>>
>> To paraphrase the JLS slightly, they are:
>>
>> 1. If x and y are actions of the same thread and x comes before y in
>> program order, then x happens before y
>>
>> ('actions' mostly means reads and writes on memory, and a few other, less
>> important things; 'program order' means the order of actions within a
>> single thread)
>
>     Is this actually the case?  IIRC, C has an as-if rule.  An
> implementation can break the rules if it can be guaranteed that the
> result will be the same as if the rules were followed.

Possibly. But i don't really know what such a rule really even means; how 
could you have a rule that banned as-if behaviour? How would that be 
enforced? How could you tell if it was being broken? Isn't there an 
implicit as-if rule in every specification? It seems like a meaningless 
thing to state explicitly.

tom

-- 
That's no moon!

[toc] | [prev] | [next] | [standalone]

#10805

On Fri, 16 Dec 2011 14:06:06 +0000, Tom Anderson
<twic@urchin.earth.li> wrote:

>On Thu, 15 Dec 2011, Gene Wirchenko wrote:
>
>> On Thu, 15 Dec 2011 14:58:04 +0000, Tom Anderson
>> <twic@urchin.earth.li> wrote:
>>
>> [snip]
>>
>>> The rules for working out happens-before relationships are simple. At
>>> least, the fundamental idea is simple; the details of exactly when a
>>> relationship arises are less simple, but if you know the few most
>>> important ones, you will be fine most of the time. *Every Java programmer
>>> should know these rules*.
>>>
>>> To paraphrase the JLS slightly, they are:
>>>
>>> 1. If x and y are actions of the same thread and x comes before y in
>>> program order, then x happens before y
>>>
>>> ('actions' mostly means reads and writes on memory, and a few other, less
>>> important things; 'program order' means the order of actions within a
>>> single thread)
>>
>>     Is this actually the case?  IIRC, C has an as-if rule.  An
>> implementation can break the rules if it can be guaranteed that the
>> result will be the same as if the rules were followed.
>
>Possibly. But i don't really know what such a rule really even means; how 
>could you have a rule that banned as-if behaviour? How would that be 
>enforced? How could you tell if it was being broken? Isn't there an 
>implicit as-if rule in every specification? It seems like a meaningless 
>thing to state explicitly.

     A language might have a rule that a certain case must be handled
in a certain way.

     If a compiler could determine in code analysis that that case
could never occur, then it could omit generating code that handled
that case.

Sincerely,

Gene Wirchenko

[toc] | [prev] | [next] | [standalone]

#10740

On Dec 14, 6:53 pm, Andreas Leitgeb <a...@gamma.logic.tuwien.ac.at>
wrote:
> Saxo <saxo...@gmx.de> 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().

[toc] | [prev] | [next] | [standalone]

#10735

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;
       }
    }
}

[toc] | [prev] | [next] | [standalone]

#10741

On Dec 14, 7:53 pm, Daniel Pitts
<newsgroup.nos...@virtualinfinity.net> 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.

[toc] | [prev] | [next] | [standalone]

#10784

On 12/14/11 11:54 AM, Saxo wrote:
> On Dec 14, 7:53 pm, Daniel Pitts
> <newsgroup.nos...@virtualinfinity.net>  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.
This sounds like the wrong reason to use AtomicBoolean, but perhaps I'm 
not understanding your use-case.

Hmm, actually, now I think I do...  Its kind of a transaction thing, 
isn't it?

Basically, you want to commit a change only under some circumstance, and 
you want the "last to set before they commit" to win on commit.

Hmm... Interesting. Have you looked at AtomicReference, or 
AtomicStampedReference? I think they do exactly what you're trying to do.

<http://docs.oracle.com/javase/6/docs/api/java/util/concurrent/atomic/AtomicReference.html>
<http://docs.oracle.com/javase/6/docs/api/java/util/concurrent/atomic/AtomicStampedReference.html>

For example:
AtomicReference<V> reference;

public void process() {
     final V oldValue = reference.get();
     V result = doSomeProcessing(oldValue);
     // commit phase:
     reference.compareAndSet(oldValue, result);
}

OR, if you need to only commit if there haven't been *any* other changes:


AtomicStampedReference<V> reference;

public void process() {
      final int[] stampHolder = new int[1];
      final V oldValue = reference.get(stampHolder);
      V result = doSomeProcessing(oldValue);
      // commit phase:
      reference.compareAndSet(oldValue, result, stampHolder[0],
                             stampHolder[0]+1);
}


The reason you might want Stamped is in the following situation:

Thread 1 grabs value "A".
Thread 2 grabs value "A".
Thread 1 uses CAS for "A" to "B", so value is now committed as "B"
Thread 3 grabs value "B"
Thread 3 uses CAS for "B" to "A", so value is now committed as "A"
Thread 1 uses CAS for "A" to C".  The result is different for stamped vs 
unstamped...

Stamped, the result is "A" remains the value (because the stamp has 
changed so the CAS fails).  For unstamped, the value is "C", because the 
old value was "A".

Decide on which outcome you care about in that approach, in order to 
decide whether to use Stamped or not.

[toc] | [prev] | [next] | [standalone]

#10789

On Dec 16, 1:38 am, Daniel Pitts
<newsgroup.nos...@virtualinfinity.net> wrote:

>
> Hmm, actually, now I think I do...  Its kind of a transaction thing,
> isn't it?

Hi Daniel, the AtomicBoolean ist not needed any more in my second
approach where useNewValue is protected by the switchOverLock lock.
But it has to be an object, of which the value can be changed by
reference when the commit is to be donne atomically "in one go" for
all nodes, which cannot be done with java.util.Boolean since it is
constant. I would have to create own MyChangeableBoolean class. Looked
to me like an overkill and therefore held on to that AtomicBoolean
instance. For the real thing I need to add a comment explaining this
or create that MyChangeableBoolean class ;-)

> Basically, you want to commit a change only under some circumstance, and
> you want the "last to set before they commit" to win on commit.
>
> Hmm... Interesting. Have you looked at AtomicReference, or
> AtomicStampedReference? I think they do exactly what you're trying to do.

I had a short look at AtomicStampedReference. Maybe it was too short
and I should have a closer look at it.

> AtomicStampedReference<V> reference;
>
> public void process() {
>       final int[] stampHolder = new int[1];
>       final V oldValue = reference.get(stampHolder);
>       V result = doSomeProcessing(oldValue);
>       // commit phase:
>       reference.compareAndSet(oldValue, result, stampHolder[0],
>                              stampHolder[0]+1);
>
> }


Yes, I see. Problem is that there is a list of SwitchableValues
(because several changes were made in the transaction) and they all
need to switch values "in one go" for the commit to be atomic, e.g.
all changes of the transaction become visible at once or not at all.
Have to see whether this can be done with such an
AtomicStampedReference.

> The reason you might want Stamped is in the following situation:
>
> Thread 1 grabs value "A".
> Thread 2 grabs value "A".
> Thread 1 uses CAS for "A" to "B", so value is now committed as "B"
> Thread 3 grabs value "B"
> Thread 3 uses CAS for "B" to "A", so value is now committed as "A"
> Thread 1 uses CAS for "A" to C".  The result is different for stamped vs
> unstamped...
>
> Stamped, the result is "A" remains the value (because the stamp has
> changed so the CAS fails).  For unstamped, the value is "C", because the
> old value was "A".
>
> Decide on which outcome you care about in that approach, in order to
> decide whether to use Stamped or not.

This is interesting. Have to go to work now and will have a closer
look at it later.

Regards, Oliver

[toc] | [prev] | [next] | [standalone]

#10801

On 12/15/11 11:01 PM, Saxo wrote:
> Yes, I see. Problem is that there is a list of SwitchableValues
> (because several changes were made in the transaction) and they all
> need to switch values "in one go" for the commit to be atomic, e.g.
> all changes of the transaction become visible at once or not at all.
> Have to see whether this can be done with such an
> AtomicStampedReference.

Okay, based on your other thread about transactions, I think you're 
starting to get a little being the scope of the original question here. 
  And general advice for transaction management is a little out of my 
league.  However, if I understood *exactly* your requirements, I might 
be able to give specific advice.

The approach you're currently taking can't be fixed to support two 
concurrent transactions that may interfere with each-other. You'd have 
to have some mechanism to detect a conflict and roll-back or retry in 
that case.

Is this purely a learning exercise or are you actually hoping that this 
code goes into production somewhere? If it is purely an experiment then 
kudos at that, but if not then I suggest escalating the problem to a 
more experienced developer.  These kinds of things you usually can't 
afford to get wrong. unless you have read and fully understood enough 
literature on the subject, it is easy to get wrong.

Good luck! This *is* a field I've been interested in, so please keep 
following up with your findings!

Thanks,
Daniel.

[toc] | [prev] | [next] | [standalone]

#10838

On Dec 16, 6:34 pm, Daniel Pitts
<newsgroup.nos...@virtualinfinity.net> wrote:
> On 12/15/11 11:01 PM, Saxo wrote:
>

> The approach you're currently taking can't be fixed to support two
> concurrent transactions that may interfere with each-other. You'd have
> to have some mechanism to detect a conflict and roll-back or retry in
> that case.

Hi Daniel, you are exactly right with this and I have also thought
about the problem with interference. What I want to do is a map
implementation that supports optimistic locking. I tried to describe
this in brief in my post from Dec 15, 8:25 am (or my 8th post in this
thread, I don't know whether the same time stamps are displayed for
you over there):

(1) BackingMap backingMap = new BackingMap();

(2) LocalMap map1 = new LocalMap(backingMap);
(3) map1.begin();
(4) Node node1 = map1.get(key1);
(5) node1.value = newValue;
(6) Node node2 = map1.putAndGet(key1, node1);
(7) map1.commit(); // or map1.mergeCommit();

A transaction knows the keys of the values that were changed (because
either a put or a remove was done using those keys). If the
transaction commits, the map needs to check whether some other
transaction is currently running its commit process and whether at
least one of the keys are shared with that committing transaction. If
so, it has to wait till the other transaction has finished committing.
If two transaction that both want to commit don't share any keys the
can commit in parallel. However, the user needs to have issued what I
called in line (7) above a merge commit. In that case keys are
"merged" in in parallel. If the entire map must have remained
unchanged from the beginning of the transaction to the end, an
ordinary commit is issued (map1.commit() in line 7) and the thing
fails fast if the map's change counter has changed meanwhile.

> Is this purely a learning exercise or are you actually hoping that this
> code goes into production somewhere? If it is purely an experiment then
> kudos at that, but if not then I suggest escalating the problem to a
> more experienced developer.  These kinds of things you usually can't
> afford to get wrong. unless you have read and fully understood enough
> literature on the subject, it is easy to get wrong.

This is a fun/learning exercise. But I still want to develop something
that one day can be used for some real purpose. The critical difficult
part is the commit phase. I might stick to some STM framework like
Deuce STM (http://www.deucestm.org) and let Deuce do the difficult
things:

@Atomic
public void commit() {
// no serialization of transactions or other critical things need to
be done
// because marked atomic and hence Deuce will take care of this
}

But that would only be done as an option to calm people down. The fun
part is really to develop a solution of my own and implement
it ... ;-).

> Good luck! This *is* a field I've been interested in, so please keep
> following up with your findings!
>
> Thanks,
> Daniel.

Thanks for the good wishes! Will take some time till I have something
finished as I don't have that much time for it. But I will keep you
informed :-).

Regards, Oliver

[toc] | [prev] | [next] | [standalone]

#10870

On Dec 17, 8:55 pm, Saxo <saxo...@gmx.de> wrote:
> On Dec 16, 6:34 pm, Daniel Pitts
>
> <newsgroup.nos...@virtualinfinity.net> wrote:
> > On 12/15/11 11:01 PM, Saxo wrote:
>
> > The approach you're currently taking can't be fixed to support two
> > concurrent transactions that may interfere with each-other. You'd have
> > to have some mechanism to detect a conflict and roll-back or retry in
> > that case.
>
> Hi Daniel, you are exactly right with this and I have also thought
> about the problem with interference. What I want to do is a map
> implementation that supports optimistic locking. I tried to describe
> this in brief in my post from Dec 15, 8:25 am (or my 8th post in this
> thread, I don't know whether the same time stamps are displayed for
> you over there):
>
> (1) BackingMap backingMap = new BackingMap();
>
> (2) LocalMap map1 = new LocalMap(backingMap);
> (3) map1.begin();
> (4) Node node1 = map1.get(key1);
> (5) node1.value = newValue;
> (6) Node node2 = map1.putAndGet(key1, node1);
> (7) map1.commit(); // or map1.mergeCommit();

You know what? Coming to think of it, the calling thread that issues
map1.commit() must not carry out the commit. Otherwise some potential
for a deadlock is created. For the commit a new thread has to be
spawned by the BackingMap...

[toc] | [prev] | [next] | [standalone]

#10739

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 with this 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 implementation choice, 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 instead of '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 concluded that 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

[toc] | [prev] | [next] | [standalone]

#10742

On Dec 14, 8:04 pm, Lew <lewbl...@gmail.com> 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' (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.

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

[toc] | [prev] | [next] | [standalone]

Page 1 of 2  [1] 2  Next page →

Back to top | Article view | comp.lang.java.programmer

csiph-web