[concurrency-interest] Concurrency-interest Digest, Vol 87, Issue 26 (Java deadlock prevented)

Rohit Kumar rohitk242 at yahoo.co.in
Mon Apr 16 13:20:15 EDT 2012


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/a6588341/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/064a4873/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/CountedCompleter.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/75746dcb/attachment-0001.html>


More information about the Concurrency-interest mailing list