Peterson's Algorithm in java, sequencial instruction execution ?

[xmarlawx]

Hello guys,

I have to implement the Peterson's algorithm in java.
For who of you which is not aware about it, is a low level concurrency
solution for two threads
that want to use a shared resource.
The algorithm use three variables, two flags (booleans) and a turn
indicator (usually implemented as an int, but possibly a boolean would
work as well).

More information about the algorithm here :
http://en.wikipedia.org/wiki/Peterson's_algorithm

Now, is really easy to implement it and in theory I won't need to use
any synchronization
construct available in java (such as synchronized keyword) since the
shared memory should be enough.

Here comes my problem : I learned that some hardware system don't
necessarily execute the instructions
in a FIFO order, such as, they don't execute necessarily instructions
in the same order as they are written in the source code (and then
compiled) to improve efficency.
All this in a standard sequencial program (not concurrent).
Such hardware, to support concurrency, has special "atomic" instrucion
such as test & set.

What about the jvm ?
Because if this is the case (such as execution of the instructions not
in a sequencial way), the instructions in my program could be executed
in an order that is not the one I wrote it that will eventually result
in an invalid state of the program.

Thank you for any information.

 

[sgoo]

Are you talking about "17.4.5 Happens-before Order"? This is the only
place I know in Java that execution sequence may be different with code
wrting sequence.
http://java.sun.com/docs/books/jls/third_edition/html/memory.html#17.4.5

 

[xmarlawx]

Are you talking about "17.4.5 Happens-before Order"? This is the only
place I know in Java that execution sequence may be different with code
wrting sequence.
http://java.sun.com/docs/books/jls/third_edition/html/memory.html#17.4.5

I'm not specifically talking about that.
I just tried to find out what is the mechanism used by the JVM made by
Sun because
if that was such the case the Peterson's algorithm would be working.
In that case it would be necessary to use the synchronized keyword when
accessing the
two variables that would lead to spinlock if both evaluating to true.

Thanks for the speed!!

 

[Mike Schilling]

Hello guys,

I have to implement the Peterson's algorithm in java.
For who of you which is not aware about it, is a low level concurrency
solution for two threads
that want to use a shared resource.
The algorithm use three variables, two flags (booleans) and a turn
indicator (usually implemented as an int, but possibly a boolean would
work as well).

More information about the algorithm here :
http://en.wikipedia.org/wiki/Peterson's_algorithm

Now, is really easy to implement it and in theory I won't need to use
any synchronization
construct available in java (such as synchronized keyword) since the
shared memory should be enough.

If you want to guarantee that thread A sees a change to memory made by
thread B, you need to use synchronization.

 

[xmarlawx]

If you want to guarantee that thread A sees a change to memory made by
thread B, you need to use synchronization.

I'm sorry Mike, but if you refer to standard Java synchronization
facility I believe you are wrong.
This is exactly what Peterson's algorithm is suppose to do,
synchronization, without the use
of language construct such as "synchronized" or particular hardware
instructions such as "Test & Set", the so called atomic actions.

Also, my point is not related to threads, but only to simple sequence
of instructions in a
program (in this case written in Java for a recent JVM 5.*).
I know that the instructions of different running threads can be (and
will be) interleaved but I've got to read on wikipedia that also some
instructions, in normal programs can be interleaved for efficency
purpose and that's what would make the whole algorithm to not work
anymore thus having the two threads not synchronized anymore.

The link I've wrote in the first message would explain more.

Thanks again.

 

[Patricia Shanahan]

Hello guys,

Guys? I hope you don't really mean that.

I have to implement the Peterson's algorithm in java.
For who of you which is not aware about it, is a low level concurrency
solution for two threads
that want to use a shared resource.
The algorithm use three variables, two flags (booleans) and a turn
indicator (usually implemented as an int, but possibly a boolean would
work as well).

Are you aware of the "volatile" keyword?
http://java.sun.com/docs/books/jls/second_edition/html/classes.doc.html#36930

Patricia

 

[Knute Johnson]

If you want to guarantee that thread A sees a change to memory made by
thread B, you need to use synchronization.

Or declare them volatile.

 

[Chris Thomasson]

Hello guys,

I have to implement the Peterson's algorithm in java.

Why?

Here is an implementation is x86:

http://groups.google.com/group/comp.programming.threads/browse_frm/thread/c49c0658e2607317

