Locking problem

[Oliver Rensen]

Hello ranchers,

I have an awkward problem with synchronized code.

In my project, there is only one instance of the Data-class. I don't use a cache for the records, I cache only the deleted record-IDs in a HashSet (suggested by Phil some months ago; I think, it's a good idea and a convenient way to deal with deleted records). The following methods are synchronized: read, update, delete, create, find and my own methods isDeleted and closeDB. lock and unlock are not synchronized. These methods include synchronized blocks, and these blocks are synchronizing on the HashMap lockedRecords (similar like in Max' book).

The methods unlock, delete and update all have the parameter lockCookie and must throw a SecurityException, if the record is locked with a cookie other than lockCookie.

And now my problem: delete, update, lock and unlock are reading or writing the lockedRecords-HashMap. delete and update are synchronizing on "this", but lock and unlock are synchronizing on "lockedRecords". When a thread is modifying the lockedRecords-HashMap in the lock- or unlock-method, another thread can read the HashMap in an inconsistent state. The access on the lockedRecords-HashMap is not completely synchronized, because the methods are synchronizing on different objects.

I see three undesirable alternatives for this dilemma:

a) I create a method isLocked(record, cookie) and check in this method, whether the record is locked with the given cookie. Either the method is synchronized or there is a synchronized block (synchronizing on the HashMap), and delete, update and unlock call this method. Disadvantage: The Data-class would contain nested synchronized code, and this is a bad design that leads to deadlocks.

b) I create the method isLocked without synchronized code. Disadvantage: The access on the lockedRecords-HashMap is not synchronized between lock/unlock and update/delete. But is this really a drawback, or do I see a problem, where no problem occurs?

c) I remove the synchronized blocks from the lockedRecords-HashMap and synchronize lock/unlock on "this", too:

public synchronized long lock(...)
public synchronized void unlock(...)

Advantage: Every Data-access is completely synchronized, and there are no nested sync-blocks.
Disadvantage: Hmm, I don't know. I think for a long time about this, but I cannot see any error. What would happen when I synchronize the complete methods lock and unlock? Would this lead to a bad design, or to a performance problem?

I prefer the solution c), but I believe, that I have overlooked a drawback.

Could any smart rancher enlighten me, please?

Tired regards
from a confused greenhorn

[mike acre]

Collections.synchronizedMap(new HashMap());

Then you don't need to nest locks.

Obviously, it goes without saying that you still need to externally synchronize in lock/unlock methods.

[Oliver Rensen]

Hello Mike,

thank you for your hint.

The Hashtable is a synchronized collection, and with the method-call

  
// synchronized-view of a map
private Map syncMap =
Collections.synchronizedMap(new HashMap());

I will get a synchronized HashMap. Thus, the Hashtable and the syncMap are both synchronized, correct?

In this thread Nested Locking

Andrew wrotes

Note that the Hashtable is synchronized, but you are calling it within a synchronized block. Therefore you are nesting synchronized blocks (implicitly, not explicitly) - this is a bad thing.

I would access on the syncMap in my synchronized methods update and delete, thus I have nested synchronized blocks, too.

Is it really a good idea to use Collections.synchronizedMap(new HashMap())?

Regards,

Oliver

[Anton Golovin]

Hi, Oliver. Your design with one Data instance is the same as mine. In my case, I chose to have a private HashMap, and it is not synchronized. The methods of the Data class, however, are synchronized - all of them. Alternatively, there could be synchronized blocks for HashMap within the lock/unlock methods, to limit the scope of synchronization. Depending on caching or not caching records, other methods would be synchronized or perhaps not - provided data write/read is synchronized.

This way, no locks are ever nested.

[mike acre]

Originally posted by Anton Golovin:
The methods of the Data class, however, are synchronized - all of them. Alternatively, there could be synchronized blocks for HashMap within the lock/unlock methods, to limit the scope of synchronization.

