[concurrency-interest] Java Deadlock prevented

David Holmes davidcholmes at aapt.net.au
Mon Apr 16 18:45:27 EDT 2012


(Fixed subject line: everyone - please don't reply to a digest and so screw
up the subject!)

I hate to be a wet blanket but really this is nothing new. Deadlock
detection and prevention is as old as deadlock. Throwing an exception when
you are potentially going to deadlock avoids the deadlock but doesn't
necessarily imply that any corrective action is possible at runtime - you
would need to employ transactional semantics to undo nested state changes,
and all of your code would need to know about the rest to know how the
locking is related and so may be done a different way. Such mechanisms can
be useful development tools, but static analysis can be better at
identifying potential deadlocks, than runtime checks that require the right
timing for the deadlock to be encountered. There's decades of literature on
this.

David Holmes
  -----Original Message-----
  From: concurrency-interest-bounces at cs.oswego.edu
[mailto:concurrency-interest-bounces at cs.oswego.edu]On Behalf Of Rohit Kumar
  Sent: Tuesday, 17 April 2012 5:45 AM
  To: Nathan Reynolds; sandeep.bansal85 at gmail.com; khilan at doc.ic.ac.uk
  Cc: concurrency-interest at cs.oswego.edu
  Subject: Re: [concurrency-interest] Concurrency-interest Digest, Vol
87,Issue 27


  The whole idea that I wanted to bring up is that use of synchronized
keyword (implicit locks) can make your program vulnerable to deadlocks as
you have no control over acquisition of locks. Once you use explicit locks
as provided by java concurrent apis, deadlocks can be prevented completely.
And yes, my program uses synchronized keywords, but all in one place and is
completely and thoroughly tested. Usage of synchronized keyword should be
confined.

  My program detects cycles in lock-acquisition graph. The overhead will be
proportional to all the threads that are holding locks but not yet released
and this is not great compared to restarting the server everytime the
deadlock happens.

  I will see if I can present it to any java forum. This is written in java
but the concept can be applied in any programming language.

  Thanks & Regards,
  Rohit Kumar


  From: Nathan Reynolds <nathan.reynolds at oracle.com>
  To: Rohit Kumar <rohitk242 at yahoo.co.in>
  Cc: "concurrency-interest at cs.oswego.edu"
<concurrency-interest at cs.oswego.edu>
  Sent: Tuesday, 17 April 2012 12:52 AM
  Subject: Re: [concurrency-interest] Concurrency-interest Digest, Vol 87,
Issue 27



  Synchronized blocks are used every where.  You could use ASM
(http://asm.ow2.org/) to instrument all synchronized blocks (i.e.
monitorenter and monitorexit bytecodes).  Simply put a call to your
deadlock-check just before the monitorenter instruction.  You could also use
this to inject your code into all Locks.

  If you want to avoid the overhead during lock acquisition, you could have
a background thread detect the deadlock and then make one thread involved in
the deadlock throw an exception using Thread.stop(Throwable).  Thread.stop()
is a misnomer in my opinion.  It doesn't stop the thread immediately.
Instead, it causes the thread to throw an exception which unwinds the stack
and if not caught causes the thread to terminate.  It is deprecated because
the exception can be thrown at any point during the execution of the thread
and this makes it very hard to get it bug free.  (It might be deprecated for
other reasons as well.)  However, if you know that the threads are
indefinitely deadlocked, then the thread won't wake up any time and I
naively don't see why using Thread.stop(Throwable) would be a problem.
(Note: I am not sure if Thread.stop() will throw an exception while the
thread is blocked inside monitorenter).

  > Finally where do I need to present this writeup?

  I have never presented anything outside of Oracle Open World.  I have
attended Java One.  Sorry, I can't be of much help.  Since this is Java
code, you might consider presenting at Java One.  I am not sure if that is
appropriate venue, though.


  Nathan Reynolds | Consulting Member of Technical Staff | 602.333.9091
  Oracle PSR Engineering | Server Technology


  On 4/16/2012 11:36 AM, Rohit Kumar wrote:
    Hans,Nathan,

    I am not aware of anything like Gadara yet. My implementation assumes
that there are no synchnonized keywords (implicit locks) in your program. It
requires you to use explicit locks (e.g. Lock class in java concurrent api).
There is no background thread running here. The deadlock-check happens at
each lock acquisition request; it runs an algorithms internally to see if
there are any cycles formed in the lock-acquisition graph. If yes, it
doesn't let you acquire the lock but throws an exception. You can catch this
exception and take necessary steps to re-acquire all the locks once again or
whatever you want. The program is written in java and it is hardly 270 lines
of code.

    Finally where do I need to present this writeup ?

    Thanks & Regards,
    Rohit Kumar


    From: "concurrency-interest-request at cs.oswego.edu"
