[concurrency-interest] Concurrency-interest Digest, Vol 87, Issue 19

Boehm, Hans hans.boehm at hp.com
Wed Apr 11 18:50:15 EDT 2012


Once you know that a program is data-race-free, you know that synchronization-free code regions appear to be atomic, even if they access shared data.  If an observer thread could witness a state in the middle of a synchronization-free code region, then the observer would be engaged in a data race with that synchronization-free region.  We rely on that regularly when optimizing multi-threaded programs; we usually optimize synchronization-free regions almost as though they were sequential code, knowing that another thread can only catch us in the act by introducing a data race.  As a result, it seems to me that data-race-freedom is potentially a very useful tool for a priori narrowing the search space.

Similarly, I believe that you can always find the first data race in a program while considering only context switches at synchronization points.  The execution up to that point is data-race-free, and hence synchronization-free regions behave atomically.  Thus if there is a data race, there has to be an interleaving of synchronization-free regions in which two conflicting operations are in synchronization-free regions not ordered by happens-before.

If you wanted to write a correct Java version of the lock implementation you cite, some of the lock fields would have to be declared volatile, and accesses to those fields would thus be considered synchronization operations.

Thus I think you need to consider context switches at ordinary shared variable accesses only for intentionally racy programs.  And to first-order approximation, you shouldn't be writing those.  And indeed considering context switches at such accesses seems inherently dubious, since compilers don't preserve access order etc. within synchronization-free regions.  You would really have to correctly model the behavior of racy variable accesses in Java, and we don't really know what that is.

It's less clear to me whether any of this actually helps in practice, or whether the search space you eliminate a priori this way would have also been easy to eliminate by other means.

Hans

From: Nathan Reynolds [mailto:nathan.reynolds at oracle.com]
Sent: Wednesday, April 11, 2012 10:07 AM
To: Boehm, Hans
Cc: concurrency-interest at cs.oswego.edu
Subject: Re: [concurrency-interest] Concurrency-interest Digest, Vol 87, Issue 19

When you said synchronization points do you mean communication points?  By communication points, I mean two threads accessing shared data.

Let's say you write a lock based off of the code in this paper.  http://www.cise.ufl.edu/tr/DOC/REP-1992-71.pdf   The paper claims it is correct.  But, can you prove that your implementation is correct?  Concurrency bugs are extremely difficult to find via code inspection.  This is where Java Path Finder can be a huge help.

Java Path Finder employs a lot of tricks to reduce the search space.  For example, operations on objects which are only visible to 1 thread never increase the search space.  Of course, reducing the amount of code tested to only those areas where threads can interact is very helpful.  Reducing the number of threads down to 2 is also very helpful (when possible).  Even so, the search space can still be very large depending upon how complex the concurrent algorithm is.
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/10/2012 10:25 AM, Boehm, Hans wrote:

Naively, this approach seems like a bit of overkill.  Once you know that the program is data-race-free, which you should be able to determine by considering only context switches at synchronization points, you then know that program behavior can't be affected by context switches anywhere other than at synchronization points.  Thus naively it seems to me that if your target is a data-race-free program, you should be able to greatly reduce the search space.  Am I missing something?  Or are there other techniques that effectively already take advantage of this?



Hans



-----Original Message-----

From: concurrency-interest-bounces at cs.oswego.edu<mailto:concurrency-interest-bounces at cs.oswego.edu> [mailto:concurrency-

interest-bounces at cs.oswego.edu<mailto:interest-bounces at cs.oswego.edu>] On Behalf Of Beverly Sanders

Sent: Tuesday, April 10, 2012 5:52 AM

To: concurrency-interest at cs.oswego.edu<mailto:concurrency-interest at cs.oswego.edu>

Subject: Re: [concurrency-interest] Concurrency-interest Digest, Vol

87, Issue 19





There is an extension to java pathfinder that can precisely detect data

races as defined by the JMM, and thus works for lock-free algorithms

that

use volatiles and atomics.



http://babelfish.arc.nasa.gov/trac/jpf/wiki/projects/jpf-racefinder



I'm not sure if the tool has kept up with the latest changes to jpf,

but

expressions of interest could encourage that to happen.



Generally, you would want to to check your program with standard JPF

first, then use jpf-racefinder to make sure there are no data races.