I guess you could use Java volatiles... However, you still need the
#StoreLoad memory barrier after the acquisition logic...

 

[Chris Thomasson]

[comp.programming.threads added]

Why?

Here is an implementation is x86:

http://groups.google.com/group/comp.programming.threads/browse_frm/thread/c49c0658e2607317

I guess you could use Java volatiles... However, you still need the
#StoreLoad memory barrier after the acquisition logic...

Also, refer to the last part of the following post:

http://groups.google.com/group/comp.arch/msg/c6f096adecdd0369


http://groups.google.com/group/comp.programming.threads/browse_frm/thread/e07adf138f0091d


Also, if you know that you are on an x86, you can use this trick:

http://groups.google.com/group/comp.programming.threads/msg/e2e6d69e8b7b1b23


http://groups.google.com/group/comp.programming.threads/msg/ca2f1af4552233df



Any thoughts?

 

[Chris Thomasson]

Petersons algorithm should be implemented in assembly language without using
any atomic operations. Alls you need are memory barriers.

 

[Chris Uppal]

Now, is really easy to implement it and in theory I won't need to use
any synchronization
construct available in java (such as synchronized keyword) since the
shared memory should be enough.

You /have/ to use either synchronised blocks/methods or mark the shared
variables as "volatile". Period. Without that there /is no guarantee at all/
that any memory actually will be shared.

E.g (pseudo-code from the Wikipedia article):

flag[0] = 0
flag[1] = 0
turn = 0

flag[0] = 1
turn = 1
while( flag[1] && turn == 1 );
// do nothing
// critical section
...
// end of critical section
flag[0] = 0

There is nothing at all to stop the JIT (or even javac, though it won't do it)
optimising out the test at the head of the while loop (turning it into an
unconditional infinite loop), since the values of flag[1] and turn are already
statically known. Alternatively, it could generate code which copied the
values from the "shared" variables into local store (for faster access) before
the loop started, and didn't look at the original values thereafter -- which
would have the same functional effect.

If you don't tell Java that a shared value may change, then it is at liberty to
assume that it won't.

-- chris

 

[Patricia Shanahan]

Petersons algorithm should be implemented in assembly language without using
any atomic operations. Alls you need are memory barriers.

Yes, but I think the OP's problem is to implement it in Java, not
assembly language.

Volatile declarations for the implementing variables should be sufficient.

"Let action A be a use or assign by thread T on variable V, let action F
be the load or store associated with A, and let action P be the read or
write of V that corresponds to F. Similarly, let action B be a use or
assign by thread T on variable W, let action G be the load or store
associated with B, and let action Q be the read or write of W that
corresponds to G. If A precedes B, then P must precede Q. (Less
formally: actions 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.)"

http://java.sun.com/docs/books/jls/second_edition/html/memory.doc.html#28330

17.7 Rules for Volatile Variables

Patricia

 

[xmarlawx]

Guys? I hope you don't really mean that.

I'm sorry, I just thought you could say that as in " Hey people".
I'm not english mother toungue

Anyway, what I do right now is to have a boolean wrapped in a class
with accessor methods and an int wrapped as well , both created in an
applet and then passed in the constractor of the two threads such as
they can both access all.
Of course one thread will only read one flag and write one, plus the
turn while the other would do the same symmetrically to the other flag.

Before writing more I'm going to read more on the volatile keyword
since I wasn't aware of it.

Thank you all a lot.
I also found on an other book (operating systems) that Peterson's
solutions is not garanteed to work since some hardware platform
optimize the code in a way that could mess up the algorithm.

I quite confused now, to implement an algorithm that is trying to
achive synchronization I have to use some other synchronization
facility.
It just sounds odd in my brain.
Will let you know as soon as I know more

BYe

 

[Patricia Shanahan]

Thank you all a lot.
I also found on an other book (operating systems) that Peterson's
solutions is not garanteed to work since some hardware platform
optimize the code in a way that could mess up the algorithm.

....

There are many layers of optimization: compiler, JVM, and hardware.
However, you should care about what is guaranteed to your program, not
about how it is achieved.

Effectively, the JLS is a contract. The Java compiler and JVM can do all
the optimization they like as long as the result follows that contract.
On the other hand, they must do whatever it takes to ensure that the
execution of the Java program does follow the JLS even in the face of
lower level optimization. That may mean, for example, adding memory
barrier instructions to code that accesses volatile fields.

I'm an expert on SPARC memory order and cache coherence issues. Even
when running on Sun systems, I've never found that knowledge in the
least bit useful for understanding Java program behavior.

You should aim to understand the ordering rules Peterson's algorithm
needs, and then look at the JLS to see what it takes to achieve those
ordering rules in Java.

Incidentally, I'm assuming you are doing this as an exercise in Java
data sharing, not for any practical use. Synchronized blocks are far
simpler, and likely to be more efficient.

Patricia

 

[Chris Thomasson]

Thank you all a lot.
I also found on an other book (operating systems) that Peterson's
solutions is not garanteed to work since some hardware platform
optimize the code in a way that could mess up the algorithm. ...

[...]


I'm an expert on SPARC memory order and cache coherence issues.

Very good to here! I am also an expert on the SPARC wrt memory, coherency,
and all sorts of lock-free programming issues. Our skills with the SPARC are
going to be very valuable in this Concurrency Revolution we are currently
in. For sure.

We need more experts in this area!

Even
when running on Sun systems, I've never found that knowledge in the
least bit useful for understanding Java program behavior.

It helps when you try to create lock-free reader patterns in Java. Your
expertise in the SPARC is sure to help you in a boat load of issues that
deal with advanced multi-threading techniques... the SPARC membar
instructions granularity is good enough to basically implement any type of
memory barrier. Its good to know exactly what memory barriers are needed to
achieve the load-acquire store-release semantics of Java. The memory model
is fundamental. I would highlight the fact that your an expert in the SPARC
in your resume. It only has to help. Big time...

This is a IMHO of course...

;^)

 

