Peterson's Algorithm in java, sequencial instruction execution ?

[Daniel Pitts]

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.

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]

Mike Schilling wrote:

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.

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]

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.

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]

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

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]

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 = new Resource_Wrap( ... ); // Ri
pm = new Phantom( rw, rq );
}
}


Resource_Wrap loan() {

for ( ... ) {
if ( .. ) {
Resource_Wrap RW = rw;
rw = 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]

void cleanupDaemon() {

Thread tr = new Thread() {
public void run() {
while (true) {
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.

 

[Chris Uppal]

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

 

[Red Orchid]

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.

In the above code, I think,
"getR()" of the class Phantom, not "get()" of the class PhantomReference.

 

[Mike Schilling]

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.

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.

 

[Mike Schilling]

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.

 

[Lew]

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

 

[xmarlawx]

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]

If i declare volatile (in the threads) the three variables used by the
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

 

[Daniel Pitts]

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.

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.