• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

The mysterious 65/80 locking score

 
Ranch Hand
Posts: 357
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hi all,

Last week I received my results and for the locking part I got the quite unique 65/80 score. I was left pondering what would have caused this score and this morning when I was in the shower it suddenly hit me. I fired up my computer even before breakfast to confirm the flaw that most likely costs me the 15 points loss.

I used what I think is probably the most common locking scheme, where each record has a lock-object on which a client wait()s if its already claimed by another thread. In the unlock() a notify() is done, which will wake up a quasi-random waiting thread that will take over the lock. I had explicitly chosen for notify() over notifyAll(), because any waiting client should be ready to take over the lock: no need to wake them all up. Or so I thought...

Now consider the following scenario:
  • client A locks record X
  • client B locks record X; is put in wait()
  • client C locks record X; is put in wait() too
  • client A deletes record X
  • client A unlocks record X; notify() is called
  • client B wakes up to find that record X is deleted; exits lock() method with RecordNotFoundException
  • Houston, we have a deadlock!


  • Because client B never acquired the lock, it does never get to call notify() and client C is left waiting for ever...

    I am pretty positive that this must be the reason for the 65/80 score. So I can recommend to you all to think hard if you need to use notify() or notifyAll() and also to test with scenarios involving many clients. I did some tests with three simultaneous clients, but the scenario above I sadly did not test.

    Frans.
     
    Ranch Hand
    Posts: 37
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    BTW this is not a deadlock, but it is a client waiting for a very long time.
    What does this scenario do if notifyAll() is used instead of notify() ?
    Thx Frans
    Greetz


    Frank
     
    Frans Janssen
    Ranch Hand
    Posts: 357
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator

    Originally posted by Frank Verbruggen:
    BTW this is not a deadlock, but it is a client waiting for a very long time.
    What does this scenario do if notifyAll() is used instead of notify() ?
    Frank


    Hi Frank,

    You are right of course (but deadlock sounds so much more dramatical ).

    NotifyAll() would have prevented it. In the example client B and C would have both woken up to find that record X no longer existed.

    Another solution could have been that if a client wakes up and detects that the record it is trying to lock has been deleted, that it then calls notify() too, to wake up the next client. This is maybe the nicer solution, because it doesn't wake up clients that will immediately fall back into wait() again, as is the case with using notifyAll().

    Frans.
     
    Frank Verbruggen
    Ranch Hand
    Posts: 37
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    Hi Frans,

    ok thx,
    have you seen my emails to u yet ?
    A reply would be nice, else send me ur working email address, so I can post u there, response time is way slow this way
    Cya


    Frank
     
    Ranch Hand
    Posts: 119
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    I feel that another way to solve this problem is to wrap all logic in a try-finally block, with the notifying call in the finally block. Using notifyAll() will cause all threads to wake up, which I think is not necessary. What do you think?
    [ February 15, 2005: Message edited by: Liang Anmian ]
     
    Frans Janssen
    Ranch Hand
    Posts: 357
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    Liang,

    I am not quite sure what you mean. In the lock() method under normal conditions no notify() is done. So adding one in a finally-clause does not sound like a sensible idea to me. Could you perhaps give a small code example to explain your idea?

    Frans.
     
    Ranch Hand
    Posts: 56
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    Hi!

    That is probably what cost you those last 15 points then.

    I have not come across any reason for calling notify rather than notifyAll, other than perhaps performance. But I believe that ESPECIALLY in this case that overhead is negligable (probably most other case also).

    Therefore, I guess if you want to be on the safe side... notifyAll is the way forward.

    Cheers /Dave
     
    Ranch Hand
    Posts: 47
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    hello Frans:
    Did you use hashtable to store the locked record, and use cookie to identify the locked record. Or, you just add a flag varible in record object to declare this record has been locked. just change this flag to unlock this record.

    Because I found many people in here use hashtalbe and cookie to manage locked record.
    I don't know what's the advantage for this way. I think direct locking is ok and easy, but maybe it will cause some problem.

    anyone can tell me is there any problem for direct locking and what the benefit for using hashtable and cookie to manage locking.
    thank you very much!
     
    Frans Janssen
    Ranch Hand
    Posts: 357
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator

    Originally posted by David Abramowicz:
    I have not come across any reason for calling notify rather than notifyAll, other than perhaps performance. But I believe that ESPECIALLY in this case that overhead is negligable (probably most other case also).

    Therefore, I guess if you want to be on the safe side... notifyAll is the way forward.



    Hi David,

    I totally agree with you and "in real life" I probably would have used notifyAll without a second thought*. However, this is an assignment and you have to justify your choices. At the time of coding I could not justify using notifyAll, save for "in case I make an error". Of course that didn't sound too good, so I choose notify, which could easily be justified with the performance word.

    Frans.

    [Added later]
    * After a second thought, I think I would have made the mistake in real life too. When I believe that one method is "better" than the other, I would choose it as a matter of principle, even though the other one has a lower risk.
    [ February 15, 2005: Message edited by: Frans Janssen ]
     
    Frans Janssen
    Ranch Hand
    Posts: 357
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator

    Originally posted by mark ken:
    hello Frans:
    Did you use hashtable to store the locked record, and use cookie to identify the locked record. Or, you just add a flag varible in record object to declare this record has been locked. just change this flag to unlock this record.



    Hi Mark,

    I used a hand-coded RecordLock object to register locks. Each record had one such object and it contained flags for isLocked and isDeleted.
    I still think it's a good design, if I had only covered the flaw as outlined above (which could be fixed simply by changing notify in notifyAll or introducing an extra notify).

    Frans.
    [ February 15, 2005: Message edited by: Frans Janssen ]
     
    Ranch Hand
    Posts: 808
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    You could always fix it then pay $400 to resubmit...
     
    mark ken
    Ranch Hand
    Posts: 47
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    thanks you Frans. I agree with you. Since we use cache to store database, this way is easy to handle.
     
    Frans Janssen
    Ranch Hand
    Posts: 357
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator

    Originally posted by Jeff Bosch:
    You could always fix it then pay $400 to resubmit...


    Hehe, I am not that much bothered!
     
    Greenhorn
    Posts: 20
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    My opinion is

    1. use notifyAll() instead of notify()
    The reason is
    a) notify() can only wake up a waiting thread. The sample is just the same.
    b)notify() can only wake up a waiting thread randomlly
    client 0 locks record Y
    client A locks record X
    client B locks record X; is put in wait()
    client C locks record Y; is put in wait() too
    client A deletes record X
    client A unlocks record X; notify() is called
    client C (Not B) wakes up to find that record Y is still locked;
    Then we have a unlucky-lock: B!

    2. if you really want to use notify(), you must make sure that each thread tried to lock must call notify() before it wait or leave
    3. use a Map Object to store lock and cookie, otherwise, you must throw a NoSuchRecordException when you try to lock a deleted record

    Welcome for any other opinion!
     
    Frans Janssen
    Ranch Hand
    Posts: 357
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator

    Originally posted by Jesse Xie Y.S.:
    My opinion is

    1. use notifyAll() instead of notify()
    The reason is
    a) notify() can only wake up a waiting thread. The sample is just the same.
    b)notify() can only wake up a waiting thread randomlly
    client 0 locks record Y
    client A locks record X
    client B locks record X; is put in wait()
    client C locks record Y; is put in wait() too
    client A deletes record X
    client A unlocks record X; notify() is called
    client C (Not B) wakes up to find that record Y is still locked;
    Then we have a unlucky-lock: B!



    This scenario only happens if all threads wait on the same object. I used one object for each record, so that I could be sure that the thread that is woken up is one that is waiting for the same record.

    Of course if one uses one lock object for all records, one has to realize that notify is not safe in that case.

    Frans.
     
    Ranch Hand
    Posts: 145
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    Hey, Frans:

    an awesome idea on record-level locking. I am interested in this case: what object do you lock on when you createRecord if you have one record lock object per record (hope I don't understand you wrong)? Mainly, client a and b try to create same record; since that record has not been created/is creating, what will be the locker object for this case?

    I used cachedRecords as a locker object and don't have the hassel over create. I got 80/80 over locking. But interested in record-level locking.
     
    Frans Janssen
    Ranch Hand
    Posts: 357
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator

    Originally posted by Andy Zhu:
    Hey, Frans:

    an awesome idea on record-level locking. I am interested in this case: what object do you lock on when you createRecord if you have one record lock object per record (hope I don't understand you wrong)? Mainly, client a and b try to create same record; since that record has not been created/is creating, what will be the locker object for this case?



    For create I indeed had to make an exception, because locking on a record that does not yet exist is of course impossible. In that case I synchronized on my LockCollection class (which is the singleton collection of all the RecordLock objects).

    Frans.
     
    Andy Zhu
    Ranch Hand
    Posts: 145
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator

    For create I indeed had to make an exception, because locking on a record that does not yet exist is of course impossible. In that case I synchronized on my LockCollection class (which is the singleton collection of all the RecordLock objects).



    In my implementation, I used one locker object, which allows minimum worry for dead lock. More than one locker objects imposes the potential danger. It is still doable, but be careful. In particular, for a non create, do you need to lock on 2 objects in your record-level locking?
    [ February 20, 2005: Message edited by: Andy Zhu ]
     
    Frans Janssen
    Ranch Hand
    Posts: 357
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator

    Originally posted by Andy Zhu:
    [QBIn my implementation, I used one locker object, which allows minimum worry for data lock. More than one locker objects imposes the potential danger. It is still doable, but be careful. In particular, for a non create, do you need to lock on 2 objects in your record-level locking?[/QB]



    When getting a specific RecordLock, the code is synchronized on both the LockCollection and the specific RecordLock object. Although looking back at my code now, I don't think the synchronization on the LockCollection is even required in that situation, because the only change to the collection can be the creation of new records.

    But anyway, because this is the only situation where there is a sync on two objects and the sync is always done in the same order, there is no risk of a deadlock there. But I admit it is something that needs a careful design.

    I had considered using one lock object for the whole database, but I felt that was a too limiting solution, because it did not allow simultaneous access to different records. It would have made a lot of stuff a lot simpler though.

    Frans.
     
    Andy Zhu
    Ranch Hand
    Posts: 145
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator

    When getting a specific RecordLock, the code is synchronized on both the LockCollection and the specific RecordLock object.



    But this is to eliminate your effort of record locking. See:
    lock LockCollection -> lock RecordLock -> do something -> unlock RecordLock -> unlock LockCollection

    is equivalent to:
    lock LockCollection -> do something -> unlock LockCollection.

    Although looking back at my code now, I don't think the synchronization on the LockCollection is even required in that situation, because the only change to the collection can be the creation of new records.



    How about deleteRecord? It should modify the LockCollection.

    ... with same order, there is no risk of a deadlock there.


    This is true. Only case I think of is the simultaneous call of update from thread A and delete from thread B. This won't cause deadlock given the above 2 locking processes existing in data access layer.
     
    Frans Janssen
    Ranch Hand
    Posts: 357
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator

    Originally posted by Andy Zhu:
    But this is to eliminate your effort of record locking. See:
    lock LockCollection -> lock RecordLock -> do something -> unlock RecordLock -> unlock LockCollection

    is equivalent to:
    lock LockCollection -> do something -> unlock LockCollection.



    What I was doing was:

    lock LockCollection -> get RecordLock -> unlock LockCollection
    lock RecordLock -> do something with record -> unlock RecordLock.

    While I am doing something to the record, the LockCollection is available to other threads to start doing things with other records.

    The only exception is the create method, where I don't use the RecordLock at all, because all other threads don't know yet the new record exists, so I don't need to lock it. **

    How about deleteRecord? It should modify the LockCollection.



    Not in my implementation. I kept RecordLock objects alive even for deleted records, for the case where they are to be reincarnated for newly created records. The main reason I did this, is because it must be legal to unlock a deleted record (if you are the lock owner), in case you did a lock-delete-unlock sequence.

    Frans.

    ** I mentioned in the previous post that I did not think I really needed the lock on the LockCollection; but now I remember that this is the scenario where I need it: if a new record is being created, I don't want other threads accessing it before the creation is completed. That's where the lock on the LockCollection is required.
    [ February 20, 2005: Message edited by: Frans Janssen ]
     
    Ranch Hand
    Posts: 1646
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    I only know as much about this scenario as I have been able to get from the discussion itself, but another method to block two Threads from creating new records at the same time would be to have a single "creating new record RecordLock" in the LockCollection. This way you don't lock the collection, blocking other Threads from operating on other records.
     
    Frans Janssen
    Ranch Hand
    Posts: 357
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator

    Originally posted by David Harkness:
    I only know as much about this scenario as I have been able to get from the discussion itself, but another method to block two Threads from creating new records at the same time would be to have a single "creating new record RecordLock" in the LockCollection. This way you don't lock the collection, blocking other Threads from operating on other records.



    David,

    I am not sure what you mean with "single". Do you mean a single synchronized method? Because that is exactly what I did. But it does block the collection during the creation of the record.

    Frans.
     
    David Harkness
    Ranch Hand
    Posts: 1646
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator

    Originally posted by Frans Janssen:
    I am not sure what you mean with "single". Do you mean a single synchronized method? Because that is exactly what I did. But it does block the collection during the creation of the record.

    If the requirement is to ensure that only one thread can be creating a new record, my proposal would be to create a single RecordLock instance for locking instead of locking on the collection.

    You said you use the following to lock a normal record for editing:From your description of creating new records, I assume you have this:Is that correct? If so, then while thread A is creating a new record, no other thread can modify or delete any other records. This problem is avoided if you change the second locking mechanism to use this single shared RecordLock instance for new records:
     
    Frans Janssen
    Ranch Hand
    Posts: 357
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator

    Originally posted by David Harkness:
    From your description of creating new records, I assume you have this:Is that correct? If so, then while thread A is creating a new record, no other thread can modify or delete any other records. This problem is avoided if you change the second locking mechanism to use this single shared RecordLock instance for new records:



    That is correct. The reason I need to hold the lock on the LockCollection, is that I do need to lock in the LockCollection to ensure that only one thread creates a new record at any given moment (otherwise they could be creating the same record). I could then lock on the new RecordLock instance, but I would have to get this lock before releasing the LockCollection lock (you all still with me? ), otherwise another thread might take it (very hypothetically of course).
    So I would want to do this:

    - lock LockCollection
    - create new RecordLock
    - lock RecordLock
    - release LockCollection
    - create record in file
    - release RecordLock.

    However, just using synchronized, this is not possible.
    It might be solved using other mechanisms than synchronized, but I felt that loss in performance would not outweigh the gain in complexity.

    Frans.
     
    With a little knowledge, a cast iron skillet is non-stick and lasts a lifetime.
    reply
      Bookmark Topic Watch Topic
    • New Topic