Re: Peterson's Algorithm in java, sequencial instruction execution ?
Knute Johnson wrote:
Mike Schilling wrote:
<xmarlawx@gmail.com> wrote in message
news:1164416886.789925.124600@14g2000cws.googlegroups.com...
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.
Or declare them volatile.
--
Knute Johnson
email s/nospam/knute/
I think the reordering of instructions you are talking about is at the
machine code level. I don't know if Java's JVM will do this, but here
is what I would suspect.
Any two interacting instructions on the same thread (i.e, a write to a
memory location, and a later read) will appear in the same order.
However the following sequences may be considered to have the same
observable pattern:
Given locations A, B, and C;
Original:
Load A from constant
Load C From B
Test stuff in C
Load C From A
Test stuff in C
Load B from C
Variation 1:
Load C From B
Test stuff in C
Load A from constant
Load C From A
Load B from C
Test stuff in C
Variation 2:
Load C From B
Load A from constant
Test stuff in C
Load C From A
Test stuff in C
Load B from C
---
Although, I don't know if Java will reorder instructions in that way.
It very well could depend on both the Compiler implementation and the
JVM implementation.
Also, having a volatile variable could quite possibly prevent such
reordering. It probably would be worth reading the relavent sections of
the JLS. If there isn't an explicit requirement, then JVM implementors
are free to do what they want. If there IS an explicit requirement,
you will know your answer before hand.
---
Haven't said all of that, if this isn't a class project, but for a real
application, make sure you're not optimizing prematurely.
Syncronization CAN be a bottleneck, but often times the bottleneck
could be somewhere else. Also, the new java.util.concurrent packages
give you a very nice toolset to deal with concurrent applications.
But, if you are implementing Peterson's algorithm just for the practice
of implementing it, go right ahead. Try to implement it, and see if it
works.
Hope this helps.
Daniel.