Home | Contact Us | FAQ | Search & Site Map | Link to Us
Sign In | Join | Other 45 Sites in Network
HomeAnnouncementsWhite Papers
Discussion GroupsFirst AidDatabasesJavaBeansGUIJava 3DVirtual MachineCORBASecurityToolsGeneral
Java DirectoryOpen Source ProjectsSample Book ChaptersUser GroupsWeb Resources
Related Topics
Databases.NETMore Topics ...

Java Forum / General / December 2006

Tip: Looking for answers? Try searching our database.

Peterson's Algorithm in java, sequencial instruction execution ?

Thread view: 
xmarlawx@gmail.com - 25 Nov 2006 01:08 GMT
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 - 25 Nov 2006 01:12 GMT
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@gmail.com - 25 Nov 2006 01:59 GMT
> 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 - 25 Nov 2006 02:29 GMT
> Hello guys,
>
[quoted text clipped - 13 lines]
> 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@gmail.com - 25 Nov 2006 04:26 GMT
> 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.
Mike Schilling - 25 Nov 2006 19:48 GMT
>> 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.

I did overstate; it's also possible to make your shared-memory volatile.
But without one or the other, there is no guarantee in the Java memory model
that a change made by one thread will be seen by another.
Mark Thornton - 25 Nov 2006 19:57 GMT
>>>If you want to guarantee that thread A sees a change to memory made by
>>>thread B, you need to use synchronization.
[quoted text clipped - 5 lines]
> But without one or the other, there is no guarantee in the Java memory model
> that a change made by one thread will be seen by another.

A third mechanism is provided by the classes in
java.util.concurrent.atomic (from Java 5).

Mark Thornton
Chris Thomasson - 25 Nov 2006 20:22 GMT
>>>>If you want to guarantee that thread A sees a change to memory made by
>>>>thread B, you need to use synchronization.
[quoted text clipped - 8 lines]
> A third mechanism is provided by the classes in
> java.util.concurrent.atomic (from Java 5).

Except that you can do Petersons algorithm without atomic operations (e.g.,
Interlocked). So, this would add even more overhead...
Mike  Schilling - 25 Nov 2006 22:03 GMT
>>>>If you want to guarantee that thread A sees a change to memory made by
>>>>thread B, you need to use synchronization.
[quoted text clipped - 8 lines]
> A third mechanism is provided by the classes in
> java.util.concurrent.atomic (from Java 5).

A mechanism not based on one of the first two?  What might that be?
Mark Thornton - 26 Nov 2006 09:03 GMT
Mike Schilling wrote:

>>>>>If you want to guarantee that thread A sees a change to memory made by
>>>>>thread B, you need to use synchronization.
[quoted text clipped - 10 lines]
>
> A mechanism not based on one of the first two?  What might that be?

The implementation of those classes is up to the VM and need not make
use of the regular synchronisation or volatile mechanisms. Many
processors have specific instructions that can be used to implement the
methods in those classes with lower overhead than using regular
synchronisation.

Mark Thornton
Chris Uppal - 26 Nov 2006 14:43 GMT
Mike Schilling wrote:

> > A third mechanism is provided by the classes in
> > java.util.concurrent.atomic (from Java 5).
>
> A mechanism not based on one of the first two?  What might that be?

Hackery in the JVM implementation, using private internal "magic" (/not/ JNI)
to replace the implementation of those features with custom machine-code
sequences.

   -- chris
Mike Schilling - 26 Nov 2006 16:06 GMT
> Mike Schilling wrote:
>
[quoted text clipped - 7 lines]
> to replace the implementation of those features with custom machine-code
> sequences.

Got that, but which features are they?  (My customers, and thus me, aren't
using 1.5 yet.)
Mark Thornton - 26 Nov 2006 16:21 GMT
>>Mike Schilling wrote:
>>
[quoted text clipped - 10 lines]
> Got that, but which features are they?  (My customers, and thus me, aren't
> using 1.5 yet.)

http://java.sun.com/javase/6/docs/api/java/util/concurrent/atomic/package-summar
y.html

