I'm working on synchronization strategy with all methods 'synchronized' in my Data class (Data class implements interface provided by Sun).
I want to be 100% sure that I won't end up with deadlock so I decided mark all methods in Data class synchronized - I thought it would be the safest because as long as Data class is singleton only one method can be executed at time.
Now little about locking strategy:
- hashMap (recNo -> lockCookie)
- synchronizing on the map in lock/unlock methods.
So my lock method looked like:
But with such approach the simplest scenario causes deadlock:
Thread A: data.lockRecord(1)
Thread B: data.lockRecord(1) <- B is waiting but does not release monitor on Data class but only on map, so any subsequent method invocation on Data class causes deadlock because B is waiting with Data class monitor and other threads can't invoke any method on Data.
I tested that after I remove synchronize statements on lock/unlock methods DataClassTest (thanks Roberto ) passes without deadlock but now I'm not sure if there aren't some tricky scenarios that will cause deadlock.
To conclude, currently I ended up with synchronized CRUD operations (on Data class) and not synchronized lock/unlock methods. (in lock/unlock I have synchronization block on map).
Now the trickiest part to me is that in some CRUD operations I need to check if records are locked in map (for example: in update method I must verify if record is locked with provided cookie) and in lock method I must check if record is not deleted after thread is woken (see pseudo code of lock method).
And I don't have any extra synchronized code to handle those checkings - just simple private methods: isRecordLocked(), recordExists().
So my certainty dropped to 70% cause it sounds like possible chance of races.
I think that I'm gonna start analysing all worst cases scenarios with pencil and sheet of paper till I'm sure it's working as should.
Maybe I'm exaggerating but you know I don't want fail at automatic level.
I shared my design to hear from you any comments / maybe there are some obvious mistakes you can point out ? Any comments are welcome
If I have a look at the code snippet I have my doubts about your knowledge about the keyword "synchronized". If you synchronize on the lockRecord-method why on earth are you synchronizing on the map-instance There is completely no need for, because you are already synchronizing the complete method. And I marked all methods (= every method in Data class) as synchronized.
If you can run Roberto's data class test with 1000 or 10000 iterations without deadlocking your code works fine. There is one specific case where a deadlock might occur, caused by a specific order of update and delete + a flaw in your code. But it's up to you to do some thinking about it
As for your question why I synchronized on map - because I call wait/notifyAll methods on map and I believe that I need monitor on the object to call those methods.
So what object do you use to wait/notify threads ? Your Data class ?
I just have tested approach 'all methods synchronized' and waiting on Data class. Performance dropped dramatically but I guess this is a price for 100% certainty.
As for "There is one specific case where a deadlock might occur". I started thinking on this and realized that simple scenario: lock(1), delete(1), update(1) will cause problems. Looks like in my update method I also need to check if record exists and throw RNFE otherwise update will be performed on deleted record.
Assuming I'm gonna stick to 'all methods synchronized' approach I must say that I don't see any possibility of deadlock. Did you mean that this possibility is in the case I left lock/unlock without 'synchronized' or is this some general issue ? Any clue will be appreciated.
Because time is the issue I'm gonna master my first approach but I also considered some redesign of Data class. Basically there are 2 resources that need atomic access: records(file) and map with locks. Atomic access can be achived be synchronizing on objects: FileDataAccess for records and on map for locks (I havn't created separate class like LockManager to wrap my map). Now in some methods I would need synchronize on both them - creating nested locks, but the idea is to acquire locks always in the same order. And waiting/notifying would be performed only on map. Just thoughts - but I guess one puprose of this assignment is to make us thinking .
So what object do you use to wait/notify threads ? Your Data class ?
I used the this object (which is the sole instance of Data class) to call wait/notifyAll.
I'm curious to know how you measured the performance dropping dramatically. Of course the performance of your application will be less than when you use synchronize blocks or the new concurrency api, but a more performant application will not score higher than a less performant one (that's clearly stated in your instructions). But I never experience dramatic performance.
About the possible deadlock situation: your suggestion is in the good direction, but of course that sequence can not happen at all. Because after each update/delete the unlock method must be called. And a client can only update/delete a record when it has the lock on that record, so another client can NOT update/delete that record.
But if you think a bit further, you'll discover (and handle) the situation I was referring too
And I'll throw another question at you: what about allowing a client to lock multiple records at a given time...
Joined: Oct 11, 2010
I take back what I said about performance.
Tests are really simple and probably don't have much to do with real conditions. Basically I increased number of threads in loop and measured time to program end. My first impression was that on computer at work with 4 cores (at home I have only 1 core) tests took about minute while at home about 15 seconds, but now I think that I'd had some stuff running in background. I came home and performed tests again and I must say that in both cases I got similar time.
It's obviously wrong usage of API but having RNFE at update/delete on deleted record sounds ok to me (maybe this is why my interface defines RNFE on those methods).
As for allowing a client to lock multiple records at a given time.
If you mean that client via GUI can lock multiple records it's not an option at this stage. I have almost completed GUI where you select record, provide customer id and on ok button I call my service (thin client approach, one method in service that quickly does all magic: lock/read/update/finally:unlock).
At low level assuming that client is a thread no problem with sequence like:
locked forever . I think there is no simple solution. To track such situations I would need to have a way to identify clients. Probably I would have to extend interface to pass an id. I think I'm gonna state in javadoc that locking on a record twice (without unlock) by the same thread will result in deadlock.
Przemyslaw Pankowski wrote:It's obviously wrong usage of API but having RNFE at update/delete on deleted record sounds ok to me (maybe this is why my interface defines RNFE on those methods).
I don't throw a RNFE from update, delete and unlock method. The only method which should throw this kind of exception is the lock-method. Because once a method is successfully locked, it can't disappear (unless your code has a bug). And of course you don't have to handle wrong usage of the API, because that's not supposed to happen. But you can of course try to prevent wrong API-usage (e.g. when a String is passed to my update-method with too many/little elements will result in an IllegalArgumentException). Another example: in my assignment I didn't have an interface with lockCookie, so I added a way to identify a client and that's why I (or my code) was able to know when a client was locking a 2nd record before unlocking the 1st one. Again this situation is wrong API-usage and I blocked it by throwing an IllegalStateException. People with a lockCookie-interface can't do anything more than documenting the intended use of their API in the javadoc (and hope any new developer will have a read before using it), because there is no way to identify the client.
Przemyslaw Pankowski wrote:If you mean that client via GUI can lock multiple records it's not an option at this stage.
Your Data class must be able to handle concurrent requests (as per instructions). So I can use your Data class to develop another application (without using your GUI and/or business service) and I hope your Data class will be thread-safe (when I use your API appropriately) and does not deadlock. Otherwise I will hunt you down and do a bit of with your head
I recall having a similar problems with synchronization, and even though my locking passed with 1000 iterations of Roberto's test case, I did come up with the scenario where there could theoretically be a problem, and then managed to make a test case and reassure it as well. Thus what I did was to have my locking manager class to store its own list of record numbers separately and create/delete methods of Data class had to separately add record numbers to that list.