deadlocks

Discussion in 'Java' started by ndxp@hotmail.com, Dec 8, 2005.

  1. Guest

    I need to know if there are any thumb rules which i need to follow in
    order to avoid deadlocks
    in thread.

    thanks
     
    , Dec 8, 2005
    #1
    1. Advertising

  2. > I need to know if there are any thumb rules which i need to follow in
    > order to avoid deadlocks
    > in thread.


    Here are a couple:
    - Only update the user interface from one thread
    - Use synchronization features as little as possible
    - Try to avoid calling functions that might be modified from synchronized
    blocks (calling api functions that are welldefined and do not have any
    synchronized blocks are ok)

    Niels Dybdahl
     
    Niels Dybdahl, Dec 8, 2005
    #2
    1. Advertising

  3. wrote:
    > I need to know if there are any thumb rules which i need to follow in
    > order to avoid deadlocks
    > in thread.


    Not really. You have to know what you are doing. You have to understand
    threads, and you have to know what is going on in your source code (the
    different flows of control and their interdependencies, critical
    sections of code, access patterns to data, etc.).

    Rules of thumb don't work very well with threading. Such rules basically
    mean "usually it works out if you do XYZ". However, something "usually
    working out" is not good enough when it comes to multi threading. The
    cases when it suddenly doesn't work out on that particular machine of
    that important customers in the middle of the night or at that important
    demo are the ones that hurt and are the ones which are extremely
    difficult to debug. The 1 out of 1000 failure which is almost impossible
    to reproduce in the lab.

    /Thomas
    --
    The comp.lang.java.gui FAQ:
    ftp://ftp.cs.uu.nl/pub/NEWS.ANSWERS/computer-lang/java/gui/faq
    http://www.uni-giessen.de/faq/archiv/computer-lang.java.gui.faq/
     
    Thomas Weidenfeller, Dec 8, 2005
    #3
  4. Alun Harford Guest

    <> wrote in message
    news:...
    >I need to know if there are any thumb rules which i need to follow in
    > order to avoid deadlocks
    > in thread.


    Know what you're doing.
    Prove that your program cannot deadlock. (Note that a simple solution to
    this is to ensure that a thread can only take out one lock at a time)

    Alun Harford
     
    Alun Harford, Dec 8, 2005
    #4
  5. Daniel Dyer Guest

    On Thu, 08 Dec 2005 10:04:38 -0000, Alun Harford <>
    wrote:

    > <> wrote in message
    > news:...
    >> I need to know if there are any thumb rules which i need to follow in
    >> order to avoid deadlocks
    >> in thread.

    >
    > Know what you're doing.
    > Prove that your program cannot deadlock. (Note that a simple solution to
    > this is to ensure that a thread can only take out one lock at a time)
    >
    > Alun Harford
    >


    There are for conditions that must be true in order for a program to
    deadlock. By ensuring that at least one of these is not true you can
    avoid deadlocking.

    http://en.wikipedia.org/wiki/Deadlock#Necessary_conditions

    Dan.

    --
    Daniel Dyer
    http://www.dandyer.co.uk
     
    Daniel Dyer, Dec 8, 2005
    #5
  6. Viator Guest

    Read some theory of concurrent programming. You can find the same in
    any general purpose OS book.
     
    Viator, Dec 8, 2005
    #6
  7. Guest

    Proving a deadlock will not occur is quite hard for large complex
    system.
    I think we can probably minimize the possibility of a deadlock, but
    cannot
    completely avoid it. ( somebody tell me I'm wrong)


    Alun Harford wrote:

    > <> wrote in message
    > news:...
    > >I need to know if there are any thumb rules which i need to follow in
    > > order to avoid deadlocks
    > > in thread.

    >
    > Know what you're doing.
    > Prove that your program cannot deadlock. (Note that a simple solution to
    > this is to ensure that a thread can only take out one lock at a time)
    >
    > Alun Harford
     
    , Dec 8, 2005
    #7
  8. Roedy Green Guest

    On 7 Dec 2005 22:32:07 -0800, wrote, quoted or
    indirectly quoted someone who said :

    >I need to know if there are any thumb rules which i need to follow in
    >order to avoid deadlocks
    >in thread.


    Use the Sun concurrent classes rather that doing synchronsation logic
    with primitives. See http://mindprod.com/jgloss/queue.html
    --
    Canadian Mind Products, Roedy Green.
    http://mindprod.com Java custom programming, consulting and coaching.
     
    Roedy Green, Dec 8, 2005
    #8
  9. Roedy Green Guest

    On 7 Dec 2005 22:32:07 -0800, wrote, quoted or
    indirectly quoted someone who said :

    >I need to know if there are any thumb rules which i need to follow in
    >order to avoid deadlocks
    >in thread.

    the main one is always acquire resources in the same order.
    --
    Canadian Mind Products, Roedy Green.
    http://mindprod.com Java custom programming, consulting and coaching.
     
    Roedy Green, Dec 8, 2005
    #9
  10. Alun Harford Guest

    <> wrote in message
    news:...
    > Proving a deadlock will not occur is quite hard for large complex
    > system.
    > I think we can probably minimize the possibility of a deadlock, but
    > cannot
    > completely avoid it. ( somebody tell me I'm wrong)


    For arbitrary systems, yes (deadlock detection is as hard as the halting
    problem). BUT: We make the system so we can use methods to ensure that
    deadlock cannot occur (just like we can prove that a particular program we
    make will halt).
    If you're making little programs, the method I gave is the easiest way (well
    actually I guess the easiest way is to not multithread, but that can be
    nasty if you're doing anything over a network).
    If you're making large, complex systems then you should know what you're
    doing.

    Alun
     
    Alun Harford, Dec 8, 2005
    #10
  11. In message <>, Roedy Green
    <> writes
    >the main one is always acquire resources in the same order.


    A more complete way of stating this is always acquire in the same order
    and always release in the reverse order to acquisition. If you get the
    releasing part wrong you can also have problems. Because of the way Java
    exposes the releasing part of the problem this is not an issue with
    Java, but can be with other languages (such as using the Win32 APIs
    directly for say Delphi, C++ or writing Java bytecode directly as the
    output for a given language).

    Those of you writing multi-threaded code may be interested in Java
    Thread Validator, an automated deadlock detector for Java.

    http://www.softwareverify.com

    Stephen
    --
    Stephen Kellett
    Object Media Limited http://www.objmedia.demon.co.uk/software.html
    Computer Consultancy, Software Development
    Windows C++, Java, Assembler, Performance Analysis, Troubleshooting
     
    Stephen Kellett, Dec 8, 2005
    #11
  12. Stephen Kellett wrote:
    > In message <>, Roedy Green
    > <> writes
    >> the main one is always acquire resources in the same order.

    >
    > A more complete way of stating this is always acquire in the same order
    > and always release in the reverse order to acquisition. If you get the
    > releasing part wrong you can also have problems. Because of the way Java
    > exposes the releasing part of the problem this is not an issue with
    > Java, but can be with other languages (such as using the Win32 APIs
    > directly for say Delphi, C++ or writing Java bytecode directly as the
    > output for a given language).


    Can you explain why that might be? I can see that if a release
    call resulted in a hidden release-acquire-release sequence that
    this could be a problem - the hidden acquire might be out of
    order with other acquisitions. But I can't think why a clean
    release on its own might be problematic.

    Steve
     
    Steve Horsley, Dec 8, 2005
    #12
  13. In message <dn9ks7$ruu$2surf.net>, Steve Horsley
    <> writes
    >Can you explain why that might be? I can see that if a release call
    >resulted in a hidden release-acquire-release sequence that this could
    >be a problem - the hidden acquire might be out of order with other
    >acquisitions.
    >But I can't think why a clean release on its own might be problematic.


    I'm not sure you understood what I meant - you may have, just your
    comment "clean release" makes me unsure, as I am not talking about a
    clean release. Two examples:

    This is OK. (this is what I'd call a clean release if using that
    terminology).

    1.acquire.
    2.acquire.
    3.acquire.
    3.release
    2.release
    1.release

    This is not OK.

    1.acquire.
    2.acquire.
    3.acquire.
    2.release <- mistake.
    1.release <- mistake
    3.release <- mistake

    At some point another thread will be able to acquire 1 and 2 out of
    order with the acquisition of 3. This will lead to problems, most likely
    with some other thread that is using some or all of these locks.

    I haven't got time to write you a code example that dies, but I've seen
    some pretty nasty results in Win32 multi-threading as a result of things
    like this.

    Stephen
    --
    Stephen Kellett
    Object Media Limited http://www.objmedia.demon.co.uk/software.html
    Computer Consultancy, Software Development
    Windows C++, Java, Assembler, Performance Analysis, Troubleshooting
     
    Stephen Kellett, Dec 8, 2005
    #13
  14. wrote:
    > I need to know if there are any thumb rules which i need to follow in
    > order to avoid deadlocks
    > in thread.


    First off, it is important that you know what you application is doing
    with respect to threads. Adding a few synchronized keywords randomly may
    stop the odd problem, but it is not a viable solution.


    Don't synchronise at all.

    The easy, yet high performance solution. A number of approaches: Require
    that everything is run in one thread (thread hostile, like Swing).
    Require that the client take care of synchronisation/single threading
    (thread agnostic). Make your objects immutable (technically you require
    1.5 and need to declare fields final).


    Keep synchronised blocks as small as possible.

    Generally copy out what you need, then let go of the lock. Avoid calling
    all but the most well understood functions from within the block. In
    particular do not call callback methods while holding a lock.


    Synchronise in a particular order

    If you must nest synchronisations, make sure acquire the locks in a
    particular order. This may be on the basis of type or another property
    of the objects.


    There are some tricky situations. For instance binary operators.

    Consider StringBuffer.append(StringBuffer). It would probably be a bug
    on the part of the client code in this case, but you can deadlock with
    StringBuffers attempting to append to each other. a.append(b) in one
    thread, and b.append(a) in another.

    A general approach is to use a global lock. Synchronize to a static
    around all binary operations, then synchronize onto operands in whatever
    order. Obviously this can cause hideous problems in code that makes
    extensive use of threads. To be avoided for server applications.

    private static class Lock { } // Make thread dumps more readable.
    private static final Object GLOBAL_LOCK = new Lock();
    public StringBuffer append(StringBuffer text) {
    if (text == null) return appendNull();
    synchronized (GLOBAL_LOCK) {
    synchronized (this) {
    synchronized (text) {
    super.append(text);
    }
    }
    }
    return this;
    }

    Another approach for StringBuffer.append is to copy out the contents.
    This is the copy-out advice from above. So:

    public StringBuffer append(StringBuffer text) {
    // toString is done under lock.
    String str = text==null ? NULL_STRING : text.toString();
    synchronized (this) {
    super.append(str);
    }
    return this;
    }

    A third approach is to attempt to order the locking. 99.999% of the time
    Object.hashCode (i.e. System.identityHashCode) will give different
    values for a pair of Objects. In the unlikely event of a tie, we can use
    a fallback technique.

    public StringBuffer append(StringBuffer text) {
    if (text == null) return appendNull();
    int thisHash = this.hashCode();
    int textHash = text.hashCode();
    final StringBuffer firstLock;
    final StringBuffer secondLock;
    if (thisHash < textHash) {
    firstLock = this;
    secondLock = text;
    } else if (thisHash > textHash) {
    secondLock = this;
    firstLock = text;
    } else {
    assert thisHash == textHash;
    // Damn - cop out.
    return append(text.toString());
    }
    synchronized (firstLock) {
    synchronized (secondLock) {
    super.append(text);
    }
    }
    return this;
    }

    Tom Hawtin
    --
    Unemployed English Java programmer
    http://jroller.com/page/tackline/
     
    Thomas Hawtin, Dec 8, 2005
    #14
  15. Guest

    In article <>,
    Stephen Kellett <> wrote:
    >In message <dn9ks7$ruu$2surf.net>, Steve Horsley
    ><> writes
    >>Can you explain why that might be? I can see that if a release call
    >>resulted in a hidden release-acquire-release sequence that this could
    >>be a problem - the hidden acquire might be out of order with other
    >>acquisitions.
    >>But I can't think why a clean release on its own might be problematic.

    >
    >I'm not sure you understood what I meant - you may have, just your
    >comment "clean release" makes me unsure, as I am not talking about a
    >clean release. Two examples:
    >
    >This is OK. (this is what I'd call a clean release if using that
    >terminology).
    >
    >1.acquire.
    >2.acquire.
    >3.acquire.
    >3.release
    >2.release
    >1.release
    >
    >This is not OK.
    >
    >1.acquire.
    >2.acquire.
    >3.acquire.
    >2.release <- mistake.
    >1.release <- mistake
    >3.release <- mistake
    >
    >At some point another thread will be able to acquire 1 and 2 out of
    >order with the acquisition of 3. This will lead to problems, most likely
    >with some other thread that is using some or all of these locks.


    Umm ....

    If the other thread is performing the same sequence of acquisitions
    (first 1, then 2, then 3), how is this a problem? The other thread
    isn't going to attempt to acquire 2 until it has 1.

    What you're saying is at odds with what I've gathered from reading
    discussions of synchronization mechanisms in textbooks on operating
    systems. One of us is confused -- or possibly we don't mean the
    same thing by "acquire"??

    >I haven't got time to write you a code example that dies, but I've seen
    >some pretty nasty results in Win32 multi-threading as a result of things
    >like this.
    >


    Curious. Too bad you can't show us an example.

    --
    | B. L. Massingill
    | ObDisclaimer: I don't speak for my employers; they return the favor.
     
    , Dec 9, 2005
    #15
  16. In message <>, writes
    >>I haven't got time to write you a code example that dies, but I've seen
    >>some pretty nasty results in Win32 multi-threading as a result of things
    >>like this.

    >
    >Curious. Too bad you can't show us an example.


    The examples are usually very convoluted and not easy to demonstrate (or
    remember!) in a forum such as this. I'm not even sure I could write an
    example on demand. Its part of my memory of implementation of multi
    threaded systems and what caused them to fail.

    Another issue not considered here is that releasing in the wrong order
    also has the following potential liablilities:
    o Possible performance drop as some locks will be held for longer than
    needed.
    o Possible data integrity problems as some locks will be released too
    early.

    Anyway, as I initially said, it isn't an issue in Java unless you are
    writing bytecode directly.

    Stephen
    --
    Stephen Kellett
    Object Media Limited http://www.objmedia.demon.co.uk/software.html
    Computer Consultancy, Software Development
    Windows C++, Java, Assembler, Performance Analysis, Troubleshooting
     
    Stephen Kellett, Dec 9, 2005
    #16
  17. Guest

    In article <>,
    Stephen Kellett <> wrote:
    >In message <>, writes
    >>>I haven't got time to write you a code example that dies, but I've seen
    >>>some pretty nasty results in Win32 multi-threading as a result of things
    >>>like this.

    >>
    >>Curious. Too bad you can't show us an example.

    >
    >The examples are usually very convoluted and not easy to demonstrate (or
    >remember!) in a forum such as this. I'm not even sure I could write an
    >example on demand. Its part of my memory of implementation of multi
    >threaded systems and what caused them to fail.


    Well, maybe you can talk a little more, in a general way, about
    the earlier part of my post. I'm a bit bothered by your claim
    in that it seems to directly contradict what I've read in general
    descriptions of deadlocks and synchronization mechanisms in operating
    systems textbooks -- bothered in that I wonder whether maybe I don't
    understand this as well as I thought.

    Repeating from my previous post (quoted text yours):

    >This is OK. (this is what I'd call a clean release if using that
    >terminology).
    >
    >1.acquire.
    >2.acquire.
    >3.acquire.
    >3.release
    >2.release
    >1.release
    >
    >This is not OK.
    >
    >1.acquire.
    >2.acquire.
    >3.acquire.
    >2.release <- mistake.
    >1.release <- mistake
    >3.release <- mistake
    >
    >At some point another thread will be able to acquire 1 and 2 out of
    >order with the acquisition of 3. This will lead to problems, most likely
    >with some other thread that is using some or all of these locks.


    Umm ....

    If the other thread is performing the same sequence of acquisitions
    (first 1, then 2, then 3), how is this a problem? The other thread
    isn't going to attempt to acquire 2 until it has 1.


    >
    >Another issue not considered here is that releasing in the wrong order
    >also has the following potential liablilities:
    >o Possible performance drop as some locks will be held for longer than
    >needed.


    Agreed on this one.

    >o Possible data integrity problems as some locks will be released too
    >early.


    Not agreed on this one.

    >Anyway, as I initially said, it isn't an issue in Java unless you are
    >writing bytecode directly.


    Maybe it would help if you could point me/us to an API for acquiring
    and releasing resources that *does* have the kind of problems you're
    talking about.

    --
    | B. L. Massingill
    | ObDisclaimer: I don't speak for my employers; they return the favor.
     
    , Dec 12, 2005
    #17
  18. In message <>, writes
    >If the other thread is performing the same sequence of acquisitions
    >(first 1, then 2, then 3), how is this a problem? The other thread
    >isn't going to attempt to acquire 2 until it has 1.


    In that trivial example I posted it isn't a problem. As I said, the
    problems I've come up against were convoluted examples a lot more
    complex than several identical threads using the same locks. Most
    software I've worked on is not multiple identical threads working with
    the same locks. It is multiple different threads working with the same
    locks plus their own locks, some of which may be used by other threads.
    The trivial examples people use in these discussions (this one included)
    do not represent the real world.

    >>o Possible data integrity problems as some locks will be released too
    >>early.

    >
    >Not agreed on this one.


    1.acquire
    modify A
    2.acquire
    modify B
    3.acquire
    modify C
    1.release
    at this point another thread can modify A <- potential damage
    3.release
    2.release

    The potential damage is because the A should be protected. Since you've
    unlocked (1) in the wrong order A is not protected. 3 and 2 may still be
    held for quite a long time. But 3 and 2 are not protecting A.

    In a trivial example where the locks are acquired immediately one after
    each other there is no problem. Real world examples usually have locks
    acquired in different functions. Thus if you release one too early you
    are exposing data that should be protected to potential manipulation
    from another thread.

    >Maybe it would help if you could point me/us to an API for acquiring
    >and releasing resources that *does* have the kind of problems you're
    >talking about.


    Win32 EnterCriticalSection/LeaveCriticalSection and the equivalent java
    bytecode instructions for entering and leaving a monitor.

    Stephen
    --
    Stephen Kellett
    Object Media Limited http://www.objmedia.demon.co.uk/software.html
    Computer Consultancy, Software Development
    Windows C++, Java, Assembler, Performance Analysis, Troubleshooting
     
    Stephen Kellett, Dec 12, 2005
    #18
  19. Guest

    In article <>,
    Stephen Kellett <> wrote:
    >In message <>, writes
    >>If the other thread is performing the same sequence of acquisitions
    >>(first 1, then 2, then 3), how is this a problem? The other thread
    >>isn't going to attempt to acquire 2 until it has 1.

    >
    >In that trivial example I posted it isn't a problem. As I said, the
    >problems I've come up against were convoluted examples a lot more
    >complex than several identical threads using the same locks. Most
    >software I've worked on is not multiple identical threads working with
    >the same locks. It is multiple different threads working with the same
    >locks plus their own locks, some of which may be used by other threads.
    >The trivial examples people use in these discussions (this one included)
    >do not represent the real world.
    >
    >>>o Possible data integrity problems as some locks will be released too
    >>>early.

    >>
    >>Not agreed on this one.

    >
    >1.acquire
    >modify A
    >2.acquire
    >modify B
    >3.acquire
    >modify C
    >1.release
    >at this point another thread can modify A <- potential damage
    >3.release
    >2.release
    >
    >The potential damage is because the A should be protected. Since you've
    >unlocked (1) in the wrong order A is not protected. 3 and 2 may still be
    >held for quite a long time. But 3 and 2 are not protecting A.


    I don't understand your example here. You have three locks, numbered
    1, 2, and 3? What does 1 represent? from the fact that you acquire
    it just before modifying A, it would seem to be something you need to
    hold to modify A -- but then if the code modifies A after releasing
    this lock, then .... I wouldn't call that a problem with releasing
    locks in the wrong order so much as with failing to protect A by
    only modifying it while holding the associated lock. You would
    have the same problem if you released the three locks in the "correct"
    order, but modified A after releasing lock #1, wouldn't you?

    >
    >In a trivial example where the locks are acquired immediately one after
    >each other there is no problem. Real world examples usually have locks
    >acquired in different functions. Thus if you release one too early you
    >are exposing data that should be protected to potential manipulation
    >from another thread.
    >
    >>Maybe it would help if you could point me/us to an API for acquiring
    >>and releasing resources that *does* have the kind of problems you're
    >>talking about.

    >
    >Win32 EnterCriticalSection/LeaveCriticalSection and the equivalent java
    >bytecode instructions for entering and leaving a monitor.
    >


    The first Google hit for the former is this ....

    http://msdn.microsoft.com/library/en-us/dllproc/base/entercriticalsection.asp

    from which it's not obvious why the problem you describe occurs.

    I think we may have to leave this as an unsolved mystery (from my
    point of view), since my guess is that neither of us has time to
    pursue it the depth that would be required.

    --
    | B. L. Massingill
    | ObDisclaimer: I don't speak for my employers; they return the favor.
     
    , Dec 12, 2005
    #19
  20. In message <>, writes
    >I don't understand your example here. You have three locks, numbered
    >1, 2, and 3?


    Yes.

    >What does 1 represent?


    1 represents a lock A lock that is required to modify various things. I
    happened to choose a simple example with just one variable A.

    >from the fact that you acquire
    >it just before modifying A, it would seem to be something you need to
    >hold to modify A -- but then if the code modifies A after releasing
    >this lock, then .... I wouldn't call that a problem with releasing
    >locks in the wrong order so much as with failing to protect A by
    >only modifying it while holding the associated lock.


    Which is caused because you unlocked too early! This madness, you are
    agreeing with me whilst disagreeing :). From what I have read in this
    discussion if you don't believe the
    release-in-reverse-order-to-acquisition rule you won't agree with the
    rest of what I've written.

    I probably shouldn't have mentioned any of this at all as it doesn't
    apply to Java due to the way the language is constructed. We don't
    appear to be getting anywhere with this so best to leave it. It appears
    that you have come to the same conclusion.

    Stephen
    --
    Stephen Kellett
    Object Media Limited http://www.objmedia.demon.co.uk/software.html
    Computer Consultancy, Software Development
    Windows C++, Java, Assembler, Performance Analysis, Troubleshooting
     
    Stephen Kellett, Dec 12, 2005
    #20
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Martin Blackstone [MVP - Exchange]

    ASP.NET Deadlocks

    Martin Blackstone [MVP - Exchange], Aug 23, 2003, in forum: ASP .Net
    Replies:
    6
    Views:
    770
    Nick Wienholt
    Aug 24, 2003
  2. Mike Carr

    Deadlocks

    Mike Carr, Jul 16, 2004, in forum: ASP .Net
    Replies:
    9
    Views:
    645
    Mike Carr
    Jul 23, 2004
  3. Rogan Dawes

    Automatically detecting deadlocks?

    Rogan Dawes, May 5, 2004, in forum: Java
    Replies:
    2
    Views:
    432
    Rogan Dawes
    May 6, 2004
  4. commie
    Replies:
    16
    Views:
    1,044
  5. Eloff
    Replies:
    14
    Views:
    494
    Tim Peters
    Jun 23, 2005
Loading...

Share This Page