Mike Schilling - 26 Nov 2006 19:44 GMT
>>>Mike Schilling wrote:
>>>
[quoted text clipped - 12 lines]
>
> http://java.sun.com/javase/6/docs/api/java/util/concurrent/atomic/package-summar
y.html

Which includes the sentence:

   The memory effects for accesses and updates of atomics generally follow
   the rules for volatiles, as stated in
   The Java Language Specification, Third Edition (17.4 Memory Model):

Which is a good thing; having finally updated the memory model into
something sensible, it would be unfortunate to add 1 new set of semantics to
it.  Though given that, under JSR 133:

   Writing to a volatile field has the same memory effect as a monitor
release, and reading from a volatile
   field has the same memory effect as a monitor acquire.

(from the JSR 133 FAQ at
http://www.cs.umd.edu/~pugh/java/memoryModel/jsr-133-faq.html#volatile)

It's not obvious to me that the use of atomics is substantially more
"efficient" than using synchronization.  (Yes, I see lazySet() and
weakCompareAndSet(), but how often would one use them?)
Mark Thornton - 26 Nov 2006 21:08 GMT
>>>>Mike Schilling wrote:
>>>>
[quoted text clipped - 33 lines]
> "efficient" than using synchronization.  (Yes, I see lazySet() and
> weakCompareAndSet(), but how often would one use them?)

No idea. I suspect that Doug Lea is one of the few people who could
answer that question.

Mark Thornton
Mike Schilling - 26 Nov 2006 21:57 GMT
>> It's not obvious to me that the use of atomics is substantially more
>> "efficient" than using synchronization.  (Yes, I see lazySet() and
>> weakCompareAndSet(), but how often would one use them?)
>
> No idea. I suspect that Doug Lea is one of the few people who could answer
> that question.

If you see him, ask if he knows what PhantomReferences are for too. :-)
Mark Thornton - 26 Nov 2006 22:25 GMT
>>>It's not obvious to me that the use of atomics is substantially more
>>>"efficient" than using synchronization.  (Yes, I see lazySet() and
[quoted text clipped - 4 lines]
>
> If you see him, ask if he knows what PhantomReferences are for too. :-)

Objects that are only phantom reachable can't be resurrected by
finalize, so they are definitely dead.

Mark Thornton
Mike Schilling - 26 Nov 2006 22:27 GMT
>>>>It's not obvious to me that the use of atomics is substantially more
>>>>"efficient" than using synchronization.  (Yes, I see lazySet() and
[quoted text clipped - 7 lines]
> Objects that are only phantom reachable can't be resurrected by finalize,
> so they are definitely dead.

OK.  Can you give me an example of how you'd use a PhantomReference
programmatically?  I've asked this before on the n.g, and never gotten an
answer.
Daniel Pitts - 27 Nov 2006 04:36 GMT
> >>>>It's not obvious to me that the use of atomics is substantially more
> >>>>"efficient" than using synchronization.  (Yes, I see lazySet() and
[quoted text clipped - 11 lines]
> programmatically?  I've asked this before on the n.g, and never gotten an
> answer.

Usually you would extends PhantomReference with your own custom class,
and register it with a reference queue, so you know when the object it
was referencing has gone away.

Its a very edge case, usually you would use WeakReference (such as in
WeakHashMap)
If you look at the WeakHashMap implementation in Sun's JDK, each Entry
object extends WeakReference, where the referenced object is the value
of the Entry.
Mike Schilling - 27 Nov 2006 05:08 GMT
>> OK.  Can you give me an example of how you'd use a PhantomReference
>> programmatically?  I've asked this before on the n.g, and never gotten an
[quoted text clipped - 9 lines]
> object extends WeakReference, where the referenced object is the value
> of the Entry.

When would you use PhantomReference instead?  The exaplnation given in the
Javadoc:

   Phantom references are most often used for scheduling pre-mortem
   cleanup actions in a more flexible way than is possible with the Java
   finalization mechanism.

is opaque to me.
Daniel Pitts - 27 Nov 2006 07:12 GMT
> >> OK.  Can you give me an example of how you'd use a PhantomReference
> >> programmatically?  I've asked this before on the n.g, and never gotten an
[quoted text clipped - 18 lines]
>
> is opaque to me.

I don't know.  Most likely you will know when you need to use it when
you come across something you can't do any other way.

I interpret the Javadoc's explanation as "Phatom References allow you
to clean up after objects are ready to be garbage collected, without
the risk of reintroducing the refered Object back into the reachable
object graph (and therefore delaying garbage collection of that object).
Mike Schilling - 27 Nov 2006 07:45 GMT
>> >> OK.  Can you give me an example of how you'd use a PhantomReference
>> >> programmatically?  I've asked this before on the n.g, and never gotten
[quoted text clipped - 28 lines]
> the risk of reintroducing the refered Object back into the reachable
> object graph (and therefore delaying garbage collection of that object).

The differences between PhantomReference and WeakReference are:

1. The phantom reference is not queued until the object has been finalized,
while the weak reference may be queued before finalization.
2. Weak references are cleared  by the GC before being queued, while phantom
references are not.
3. It isn't possible to get an object from a phantom reference (get() always
return null), while it is possible to get an object from a weak reference.
(Not after the weak reference in enqueued, of course: see 2.)
4. A phantom reference much be part of a queue, while a weak reference need
not be.

4 follows from 3: a phantom reference that's not in a queue would be
useless.  Otherwise, the differences can be summarized as:

o - A weak reference tells you whether the object is active or not.  If
get() returns true, it's active.  If not (and it never will after being
enqueued), it's inactive, though there's no way to tell whether it's
finalizable, finalized, or deleted.

