B&S Locking

[Joe Murphy]

Hi all,

Have dusted off my assignment after a very long time and hope to submit within the next few weeks. I wonder if anyone can point out any huge gapingly obvious holes in my locking approach!. I have placed pseudo-codish versions of lock() and unlock() below followed by explanation of what I'm trying to achieve!

lockMap is a HashMap, keyed by record number (id)

Lock:
-----

 
synchronized(lockMap) {
  while (lockMap.containsKey(recordNo)) {
      try {
          lockMap.wait();
      } catch (InterruptedException e) {}
  }
  long cookie = (long) (Math.random() * Long.MAX_VALUE);
  lockMap.put(recordNo, cookie);
  return cookie;
}

The Javadoc for the lock() method states that the client must call lock()/process()/unlock() within context of a single method call to guarantee it will happen in a single thread of execution.

I would very much appreciate any comments on this approach!

Many thanks

[ May 05, 2006: Message edited by: Joe Murphy ]

[Andrew: Removed Unlocking code]
[ May 05, 2006: Message edited by: Andrew Monkhouse ]

[Jeroen T Wenting]

Your lock method is pretty similar to mine, except I use a nanosecond precision timestamp (OK, it's a bit less than that on most machines, but still precise enough that it should be impossible in practice to get 2 records with the same lock) instead of a random number.
Remember that Math.random() is AFAIK not guaranteed either to not yield the same result twice (though I could be wrong).

For the unlock method I've chosen to just silently return if the record wasn't locked.
After all, there's no risk involved there, no attempt is made to unlock something the client isn't allowed to unlock.

Besides that, you may want to do some more testing on your wait/notify cycle to see whether it's airtight.
I'm not sure if there are holes, but it's better to be safe than sorry.

[Joe Murphy]

Thanks Jeroen for your quick response.... I presume you are using System.nanoTime() in 1.5?

Started the assignment pre 1.5 (a long time ago!) but I like your approach to ensure uniqueness of the lock.

[Jeroen T Wenting]

yup, that's what I use.
Started it off on 1.5 from the outset. Had never used 1.5 before so it's been a learning experience.

[Andrew Monkhouse]

Hi Joe,

I removed your unlock method as we do not allow posting significant segments of code (refer to the JavaRanch SCJD FAQ).

What happens in the case of:

Client A gets a lock

Client B requests the same lock

Client A deletes the record

Client A releases the lock

Originally posted by Jeroen T Wenting:For the unlock method I've chosen to just silently return if the record wasn't locked.
After all, there's no risk involved there, no attempt is made to unlock something the client isn't allowed to unlock.

Fair enough for some assignments, but for those assignments which specify that an exception must be thrown, then there is no choice.

Regards, Andrew
[ May 06, 2006: Message edited by: Andrew Monkhouse ]

[Joe Murphy]

Thanks Andrew for your insight, I really appreciate it. Apologies for posting code against regulations, will not do it again.
The scenario you raise is not one I had considered and I guess I will need to re-think my approach to locking.

[Czarak Ynehac]

Andrew,

You asked:

What happens in the case of:

* Client A gets a lock
* Client B requests the same lock
* Client B deletes the record
* Client B releases the lock

Is it not the case that if Client A has the lock for a particular record in step one, then in step two Client B will not get a lock for that record as A has it, therefore B will not be able to delete the record?

[Andrew Monkhouse]

Originally posted by Czarak Ynehac:
[QB]Andrew,

You asked:

Doh

You are quite correct. I posted too late on a Friday night after too many good beers. Always a bad thing to do. What I meant to ask is what happens if client A deletes the record, viz:

Client A gets a lock

Client B requests the same lock

Client A deletes the record

Client A releases the lock

Joe seems to have done a translation and worked out what I meant to say (thankfully), and realized that a client using his existing lock() method could end up owning a lock on a deleted (non-existant) record.

Regards, Andrew

[Joe Murphy]

As a solution to the problem Andrew identified of a client being able to hold a lock on a deleted record, my solution is that before adding the record no to the map of locked records in the lock() method, to iterate through the list of contractors and to check if the contractor record to be locked is marked as deleted. If it IS, then a RecordNotFoundException is thrown. Basic idea in code below:

    
synchronized(lockMap) {
  while (lockMap.contains(recordNo) {
    //wait
  }
  //Iterate over contractor list to find recordNo
  //If recordNo is DELETED, throw RecordNotFoundException
  lockMap.put(recNo, cookie);
}

Would this adequately address the problem?
Thanks!

[Jeroen T Wenting]

that's indeed the way to go, but make darn sure that you don't do that when releasing a lock on a deleted record...
Else you'd get the following:

- lock record
- delete record
- unlock record BOOM!

[Andrew Monkhouse]

Originally posted by Jeroen T Wenting:
BOOM!

You do not want to let the smoke out of your computer! Contrary to popular belief, computers run on smoke, and once the smoke comes out of them they no longer work!



On a more serious note, those of you who have unlock methods which throw a RecordNotFoundException will have to consider the issue raised by Jeroen very carefully. Things to consider: how does the record ever get unlocked, and what documentation do you need to write regarding this (and where should said documentation go)?

Joe - in going back over your first post, I noticed that you are swallowing the InterruptedException. Are you sure that is the way to go?

Regards, Andrew

[Joe Murphy]

Ha ha yes after this project is finished I will need some more smoke for sure

On a serious note, thanks guys for your comments, it really helps. Jeroen - I do not perform the check to see if the record is deleted in the unlock() method, only in the lock() method. So in the scenario of :

- lock record
- delete record
- unlock record

This should still be okay as far as I can tell. If the record was able to be locked in the first place, it should be unlocked okay.

Andrew - my unlock() method does not throw RecordNotFoundException, only SecurityException (which is thrown when an attempt is made to unlock a record with a different cookie to the one it was locked with). Since the locking API is used as lock/process/unlock in the context of a single method call, the only way a record could remain locked is if the client making the call failed before calling unlock(). I am going to include this scenario in my choices.txt, saying I am aware of it, but consider it beyond the scope of the assignment - do you think this is okay or should I implement some kind of lock timeout in case of client failure?

In case of the InterruptedException thanks for pointing out that I am swallowing it. Since interrupt() is not called explicitly within the application, I propose to handle the exception by throwing a RuntimeException after setting the interrupt flag back again. So I would handle with the following:

    
Thread.currentThread().interrupt();
throw new RuntimeException("Thread interrupted", e);

[Jeroen T Wenting]

No worries Andrew, my computer uses smokeless explosives

As an aside: I've changed my locking in the lock and unlock to if possible lock on the actual lock.
Prevents the entire lockMap from being locked in the lock method when some thread is waiting for an entry to be removed.
When no lock exists, it locks the entire lockMap instead.

Any thoughts about that approach?
It should give better performance, and if my reasoning is correct should be secure enough to prevent multiple threads locking the same record.

skeleton code (error handling, logging, etc. etc. removed):

        Object synch = locks.get(recordId);
        if (synch == null) {
            synch = locks;
        }
        synchronized (synch) {
            while (locks.containsKey(recordId)) {
                    synch.wait();
            }
            locks.put(recordId, cookie);
// further code

I'm not quite certain if it's bulletproof, altough testing it with 5 clients all trying to grab locks on the same record shows no 2 threads getting a lock on the same record at the same time.

[Josephx Rainerd]

Object synch = locks.get(recordId); if (synch == null) { synch = locks; } synchronized (synch) { while (locks.containsKey(recordId)) { synch.wait(); } locks.put(recordId, cookie);// further code

Not sure if the its typo, seems the check if (synch == null) is not done in sync-ed context and might not fulfill the purpose.

I check if record is active before going into and after waking up from wait state. And the baby waits and wakes up in sync context obviously.

Thanks
[ May 10, 2006: Message edited by: Josephx Rainerd ]

[Jeroen T Wenting]

the check indeed isn't in synched context. In fact it can't be because it determines the object to synch on.
If it's null, the entire lockMap is used instead.
That's a failsafe fallback system, if it's used more often than strictly needed it should do no harm except potentially some clients may have to wait on something unnecessarilly.

Where I have some doubts as to the validity of the code is mainly in the area of code coverage.
Would there be a possibillity of a thread gaining entry to the synchronised block for a locked record and gaining another lock on that same record.
Logic tells me it won't happen, but I'd like some more eyes to look at it.

[Josephx Rainerd]

Object synch = locks.get(recordId); if (synch == null) { synch = locks; } synchronized (synch) { while (locks.containsKey(recordId)) { synch.wait(); } locks.put(recordId, cookie);

Regarding synchronizing, consider :
Assume a Thread1 gets, synch = locks.get(recordId) returns valid reference.


Before this Thread1 hits synchronized (synch) {..} block, the owner thread (Thread2) of that record deletes the record. Thread1 is unaware of that and locks on the stale reference and proceeds. That breaks the locking model.

[ May 10, 2006: Message edited by: Josephx Rainerd ]
[ May 10, 2006: Message edited by: Josephx Rainerd ]

[Jeroen T Wenting]

I had actually thought of that option.
My locking mechanism is a 2 stage rocket. The client calls lock() on the Data class (as dictated by the assignment) which forwards it to the LockManager.
The LockManager knows nothing about records, only locks.
The Data class synchronised on itself, calls lock() on the LockManager (if the record exists in the datastore at that point), then checks whether the record still exists in the datastore.
If the record no longer exists in the datastore after the lock() operation on the LockManager, the lock is removed and a RecordNotFoundException thrown back to the client.