If

the program is data-race free, then standard JPF is sound.



(If you are intersted in using JPF to reason about Java programs that

intentionally have, presumably benign, data races, please contact me.

See

the paper by Jin, Yavuz-Khaveci and Sanders in TACAS'12)





On Tue, April 10, 2012 7:45 am, concurrency-interest-

request at cs.oswego.edu<mailto:request at cs.oswego.edu>

wrote:

Send Concurrency-interest mailing list submissions to

  concurrency-interest at cs.oswego.edu<mailto: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<mailto:concurrency-interest-request at cs.oswego.edu>



You can reach the person managing the list at

  concurrency-interest-owner at cs.oswego.edu<mailto: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: Joint Talk for JavaOne? (Kearney, Joe)





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

-



Message: 1

Date: Tue, 10 Apr 2012 12:44:58 +0100

From: "Kearney, Joe" <Joe.Kearney at gsacapital.com><mailto:Joe.Kearney at gsacapital.com>

To: Nathan Reynolds <nathan.reynolds at oracle.com><mailto:nathan.reynolds at oracle.com>

Cc: "Concurrency-interest at cs.oswego.edu"<mailto:Concurrency-interest at cs.oswego.edu>

  <Concurrency-interest at cs.oswego.edu><mailto:Concurrency-interest at cs.oswego.edu>

Subject: Re: [concurrency-interest] Joint Talk for JavaOne?

Message-ID:

  <9319F360221C65428EA819A4E8DC34ED03A399B03C at OPMBOX21UK.options<mailto:9319F360221C65428EA819A4E8DC34ED03A399B03C at OPMBOX21UK.options>-

it.com>

Content-Type: text/plain; charset="iso-8859-1"



Does lack of support for volatile fields render this tool useless for

testing non-blocking concurrency and concurrent programs that don't

only

use synchronized blocks?



In particular does it support locking through LockSupport, AQS and

friends

- for example does it understand uses of Phaser or CyclicBarrier?



Is there a list somewhere of these limitations? Perhaps these things

are

spread around the sub-projects.



Thanks,

Joe



From: concurrency-interest-bounces at cs.oswego.edu<mailto:concurrency-interest-bounces at cs.oswego.edu>

[mailto:concurrency-interest-bounces at cs.oswego.edu] On Behalf Of

Nathan

Reynolds

Sent: 09 April 2012 17:44

To: Mohan Radhakrishnan

Cc: Concurrency-interest at cs.oswego.edu<mailto:Concurrency-interest at cs.oswego.edu>

Subject: Re: [concurrency-interest] Joint Talk for JavaOne?



Java Path Finder is great for finding deadlocks and data races.

However,

it has its limitations.



 1.  The search space is exponential in the number of threads (i.e.

O(2t)).  This program has way too many threads.  One would have to

reduce

the threads to a bare minimum.

 2.  The Java Memory Model (i.e. volatile fields) isn't supported.

That

isn't a problem in this case but something to be aware of.



Otherwise, I rely on Java Path Finder to prove that my code is going

to

work in concurrent situations.  It has found a ton of concurrency

bugs in

my code.

Nathan



Reynolds<http://psr.us.oracle.com/wiki/index.php/User: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/><http://psr.us.oracle.com/> | Server Technology



On 4/8/2012 8:23 PM, Mohan Radhakrishnan wrote:

I could look at the first deadlock by dumping locks and threads. I

was

planning to find the next one using Java Path Finder but I think it

is not

recommended for such a big codebase. I am not sure. Its heuristics

might

take too much memory.



Mohan

On Mon, Apr 9, 2012 at 3:59 AM,

<mabrouk2005 at gmail.com<mailto:mabrouk2005 at gmail.com><mailto:mabrouk2005 at gmail.com><mailto:mabrouk2005 at gmail.com>> wrote:

Nice exercise Dr Heinz,



As others mentioned there were 2 kind of deadlocks the first one was

very is easy to find via jconsole so likeI thought that was it and

went and fixed that but then when ran it again it hang it so I knew

thee was more. the interesting thing the jconsole did not detect the

AWT deadlock it showed no deadlock even though the app hang. I had to

force stack dump and get clues to where is the deadlock. Does anyone

have experienced something like this with jconsole not detecting AWT

deadlocks?



Thanks again for the nice exercise and the great java news letter I

am

a big fan.



Cheers,

Mabrouk



On Sat, Apr 7, 2012 at 7:42 AM, Remi Forax

<forax at univ-mlv.fr<mailto:forax at univ-mlv.fr><mailto:forax at univ-mlv.fr><mailto:forax at univ-mlv.fr>> wrote:

No, it's more an AWRY or Java2D bug.



R?mi



Sent from my Phone





----- Reply message -----

From: "Ben Evans"



<benjamin.john.evans at gmail.com<mailto:benjamin.john.evans at gmail.com><mailto:benjamin.john.evans at gmail.com><mailto:benjamin.john.evans at gmail.com>>

To: "Dr Heinz M. Kabutz"

<heinz at javaspecialists.eu<mailto:heinz at javaspecialists.eu><mailto:heinz at javaspecialists.eu><mailto:heinz at javaspecialists.eu>>

Cc: "R?mi Forax" <forax at univ-mlv.fr<mailto:forax at univ-mlv.fr><mailto:forax at univ-mlv.fr><mailto:forax at univ-mlv.fr>>,

<concurrency-interest at cs.oswego.edu<mailto:concurrency-interest at cs.oswego.edu><mailto:concurrency-

interest at cs.oswego.edu<mailto:interest at cs.oswego.edu>>>

Subject: [concurrency-interest] Joint Talk for JavaOne?

Date: Sat, Apr 7, 2012 10:43





Heinz, was this with the new jdk8 + lambda build?



If so, we should report this crash back to lambda-dev.



Thanks,



Ben



On Sat, Apr 7, 2012 at 11:17 AM, Dr Heinz M. Kabutz

<heinz at javaspecialists.eu<mailto:heinz at javaspecialists.eu><mailto:heinz at javaspecialists.eu><mailto:heinz at javaspecialists.eu>> wrote:

I see JDK8 crashes even with the vanilla Java2Demo from JDK 1.6.  I

see

that

the Java2Demo has been removed from the demos folder of JDK 1.7 and

1.8.

 It

thus is a Java 8 issue, rather than the changes I made to the code.

 Thanks

for the warning R?mi.





Regards



Heinz

--

Dr Heinz M. Kabutz (PhD CompSci)

Author of "The Java(tm) Specialists' Newsletter"

Sun Java Champion

IEEE Certified Software Development Professional

http://www.javaspecialists.eu

Tel: +30 69 75 595 262

Skype: kabutz





On 4/6/12 1:51 AM, R?mi Forax wrote:



jdk8 crashes if I click on images of the tapped pane.



R?mi



On 04/05/2012 10:35 PM, Dr Heinz M. Kabutz wrote:



Yes, you are correct.



However, the mistake most programmers make is to #1 scratch

around in

the

source code to try and discover the problem and #2 then fix it

without

really understanding what they are doing.  I think the lesson is

bigger

if

we give them the source code.  In addition, it is probably more

difficult to

solve if you have the sources to muse over.

Regards



Heinz

--

Dr Heinz M. Kabutz (PhD CompSci)

Author of "The Java(tm) Specialists' Newsletter"

Sun Java Champion

IEEE Certified Software Development Professional

http://www.javaspecialists.eu

Tel: +30 69 75 595 262

Skype: kabutz





On 4/5/12 11:30 PM, Nathan Reynolds wrote:



I guess it is a good idea to not initially include the source

code

in

the workshop because many times I initially don't have the

source

code

when

trying to figure out performance or scalability problems.



Nathan Reynolds

<http://psr.us.oracle.com/wiki/index.php/User: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/><http://psr.us.oracle.com/> | Server

Technology



On 4/5/2012 1:22 PM, Dr Heinz M. Kabutz wrote:



Sorry Nathan, here is the zip file including the source code an

an

Ant

script to build the code.  Sorry for accidentally excluding

that

from

the

file I sent earlier.  The problem was between the chair and the

keyboard.

 However, one should be able to pinpoint the deadlock without

seeing a

line

of code.  At the workshop I presented in Spain last week, most

of

the

programmers immediately started delving into the code before

they

knew

where

to look.

Regards



Heinz

--

Dr Heinz M. Kabutz (PhD CompSci)

Author of "The Java(tm) Specialists' Newsletter"

Sun Java Champion

IEEE Certified Software Development Professional

http://www.javaspecialists.eu

Tel: +30 69 75 595 262

Skype: kabutz



On 4/5/12 10:29 PM, Nathan Reynolds wrote:



I took the bait and tried out the demo on HotSpot 7 Update 3.

It

didn't deadlock for a minute or two.  Then the application

froze.

I

then

used jstack to dump the call stacks.  At the end of the

report, it

said

"Found one Java-level deadlock".  It then dumped out the locks

and

threads

involved in the deadlock.  I never looked at the source

code... in

fact it

wasn't in the zip file.  This took about 5-7 minutes from

starting

the

application to finding the deadlock in the call stacks.



A 100 good Java developers?  Really?  I guess I can

understand.

Most

engineers don't understand locks.  Most of the time I get

answers

like one

should put a lock around shared variables.  This is accurate

but

they

can't

really go any deeper.



It sounds like the material of your presentation should be

very

good.

 It covers things that the deadlock detection tool probably

can't

figure

out.



So, it seems like you have everything figured out.  Why do you

need

someone else?



Nathan Reynolds

<http://psr.us.oracle.com/wiki/index.php/User: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/><http://psr.us.oracle.com/> | Server

Technology



On 4/5/2012 12:03 PM, Dr Heinz M. Kabutz wrote:



Hi Nathan,



a stack trace will only show you a certain class of obvious

deadlocks

that are easy to find and solve.  I remember solving

deadlocks

/before/ we

had the brilliant deadlock detection tool in the

ThreadMXBean.

Yes,

the

deadlock detection tool shows you /some/ deadlocks, but

definitely

not all

of them.  I can think of a bunch that it would not find:



1. Semaphores running out of permits

2. ReadWriteLocks trying to upgrade from write lock to read

lock

3. Resource deadlocks



And some others that I will not describe in detail, such as

some

nasty livelocks that we can cause which will hang up the JVM

:-)