o - A phantom reference, by being enqueued, tells you specifically that the
object has been finalized but not yet deleted.

I can *almost* see why I'd want to know that the object has been finalized.
I have no idea why I'd care that it hasn't been deleted yet.
Red Orchid - 27 Nov 2006 13:03 GMT
"Mike Schilling" <mscottschilling@hotmail.com> wrote or quoted in
Message-ID: <Bxoah.15796$Sw1.9105@newssvr13.news.prodigy.com>:

> OK.  Can you give me an example of how you'd use a PhantomReference
> programmatically?  I've asked this before on the n.g, and never gotten an
> answer.

As far as I know,  PhantomReference can be used for cleanup.

For example ..

<code_0>

//
// Suppose that Resource R must be cleaned up after used.
//

class Resource_Bank {

   Resource loan() {
       ...
       return R;  
   }

   void refund(Resource R) {
       // Clean up R
   }
}

class Customer {

   void X...(..) {
       R = resource_Bank.loan();
       ...
   }
   
   void Y..(..) {
       ...
       resource_Bank.refund( R );
   }
}
</code_0>

For some reason, if Customer lose the reference of R before
she refunds R, Resource leak will occur.  

To prevent this situation, the following code is possible:

<code_1>

class Resource_Wrap {
   Resource R = ....;    
   ...
   protected void finalize() ... {
       // Clean up R          
   }
}
</code_1>

But ...
If the cleanup process of R take long time, GC may exert
a harmful influence upon the performance of App.

Therefore, the following code will be better:

<code_2>

//
// Data structure, thread-safe etc were ignored to simplify
// this "code_2".
//

class Resource_Wrap {
   Resource R = ....;    
   ...
   Resource getR() {
       return R;
   }
}

class Phantom extends PhantomReference<Resource_Wrap> {
   
   Resource R;    

   public Phantom(Resource_Wrap RW, ReferenceQueue<...> rq) {

       super(RW, rq);
       R = RW.getR();
   }

   Resource getR() {
       return R;
   }
}

class Resource_Bank {

   // Resource R0, R1, ... , Rn

   ReferenceQueue<Resource_Wrap> rq = ...;
   final int MAX_NUMBER = ...;
   Resource_Wrap[] rw = ...;
   Phantom[] pm = ...;

   void initialize() {

       for (int i = 0; i < MAX_NUMBER; ..) {
            rw[i] = new Resource_Wrap( ... );  // Ri
            pm[i] = new Phantom( rw[i], rq );
       }
   }