<concurrency-interest-request at cs.oswego.edu>
    To: concurrency-interest at cs.oswego.edu
    Sent: Monday, 16 April 2012 10:50 PM
    Subject: Concurrency-interest Digest, Vol 87, Issue 27


    Send Concurrency-interest mailing list submissions to
        concurrency-interest at cs.oswego.edu

    To subscribe or unsubscribe via the World Wide Web, visit
        http://cs.oswego.edu/mailman/listinfo/concurrency-interest
    or, via email, send a message with subject or body 'help' to
        concurrency-interest-request at cs.oswego.edu

    You can reach the person managing the list at
        concurrency-interest-owner at cs.oswego.edu

    When replying, please edit your Subject line so it is more specific
    than "Re: Contents of Concurrency-interest digest..."


    Today's Topics:

      1. Re: CountedCompleters (Wolfgang Baltes)
      2. Re: Java Deadlocks prevented (Boehm, Hans)
      3. Re: Java Deadlocks prevented (Nathan Reynolds)
      4. Re: Concurrency-interest Digest, Vol 87,    Issue 26 (Java
          deadlock prevented) (Rohit Kumar)


    ----------------------------------------------------------------------

    Message: 1
    Date: Mon, 16 Apr 2012 18:01:50 +0200
    From: Wolfgang Baltes <wolfgang.baltes at laposte.net>
    To: concurrency-interest at cs.oswego.edu
    Subject: Re: [concurrency-interest] CountedCompleters
    Message-ID: <4F8C426E.6090704 at laposte.net>
    Content-Type: text/plain; charset=ISO-8859-1; format=flowed

    I apologize for a mistake in the last paragraph of my memo: using
    quietlyJoinUnforked() in the SDK7 sample code for MergeSort does have a
    non-negligible performance impact (not no impact as stated). There is
    better performance in case of recursions which produce many tasks that
    are not explicitly forked, and it reduces the number of extra threads
    significantly, allowing larger problems to be solved with smaller memory
    footprint.

    Wolfgang.

    On 2012-04-16 16:48, Wolfgang Baltes wrote:
    > Thanks, Doug, for a this addition to the FJ framework. I think that
    > CountedCompleter will address the needs of an entire class of
    > applications in an efficient and simple to use manner.
    >
    > I used the code and noticed that method doJoin() has become more
    > effective in avoiding blocking threads, and as a result fewer extra
    > threads are created. I found the performance, compared to
    > RecursiveAction, to be equal or insignificantly different. This
    > reduces the problem described in item 3 below.
    >
    > However, at the same time, CountedCompleter does not fully satisfy the
    > needs for a class of problems I work on. To this end, here are a few
    > enhancements I would like to suggest:
    >
    > 1: Symmetrically to onCompletion(), provide
    > onExceptionalCompletion(Throwable). This allows filtering exception
    > propagation. There are cases where the propagation of the exception is
    > desired, and others where a corrective action is taken instead, such
    > as a retry.
    >
    > 2: As a further enhancement to 1: enable any Throwable, including
    > checked exceptions. This allows the use of a CountedCompleter as a
    > CompletionHandler for asynchronous IO operations or as a wrapper for
    > MethodHandles (which throw Throwable) without adding extra logic to
    > capture and convert an IO exception. I read the documentation which
    > explains why this is currently limited to unchecked exceptions. While
    > I can agree with this in general, I feel the argument is weak for
    > CountedCompleter if it is there to support asynchronous tasks/events.
    > (May I add that using this type of framework is not for the
    > faint-hearted anyway!?)
    >
    > 3: Provide a method to join a task that is not forked and/or not
    > completable, while minimizing worker thread blocking. For example,
    > CountedCompleter allows creating chains of dependent tasks. Unless the
    > ultimate task (the last in the chain) is forked/exists on the task
    > stack AND can complete because all dependencies are resolved, joining
    > it will block the worker thread. I noticed (and my testing is limited
    > to a few test cases and therefore not representative) the blocking and
    > the creation of other worker threads, ultimately running out of memory
    > or reaching the thread count limit. If this task is not forked, then
    > join()/quietlyJoin() will block the worker thread. The following code
    > is my (inexpert) attempt to provide a remedy. It is based on the
    > assumption that a task that depends on others for completion is not
    > forked until all dependencies are resolved. For example, a
    > CountedCompleter implementing CompletionHandler would fork itself
    > ("implicit fork") when the IO operation is done. This works very well
    > in my test cases, but at this time I would not claim it to be
    > universally applicable or error free. It is shown here more to
    > demonstrate the attempt rather than as a reference implementation.
    > With access to private data structures, this can be done more
    > elegantly and more reliably.
    >
    >        static final int RETRIES = 16;
    >        static final long WAIT_TIMEOUT = 1_000;    // Timeout in
    > microseconds.
    >
    >        public final void quietlyJoinUnforked() {
    >            this.doJoinUnforked(false);
    >        }
    >
    >        public final void quietlyJoinUnforkedInterruptibly()
    >        throws InterruptedException {
    >            if (this.doJoinUnforked(true)) {
    >                throw new InterruptedException();
    >            }
    >        }
    >
    >        public final boolean doJoinUnforked(final boolean
    > interruptibly) {
    >            int retries = RETRIES;
    >            boolean wasInterrupted = false;
    >            while (!this.isDone()) {
    >                ForkJoinTask<?> t;
    >                if ((t = pollTask()) != null) {
    >                    t.quietlyInvoke();
    >                    if (t == this) {
    >                        break;
    >                    }
    >                }
    >                else {
    >                    if (retries-- > 0) {
    >                        Thread.yield();
    >                        continue;
    >                    }
    >                    wasInterrupted = Thread.interrupted();
    >                    try {
    >                        // get(...) is used as a timed join(). It is
    > assumed that
    >                        // other code will perform get() on this task
    > to retrieve
    >                        // the task's result or exception.
    >                        this.get(WAIT_TIMEOUT, TimeUnit.MICROSECONDS);
    >                        break;
    >                    }
    >                    catch (final InterruptedException consumed) {
    >                        if (!interruptibly) {
    >                            wasInterrupted = true;
    >                            continue;
    >                        }
    >                        return true;
    >                    }
    >                    catch (final ExecutionException ignored) {
    >                        // See comment on get() above.
    >                        break;
    >                    }
    >                    catch (final TimeoutException ignored) {
    >                        continue;
    >                    }
    >                }
    >                retries = RETRIES;
    >            }
    >            if (wasInterrupted && !interruptibly) {
    >                Thread.currentThread().interrupt();
    >                return false;
    >            }
    >            return wasInterrupted;
    >        }
    >
    > As already mentioned this works quite well in a number of cases. For
    > example, adding this method to the example MergeSort code and calling
    > quietlyJoinUnforked(), results in the same overall performance,
    > reduces the number of extra blocked worker threads to 1 if any
    > (instead of up to 8 for the unmodified code; on a PC with 4
    > hyper-threading cores/8 threads), and allows for some extra
    > (recreational?) freedom in joining the right and left sub-tasks in any
    > order. It works in cases where no sub-task is forked explicitly. I
    > observed that worker thread blocking only occurs towards the end of a
    > large recursion, suggesting that worker threads only block - as
    > intended - when there is no other work available (sometimes while
    > implicit forking has not yet happened).
    >
    > Wolfgang.
    >
    >
    >
    > On 2012-04-09 16:16, Doug Lea wrote:
    >>
    >> After sitting on multiple variations for months, I committed
    >> CountedCompleter, a completion-based flavor of ForkJoinTask.
    >>
    >> As mentioned a few times over the past year, the main motivation
    >> is to better support tasks that perform IO or other base
    >> actions that may (or may not) take a lot of time to execute.
    >> As is the case with JDK7 async IO and other completion-based
    >> frameworks, the most common path to efficiency is for such tasks
    >> to arrange continuation actions that occur upon their completion.
    >> The main twist for CountedCompleters is that continuations
    >> might be dependent on multiple actions, not just one. (Or in
    >> other words, the continuations must be preceded by a specialized,
    >> "bottom-up" form of join.)
    >>
    >> The CountedCompleter abstract class provides a minimal basis
    >> for these kinds of tasks. While some of the mechanics are
    >> reminiscent of other FJ-like frameworks such as Intel TBB,
    >> CountedCompleters are designed to fit smoothly with other
    >> kinds of ForkJoinTasks (like RecursiveActions), and so still
    >> allow people to use the more pleasant Future-style conventions
    >> rather than count-based bottom-up joining unless they need them.
    >> At the same time, the CountedCompleter class exposes enough
    >> mechanics to allow all sorts of tweaks that people can use
    >> to improve performance.
    >> In particular, in addition to usually being the best way to deal
    >> with IO etc bound tasks, CountedCompleters sometimes fare better
    >> than RecursiveActions in programs that entail lots of garbage
    >> collection because GC can have similar impact on task variability.
    >>
    >> Even though targeted for JDK8, versions of CountedCompleter
    >> appear in the jsr166y and main repositories, not jsr166e. This is
    >> because they require a non-public hook into modified ForkJoinTask
    >> exception handling mechanics in order to properly propagate
    >> exceptional completions. For sources, docs, and jar files, see
    >> the usual links at
    >> http://gee.cs.oswego.edu/dl/concurrency-interest/index.html
    >>
    >> The API docs include more details and some examples:
    >>