If you sync against Data for your lock/unlock methods then no other thread can even read the database while it is locked. Admittedly the lock is quickly realeased when you go into wait. But it seems wrong to use the same object for unrelated tasks. There is the potential for great deal of fighting for one resource when in fact the threads want different things. To kids fighting over the red toy, except one is colour blind and actually wants the blue one

Or do I misunderstand you?

I'm on dangerous ground here, if I hear stuff I don't want to hear.
Might be wise to retire to a safe distance, whilst I await my results.

[mike acre]

Oliver,

If you had used Hashtable instead of HashMap would you be concerned about

 
 
Map myHashtable = new Hashtable();
 
//
void lock() {
  synchronized(myHashtable) {
 
    while(myHashtable.contains(...)) {
     //
    }
  }
}

Seems okay, except Hashtable is synchronized anyway, so the locks are nested. The point I'm making is that you can't easily avoid nesting locks. I think the advice is don't do it explicitly in your own code.

Afterall you may never know if a library method is synchronized, it doesn't even show up in Javadoc.
[ September 07, 2004: Message edited by: mike acre ]

[peter wooster]

Here's a forth alternative to your problem that does not involve any nested synchronized blocks:

lockMap = a unsynchronized Map of resource-cookie values where resources are Long values

treat locking a record as the following sequence
- sync on lockMap
- wait until resource available
- take resource
- exit sync on lockMap
- sync on the database file
- check if record number is valid and not deleted
- exit sync on database file
- unlock resource if the record wasn't valid, involves resynch on lockMap.

Since the items being locked are not records, but rather arbitrary Long values that just happen to be record numbers most of the time, there is no tie between the database file and the locking mechanism. Since the resource may not actually be a record number you must check. The choice is to check before or after locking. If you check before, you will still have to check after, since a delete could have been in progress, and an insert may have taken place without locking. When you check after, you will need to unlock if it turns out that the number doesn't represent a valid record.

[mike acre]

Peter,

I don't think that is sufficient.

What you propose is fine during lock/unlock but what about the check during update/delete? They will read that map, and they may do so whilst another thread is writing to the map in a lock method. In this circumstance the map must be at least internally synchronised.

[Oliver Rensen]

Why shall we not synchronize the complete methods lock and unlock? It's the safest way to avoid nested synchronizing, and every access to the raf-file and the lock-HashMap would be thread-safe. The only drawback is less performance, but it's better than risking a deadlock or inconsistent datas.

[mike acre]

Originally posted by Oliver Roell:
Why shall we not synchronize the complete methods lock and unlock? It's the safest way to avoid nested synchronizing, and every access to the raf-file and the lock-HashMap would be thread-safe. The only drawback is less performance, but it's better than risking a deadlock or inconsistent datas.

Yes but it is a lot of 'less performance' because every time those thread wake from wait they all have to aquire the lock on the Data class which will be required by other threads that read, update...

lock & unlock are very separate to the other methods, I think it is a mistake to consider them in the same way, they have different resources.
Did you read my fighting children analogy earlier? Of course I could be wrong, but this is the way I see it.

[Oliver Rensen]

Hello Mike,

thanks for your clarification.

I have read your fighting children analogy, and I agree with you.
It's not a good design to synchronize the methods lock and unlock.

I guess, you have used the synchronizedMap(new HashMap()) with the implicitly nested synchronized blocks in your assignment, am I right? I think, I will wait until you have got your results. When it's a fail or a 44/80 locking score, I don't use the synchronized map, else I will use it.

To be serious: I should go with your suggestion, although I'm not really happy with this solution, but it seems, there are no better alternatives for an easy and clear locking design.

Maybe our cunningly bartenders can help us with this topic?

Regards,
Oliver

[mike acre]

Oliver,

I think, I will wait until you have got your results. When it's a fail or a 44/80 locking score

Ouch!

Why don't you post on comp.lang.java.programmer?

Something like:

We are told it is a bad idea to nest sync blocks, but what about the implicit synced blocks of other methods we have no control over, ie