   Resource_Wrap loan() {
       
      for ( ... ) {
          if ( .. )  {
               Resource_Wrap RW = rw[i];            
               rw[i] = null;  // if Customer lose RW,
                                // she will become phontom.
               return RW;  
          }
      }
      ....
   }

   void refund(Resource_Wrap RW) {
       // Clean up R
   }

   void cleanupDaemon() {

       Thread tr = new Thread() {
            public void run() {            
                while (true) {                
                    Phantom RW = (Phantom) rq.remove();
                    Resource R = RW.getR();
                    ... // Clean up R
                    ... // Clean up RW
                 }
            }
       };
       .....
   }
}
</code_2>

In addition to the above case,
I think that there will be other cases.
Mike Schilling - 27 Nov 2006 17:09 GMT
>    void cleanupDaemon() {
>
[quoted text clipped - 3 lines]
>                     Phantom RW = (Phantom) rq.remove();
>                     Resource R = RW.getR();

This will return null.

You could put information into RW which indicates what cleanup needs to be
done, but that would work with a WeakReference as well as a
PhantomReference.
Red Orchid - 27 Nov 2006 22:15 GMT
"Mike Schilling" <mscottschilling@hotmail.com> wrote or quoted in
Message-ID: <eZEah.5022$wc5.4794@newssvr25.news.prodigy.net>:

> >    void cleanupDaemon() {
> >
[quoted text clipped - 9 lines]
> done, but that would work with a WeakReference as well as a
> PhantomReference.

In the above code, I think,
"getR()" of the class Phantom,  not "get()" of the class PhantomReference.
Mike Schilling - 28 Nov 2006 04:52 GMT
> "Mike Schilling" <mscottschilling@hotmail.com> wrote or quoted in
> Message-ID: <eZEah.5022$wc5.4794@newssvr25.news.prodigy.net>:
[quoted text clipped - 16 lines]
> In the above code, I think,
> "getR()" of the class Phantom,  not "get()" of the class PhantomReference.

Yes.

It still seems to me that this works as well with WeakReferences.
Chris Uppal - 27 Nov 2006 17:13 GMT
> OK.  Can you give me an example of how you'd use a PhantomReference
> programmatically?  I've asked this before on the n.g, and never gotten an
> answer.

I'd say that practically every application where you either don't want to,
don't need to, or don't want /to/ need to, make the object itself know about,
or carry knowledge needed for, the cleanup.

I.e. when you want to track object's lifetimes for their effect on some /other/
object, but have (otherwise) no interest in the objects themselves.

For instance, say you allocate objects on behalf of some group of customers.
You want (for whatever arcane reason) to track how many objects are still
(roughly) alive for each customer.  This is an accounting-like tracking, and
the objects themselves have no interest in either the tracking or in which
customer they are active on behalf of.  So you use a phantom reference for each
object, which also contains (by subclassing) a reference to the customer.  Thus
you can do the accounting for each customer without messing around with the
objects themselves, and do it (I presume, but don't know for sure) more
efficiently and with less chance of awkward interactions with finalisation than
if you'd used the same architecture but with weak refs.

   -- chris
Mike Schilling - 28 Nov 2006 04:49 GMT
>> OK.  Can you give me an example of how you'd use a PhantomReference
>> programmatically?  I've asked this before on the n.g, and never gotten an
[quoted text clipped - 25 lines]
> than
> if you'd used the same architecture but with weak refs.

It seems to me that there's more chance of awkwardness than with weak refs,
provided that in both cases you just queue the ref and forget about it.  In
neither case can you get at the referenced object after retrieving the ref
from the queue (since the weak ref will be cleared before being enqueued),
but you have to remember to clear the phantom ref yourself.

Why do you presume that the phantom ref is more efficient?  I myself have no
intuition either way.
Daniel Pitts - 02 Dec 2006 19:03 GMT
> > If you want to guarantee that thread A sees a change to memory made by
> > thread B, you need to use synchronization.
[quoted text clipped - 18 lines]
>
> Thanks again.

Have you head this?

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

This describes how Volitile affects memory access.  I don't know if it
is enough, but it might be useful.
Knute Johnson - 25 Nov 2006 04:52 GMT
>> Hello guys,
>>
[quoted text clipped - 16 lines]
> 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.

Signature

Knute Johnson
email s/nospam/knute/

Daniel Pitts - 25 Nov 2006 20:57 GMT
> >> Hello guys,
> >>
[quoted text clipped - 23 lines]
> 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.
Patricia Shanahan - 25 Nov 2006 21:26 GMT
...
> 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.
...

There can be reordering at a level below machine code, as part of the
processor implementation. The JVM does not have direct control, but
processors have instructions for forcing extra ordering, and the JVM is
required to use them to achieve what the JLS specifies e.g. for volatile
data.

The mental model of a processor doing one instruction at a time in
program order, and doing all work for each instruction before going on
to the next one, used to be reasonably accurate, except for some
supercomputers. Now, it is a gross simplification for most processors.

Instead, think of the processor as a sort of factory, with a main
production line several instructions wide, but many specialized stations
where different processing gets done and instructions can wait if
something they need is not available. Some operations are shunted off
e.g. to a specialized production line for doing floating point. The work
of making a store globally visible, not just visible to this processor,
may go into another production line.

A processor can have many dozens of instructions at some stage in the
processing.

It's all designed to make it look, to code executing on the processor,
as though the processor is doing one instruction at a time in program
order. However, a thread on another processor monitoring the behavior of
shared data can see the order in which some things really happened.

Patricia
Mark Thornton - 25 Nov 2006 21:52 GMT
> It's all designed to make it look, to code executing on the processor,
> as though the processor is doing one instruction at a time in program
> order. However, a thread on another processor monitoring the behavior of
> shared data can see the order in which some things really happened.

Worse it can see an order which never happened!
E.g. on processor A:

start with x=1, y=1, z=2

x = 2;
z = x+y; // 3

Then processor B might see.

start x=1, y=1, z=2.

Then x=1, y=1, z=3

then x=2, y=1, z=3

I.e. it sees the change in z before the change in x.

Mark Thornton
Patricia Shanahan - 25 Nov 2006 04:47 GMT
> 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
[quoted text clipped - 3 lines]
> 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
xmarlawx@gmail.com - 25 Nov 2006 14:54 GMT
> > Hello guys,
>
> 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 - 25 Nov 2006 15:23 GMT
...
> 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 - 25 Nov 2006 15:38 GMT
> ...
>> 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 - 25 Nov 2006 15:38 GMT
>> > Hello guys,
>>
>> Guys? I hope you don't really mean that.

> 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...
Lew - 30 Nov 2006 08:13 GMT
>>> Hello guys,
>> 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 :)

I have heard female American-English-speaking humans call each other "guys",
but I believe the convention is to say, "Hey, guys" rather than "Hello, guys". :-)

The word "guys" was originally masculine but seems to have drifted to at least
partially gender neutral.

I have heard younger American females call each other "dude" also.

FWIW, guys and dolls.

- Lew
Chris Thomasson - 25 Nov 2006 10:12 GMT
> 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/c49c06
58e2607317


I guess you could use Java volatiles... However, you still need the
#StoreLoad memory barrier after the acquisition logic...
Chris Thomasson - 25 Nov 2006 10:17 GMT
[comp.programming.threads added]

>> Hello guys,
>>
[quoted text clipped - 8 lines]
> 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/e07adf
138f0091d


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 - 25 Nov 2006 11:08 GMT
Petersons algorithm should be implemented in assembly language without using
any atomic operations. Alls you need are memory barriers.
Patricia Shanahan - 25 Nov 2006 12:41 GMT
> 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
Chris Thomasson - 25 Nov 2006 15:44 GMT
>> Petersons algorithm should be implemented in assembly language without
>> using any atomic operations. Alls you need are memory barriers.
[quoted text clipped - 3 lines]
>
> 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 - 25 Nov 2006 15:55 GMT
>>> Petersons algorithm should be implemented in assembly language without
>>> using any atomic operations. Alls you need are memory barriers.
[quoted text clipped - 7 lines]
> 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@gmail.com - 25 Nov 2006 16:20 GMT
> 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.
Chris Thomasson - 25 Nov 2006 18:08 GMT
>> Or make any shared data accessed in the critical region volatile.
>>
[quoted text clipped - 17 lines]
>
> Again, I must say, thank you all.

Making everything volatile will generated a boat load of memory barriers.
Remember, the Java memory model is basically like this:

// load acquire
void* load(void **_pthis) {
 void *state = ATOMIC_LOAD(_pthis);
 membar #LoadStore | #LoadLoad;
}

// store release
void store(void **_pthis, void *state) {
 membar #LoadStore | #StoreStore;
 ATOMIC_STORE(_pthis, state);
}

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..
Chris Thomasson - 25 Nov 2006 18:08 GMT
> // load acquire
> void* load(void **_pthis) {
>  void *state = ATOMIC_LOAD(_pthis);
>  membar #LoadStore | #LoadLoad;

  return state; // of course!
> }

;^)
Patricia Shanahan - 25 Nov 2006 18:08 GMT
....
> 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
xmarlawx@gmail.com - 25 Nov 2006 18:14 GMT
[SNIP-quote]
> Making everything volatile will generated a boat load of memory barriers.
> Remember, the Java memory model is basically like this:
[SNIP-code]
> 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..

