interrupt / notify races even in 6.0 beta?

classic Classic list List threaded Threaded
10 messages Options
Reply | Threaded
Open this post in threaded view
|

interrupt / notify races even in 6.0 beta?

Dawid Kurzyniec
The following code:

public class Test {
    public static void main(String[] args) throws Exception {
        final Object lock = new Object();
        Thread t = new Thread() {
            public void run() {
                try {
                    synchronized (lock) { lock.wait(); }
                    System.out.println("Awaken");
                } catch (InterruptedException e) {
                    System.out.println("Interrupted");
                }
            }
        };
        t.start();
        Thread.sleep(100);
        t.interrupt();
        synchronized (lock) { lock.notify(); }
        t.join();
    }
}

reports "Awaken" instead of "Interrupted" on all JVMs I tested it, including jdk6.0beta for Linux, as well as the latest 5.0 and 1.4.2 JVMs from SUN and IBM. I thought that the race between notify and interrupt has been long fixed?... This problem causes the backported ReentrantLock to miss the interruption and fail on ReentrantLockTest.testLockInterruptibly1(). What to think? And how come j.u.c.ReentrantLock is not affected?

Regards,
Dawid


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: interrupt / notify races even in 6.0 beta?

Dawid Kurzyniec
Doug Lea wrote:
Dawid Kurzyniec wrote:


reports "Awaken" instead of "Interrupted" on all JVMs I tested it,

Are you sure?? It reports "interrupted" on all that I've tried it
on, including 5.0 and mustang on both linux and solaris, and IBM 5.0
on linux.

OK, so here's what I got after running a revised test program below on the machines I have access to:

public class Test extends Thread {

    final static Object lock = new Object();

    public void run() {
        try {
            synchronized (lock) { lock.wait(); }
            System.out.println("Awaken");
        } catch (InterruptedException e) {
            System.out.println("Interrupted");
        }
    }

    public static void main(String[] args) throws Exception {
        Thread t;
        t = new Test();
        t.start();
        Thread.sleep(100);
        t.interrupt();
        synchronized (lock) { lock.notify(); }
        t.join();
        t = new Test();
        t.start();
        Thread.sleep(100);
        synchronized (lock) { lock.notify(); }
        t.interrupt();
        t.join();
        System.out.println("Should be: first Interrupted; then Awaken");
        System.out.flush();
    }
}

Linux, 2 different machines but both with Mandriva 2006 and kernel 2.6.12-12mdk-i686-up-4GB:

IBM 1.4.2, build cxia32142ifx-20060209 (SR4-1): Interrupted, Interrupted
IBM 1.5.0, build 2.3 x86-32 j9vmxi3223ifx-20060124: Awaken, Awaken

SUN: 1.4.1, 1.4.1_01, 1.4.2, 1.4.2_03, 1.4.2_06, 1.4.2_08, 1.5.0-beta, 1.5.0-beta2, 1.5.0, 1.5.0_06, 1.6.0-beta (b59g): all Awaken, Awaken!


Solaris SPARC, SunOS 5.10 Generic_118822-25 sun4u:

SUN 1.3.1_02, 1.4.0_01, 1.4.1_01, 1.4.2_02, 1.4.2_06: Awaken, Awaken
SUN 1.5.0: Interrupted, Awaken (correct)
SUN 1.2.1_03: Interrupted, Interrupted (ocassionally the 2nd one is Awaken)

Windows XP SP2:

1.4.2_05, 1.5.0_06: Interrupted, Awaken (correct)


I suspect that on IBM SP2, I'd probably see Interrupted, Interrupted - judging from past backport bug reports.

It seems that this race is more pervasive that I thought. (I had the impression that it has been fixed somewhere in the 1.4 line). It means that the backport must bite the bullet. I am probably going to relax the unit test a little bit (by inserting a short sleep between interrupt() and notify()) to make it pass. (For anxious backport users: I wouldn't worry too much about it; the revised unit test is arguably unfairly pessimistic from the usage patterns point of view, and the code that now started failing the test is exactly the same as the one that we all happily used since dl.util.concurrent).

The continuous presence of this race in 1.5 and Mustang on Linux is the troubling, though. Since Doug says it's working for him, I am guessing that the problem may have something to do with the kernel version?... It would be good if somebody tested it on some other Linux boxes.

Regards,
Dawid


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: interrupt / notify races even in 6.0 beta?

Holger Hoffstätte-2
In reply to this post by Dawid Kurzyniec
Dawid,

I extended the test to collect results for multiple runs. I then ran this
for longer periods and got some more interesting results.
       
1) Linux version 2.6.16.9 (Gentoo), no preemptible scheduler or other toys
configured ('vanilla' as it can get), glibc 2.4 and Sun JDKs 1.4.2.11,
1.5.0.06 and Mustang b82 consistently gives A-A (i.e. 'wrong' behaviour)
every time, regardless how many samples I run.

