GeeCON Prague 2014*
The moose likes Java in General and the fly likes Lazy Initialization and Thread Deadlock Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


JavaRanch » Java Forums » Java » Java in General
Bookmark "Lazy Initialization and Thread Deadlock" Watch "Lazy Initialization and Thread Deadlock" New topic
Author

Lazy Initialization and Thread Deadlock

Jason Voegele
Greenhorn

Joined: Oct 12, 2001
Posts: 9
Hello Ranchers,
I've developed a Web application that is currently experiencing some problems with thread deadlock. After reviewing some of the code that (I suspect) is causing the deadlock, I noticed that many methods were either unnecessarily synchronized or where the synchronization could be done in a finer grained manner. I've fixed many such problems by implementing finer-grained synchronization (i.e. locking only a subset of the fields of the object, rather than the entire object).
However, now I've come across a scenario that I'm not sure quite how to handle. As I'm sure you know, it is necessary to synchronize access/modification of mutable fields of an object. Another rule is that you should (almost) never call a method on an external object from within a synchronized block or method. This raises a problem for my system due to the use of lazy initialization of data that is gathered from a database.
Consider this example. I have a class called Organization that represents a single organization within some company. One of the methods in the Organization class is called getEmployees(), which returns a list of all employees working in that organization. This method uses lazy initialization to defer the construction of the list of employees until the first time the method is called. My original implementation looked like this:

I then refactored the method to use finer-grained locking:

This is an improvement in the sense that it does not lock the entire Organization object while the data is being loaded from the database.
However, this method violates the (well-publicized) rule that you should (almost) never invoke a method on an external object (such as the DAO) from within a synchronized block. And indeed, it is the violation of this rule that is causing the deadlock in this system.
I've considered the following solution:

However, this is not a viable solution since another thread could come in and initialize the employees field between the two synchronized blocks.
Sorry for the length of this post, but does anyone have any ideas for a good solution to this problem?
Thanks,
Jason Voegele
[ February 21, 2003: Message edited by: Jason Voegele ]
Robert Paris
Ranch Hand

Joined: Jul 28, 2002
Posts: 585
Well, I don't know your problem but I do have a problem with this:
As I'm sure you know, it is necessary to synchronize access/modification of mutable fields of an object.

Not true. Only sometimes. Remember, depending on the scope of your object, it may not need ANY thread safety. Scope is what matters here and I don't know what the scope would be of your object in the application you have. Is it's scope request? If so, then there's no need to synchronize it. Check that first.
Jason Voegele
Greenhorn

Joined: Oct 12, 2001
Posts: 9
Originally posted by Robert Paris:
Well, I don't know your problem but I do have a problem with this:

Not true. Only sometimes. Remember, depending on the scope of your object, it may not need ANY thread safety. Scope is what matters here and I don't know what the scope would be of your object in the application you have. Is it's scope request? If so, then there's no need to synchronize it. Check that first.

True, my wording was sloppy. I should have explicitly mentioned shared mutable data. And the fields that I am working with are in fact shared and mutable.
[ February 21, 2003: Message edited by: Jason Voegele ]
Peter den Haan
author
Ranch Hand