Sorry I don't understand.I don't know what is a memory barrier.
Will look now.
By putting all volatile i only mean the three variables used
(flag[0],flag[1],turn)
An other thing is that i'm not using simple variable type such as int
and boolean but i'm using those
wrapped in a class i've wrote with accessor methods (without
synchronized methods).

When you say to put it in a synch block do you mean nesting the two
variables check (the spinlock),
or you mean simply the operation on the variables such as writing ?
Both ?

Right now i'm making some experiments ( i can upload the code) and
works with volatile.
Without volatile seemed to work too, but i guess that is not garanteed.
Probably (surely?) it will work as well with synchronized blocks or
methods.
xmarlawx@gmail.com - 01 Dec 2006 02:38 GMT
> 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.

Sorry,
If i declare volatile (in the threads) the three variables used by the
Peterson's algorithm that
is not enough ?
How shall i do a full memory barrier ?
Chris Uppal - 01 Dec 2006 14:17 GMT
> > Yeah... However, you have to do a full memory barrier in order to get
> > the #StoreLoad barrier after the Petersons lock acquisition logic... The
[quoted text clipped - 4 lines]
> Peterson's algorithm that
> is not enough ?

It is enough.

> How shall i do a full memory barrier ?

You can't (not as a separate operation).

Chris's comments were a bit confusing.  He was talking about how Java concepts
like "volatile" should be implemented internally by the JVM -- you shouldn't
worry about that (except, of course, if you find such details interesting or
enlightening).  In any case, whether you worry or not, you have no way to
control what code the JVM generates and executes beyond the fact that, whatever
it is, it must implement the operations your Java code asks for consistently
with Java semantics.

   -- chris
Chris Uppal - 25 Nov 2006 12:02 GMT
> 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
Chris - 25 Nov 2006 22:04 GMT
Just for the record, all of this has been discussed in considerable
detail in the past. Google the term "double-checked locking".

The conclusion of all these are articles is: don't try to fool the
compiler. Attempts to add quasi-memory barriers and whatnot will fail.
Use regular old synchronization.


Free Magazines

Get these publications absolutely FREE for up to 12 months. There are no hidden fees and no obligation. Simply choose a title, complete the application form and submit it. Read more ...

Oracle MagazineNetwork ComputingComputer WorldBio-IT WorldeWeekInformation WeekInfosecurity
 
Sign In
Join
My Latest Posts
My Monitored Threads
My Blog
My Photo Gallery
My Profile
My Homepage

Start New Thread
Enable EMail Alerts
Rate this Thread



©2009 Advenet LLC   Privacy Policy - Terms of Use
This website includes both content owned or controlled by Advenet as well as content owned or controlled by third parties.