Deadlock prevention in record locking mechanism

[Garik Ustinov]

Hi ranchers
Since we are supposed to implement lock & unlock methods which are exposed to client, I feel the deadlock's breath. The opportunities are numerous: bad client side code, which calls these methods incorrectly; network problem in between lock and unlock; after all, client machine may crush before it calls unlock and we will find ourselves in trouble.
So what I was thinking about is a little single-threaded ExecutorService, which would periodically check all currently held locks (and if it finds a lock, which is 'older' than, well I don't know, 10 sec, it would assume a deadlock, remove the lock from the map and notify()).
I would appreciate your thoughts about it.

[K. Tsang]

Hello there. First the lock/unlock methods don't have to be exposed to the client. There are several ways to do this:
1) directly expose lock/unlock methods so that your GUI/client code call lock() -> update() -> unlock() of the Data class
2) use a service layer where only the necessary methods are exposed eg book and search

Talking about deadlock, it can happen doesn't matter where you put the lock/unlock methods. Assuming the code was used correctly, your methods need to be synchronized so that ideally only one thread executes the lock->update->unlock process. Also using a timer may not be because what happens if 2 clients try to lock a record and some how network is slow (eg over 10sec) and by then you deadlock the first client. If this is the case, then all other clients would deadlock or their GUI will freeze because Swing code is execute on the event dispatching thread which is single threaded.

[Garik Ustinov]

Timer length of course must be configurable and could be switched off completely. I am just assuming that 10 s is more than enough for the majority of small networks. And I don't see why it wouldn't work. If 2 clients try to lock a record, one of them would acquire it and LockEntry containing client id, token or instance as well as timestamp would be added to the dedicated map. The second client goes to wait. Some time later, a separate thread in properly synchronized method checks all entries in the map and if it decides that the entry is too old, it removes it and notifies the second client. Everyone's happy (of course except client 1, the Troublemaker).

only one thread executes the lock->update->unlock process

But in this case, if all methods are synchronized, each thread is guaranteed to execute update() atomically, which leads us to the question: whats the point in using lock/unlock at all? OK, the reason for doing this could be executing big batch read/update jobs, but there's nothing about it in the instructions.

use a service layer where only the necessary methods are exposed eg book and search

This is probably the simplest and quite sensible thing to do. Thanks, I will consider using it. I just don't like the idea of creating the interface implementation which must be used in a very specific way and if used incorrectly it would inevitably cause problems.

[Roberto Perillo]

Howdy, Garik!

Champion, in my case, I did just like my good buddy K: the client uses a business interface with a few methods, and one of these methods is bookRoom(). In this method, there's the logic of calling lock/update/unlock. I see that you are worried about something happening and the application hanging forever. In my case, I didn't implement any mechanism to prevent this kind of thing, just the locking mechanism. I justified my decision though. This isn't really necessary, but you can come up with such a mechanism.

Garik Ustinov wrote:But in this case, if all methods are synchronized, each thread is guaranteed to execute update() atomically, which leads us to the question: whats the point in using lock/unlock at all?

Please take a look here. I think it might be helpful!

[Andrew Monkhouse]

Hmmm - I don't like the idea of a timer removing locks. It is not necessary, and I think that you would have to explicitly change the description for the lock method to indicate that it is only owned for a limited time - I personally believe that changing how any method in the supplied interface is supposed to work is a really bad idea - it could potentially lead to failure.

As for how to do this - take a look at the java.rmi.server.Unreferenced interface if you are using RMI, or have a look at java.net.SocketException if you are using Sockets.

Having said that - I know that there have been candidates who have used timeouts and passed. Time for you to make a design decision (and document it).

[Garik Ustinov]

Hi Roberto!
I think Client 2 would happily overwrite Client 1 booking without hesitation regardless of our locking implementation. If we want to completely avoid this kind of things we need some sort of versioning mechanism or a set of business rules preventing the clients to overwrite existing bookings. My guess is that Sun was struggling to give us something exciting to implement and fortunately it managed to come up with lock/unlock methods .
What I was saying is that there is no need to make lock() -> update() -> unlock() cycle as atomic operation or declare update() as synchronized. I think, lock/unlock logic synchronized on the map which holds the locks would do just fine provided that update() checks if the client is holding the lock. Well, physical file access should be synced as well of course.
Cheers

[Garik Ustinov]

Thanks Andrew, I haven't really thought about it in this way. The idea of exposing only find() and book() instead of creating a timer is beginning to appeal to me