[Chris Thomasson]

I quite confused now, to implement an algorithm that is trying to
achive synchronization I have to use some other synchronization
facility.

Yup. You have to ensure that you handle the #StoreLoad dependencies wrt lock
acquisition, and the #LoadStore dependency associated with lock release.
Petersons algorithm is no different. BTW, creating Petersons algorithm
directly in Java will force you to execute more memory barriers than you
need. It will be overkill. Better off implementing in Assembly Language,
create a C API/ABI, and call than from Java.

It just sounds odd in my brain.
Will let you know as soon as I know more

You can get it working in Java for sure... But, again, IMHO, it will be
overkill...

 

[Chris Thomasson]

Yes, but I think the OP's problem is to implement it in Java, not
assembly language.

Volatile declarations for the implementing variables should be sufficient.

Yeah... However, you have to do a full memory barrier in order to get the
#StoreLoad barrier after the Petersons lock acquisition logic... The
store-release barrier doesn't prevent subsequent loads to other locations
from migrating above it.

 

[Patricia Shanahan]

Yeah... However, you have to do a full memory barrier in order to get the
#StoreLoad barrier after the Petersons lock acquisition logic... The
store-release barrier doesn't prevent subsequent loads to other locations
from migrating above it.

Or make any shared data accessed in the critical region volatile.

It would be SO much simpler to make the critical regions into
synchronized blocks and let the JVM sort it out.

Patricia

 

[xmarlawx]

Or make any shared data accessed in the critical region volatile.

It would be SO much simpler to make the critical regions into
synchronized blocks and let the JVM sort it out.

That is what I'm going to do.
Use any shared memory (variable) as volatile inside the threads.
And, yes, it is an exercise and it won't be used in any real
application.
I don't have choice about the language, is to be done in java.

I will try my best to not use the synchronized blocks (either nested or
not)
since it can be confusing.Volatile seems exactly what I need.

I found this as well :
http://www.javaperformancetuning.com/news/qotm030.shtml

Which explain the differences between synchronized and volatile only.

Again, I must say, thank you all.

 

[Patricia Shanahan]

Chris Thomasson wrote:
.....

Those barriers will be executed every time you load/store into a volatile
variable. Keep that in mind. Go with Patricia's advice and just use a normal
mutex (e.g., sync block). You will use far fewer barriers that way... IMHO,
volatile on Java is way too strict IMHO. The granularity is very, very poor.
Java doesn't support loads with data-dependencies, or naked atomic
loads/stores... Or, many other types of fine-grain memory barriers..

As I understand the situation, this is an exercise in writing
synchronization code, not a practical piece of programming. Possibly,
the OP is supposed to be learning the hard way how much easier and more
efficient it is to use Java's own higher level synchronization features.

Patricia