sync(this) {
aSyncedMethod();
}

I'm afraid I already post too much on there
[ September 08, 2004: Message edited by: mike acre ]

[peter wooster]

Originally posted by mike acre:
Peter,

I don't think that is sufficient.

What you propose is fine during lock/unlock but what about the check during update/delete? They will read that map, and they may do so whilst another thread is writing to the map in a lock method. In this circumstance the map must be at least internally synchronised.

Of course, all accesses to the Map must be made from code that synchronizes on the Map. I use the smallest blocks of code possible.

My updateRecord and deleteRecord methods call a validateLock method in the LockManager that synchronizes on the Map. They then call the writeRaw method that synchronizes on the RandomAccessFile.

[mike acre]

Originally posted by peter wooster:

My updateRecord and deleteRecord methods call a validateLock method in the LockManager that synchronizes on the Map. They then call the writeRaw method that synchronizes on the RandomAccessFile.

Okay fine.

Of course, all accesses to the Map must be made from code that synchronizes on the Map. I use the smallest blocks of code possible.

But that isn't true. All access do not require to synchronise on the map.
If the Map is in a multithreaded environment and there are only non-structural changes to the map then there is no need to synchronise on the map and no need to even have a synchronised map. I realise that this is not the case.
Our typical case is that there are structural modifications to the map in lock/unlock methods and non-structural accesses in update/delete. Therefore the only synchronisation required in update/delete is with an internally sychronised map (ie Collections.synchronisedMap), this is the case because they do not modify the map but there is concurrent access that does.
This I believe is more minimal sync than you are proposing.

[peter wooster]

Originally posted by mike acre:

But that isn't true. All access do not require to synchronise on the map.
If the Map is in a multithreaded environment and there are only non-structural changes to the map then there is no need to synchronise on the map and no need to even have a synchronised map. I realise that this is not the case.
Our typical case is that there are structural modifications to the map in lock/unlock methods and non-structural accesses in update/delete. Therefore the only synchronisation required in update/delete is with an internally sychronised map (ie Collections.synchronisedMap), this is the case because they do not modify the map but there is concurrent access that does.
This I believe is more minimal sync than you are proposing.

I was refering to our locking code not to the use of Maps in general. In our case there are threads that make structural changes, so all accesses must be from within synchronized blocks or by using the Collections.synchronisedMap. I use synchronized blocks.

The original point of my post was that you should avoid the nested locking, and that this can be done by checking the lock status first and then locking on the file. The use of synchronized blocks helps avoid accidental nested synchronization.

[Oliver Rensen]

Even though Mike will lynch a stubborn greenhorn like me, I still thinking about the bad design decision "synchronize the methods lock and unlock".

In my DB-interface and Data-class I must implement the following methods:

- read(int recNo) throws RecordNotFoundException
- update(int recNo, String[] data, long lockCookie)
throws RecordNotFoundException, SecurityException
- delete(int recNo, long lockCookie)
throws RecordNotFoundException, SecurityException {
- create(String[] data) throws DuplicateKeyException
- lock(int recNo) throws RecordNotFoundException
- unlock(int recNo, long cookie)
throws RecordNotFoundException, SecurityException

The methods create and delete can influence the number of deleted records. Lock and unlock needs this information to throw an RNFE.
The methods lock and unlock can influence the number of locked records. Update and delete needs this information to throw an SE.
Summary: update and delete must synchronize on an object that can be modified by lock and unlock - and vice versa.

You can solve this problem with sophisticated synchronized blocks, and I believe, that it could work, but IMO its neither KISS nor easy to understand by junior programmers. It's difficult and dangerous, and there are a lot of possibilities for side effects.

When lock & unlock must synchronize on an object that can be modified through create & delete, and update & delete must synchronize on an object that can be modified through lock & unlock, it will be the safest way to synchronize all these methods on "this". No deadlocks, no nested synchronization, no inconsistent datas. Only less performance. But performance is not a SCJD-requirement.