http://gee.cs.oswego.edu/dl/jsr166/dist/docs/java/util/concurrent/CountedCom
pleter.html
    >>
    >>
    >> I also added a few (with more to come) test/demo programs that
    >> illustrate
    >> other usages. See CCBoxedLongSort and CCJacobi in
    >> http://gee.cs.oswego.edu/cgi-bin/viewcvs.cgi/jsr166/src/test/loops/
    >>
    >> Please try these out. As always, comments and suggestions
    >> (hopefully based on usage experience) would be welcome.
    >>
    >> -Doug
    >>
    >>
    >> _______________________________________________
    >> Concurrency-interest mailing list
    >> Concurrency-interest at cs.oswego.edu
    >> http://cs.oswego.edu/mailman/listinfo/concurrency-interest
    >>
    > _______________________________________________
    > Concurrency-interest mailing list
    > Concurrency-interest at cs.oswego.edu
    > http://cs.oswego.edu/mailman/listinfo/concurrency-interest
    >


    ------------------------------

    Message: 2
    Date: Mon, 16 Apr 2012 16:38:00 +0000
    From: "Boehm, Hans" <hans.boehm at hp.com>
    To: Andrew Haley <aph at redhat.com>,
        "concurrency-interest at cs.oswego.edu"
        <concurrency-interest at cs.oswego.edu>
    Subject: Re: [concurrency-interest] Java Deadlocks prevented
    Message-ID:
        <A3E67C2071F49C4CBC4F17E6D77CDDD235543F5B at G4W3299.americas.hpqcorp.n