I agree with Kirk - it should probably be a 3 hour workshop.

I've

done this three times now - twice in Spain and once via

webinar.

 The

workshop would involve some lessons on deadlocks, what causes

them

and how

we can prevent them.  Also an explanation as to why we see

them

so

seldom in

real production.  I've got material prepared for this

workshop.

And

then a

practical part to the workshop where they can try to find a

deadlock

in a

body of code.



Attached is an example of the workshop.  You can try find the

deadlock if you like.  I've shown it to almost 100 good Java

developers and

so far, not one has found it by themselves.  I would expect

that

they should

find it in 5 minutes.  In our workshop they would obviously

be

helped a bit

with hints, so that they can walk away with a good

experience.

Use

anything

you like.  Oscilloscope, jstack, jconsole, whatever you like.

Only

rule for

you guys on the "concurrency-interest" list is: you can only

look

at

the

code once you've found the problem, otherwise it would be too

easy

for you

:-)  Once you have found it, you can also fix the code and

make

sure

that

the code then works correctly.

Regards



Heinz

--

Dr Heinz M. Kabutz (PhD CompSci)

Author of "The Java(tm) Specialists' Newsletter"

Sun Java Champion

IEEE Certified Software Development Professional

http://www.javaspecialists.eu

Tel: +30 69 75 595 262