2) Windows XP SP1, Sun JDK 1.4.2.09, 1.5.0.06 and Mustang b82 relatively
consistently give I-A with the occasional A-A. Multipe test runs are
necessary to observe this; in other words it happens on Windows too.

The modified test is attached.

Holger


import java.util.List;
import java.util.ArrayList;

public class Test extends Thread {

        public static int NUM = 10;
        public static int SLEEP = 100;
        public static List values = new ArrayList();

        public static volatile char s;

    final static Object lock = new Object();

    public void run() {
        try {
            synchronized (lock) { lock.wait(); }
            s = 'A';
        } catch (InterruptedException e) {
        s = 'I';
        }
    }

    public static void main(String[] args) throws Exception {
   
                for (int i = 0; i < NUM; i++)
                {
                        Thread t;
                        t = new Test();
                        t.start();
                        Thread.sleep(SLEEP);
                        t.interrupt();
                        synchronized (lock) { lock.notify(); }
                        t.join();
                        char s1 = s;

                        t = new Test();
                        t.start();
                        Thread.sleep(SLEEP);
                        synchronized (lock) { lock.notify(); }
                        t.interrupt();
                        t.join();
                        char s2 = s;

                        values.add(new String(new char[]{s1, s2}));

                        Thread.sleep(SLEEP*2);
                }

                System.out.println(values);
    }
}


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Re: interrupt / notify races even in 6.0 beta?

Doug Lea
In reply to this post by Dawid Kurzyniec
First, note that the JLS-3 specs allow some non-determinism here. See
   http://java.sun.com/docs/books/jls/third_edition/html/memory.html
Which says...
[Sec 17.8.4]
   The above specifications allow us to determine several properties having to do
   with the interaction of waits, notification and interruption. If a thread is
   both notified and interrupted while waiting, it may either:

     * return normally from wait, while still having a pending interrupt (in
other works, a call to Thread.interrupted would return true)
     * return from wait by throwing an InterruptedException

   The thread may not reset its interrupt status and return normally from the
   call to wait.

   Similarly, notifications cannot be lost due to interrupts. Assume that a set s
   of threads is in the wait set of an object m, and another thread performs a
   notify on m. Then either

     * at least one thread in s must return normally from wait, or
     * all of the threads in s must exit wait by throwing InterruptedException

   Note that if a thread is both interrupted and woken via notify, and that
   thread returns from wait by throwing an InterruptedException, then some other
   thread in the wait set must be notified.
[BTW: notice the typo "in other works"!]

This boils down to saying that there are two forbidden outcomes:
   1. A thread woken up via notify does not "lose" its interrupt status.
   2. An InterruptedException does not "lose" the fact there is a
      pending notification (that may wake up some other waiting thread).

These are the "bugs" fixed in 1.5 JVMs in accord with JSR133 specs.

I just threw together a little test program (attached) to verify that
#1 does not happen. It doesn't on the JVMs/platforms I've checked.
(This is not a pretty program because it has to
use spins/yields to advance the threads so as not to contaminate
with additional locks, waits, or sleeps.)

However, it is the case that on all platforms I've tried, sometimes
the "notifyBeforeInterrupt" method says it was interrupted before
notified, and vice versa. This reflects the unavoidable race here,
that will come out one way or the other depending on exactly what
the target thread is doing when signaller invokes notify or interrupt.