et>

    Content-Type: text/plain; charset="us-ascii"

    Important questions to consider when you write it up:

    How does it compare to something like Gadara that uses whole program
analysis and scheduling to avoid lock-based deadlocks?  (Hopefully it
doesn't need whole program analysis.)  Other deadlock avoidance schemes?

    Once you detect a potential deadlock, how do you recover?  Or can you
always schedule so that the possibility doesn't arise?

    Hans

    > -----Original Message-----
    > From: concurrency-interest-bounces at cs.oswego.edu [mailto:concurrency-
    > interest-bounces at cs.oswego.edu] On Behalf Of Andrew Haley
    > Sent: Monday, April 16, 2012 4:34 AM
    > To: concurrency-interest at cs.oswego.edu
    > Subject: Re: [concurrency-interest] Java Deadlocks prevented
    >
    > On 04/16/2012 12:06 PM, Rohit Kumar wrote:
    >
    > > I have found a way of preventing deadlocks in java. The
    > > methodology(which is code) completely prevents the deadlock from
    > > occuring by detecting it in advance. This can be used across the
    > > systems seamlessly.
    > >
    > > Kindly let me know what I need to do next. I want this to be part of
    > > next jdk release. I am writing this email as I have no idea what I
    > > need to do next to bring it into limelight.
    >
    > Write it up, maybe present it to a conference, and wait for feedback.
    > That's how it always works.  If your idea really works, people will
    > use it.
    >
    > Andrew.
    > _______________________________________________
    > Concurrency-interest mailing list
    > Concurrency-interest at cs.oswego.edu
    > http://cs.oswego.edu/mailman/listinfo/concurrency-interest



    ------------------------------

    Message: 3
    Date: Mon, 16 Apr 2012 10:11:00 -0700
    From: Nathan Reynolds <nathan.reynolds at oracle.com>
    To: "Boehm, Hans" <hans.boehm at hp.com>
    Cc: "concurrency-interest at cs.oswego.edu"
        <concurrency-interest at cs.oswego.edu>
    Subject: Re: [concurrency-interest] Java Deadlocks prevented
    Message-ID: <4F8C52A4.70002 at oracle.com>
    Content-Type: text/plain; charset="iso-8859-1"; Format="flowed"

    Deadlock prevention is very valuable.  It means deadlock prone code
    won't bring down a production server and cost the company millions in
    down time.  It means consumers won't kill the process and request a
refund.

    How much does deadlock prevention cost?  Is the cost on the thread that
    acquires locks or is it in a background thread?

    Each time processors or systems increase the number of cores, I find we
    have to do a round of lock contention fixing.  I have only seen 1 lock
    at a time be the bottleneck in the system.  Does deadlock prevention
    increase the critical region of locks?  If so, this will definitely
    reduce the scalability of the system if it impacts the 1 bottlenecking
lock.

    Lock performance is a very important consideration.  Locks have evolved
    from fat locks (i.e trips into the OS kernel) to thin locks (i.e. spin
    and CAS in user mode) to biased/lazy locks (i.e. no CAS and an
    indefinite lock owner).  All of this was done to reduce the performance
    overhead of locks.  How does deadlock prevention impact the performance
    of biased, thin and fat locks?  I am not as concerned about fat lock
    performance since most of the time the thread is going to block.

    Nathan Reynolds
    <http://psr.us.oracle.com/wiki/index.php/User:Nathan_Reynolds> |
    Consulting Member of Technical Staff | 602.333.9091
    Oracle PSR Engineering <http://psr.us.oracle.com/> | Server Technology

    On 4/16/2012 9:38 AM, Boehm, Hans wrote:
    > Important questions to consider when you write it up:
    >
    > How does it compare to something like Gadara that uses whole program
analysis and scheduling to avoid lock-based deadlocks?  (Hopefully it
doesn't need whole program analysis.)  Other deadlock avoidance schemes?
    >
    > Once you detect a potential deadlock, how do you recover?  Or can you
always schedule so that the possibility doesn't arise?
    >
    > Hans
    >
    >> -----Original Message-----
    >> From: concurrency-interest-bounces at cs.oswego.edu [mailto:concurrency-
    >> interest-bounces at cs.oswego.edu] On Behalf Of Andrew Haley
    >> Sent: Monday, April 16, 2012 4:34 AM
    >> To: concurrency-interest at cs.oswego.edu
    >> Subject: Re: [concurrency-interest] Java Deadlocks prevented
    >>
    >> On 04/16/2012 12:06 PM, Rohit Kumar wrote:
    >>
    >>> I have found a way of preventing deadlocks in java. The
    >>> methodology(which is code) completely prevents the deadlock from
    >>> occuring by detecting it in advance. This can be used across the
    >>> systems seamlessly.
    >>>
    >>> Kindly let me know what I need to do next. I want this to be part of
    >>> next jdk release. I am writing this email as I have no idea what I
    >>> need to do next to bring it into limelight.
    >> Write it up, maybe present it to a conference, and wait for feedback.
    >> That's how it always works.  If your idea really works, people will
    >> use it.
    >>
    >> Andrew.
    >> _______________________________________________
    >> Concurrency-interest mailing list
    >> Concurrency-interest at cs.oswego.edu
    >> http://cs.oswego.edu/mailman/listinfo/concurrency-interest
    > _______________________________________________
    > Concurrency-interest mailing list
    > Concurrency-interest at cs.oswego.edu
    > http://cs.oswego.edu/mailman/listinfo/concurrency-interest
    -------------- next part --------------
    An HTML attachment was scrubbed...
    URL:
<http://cs.oswego.edu/pipermail/concurrency-interest/attachments/20120416/7e
a89bb3/attachment-0001.html>

    ------------------------------

    Message: 4
    Date: Tue, 17 Apr 2012 01:20:15 +0800 (SGT)
    From: Rohit Kumar <rohitk242 at yahoo.co.in>
    To: "concurrency-interest at cs.oswego.edu"
        <concurrency-interest at cs.oswego.edu>
    Subject: Re: [concurrency-interest] Concurrency-interest Digest, Vol
        87,    Issue 26 (Java deadlock prevented)
    Message-ID:
        <1334596815.27848.YahooMailNeo at web193403.mail.sg3.yahoo.com>
    Content-Type: text/plain; charset="iso-8859-1"

    Andrew:
    ?
    Thanks for the reply. Can you kindly let me know where do I need to
present it ? Where will the conference be held ? Can I present it online or
I have to come in person ?
    ?
    Waiting for your early reply once again.
    ?
    Thanks & Regards,
    Rohit Kumar

    From: "concurrency-interest-request at cs.oswego.edu"
<concurrency-interest-request at cs.oswego.edu>
    To: concurrency-interest at cs.oswego.edu
    Sent: Monday, 16 April 2012 9:30 PM
    Subject: Concurrency-interest Digest, Vol 87, Issue 26

    Send Concurrency-interest mailing list submissions to
    ??? concurrency-interest at cs.oswego.edu

    To subscribe or unsubscribe via the World Wide Web, visit
    ??? http://cs.oswego.edu/mailman/listinfo/concurrency-interest
    or, via email, send a message with subject or body 'help' to
    ??? concurrency-interest-request at cs.oswego.edu

    You can reach the person managing the list at
    ??? concurrency-interest-owner at cs.oswego.edu

    When replying, please edit your Subject line so it is more specific
    than "Re: Contents of Concurrency-interest digest..."


    Today's Topics:

    ? 1. (no subject) (Rohit Kumar)
    ? 2. Java Deadlocks prevented (Rohit Kumar)
    ? 3. Re: Java Deadlocks prevented (Andrew Haley)
    ? 4. Re: CountedCompleters (Wolfgang Baltes)


    ----------------------------------------------------------------------

    Message: 1
    Date: Mon, 16 Apr 2012 19:03:59 +0800 (SGT)
    From: Rohit Kumar <rohitk242 at yahoo.co.in>
    To: "concurrency-interest at cs.oswego.edu"
    ??? <concurrency-interest at cs.oswego.edu>
    Cc: "concurrency-interest-owner at cs.oswego.edu"
    ??? <concurrency-interest-owner at cs.oswego.edu>
    Subject: [concurrency-interest] (no subject)
    Message-ID:
    ??? <1334574239.81244.YahooMailNeo at web193402.mail.sg3.yahoo.com>
    Content-Type: text/plain; charset="iso-8859-1"

    Hi All,
    ?
    I have found a way of preventing deadlocks in java. The
methodology(which is code) completely prevents the deadlock from accuring by
detecting it in advance. This can be used across the systems seamlessly.
    ?
    Kindly let me know what I need to do next. I want this to be part of
next jdk release.
    ?
    Thanks & Regards,
    Rohit Kumar
    -------------- next part --------------
    An HTML attachment was scrubbed...
    URL:
<http://cs.oswego.edu/pipermail/concurrency-interest/attachments/20120416/a6
588341/attachment-0001.html>

    ------------------------------

    Message: 2
    Date: Mon, 16 Apr 2012 19:06:22 +0800 (SGT)
    From: Rohit Kumar <rohitk242 at yahoo.co.in>
    To: "concurrency-interest at cs.oswego.edu"
    ??? <concurrency-interest at cs.oswego.edu>
    Cc: "concurrency-interest-owner at cs.oswego.edu"
    ??? <concurrency-interest-owner at cs.oswego.edu>
    Subject: [concurrency-interest] Java Deadlocks prevented
    Message-ID:
    ??? <1334574382.90584.YahooMailNeo at web193403.mail.sg3.yahoo.com>
    Content-Type: text/plain; charset="utf-8"



    Hi All,

    I have found a way of preventing deadlocks in java. The
methodology(which is code) completely prevents the deadlock from occuring by
detecting it in advance. This can be used across the systems seamlessly.

    Kindly let me know what I need to do next. I want this to be part of
next jdk release. I am writing this email as I have no idea what I need to
do next to bring it into limelight.

    Thanks & Regards,
    Rohit Kumar
    -------------- next part --------------
    An HTML attachment was scrubbed...
    URL:
<http://cs.oswego.edu/pipermail/concurrency-interest/attachments/20120416/06
4a4873/attachment-0001.html>

    ------------------------------

    Message: 3
    Date: Mon, 16 Apr 2012 12:33:45 +0100
    From: Andrew Haley <aph at redhat.com>
    To: concurrency-interest at cs.oswego.edu
    Subject: Re: [concurrency-interest] Java Deadlocks prevented
    Message-ID: <4F8C0399.8040301 at redhat.com>
    Content-Type: text/plain; charset=ISO-8859-1

    On 04/16/2012 12:06 PM, Rohit Kumar wrote:

    > I have found a way of preventing deadlocks in java. The
    > methodology(which is code) completely prevents the deadlock from
    > occuring by detecting it in advance. This can be used across the
    > systems seamlessly.
    >
    > Kindly let me know what I need to do next. I want this to be part of
    > next jdk release. I am writing this email as I have no idea what I
    > need to do next to bring it into limelight.

    Write it up, maybe present it to a conference, and wait for feedback.
    That's how it always works.? If your idea really works, people will
    use it.

    Andrew.


    ------------------------------

    Message: 4
    Date: Mon, 16 Apr 2012 16:48:31 +0200
    From: Wolfgang Baltes <wolfgang.baltes at laposte.net>
    To: "Concurrency-interest at cs.oswego.edu"
    ??? <Concurrency-interest at cs.oswego.edu>
    Subject: Re: [concurrency-interest] CountedCompleters
    Message-ID: <4F8C313F.2080308 at laposte.net>
    Content-Type: text/plain; charset=ISO-8859-1; format=flowed

    Thanks, Doug, for a this addition to the FJ framework. I think that
    CountedCompleter will address the needs of an entire class of
    applications in an efficient and simple to use manner.

    I used the code and noticed that method doJoin() has become more
    effective in avoiding blocking threads, and as a result fewer extra
    threads are created. I found the performance, compared to
    RecursiveAction, to be equal or insignificantly different. This reduces
    the problem described in item 3 below.

    However, at the same time, CountedCompleter does not fully satisfy the
    needs for a class of problems I work on. To this end, here are a few
    enhancements I would like to suggest:

    1: Symmetrically to onCompletion(), provide
    onExceptionalCompletion(Throwable). This allows filtering exception
    propagation. There are cases where the propagation of the exception is
    desired, and others where a corrective action is taken instead, such as
    a retry.

    2: As a further enhancement to 1: enable any Throwable, including
    checked exceptions. This allows the use of a CountedCompleter as a
    CompletionHandler for asynchronous IO operations or as a wrapper for
    MethodHandles (which throw Throwable) without adding extra logic to
    capture and convert an IO exception. I read the documentation which
    explains why this is currently limited to unchecked exceptions. While I
    can agree with this in general, I feel the argument is weak for
    CountedCompleter if it is there to support asynchronous tasks/events.
    (May I add that using this type of framework is not for the
    faint-hearted anyway!?)

    3: Provide a method to join a task that is not forked and/or not
    completable, while minimizing worker thread blocking. For example,
    CountedCompleter allows creating chains of dependent tasks. Unless the
    ultimate task (the last in the chain) is forked/exists on the task stack
    AND can complete because all dependencies are resolved, joining it will
    block the worker thread. I noticed (and my testing is limited to a few
    test cases and therefore not representative) the blocking and the
    creation of other worker threads, ultimately running out of memory or
    reaching the thread count limit. If this task is not forked, then
    join()/quietlyJoin() will block the worker thread. The following code is
    my (inexpert) attempt to provide a remedy. It is based on the assumption
    that a task that depends on others for completion is not forked until
    all dependencies are resolved. For example, a CountedCompleter
    implementing CompletionHandler would fork itself ("implicit fork") when
    the IO operation is done. This works very well in my test cases, but at
    this time I would not claim it to be universally applicable or error
    free. It is shown here more to demonstrate the attempt rather than as a
    reference implementation. With access to private data structures, this
    can be done more elegantly and more reliably.

    ? ? ? ? static final int RETRIES = 16;
    ? ? ? ? static final long WAIT_TIMEOUT = 1_000;? ? // Timeout in
    microseconds.

    ? ? ? ? public final void quietlyJoinUnforked() {
    ? ? ? ? ? ? this.doJoinUnforked(false);
    ? ? ? ? }

    ? ? ? ? public final void quietlyJoinUnforkedInterruptibly()
    ? ? ? ? throws InterruptedException {
    ? ? ? ? ? ? if (this.doJoinUnforked(true)) {
    ? ? ? ? ? ? ? ? throw new InterruptedException();
    ? ? ? ? ? ? }
    ? ? ? ? }

    ? ? ? ? public final boolean doJoinUnforked(final boolean interruptibly)
{
    ? ? ? ? ? ? int retries = RETRIES;
    ? ? ? ? ? ? boolean wasInterrupted = false;
    ? ? ? ? ? ? while (!this.isDone()) {
    ? ? ? ? ? ? ? ? ForkJoinTask<?> t;
    ? ? ? ? ? ? ? ? if ((t = pollTask()) != null) {
    ? ? ? ? ? ? ? ? ? ? t.quietlyInvoke();
    ? ? ? ? ? ? ? ? ? ? if (t == this) {
    ? ? ? ? ? ? ? ? ? ? ? ? break;
    ? ? ? ? ? ? ? ? ? ? }
    ? ? ? ? ? ? ? ? }
    ? ? ? ? ? ? ? ? else {
    ? ? ? ? ? ? ? ? ? ? if (retries-- > 0) {
    ? ? ? ? ? ? ? ? ? ? ? ? Thread.yield();
    ? ? ? ? ? ? ? ? ? ? ? ? continue;
    ? ? ? ? ? ? ? ? ? ? }
    ? ? ? ? ? ? ? ? ? ? wasInterrupted = Thread.interrupted();
    ? ? ? ? ? ? ? ? ? ? try {
    ? ? ? ? ? ? ? ? ? ? ? ? // get(...) is used as a timed join(). It is
    assumed that
    ? ? ? ? ? ? ? ? ? ? ? ? // other code will perform get() on this task
    to retrieve
    ? ? ? ? ? ? ? ? ? ? ? ? // the task's result or exception.
    ? ? ? ? ? ? ? ? ? ? ? ? this.get(WAIT_TIMEOUT, TimeUnit.MICROSECONDS);
    ? ? ? ? ? ? ? ? ? ? ? ? break;
    ? ? ? ? ? ? ? ? ? ? }
    ? ? ? ? ? ? ? ? ? ? catch (final InterruptedException consumed) {
    ? ? ? ? ? ? ? ? ? ? ? ? if (!interruptibly) {
    ? ? ? ? ? ? ? ? ? ? ? ? ? ? wasInterrupted = true;
    ? ? ? ? ? ? ? ? ? ? ? ? ? ? continue;
    ? ? ? ? ? ? ? ? ? ? ? ? }
    ? ? ? ? ? ? ? ? ? ? ? ? return true;
    ? ? ? ? ? ? ? ? ? ? }
    ? ? ? ? ? ? ? ? ? ? catch (final ExecutionException ignored) {
    ? ? ? ? ? ? ? ? ? ? ? ? // See comment on get() above.
    ? ? ? ? ? ? ? ? ? ? ? ? break;
    ? ? ? ? ? ? ? ? ? ? }
    ? ? ? ? ? ? ? ? ? ? catch (final TimeoutException ignored) {
    ? ? ? ? ? ? ? ? ? ? ? ? continue;
    ? ? ? ? ? ? ? ? ? ? }
    ? ? ? ? ? ? ? ? }
    ? ? ? ? ? ? ? ? retries = RETRIES;
    ? ? ? ? ? ? }
    ? ? ? ? ? ? if (wasInterrupted && !interruptibly) {
    ? ? ? ? ? ? ? ? Thread.currentThread().interrupt();
    ? ? ? ? ? ? ? ? return false;
    ? ? ? ? ? ? }
    ? ? ? ? ? ? return wasInterrupted;
    ? ? ? ? }

    As already mentioned this works quite well in a number of cases. For
    example, adding this method to the example MergeSort code and calling
    quietlyJoinUnforked(), results in the same overall performance, reduces
    the number of extra blocked worker threads to 1 if any (instead of up to
    8 for the unmodified code; on a PC with 4 hyper-threading cores/8
    threads), and allows for some extra (recreational?) freedom in joining
    the right and left sub-tasks in any order. It works in cases where no
    sub-task is forked explicitly. I observed that worker thread blocking
    only occurs towards the end of a large recursion, suggesting that worker
    threads only block - as intended - when there is no other work available
    (sometimes while implicit forking has not yet happened).

    Wolfgang.



    On 2012-04-09 16:16, Doug Lea wrote:
    >
    > After sitting on multiple variations for months, I committed
    > CountedCompleter, a completion-based flavor of ForkJoinTask.
    >
    > As mentioned a few times over the past year, the main motivation
    > is to better support tasks that perform IO or other base
    > actions that may (or may not) take a lot of time to execute.
    > As is the case with JDK7 async IO and other completion-based
    > frameworks, the most common path to efficiency is for such tasks
    > to arrange continuation actions that occur upon their completion.
    > The main twist for CountedCompleters is that continuations
    > might be dependent on multiple actions, not just one. (Or in
    > other words, the continuations must be preceded by a specialized,
    > "bottom-up" form of join.)
    >
    > The CountedCompleter abstract class provides a minimal basis
    > for these kinds of tasks. While some of the mechanics are
    > reminiscent of other FJ-like frameworks such as Intel TBB,
    > CountedCompleters are designed to fit smoothly with other
    > kinds of ForkJoinTasks (like RecursiveActions), and so still
    > allow people to use the more pleasant Future-style conventions
    > rather than count-based bottom-up joining unless they need them.
    > At the same time, the CountedCompleter class exposes enough
    > mechanics to allow all sorts of tweaks that people can use
    > to improve performance.
    > In particular, in addition to usually being the best way to deal
    > with IO etc bound tasks, CountedCompleters sometimes fare better
    > than RecursiveActions in programs that entail lots of garbage
    > collection because GC can have similar impact on task variability.
    >
    > Even though targeted for JDK8, versions of CountedCompleter
    > appear in the jsr166y and main repositories, not jsr166e. This is
    > because they require a non-public hook into modified ForkJoinTask
    > exception handling mechanics in order to properly propagate
    > exceptional completions. For sources, docs, and jar files, see
    > the usual links at
    > http://gee.cs.oswego.edu/dl/concurrency-interest/index.html
    >
    > The API docs include more details and some examples:
    >
http://gee.cs.oswego.edu/dl/jsr166/dist/docs/java/util/concurrent/CountedCom
pleter.html
    >
    >
    > I also added a few (with more to come) test/demo programs that
illustrate
    > other usages. See CCBoxedLongSort and CCJacobi in
    > http://gee.cs.oswego.edu/cgi-bin/viewcvs.cgi/jsr166/src/test/loops/
    >
    > Please try these out. As always, comments and suggestions
    > (hopefully based on usage experience) would be welcome.
    >
    > -Doug
    >
    >
    > _______________________________________________
    > Concurrency-interest mailing list
    > Concurrency-interest at cs.oswego.edu
    > http://cs.oswego.edu/mailman/listinfo/concurrency-interest
    >


    ------------------------------

    _______________________________________________
    Concurrency-interest mailing list
    Concurrency-interest at cs.oswego.edu
    http://cs.oswego.edu/mailman/listinfo/concurrency-interest


    End of Concurrency-interest Digest, Vol 87, Issue 26
    ****************************************************
    -------------- next part --------------
    An HTML attachment was scrubbed...
    URL:
<http://cs.oswego.edu/pipermail/concurrency-interest/attachments/20120417/75
746dcb/attachment.html>

    ------------------------------

    _______________________________________________
    Concurrency-interest mailing list
    Concurrency-interest at cs.oswego.edu
    http://cs.oswego.edu/mailman/listinfo/concurrency-interest


    End of Concurrency-interest Digest, Vol 87, Issue 27
    ****************************************************






_______________________________________________
Concurrency-interest mailing list
Concurrency-interest at cs.oswego.edu
http://cs.oswego.edu/mailman/listinfo/concurrency-interest


-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs.oswego.edu/pipermail/concurrency-interest/attachments/20120417/f6329099/attachment-0001.html>


More information about the Concurrency-interest mailing list