Skype: kabutz



On 4/5/12 8:01 PM, Nathan Reynolds wrote:



I am curious as to the intended content of your

presentation.

 Here's some ideas.  I wondering what you are planing on

doing.



 1. Printing the call stacks with lock information using a

tool

   such as jstack

 2. Press the "Detect Deadlock" button in JConsole

 3. Dealing with Lock and Condition objects instead of

   synchronized blocks

 4. Detecting live lock

 5. Distributed deadlocks



Nathan Reynolds



<http://psr.us.oracle.com/wiki/index.php/User: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/><http://psr.us.oracle.com/> | Server

Technology



On 4/5/2012 7:57 AM, Dr Heinz M. Kabutz wrote:



Good afternoon,



I am thinking of submitting a talk on finding and

diagnosing

deadlocks for JavaOne.  It might be a workshop, instead of

a

simple

conference talk.  Or we might be able to turn the talk into

a

workshop where

they need to find a deadlock in a body of code.  Could be

something

different, which might go incredibly well or crash in a

blaze

of

flames.

 Would any of you be interested in co-presenting this with

me

at

JavaOne?



Regards



Heinz







_______________________________________________

Concurrency-interest mailing list

Concurrency-interest at cs.oswego.edu<mailto:Concurrency-interest at cs.oswego.edu><mailto:Concurrency-