(There are also some tests for #2 around developed during JSR133,
but I'm not sure where they are.)


-Doug

public class T516 extends Thread {
    static final int NTESTS = 100;
    static final int ITERS_PER_TEST = 50;
    static final int NORMAL = 1;
    static final int INTERRUPTED = 2;
    volatile int waitStatus;
    volatile int exitStatus;
    volatile boolean started;
    volatile boolean stop;
    final Object lock = new Object();

    public void run() {
        started = true;
        synchronized(lock) {
            try {
                lock.wait();
                waitStatus = NORMAL;
            } catch (InterruptedException e) {
                waitStatus = INTERRUPTED;
            }
        }
        while (!stop)
            Thread.yield();
        exitStatus = interrupted()? INTERRUPTED : NORMAL;
    }

    public static void main(String[] args) throws Exception {
        for (int i = 0; i < NTESTS; ++i) {
            interruptBeforeNotify();
            notifyBeforeInterrupt();
        }
    }

    static void interruptBeforeNotify() throws Exception {
        for (int i = 0; i < ITERS_PER_TEST; i++) {
            T516 t = new T516();
            t.start();
            while (!t.started)
                Thread.yield();
            t.interrupt();
            synchronized (t.lock) { t.lock.notify(); }
            while(t.waitStatus == 0)
                Thread.yield();
            t.stop = true;
            while(t.exitStatus == 0)
                Thread.yield();
            int r = t.waitStatus;
            int e = t.exitStatus;
            if (r == NORMAL && e == NORMAL)
                throw new Error("Notified but not interrupted");
            else if (r == NORMAL) System.out.print("n");
            else if (r == INTERRUPTED) System.out.print("i");
            else throw new Error("Cannot happen");
            t.join();
        }

        System.out.println();
    }

   
    static void notifyBeforeInterrupt() throws Exception {
        for (int i = 0; i < ITERS_PER_TEST; i++) {
            T516 t = new T516();
            t.start();
            while (!t.started)
                Thread.yield();
            synchronized (t.lock) { t.lock.notify(); }
            t.interrupt();
            while(t.waitStatus == 0)
                Thread.yield();
            t.stop = true;
            while(t.exitStatus == 0)
                Thread.yield();
            int r = t.waitStatus;
            int e = t.exitStatus;
            if (r == NORMAL && e == NORMAL)
                throw new Error("Notified but not interrupted");
            else if (r == NORMAL) System.out.print("N");
            else if (r == INTERRUPTED) System.out.print("I");
            else throw new Error("Cannot happen");
            t.join();
        }
        System.out.println();
    }
}




_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Re: interrupt / notify races even in 6.0 beta?

Bart Jacobs-2
Dawid's test case has the special circumstance that the notify() and the
interrupt() occur in the same thread. The question is: are both of these
calls considered to occur "while [the target thread is] waiting" or not?

Arguments pro:
- There is no synchronizes-with edge from the wait to the
notify()/interrupt() call.
- Section 17.8.1 says:

Each thread must determine an order over the events that could cause it
to be removed from a wait set. That order does not have to be consistent
with other orderings, but the thread must behave as though those events
occurred in that order.

So the order does not have to be consistent with program order.

Argument contra:
- A reader could be forgiven for thinking that after a
notify()/interrupt() call, the target thread is not longer considered to
be waiting, and therefore, operations that happen-after the
notify()/interrupt() call do not occur "while [the target thread is]
waiting" and "could [not] cause it to be removed from a wait set". As a
result, neither 17.8.1 nor 17.8.4 would apply in the first place.

So it seems it would help if the JLS clarified the meaning of "while
waiting" (both for 17.8.1 and 17.8.4), by saying that the thread "stops
waiting" sometime after the notify()/interrupt() call, and therefore is
still considered to "be waiting" until such time.

Bart

Doug Lea wrote:

> First, note that the JLS-3 specs allow some non-determinism here. See
>   http://java.sun.com/docs/books/jls/third_edition/html/memory.html
> Which says...
> [Sec 17.8.4]
>   The above specifications allow us to determine several properties
> having to do
>   with the interaction of waits, notification and interruption. If a
> thread is
>   both notified and interrupted while waiting, it may either:
>
>     * return normally from wait, while still having a pending
> interrupt (in other works, a call to Thread.interrupted would return
> true)
>     * return from wait by throwing an InterruptedException
>
>   The thread may not reset its interrupt status and return normally
> from the
>   call to wait.
>
>   Similarly, notifications cannot be lost due to interrupts. Assume
> that a set s
>   of threads is in the wait set of an object m, and another thread
> performs a
>   notify on m. Then either
>
>     * at least one thread in s must return normally from wait, or
>     * all of the threads in s must exit wait by throwing
> InterruptedException
>
>   Note that if a thread is both interrupted and woken via notify, and
> that
>   thread returns from wait by throwing an InterruptedException, then
> some other
>   thread in the wait set must be notified.
> [BTW: notice the typo "in other works"!]
>
> This boils down to saying that there are two forbidden outcomes:
>   1. A thread woken up via notify does not "lose" its interrupt status.
>   2. An InterruptedException does not "lose" the fact there is a
>      pending notification (that may wake up some other waiting thread).
>
> These are the "bugs" fixed in 1.5 JVMs in accord with JSR133 specs.
>
> I just threw together a little test program (attached) to verify that
> #1 does not happen. It doesn't on the JVMs/platforms I've checked.
> (This is not a pretty program because it has to
> use spins/yields to advance the threads so as not to contaminate
> with additional locks, waits, or sleeps.)
>
> However, it is the case that on all platforms I've tried, sometimes
> the "notifyBeforeInterrupt" method says it was interrupted before
> notified, and vice versa. This reflects the unavoidable race here,
> that will come out one way or the other depending on exactly what
> the target thread is doing when signaller invokes notify or interrupt.
>
> (There are also some tests for #2 around developed during JSR133,
> but I'm not sure where they are.)
>
>
> -Doug
>
>------------------------------------------------------------------------
>
>public class T516 extends Thread {
>    static final int NTESTS = 100;
>    static final int ITERS_PER_TEST = 50;
>    static final int NORMAL = 1;
>    static final int INTERRUPTED = 2;
>    volatile int waitStatus;
>    volatile int exitStatus;
>    volatile boolean started;
>    volatile boolean stop;
>    final Object lock = new Object();
>
>    public void run() {
>        started = true;
>        synchronized(lock) {
>            try {
>                lock.wait();
>                waitStatus = NORMAL;
>            } catch (InterruptedException e) {
>                waitStatus = INTERRUPTED;
>            }
>        }
>        while (!stop)
>            Thread.yield();
>        exitStatus = interrupted()? INTERRUPTED : NORMAL;
>    }
>
>    public static void main(String[] args) throws Exception {
>        for (int i = 0; i < NTESTS; ++i) {
>            interruptBeforeNotify();
>            notifyBeforeInterrupt();
>        }
>    }
>
>    static void interruptBeforeNotify() throws Exception {
>        for (int i = 0; i < ITERS_PER_TEST; i++) {
>            T516 t = new T516();
>            t.start();
>            while (!t.started)
>                Thread.yield();
>            t.interrupt();
>            synchronized (t.lock) { t.lock.notify(); }
>            while(t.waitStatus == 0)
>                Thread.yield();
>            t.stop = true;
>            while(t.exitStatus == 0)
>                Thread.yield();
>            int r = t.waitStatus;
>            int e = t.exitStatus;
>            if (r == NORMAL && e == NORMAL)
>                throw new Error("Notified but not interrupted");
>            else if (r == NORMAL) System.out.print("n");
>            else if (r == INTERRUPTED) System.out.print("i");
>            else throw new Error("Cannot happen");
>            t.join();
>        }
>
>        System.out.println();
>    }
>
>    
>    static void notifyBeforeInterrupt() throws Exception {
>        for (int i = 0; i < ITERS_PER_TEST; i++) {
>            T516 t = new T516();
>            t.start();
>            while (!t.started)
>                Thread.yield();
>            synchronized (t.lock) { t.lock.notify(); }
>            t.interrupt();
>            while(t.waitStatus == 0)
>                Thread.yield();
>            t.stop = true;
>            while(t.exitStatus == 0)
>                Thread.yield();
>            int r = t.waitStatus;
>            int e = t.exitStatus;
>            if (r == NORMAL && e == NORMAL)
>                throw new Error("Notified but not interrupted");
>            else if (r == NORMAL) System.out.print("N");
>            else if (r == INTERRUPTED) System.out.print("I");
>            else throw new Error("Cannot happen");
>            t.join();
>        }
>        System.out.println();
>    }
>}
>
>
>
>  
>
>------------------------------------------------------------------------
>
>_______________________________________________
>Concurrency-interest mailing list
>[hidden email]
>http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
>  
>


Disclaimer: http://www.kuleuven.be/cwis/email_disclaimer.htm

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Re: interrupt / notify races even in 6.0beta?

Dawid Kurzyniec
Bart Jacobs wrote:
> (...)
> Argument contra:
> - A reader could be forgiven for thinking that after a
> notify()/interrupt() call, the target thread is not longer considered
> to be waiting, and therefore, operations that happen-after the
> notify()/interrupt() call do not occur "while [the target thread is]
> waiting" and "could [not] cause it to be removed from a wait set". As
> a result, neither 17.8.1 nor 17.8.4 would apply in the first place.
>

Exactly. My intuitive expectation would be that the call to interrupt()
is synchronous, i.e. does not return until the thread has the interrupt
flag set, and has been removed from the wait set. If that happened, the
subsequent notify() from the same thread would have no effect. It seems
that most JVMs currently implement interrupt() asynchronously, which
leads to the possibility that the notify() shortly following interrupt()
may succeed before the interrupt() finishes. If keeping the weaker
asynchronous semantics is necessary due to practical purposes, I think
it should be documented in Thread.interrupt() javadoc. Although I can't
see what would be wrong with making interrupt synchronous?...

Regards,
Dawid

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Re: interrupt / notify races even in 6.0 beta?

Doug Lea
In reply to this post by Bart Jacobs-2
Bart Jacobs wrote:
>
> So it seems it would help if the JLS clarified the meaning of "while
> waiting" (both for 17.8.1 and 17.8.4), by saying that the thread "stops
> waiting" sometime after the notify()/interrupt() call, and therefore is
> still considered to "be waiting" until such time.
>

Yes; this is a good idea.

The effects seen here might seem less mysterious if you know
the basic implementation scheme, which is typically the one
documented for AbstractQueuedSynchronizer.Condition.await; see
http://gee.cs.oswego.edu/dl/jsr166/dist/docs/java/util/concurrent/locks/AbstractQueuedSynchronizer.ConditionObject.html

        1. If current thread is interrupted, throw InterruptedException
        2. Save lock state returned by AbstractQueuedSynchronizer.getState()
        3. Invoke AbstractQueuedSynchronizer.release(int) with saved state as
argument, throwing IllegalMonitorStateException if it fails.
        4. Block until signalled or interrupted
        5. Reacquire by invoking specialized version of
AbstractQueuedSynchronizer.acquire(int) with saved state as argument.
        6. If interrupted while blocked in step 4, throw exception


Notice that interrupt status is checked (at least) twice -- on entry, and then
again during/after an OS-level blocking.

This means that response to (notify; interrupt) or (interrupt; notify)
can go either way, depending on whether each came at/before
step 1, or step 4, or later. So even though in the test programs
here, the caller "knows" which came first, it cannot control the
points at which the waiting thread is paying attention to which of these
events.

(This is not a bug; it's a feature! People would not like to use
a condition wait implementation that disables either the "early"
or the "late" checks.)

-Doug


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Re: interrupt / notify races even in 6.0beta?

Dawid Kurzyniec
Doug Lea wrote:

> Bart Jacobs wrote:
>>
>> So it seems it would help if the JLS clarified the meaning of "while
>> waiting" (both for 17.8.1 and 17.8.4), by saying that the thread
>> "stops waiting" sometime after the notify()/interrupt() call, and
>> therefore is still considered to "be waiting" until such time.
>>
>
> Yes; this is a good idea.
>
> The effects seen here might seem less mysterious if you know
> the basic implementation scheme, which is typically the one
> documented for AbstractQueuedSynchronizer.Condition.await; see
> http://gee.cs.oswego.edu/dl/jsr166/dist/docs/java/util/concurrent/locks/AbstractQueuedSynchronizer.ConditionObject.html 
>
>
>        1. If current thread is interrupted, throw InterruptedException
>        2. Save lock state returned by
> AbstractQueuedSynchronizer.getState()
>        3. Invoke AbstractQueuedSynchronizer.release(int) with saved
> state as argument, throwing IllegalMonitorStateException if it fails.
>        4. Block until signalled or interrupted
>        5. Reacquire by invoking specialized version of
> AbstractQueuedSynchronizer.acquire(int) with saved state as argument.
>        6. If interrupted while blocked in step 4, throw exception
>
>
> Notice that interrupt status is checked (at least) twice -- on entry,
> and then
> again during/after an OS-level blocking.
>
> This means that response to (notify; interrupt) or (interrupt; notify)
> can go either way, depending on whether each came at/before
> step 1, or step 4, or later. So even though in the test programs
> here, the caller "knows" which came first, it cannot control the
> points at which the waiting thread is paying attention to which of these
> events.
>

I guess in this particular case we're only talking about the
interruption during OS-level blocking in step 4.

I realize that you (EG) have dealt with this issue for decades now; so
please have a little patience with me here; I'd like to understand the
problem fully to make sure that I don't screw up anything in the
backport. It is no mystery that there is a possible race between notify
/ interrupt, as it is between memory read / write, when there is no
happens-before relationship between these operations. Ideally, and
intuitively however, I would expect that the ordering of notify /
interrupt becomes deterministic when there is a happens-before
relationship, e.g. if the operations are invoked from the same thread.
Apparently, it is not the case, and the spec does not actually promise
it. I am trying to understand why it can't be made to be the case. For
instance, why can't the interruption status be combined with a thread
state (runnable, blocked, waiting, io) into an atomic state variable -
having interrupt() CAS-ing it to INTERRUPTED, removing the tread from
the condition's wait set if was WAITING, and having notify() loop
CAS-ing the state of a candidate thread to RUNNABLE if was WAITING, and
skipping it over if was INTERRUPTED. Perhaps the problem is that the OS
layer does not expose things this way?... But then again, with the
low-level primitives like those used by park/unpark, wouldn't it be
possible to implement it at the JVM side, without relying on OS-level
wait sets etc?

In any case, since the ordering is not deterministic, the aforementioned
ReentrantLock unit test is probably too strict. Would a Thread.yield()
or a delay inserted between interrupt and notify be a reasonable fix?...

Regards,
Dawid

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Re: interrupt / notify races even in 6.0beta?

Doug Lea
Dawid Kurzyniec wrote:
>
> ...
> Perhaps the problem is that the OS
> layer does not expose things this way?

Yes. This is the main issue. For example, on some platforms,
Java-level interrupts may sometimes entail OS-level signals. There is better
(although as-yet unexploited) OS integration possible using park/unpark,
but even here, the interaction with interrupts is messy.


> In any case, since the ordering is not deterministic, the aforementioned
> ReentrantLock unit test is probably too strict. Would a Thread.yield()
> or a delay inserted between interrupt and notify be a reasonable fix?...
>

Thanks! You are right that a few TCK tests implicitly assumed orderings
that aren't mandated by any specs, and so should force delays. Updated
versions are now in our CVS.

-Doug

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

RE: Re: interrupt / notify races even in 6.0beta?

David Holmes-3
In reply to this post by Dawid Kurzyniec
Dawid,

> Dawid Kurzyniec wrote:
> I realize that you (EG) have dealt with this issue for decades now; so
> please have a little patience with me here; I'd like to understand the
> problem fully to make sure that I don't screw up anything in the
> backport. It is no mystery that there is a possible race between notify
> / interrupt, as it is between memory read / write, when there is no
> happens-before relationship between these operations. Ideally, and
> intuitively however, I would expect that the ordering of notify /
> interrupt becomes deterministic when there is a happens-before
> relationship, e.g. if the operations are invoked from the same thread.
> Apparently, it is not the case, and the spec does not actually promise
> it. I am trying to understand why it can't be made to be the case. For
> instance, why can't the interruption status be combined with a thread
> state (runnable, blocked, waiting, io) into an atomic state variable -
> having interrupt() CAS-ing it to INTERRUPTED, removing the tread from
> the condition's wait set if was WAITING, and having notify() loop
> CAS-ing the state of a candidate thread to RUNNABLE if was WAITING, and
> skipping it over if was INTERRUPTED. Perhaps the problem is that the OS
> layer does not expose things this way?...

I fully sympathise with you as I was in the exact same position asking the
exact same questions and wanting similar answers. Since then I have learned
the "why" of it.

Anything is possible, and a design as outlined above is possible, but that
isn't the way hotspot evolved in this area. In simple terms there are two
things going on here:

1. interrupt() is only loosely coupled to the use of monitors. interrupt()
ensures that a blocked thread wakes up but it doesn't check to see why (or
even if) the thread was blocked in the first place, and so in this case it
doesn't make any change to the wait-set. So in a sense, yes it is
"asynchronous".

2. Contrary to what Doug indicated the VM actually favours notification over
interruption (while jsr-166 stuff does the opposite).

Hence by the time the thread wakes up due to the interrupt, the main thread
has also removed it from the wait-set. The VM favours notification and so
you get a normal return with the interrupt bit set.

The OS issues are more to do with timeouts - because the OS sometimes lies
and you can't tell you timed-out. That is something else I lament - that
even with jsr-166 you can't truly tell for certain whether or not you
timed-out. :(

> But then again, with the
> low-level primitives like those used by park/unpark, wouldn't it be
> possible to implement it at the JVM side, without relying on OS-level
> wait sets etc?

If at some point in the future the same mechanism were to be used for
jsr-166 sync and monitor sync, then you would get the same (unspecified)
behaviour from each.

So any "test" that assumes the order of notifications and interrupts is
invalid. All you can test is whether the interrupt state is set or cleared
correctly, and that notifications are not lost.

If you want all the gory details sign up at java.net and download the
Mustang snapshots :)

Cheers,
David Holmes

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest