The mysterious 65/80 locking score

[Frans Janssen]

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.

[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() ?
Thx Frans
Greetz


Frank

[Frans Janssen]

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]

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

[Liang Anmian]

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]

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.

[David Abramowicz]

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

[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.

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]

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]

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 ]

[Jeff Bosch]

You could always fix it then pay $400 to resubmit...

[mark ken]

thanks you Frans. I agree with you. Since we use cache to store database, this way is easy to handle.

[Frans Janssen]

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

Hehe, I am not that much bothered!

[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!

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]

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.

[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?

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]

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]

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]

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]

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]

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 ]

[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.

[Frans Janssen]

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]

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:

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

From your description of creating new records, I assume you have this:

lock LockCollection -> create new record -> unlock LockCollection.

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:

get shared RecordLock for creating new records
lock RecordLock -> do something with record -> unlock RecordLock.

[Frans Janssen]

Originally posted by David Harkness:
From your description of creating new records, I assume you have this:

lock LockCollection -> create new record -> unlock LockCollection.

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:

get shared RecordLock for creating new records
lock RecordLock -> do something with record -> unlock RecordLock.

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.