interest at cs.oswego.edu<mailto:interest at cs.oswego.edu>>

http://cs.oswego.edu/mailman/listinfo/concurrency-interest





_______________________________________________

Concurrency-interest mailing list

Concurrency-interest at cs.oswego.edu<mailto:Concurrency-interest at cs.oswego.edu><mailto:Concurrency-

interest at cs.oswego.edu<mailto:interest at cs.oswego.edu>>

http://cs.oswego.edu/mailman/listinfo/concurrency-interest



_______________________________________________

Concurrency-interest mailing list

Concurrency-interest at cs.oswego.edu<mailto:Concurrency-interest at cs.oswego.edu><mailto:Concurrency-

interest at cs.oswego.edu<mailto:interest at cs.oswego.edu>>

http://cs.oswego.edu/mailman/listinfo/concurrency-interest



_______________________________________________

Concurrency-interest mailing list

Concurrency-interest at cs.oswego.edu<mailto:Concurrency-interest at cs.oswego.edu><mailto:Concurrency-

interest at cs.oswego.edu<mailto:interest at cs.oswego.edu>>

http://cs.oswego.edu/mailman/listinfo/concurrency-interest





_______________________________________________

Concurrency-interest mailing list

Concurrency-interest at cs.oswego.edu<mailto:Concurrency-interest at cs.oswego.edu><mailto:Concurrency-

interest at cs.oswego.edu<mailto:interest at cs.oswego.edu>>

http://cs.oswego.edu/mailman/listinfo/concurrency-interest











_______________________________________________



Concurrency-interest mailing list



Concurrency-interest at cs.oswego.edu<mailto:Concurrency-interest at cs.oswego.edu><mailto:Concurrency-

interest at cs.oswego.edu<mailto:interest at cs.oswego.edu>>



http://cs.oswego.edu/mailman/listinfo/concurrency-interest





This email and any files transmitted with it contain confidential and

proprietary information and is solely for the use of the intended

recipient.  If you are not the intended recipient please return the

email

to the sender and delete it from your computer and you must not use,

disclose, distribute, copy, print or rely on this email or its

contents.

This communication is for informational purposes only.  It is not

intended

as an offer or solicitation for the purchase or sale of any financial

instrument or as an official confirmation of any transaction.   Any

comments or statements made herein do not necessarily reflect those

of GSA

Capital. GSA Capital Partners LLP is authorised and regulated by the

Financial Services Authority and is registered in England and Wales

at

Stratton House, 5 Stratton Street, London W1J 8LA, number OC309261.

GSA

Capital Services Limited is registered in England and Wales at the

same

address, number 5320529.





-------------- next part --------------

An HTML attachment was scrubbed...

URL:

<http://cs.oswego.edu/pipermail/concurrency-

interest/attachments/20120410/196f40e9/attachment.html>



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



_______________________________________________

Concurrency-interest mailing list

Concurrency-interest at cs.oswego.edu<mailto:Concurrency-interest at cs.oswego.edu>

http://cs.oswego.edu/mailman/listinfo/concurrency-interest





End of Concurrency-interest Digest, Vol 87, Issue 19

****************************************************









--

Beverly A. Sanders, Ph.D.

Associate Professor

Department of Computer & Information Science & Engineering

P.O. Box 116120

University of Florida

Gainesville, FL 32611-6120

www.cise.ufl.edu/~sanders<http://www.cise.ufl.edu/~sanders>

tel: (352) 505-1563

fax: (352) 392-1220



_______________________________________________

Concurrency-interest mailing list

Concurrency-interest at cs.oswego.edu<mailto:Concurrency-interest at cs.oswego.edu>

http://cs.oswego.edu/mailman/listinfo/concurrency-interest



_______________________________________________

Concurrency-interest mailing list

Concurrency-interest at cs.oswego.edu<mailto: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/20120411/d3359572/attachment-0001.html>


More information about the Concurrency-interest mailing list