[Andrew Monkhouse]

Garik Ustinov wrote:
I think Client 2 would happily overwrite Client 1 booking without hesitation regardless of our locking implementation.

Having locks by themselves does not stop overwriting bookings, however you can use them in your business logic to ensure data integrity. Take a look at the JavaRanch SCJD FAQ entry for Why do we have lock() methods in the Data class? to see if it gives you some hints.

[Garik Ustinov]

Well, checking for availability prior to updating may contradict with business rules, because that would somehow complicate for example booking cancellation in future (and according to modern business trends this is quite an important functionality . But after all it definitely makes sense in terms of database integrity.
Cheers!

[Andrew Monkhouse]

I wouldn't advise performing any business logic checking within the update method itself - that method could be used to update any field at all.

Somewhere in your application you are going to call the 3 methods lock - update - unlock. I would suggest that these after the call to lock and before the call to update you would perform any business sanity checks. For the purpose of the assignment, this is probably just a check to ensure that the record is not yet booked. In the example you gave of canceling a booking you would probably check that there was a booking. If we were updating prices we might check that there is no booking (might be considered a bit rude if we changed the price after the record was already booked). And so on.

[Roel De Nijs]

Garik Ustinov wrote:checking for availability prior to updating may contradict with business rules, because that would somehow complicate for example booking cancellation in future

I don't see how it can contradict with business rules. I think it's a very important business rule "not to override the booking of another client" (a lot more important than for example the 48 hour rule), otherwise 2-3-4 people may show up that night, because they all got a "successful" booking. I also don't see how it can complicate booking cancellation in future... But of course, just my opinion

my booking pseudo-code:

    
        try {
            // lock record
            // read record
            // check room still available (if still available: update, otherwise throw exception)
        } catch (...) {
            // handle exceptions appropriately
        } finally {
            // always unlock record
        }

And the code for unbooking a hotel room would be very similar, the only thing you have to handle is: what should happen if an available room is unbooked (throwing an exception or just doing nothing).

[edit] Just saw Andrew was a bit faster

Kind regards,
Roel

[Garik Ustinov]

I see the point. I was a little worried about the Sun's interface implementation itself. I mean the interface was given to us, it is presumably used somewhere else and we have no means to know where and how. Hopefully the Testing Program isn't evil enough to choose some weird combination of multithreaded calls to lock/update methods and blame the implementation for unexpected overwritings (by the way, what's the chance of getting paranoia during SCJD preparation? .
Thanks to everyone, I see things a bit clearer now.

[Roel De Nijs]

Hi Grary,

If the (evil) testing program is able to do something like this and successfully update record 1, it certainly will blame the implementation and even will fail you automatically.

    
client1.lock(1);
client2.update(1, newData);
client1.unlock(1);

If the testing program is able to do something like this and newData1 gets overwritten by newData2, your implementation certainly won't get the blame, because it's expected behavior.

    
client1.lock(1);
client1.update(1, newData1);
client1.unlock(1);

client2.lock(1);
client2.update(1, newData2);
client2.unlock(1);

Kind regards,
Roel

[Elchin Asgarli]

client1.lock(1);  
client1.lock(2);  
client1.update(1, newData1);  
client1.update(2, newData1);  
client1.unlock(1);  
client1.unlock(2);  


client2.lock(2);  
client2.lock(1);  
client2.update(2, newData1);  
client2.update(1, newData1);  
client2.unlock(2);  
client2.unlock(1);  

What about this code above? If it hangs in a deadlock, is it also an expected behavior and implementation will not get blamed for it?

[Roel De Nijs]

In my assignment this is impossible. A client can lock 1 record at a time. Before locking another one, it has to release the lock on the other record first. I know this approach is not suitable for every assignment (depends on the interface you have to implement). These people have documented this in javadoc and decision document.

[Roberto Perillo]

In my case, when a client that already owns the lock of a record tries to lock another record, a RuntimeException is thrown. So it is also impossible.

[Elchin Asgarli]

I am pretty confused now...

Does this mean that Data class(!) has to have a mechanism to recognize clients? How did you guys achieve that?

Also note that I am planning to have an RMI-based business service on top of Data class, which will have methods for booking and retrieving records only, so my GUI clients will never be able to lock/unlock records themselves, my business layer will do that. But do I also need to somehow protect Data class itself from locking of two records by their invokers? And if yes, what are my options to do that?

[Roel De Nijs]

Hi Elchin,

It depends on your assignment. If you have an assignment where the lock-method in your interface does not have a lockCookie (like Roberto and me), it's very easy to identify your clients. IF you have to return a lockCookie you can't do that. So you have to trust that your Data class is used correctly: a client/thread can only lock 1 record; if it wants to lock another one, it has to release the lock on the other record (and of course document it in javadoc and decisions document).

And I also had a RMI-based business service on top of the Data class, but that does not mean your Data class may deadlock. You have to do everything what's in your power to prevent possible deadlock, because your Data class could be (re)used in a multi-threaded environment (without your business service).

Kind regards,
Roel

[Elchin Asgarli]

I am even more confused, how me NOT having a lockCookie will make it easy for me to identify my clients?

But on a bright side that is not the case for me, my method signature is public long lock(int recNo) throws RecordNotFoundException, where returned long is the cookie that needs to be used with update, delete and unlock methods. Does this mean that my Data class is not meant for abusing in a way I described above?

Besides what if my Data class is meant to be used in a way that one client must be able to lock two records?

[Roel De Nijs]

Hi Elchin,

First of all it's not my intention to make you doubt more and more

if you have a lockCookie, you just generate a unique value and the client/thread with this unique value is allowed to delete/update the record. It does not get any easier than that.
if you don't have a lockCookie, you need a way to identify your clients, because as you know (or should know) RMI does not guarantee that a request from the same client or handled by the same thread. So you need some mechanism to identify the client, because a record locked by a client, may only be updated/deleted by that specific client. So it is a bit more work to do (then just generating a lockCookie), but you can prevent a deadlock without any problem: you (can) know exactly how many records a specific client has already locked, so when it has already locked a record, you can block another record being locked by the same client (by throwing an IllegalStateException for example).

Your Data class could be abused if multiple records are locked by different clients in a specific order. So you'll have to add some comments (in javadoc and/or decisions document) to define proper use of the Data class (and so you give the accessor obvious indications you identified the possibility of deadlock, and you have thought about how to avoid it)

Elchin Asgarli wrote:Besides what if my Data class is meant to be used in a way that one client must be able to lock two records?

That's not the case for this assignment, so YAGNI. And if in near future this functionality is required, you will have to create some sort of "preventing deadlock"-mechanism.

Kind regards,
Roel

[Elchin Asgarli]

Roel De Nijs wrote:Hi Elchin,

First of all it's not my intention to make you doubt more and more

I never meant to say anything like that

Roel De Nijs wrote:
if you have a lockCookie, you just generate a unique value and the client/thread with this unique value is allowed to delete/update the record. It does not get any easier than that.
if you don't have a lockCookie, you need a way to identify your clients, because as you know (or should know) RMI does not guarantee that a request from the same client or handled by the same thread. So you need some mechanism to identify the client, because a record locked by a client, may only be updated/deleted by that specific client. So it is a bit more work to do (then just generating a lockCookie), but you can prevent a deadlock without any problem: you (can) know exactly how many records a specific client has already locked, so when it has already locked a record, you can block another record being locked by the same client (by throwing an IllegalStateException for example).

Isn't client authentication out of scope for Data class? I think in my version of assignment it is, since its methods have cookies, and they are meant to be the only tools for handling access.

Roel De Nijs wrote:
Your Data class could be abused if multiple records are locked by different clients in a specific order. So you'll have to add some comments (in javadoc and/or decisions document) to define proper use of the Data class (and so you give the accessor obvious indications you identified the possibility of deadlock, and you have thought about how to avoid it)

So in this case I will just leave it the way I have it now : clients can lock multiple entries, and I will document in my decision document why I made it this way, and how can it be changed if necessary (by extending Data class and adding the functionality there for example.)

Roel De Nijs wrote:
That's not the case for this assignment, so YAGNI. And if in near future this functionality is required, you will have to create some sort of "preventing deadlock"-mechanism.

I was telling this as an argument against implementing deadlock prevention, so indeed YANGI

Thanks for answers!

[Roel De Nijs]

Elchin Asgarli wrote:Isn't client authentication out of scope for Data class? I think in my version of assignment it is, since its methods have cookies, and they are meant to be the only tools for handling access.

When you have a cookie in your interface, it certainly is. because the cookie guarantees that the client which has locked the record, will be the one doing the update/delete. If you don't have a cookie in your interface (like me) you have to think of some way to identify your clients (due to the known RMI limitation, as described above). And because of this topic could be read by developers who have to implement an interface with and without lockCookie, I make the distinction between them.

indeed YANGI

It's YAGNI