Joined: Apr 20, 2000
Posts: 3252
Originally posted by Jason Voegele:
[...] However, this method violates the (well-publicized) rule that you should (almost) never invoke a method on an external object (such as the DAO) from within a synchronized block.
Sheesh. That rule is for wimps We are made of stronger stuff
The rule is just a special case of the fact that deadlocks may occur as soon as you (attempt to) acquire locks on more than one resource in anything other than a fixed order.
Say you have two objects, A and B; both synchronize their methods. If A can only call B, but B can never call A (neither directly, nor via some other code), then you're fine. As soon as there is some pathway for calls to go in both directions, then a thread acquiring first the lock on A, and then the lock on B, can deadlock with another thread acquiring the locks the other way around.
With this in mind, I suspect that you're seeing deadlock because in a different thread that does not have a lock on lazyLoaderLock, the DAO may try to invoke methods on your object. What I'd like to ask is:
  • Is this true?
  • Does your DAO really need to be synchronized?
  • If you have some elaborate synchronization as a performance optimisation, undo this straightaway unless you have used a profiler and proved that this is a performance bottleneck.
  • Can you use extra monitor locks? For example, there could perhaps be a separate monitor lock for the employees field. If the DAO will never call a method that would acquire that lock, you're rid of your deadlock.
  • Can you enforce a locking order? For instance, you could modify relevant DAO methods to first lock your Organization object before acquiring a lock on the DAO object itself.
  • These are just some suggestions, and not necessarily complete. Hopefully they'll help you progress the problem.
    - Peter
    Mr. C Lamont Gilbert
    Ranch Hand

    Joined: Oct 05, 2001
    Posts: 1170

    Do not be concerned about the cost of synchronization of lazily initialized objects. Objects are lazily initialized because their initialization is heavy. If this is the case, then the initialization is going to be much more time consuming than the synchronization.
    Also, dont you dare check the value of a variable that is modified inside synchronized blocks, from outside of synchronized blocks.

    if(results == null) is totally bad and not thread safe. bouncing in and out of synchronization is going to be much more costly than just finishing the job once your in. Also double checked locking does not work in Java and this is essentially a form of it.
    Max Habibi
    town drunk
    ( and author)
    Sheriff

    Joined: Jun 27, 2002
    Posts: 4118
    Jason,
    I agree with CL, you don't want to nest synchronized locks, especially on the same object. Try the following,

    It's pretty close to what you originally had, but explicitly calls notifyAll, which is where I think your problem is. Let me know how that turns out.
    HTH,
    M, author
    The Sun Certified Java Developer Exam with J2SE 1.4


    Java Regular Expressions
    Peter den Haan
    author
    Ranch Hand

    Joined: Apr 20, 2000
    Posts: 3252
    Originally posted by CL Gilbert:
    Also, dont you dare check the value of a variable that is modified inside synchronized blocks, from outside of synchronized blocks.
    Why not? There's absolutely nothing wrong with that -- especially seeing that the variable being used is a local one. Heck, it is hard to think of a problem in concurrent programming that does not involve passing data in and out of synchronized blocks in some way.
    The "if(results == null)" test is neither bad nor thread-unsafe. You do, of course, have to realise that "result" is an obsolete copy of "this.employee" the moment you leave the synchronized block. In this particular code snippet, this means that a race condition may cause the employees list to be loaded twice. Depending on whether it could lead to inconsistencies, what the likelihood of such race conditions is, and how heavyweight the call is, this may be acceptable. Jason clearly realised this and has already indicated that he doesn't think this is viable.
    By the way, this is totally different from the double-checked locking problem as there is no unsynchronized access to a shared resource. The behaviour of the code is perfectly well-defined, even if it is perhaps not what you'd ideally want.
    Originally posted by Max Habibi:
    It's pretty close to what you originally had, but explicitly calls notifyAll, which is where I think your problem is.
    That will only make a difference if there's a wait() somewhere. The way Jason described the problem, it sounded more as if the deadlock was caused by unhappy synchronization. But you may well be right. Jason?
    Jason, you might find the Programming Java threads in the real world series of articles interesting reading.
    - Peter
    Max Habibi
    town drunk
    ( and author)
    Sheriff

    Joined: Jun 27, 2002
    Posts: 4118
    Originally posted by Peter den Haan:
    Why not? There's absolutely nothing wrong with that
    - Peter

    Actually, it's bad practice, but not for reason that Cl states.
    It's bad practice because the overhead associated with releasing the lock, the contending for it, then achieving it again, is prohibitiveL: remember, each time to do this, you're hitting thread memory again. Try a simple time test, and I you'll see what I mean. Now try adding some contending threads, and your overhead will, I expect, skyrocket.
    HTH,
    M, author
    The Sun Certified Java Developer Exam with J2SE 1.4
    Stan James
    (instanceof Sidekick)
    Ranch Hand

    Joined: Jan 29, 2003
    Posts: 8791
    It's pretty well proved in discussions of the singleton pattern that all forms of

    and even Sun's recommended double check

    are broken by JVM optimization and multiple CPUs. Here's an article with a list of resources:
    Newsflash: Double-checked locking is still broken
    Now the question: Does this apply to your situation?
    [ February 24, 2003: Message edited by: Crash Landon ]

    A good question is never answered. It is not a bolt to be tightened into place but a seed to be planted and to bear more seed toward the hope of greening the landscape of the idea. John Ciardi
    Peter den Haan
    author
    Ranch Hand

    Joined: Apr 20, 2000
    Posts: 3252
    Originally posted by Max Habibi:
    Actually, it's bad practice, but not for reason that Cl states.
    It's not at all bad practice to move a time-consuming operation out of a synchronized block; to the contrary. The cost of an extra monitor lock acquisition can be totally insignficant compared to the improvement in concurrency that you might gain from moving something as heavyweight as a database operation out of the way.
    The performance of a multi-threaded program is determined by so much more than just the cost of acquiring monitor locks, and the field is littered with examples where finer-grained locking increases rather than reduces performance. Surely I'm not telling you anything new. Surely you don't mean to call code like the above "bad practice" without any qualification whatsoever.
    But this is all quite academic. The objective of Jason's exercise is neither to improve concurrency by moving the database operation outside a synchronized block, nor to decrease locking overhead by minimizing the number of lock acquisitions, but to avoid a deadlock. If it takes an extra lock then that's not likely to keep anyone awake at night.
    - Peter
    [ February 25, 2003: Message edited by: Peter den Haan ]
    Jason Voegele
    Greenhorn

    Joined: Oct 12, 2001
    Posts: 9
    Thanks to all of you who have provided answers to my query here.
    To address the issues brought up surrounding whether or not it is a good idea for my application to release a lock while performing an expensive operation, the answer is that it will not cause any real harm. Peter mentioned that (in my example), certain timing conditions may cause the employee list to be loaded twice. This is not ideal, but it is acceptable, and given the absolutely dreadful connection to the database, I'm willing to allow this to happen in favor of releasing locks during (extremely expensive) database calls.
    It turns out that the code snippet I posted had nothing to do with the deadlock problem. The deadlock was occuring during a "roll-up" of information down the organization hierarchy. This roll-up was obtaining locks on each and every organization involved in the summation, and holding them until the entire summation was done. In addition, some methods in both the Organization class as well as the DAO were needlessly synchronized, so it was possible for the Organization<=>DAO interaction to lock different resources in different orders. Thus, if two or more users attempted to perform a roll-up under the right timing conditions, deadlock was bound to happen. These locks were for the most part unnecessary, and I reduced the locking in a manner similar to the code snippet I posted.
    Thanks again,
    Jason
    [ February 26, 2003: Message edited by: Jason Voegele ]
    Jason Voegele
    Greenhorn

    Joined: Oct 12, 2001
    Posts: 9
    Originally posted by Max Habibi:
    Jason,
    I agree with CL, you don't want to nest synchronized locks, especially on the same object. Try the following,


    Well, there's a problem with the above code in that if employees is indeed null, then the code basically reduces to synchronized(null) , which, I'm pretty sure, is undefined behavior.
    Thanks for your help, though.
    Jason
    Jim Yingst
    Wanderer
    Sheriff

    Joined: Jan 30, 2000
    Posts: 18671
    Well, there's a problem with the above code in that if employees is indeed null, then the code basically reduces to synchronized(null) , which, I'm pretty sure, is undefined behavior.
    It's not undefined - it will throw a NullPointerException (see here). So you're right, the code Max shows won't work.


    "I'm not back." - Bill Harding, Twister
    Max Habibi
    town drunk
    ( and author)
    Sheriff

    Joined: Jun 27, 2002
    Posts: 4118
    Obviously true: didn't think that one through. Apologies for any confusion that caused.
    M, author
    The Sun Certified Java Developer Exam with J2SE 1.4
    [ February 26, 2003: Message edited by: Max Habibi ]
    Max Habibi
    town drunk
    ( and author)
    Sheriff

    Joined: Jun 27, 2002
    Posts: 4118

    The performance of a multi-threaded program is determined by so much more than just the cost of acquiring monitor locks, and the field is littered with examples where finer-grained locking increases rather than reduces performance. Surely I'm not telling you anything new. Surely you don't mean to call code like the above "bad practice" without any qualification whatsoever.

    Just to be clear: Of course you're not telling me anything new Peter.
    And yes, I do mean to call it bad practice given the way you're advocating here: in the sense of "to do or perform often, customarily, or habitually". Surely you don't think it's the sort of thing that should be engaged in often? Surely you don't do it habitually? I'm sure that a scenario can be made. However, I doubt that it's a commonly occurring event.
    HTH,
    M, author
    The Sun Certified Java Developer Exam with J2SE 1.4
    HTH,
    M
    [ February 27, 2003: Message edited by: Max Habibi ]
    [ February 27, 2003: Message edited by: Max Habibi ]
    Peter den Haan
    author
    Ranch Hand

    Joined: Apr 20, 2000
    Posts: 3252
    Originally posted by Max Habibi:
    Just to be clear: Of course you're not telling me anything new Peter.
    I did not doubt that for a minute, Max.
    And yes, I do mean to call it bad practice given the way you're advocating here: in the sense of "to do or perform often, customarily, or habitually".
    My apologies if I gave that impression. Of course I did not mean to advocate it in this sense at all -- this would be rather at odds with my fondness for the first rule of optimisation. I merely responded to the assertion that the code is inherently bad because its behaviour is ill-defined and thread-unsafe. So it seems we are in full agreement, which makes a delightful change
    Anyway, I'm really happy that Jason managed to find the root cause of his deadlock and fix it with some simple changes to the synchronization.
    - Peter
    [ February 27, 2003: Message edited by: Peter den Haan ]
    Max Habibi
    town drunk
    ( and author)
    Sheriff

    Joined: Jun 27, 2002
    Posts: 4118
    Originally posted by Peter den Haan:
    My apologies if I gave that impression. Of course I did not mean to advocate it in this sense at all -- this would be rather at odds with my fondness for the first rule of optimisation.

    lol...I like that site: will be using it in the future.

    I merely responded to the assertion that the code is inherently bad because its behaviour is ill-defined and thread-unsafe. So it seems we are in full agreement, which makes a delightful change

    I see what you mean now: and yes, of course you are correct, and of course I agree with you. Wow .

    Anyway, I'm really happy that Jason managed to find the root cause of his deadlock and fix it with some simple changes to the synchronization.
    - Peter

    Agreed: Btw, you brought up an interesting subtlety in the discussion that I had not considered before(maybe in another thread?). You mentioned that notityAll() would only call those threads that had had wait() previously called on them: the implication being, I think, that those threads that went into a wait state 'naturally' simply by hitting the synchronization block would not be responsive to the notifyAll() call. an you expand on that a bit? I'm afraid that I had always lumped the two together.
    Thanks,
    M, author
    The Sun Certified Java Developer Exam with J2SE 1.4
    Jim Yingst
    Wanderer
    Sheriff

    Joined: Jan 30, 2000
    Posts: 18671
    I'm afraid that I had always lumped the two together.

    And to think, I just bought a book from this man. What was I thinking?
    Seriously though - waiting as a result of wait() is different from waiting to acquire a lock. The notify() and notifyAll() methods pertain only to those threads which have called wait() using the appropriate monitor. After one or more wait()-ing threads have been notify()-ed they are no longger wait()-ing, but they must still "wait" (in the other sense) until they (re-)acquire a lock on the appropriate lock. More info can be found in the JLS, particularly 17.13 and 17.14. Note that the JLS avoids using the term "wait" in 17.13 when talking about the synchronized keyword - it says instead that the thread "may not proceed" until the lock is acquired. "Wait" is used only for the result of the wait() command. I guess we need another term for "waiting for a lock" which does not cause this confusion.
    [ February 27, 2003: Message edited by: Jim Yingst ]
    Max Habibi
    town drunk
    ( and author)
    Sheriff

    Joined: Jun 27, 2002
    Posts: 4118
    Originally posted by Jim Yingst:
    I'm afraid that I had always lumped the two together.

    And to think, I just bought a book from this man. What was I thinking?


    Money well spent, I'm sure.

    Seriously though - waiting as a result of wait() is different from waiting to acquire a lock. The notify() and notifyAll() methods pertain only to those threads which have called wait() using the appropriate monitor. After one or more wait()-ing threads have been notify()-ed they are no longger wait()-ing, but they must still "wait" (in the other sense) until they (re-)acquire a lock on the appropriate lock. More info can be found in the JLS, particularly 17.13 and 17.14. Note that the JLS avoids using the term "wait" in 17.13 when talking about the synchronized keyword - it says instead that the thread "may not proceed" until the lock is acquired. "Wait" is used only for the result of the wait() command. I guess we need another term for "waiting for a lock" which does not cause this confusion.
    [ February 27, 2003: Message edited by: Jim Yingst ][/QB]

    I had always assumed that the implementation would lump the two kinds of 'waiting' threads into a single que: I wonder if there are, in fact, implementations that do this, or if there is a practical limitation on such.

    M, author
    The Sun Certified Java Developer Exam with J2SE 1.4
    Peter den Haan
    author
    Ranch Hand

    Joined: Apr 20, 2000
    Posts: 3252
    There is an important difference between the two sets, and lumping them together would change the semantics of at least one of them significantly. A thread contending for a lock will continue to run as soon as it can grab the lock, whereas a thread in the wait set needs explicit notification.
    I'm sure I've seen complete state diagrams that fully describe the various states a thread can be in, but all I could find was this "overview of the more interesting and common facets of a thread's life" that completely hides the "contending for a monitor lock" state inside composite states.
    Threads which have stopped executing because they need to acquire a monitor lock will eventually get their turn and proceed -- if you avoid deadlock and thread starvation, that is. Whenever the thread that owns the monitor releases the lock, the JVM will give the lock to one of the threads that are contending for it. If I remember correctly, there are no guarantees as to which thread gets selected.
    If a thread calls wait(), it releases its monitor lock (giving other threads a chance) and joins the object's wait set. The thread no longer contends for the object's monitor lock; it will have to be explicitly notified using notify() or notifyAll() in order to leave the wait set. When notified, the thread becomes runnable again and joins the threads contending for the monitor lock. It does not start to execute immediately: even if there are no other contending threads, the notifying thread will still own the lock at that time!
    If you have Doug's book, there's an overview of this stuff in 3.2.2, p184 (2nd ed.), especially the diagram on p186.
    - Peter
    [ February 28, 2003: Message edited by: Peter den Haan ]
     
    GeeCON Prague 2014
     
    subject: Lazy Initialization and Thread Deadlock