aspose file tools*
The moose likes Developer Certification (SCJD/OCMJD) and the fly likes How does multiple calls to lock cause Deadlock? Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Certification » Developer Certification (SCJD/OCMJD)
Bookmark "How does multiple calls to lock cause Deadlock?" Watch "How does multiple calls to lock cause Deadlock?" New topic
Author

How does multiple calls to lock cause Deadlock?

Sean Keane
Ranch Hand

Joined: Nov 03, 2010
Posts: 581

It was mentioned in another thread that multiple calls to the lock-method can result in deadlock - but how can this happen?

Deadlock occurs when two processes each want a resource that the other process has a lock on. Thus they both sit there for eternity!

Here is a good description of deadlock:
This situation may be likened to two people who are drawing diagrams, with only one pencil and one ruler between them. If one person takes the pencil and the other takes the ruler, a deadlock occurs when the person with the pencil needs the ruler and the person with the ruler needs the pencil to finish his work with the ruler. Neither request can be satisfied, so a deadlock occurs.


So how does deadlock apply in the situation where someone makes multiple calls to the lock-method of the data class? Are people simply using incorrect terminology? Because I can't see how deadlock can occur?

This is the scenario based on my API that returns a cookie value:

1) Client-A calls lock(1) to lock Record-1 and receives back cookie value 999

- Client-A gets the lock as no other process has it locked.
- A cookie is generated to identify the request from Client-A
- The record and cookie value are stored in a Map of locked records.


2) Client-A calls lock(1) to lock Record-1

- This request is left waiting as Client-A already has locked Record-1.


3) Client-A carries out whatever operation it wanted to carry out from the first call to lock(1) e.g. update().

4) Client-A calls unlock(1, 999) to unlock it Record-1

- The Data class checks that Record-1 is locked by the client using cookie value 999, and it finds that it is.
- The Data class removes Record-1 from the Map of locked records.
- The Data class calls notifyAll()

5) The call to notifyAll() causing the second request by Client-A to check if Record-1 is available. It finds that Record-1 is available and it goes ahead and locks it.



So where exactly is the opportunity for deadlock here?


SCJP (1.4 | 5.0), OCJP (6.0), OCMJD
Jeff Philp
Greenhorn

Joined: Jun 04, 2011
Posts: 12
I suppose you might be referring to the thread I started here

I think I was probably using the wrong terminology in calling it deadlock.

You could however get deadlock in the following situation:

Imagine a client whom is single threaded making the following calls:
Client A: lock(1)
Client A: lock(1)

And if the lock method doesn't allow the same client to lock the record then doesn't this potentially lead to deadlock? if for example a client B also wanted the lock for record 1, but Client A never returned from the second call to lock?
Sean Keane
Ranch Hand

Joined: Nov 03, 2010
Posts: 581

Jeff Philp wrote:I suppose you might be referring to the thread I started here


Well your thread sparked my thinking Jeff. But people seem to consistently use the term deadlock on the forum when describing this scenario. So I was puzzled, because it doesn't seem like deadlock is possible to me, so maybe I was missing something .
Jeff Philp
Greenhorn

Joined: Jun 04, 2011
Posts: 12
Sean Keane wrote:
Well your thread sparked my thinking Jeff. But people seem to consistently use the term deadlock on the forum when describing this scenario. So I was puzzled, because it doesn't seem like deadlock is possible to me, so maybe I was missing something .


Sean you are right, the more I think about it its not deadlock. Because technically (in the simple example I proposed) client A is stuck on itself, and it just means that client B is stuck waiting for the Client A to release the lock which will never happen. Client A isn't waiting on client B to release a lock.

I don't know how you would correctly describe this situation, but its a potentially bad one none the less.
Sean Keane
Ranch Hand

Joined: Nov 03, 2010
Posts: 581

Jeff Philp wrote:technically (in the simple example I proposed) client A is stuck on itself, and it just means that client B is stuck waiting for the Client A to release the lock which will never happen. Client A isn't waiting on client B to release a lock.


But that is how locking works. If your process locks a shared resources, then every other process is stuck waiting until you unlock it. But this is not deadlock - it's just how locking works.

I don't see what is strange about this. I'm not even sure why you would want to guard against it - someone using your API should be aware that a call to the lock-method will not return until it gets the lock.

But then again, if you can guard against someone mis-using your API, then that is good thing as it reduces the chances for errors (due to misuse of API) and puts the point of failure right at the problem line of code.
Jeff Philp
Greenhorn

Joined: Jun 04, 2011
Posts: 12
Its not deadlock I agree, I just didn't know if other OCMJD candidates worried about such a situation. Its more protecting a programmer using the API against themselves.

I think the hardest thing with this assignment is determining the right amount of functionality to include, walking that fine line between too little, or too much.
Sean Keane
Ranch Hand

Joined: Nov 03, 2010
Posts: 581

Yep, I don't think it's deadlock. But many of the threads I've read refer to it as deadlock (for example here) and suggest commenting on this possible deadlock in your choices.txt. I think it's a good idea to comment on this scenario - but it may be a bit unwise to refer to it as deadlock, because to me it sounds like you don't understand what deadlock is.
Roel De Nijs
Bartender

Joined: Jul 19, 2004
Posts: 5599
    
  15

You could have this little scenario:
- clientA locks record 1
- clientB locks record 2
- clientA decides to lock record 2 (and is moved to waiting state)
- clientB decides to lock record 1 (and is moved to waiting state)

That's a deadlock to me, because 2 threads are waiting on each other.


SCJA, SCJP (1.4 | 5.0 | 6.0), SCJD
http://www.javaroe.be/
Sean Keane
Ranch Hand

Joined: Nov 03, 2010
Posts: 581

Roel De Nijs wrote:You could have this little scenario:
- clientA locks record 1
- clientB locks record 2
- clientA decides to lock record 2 (and is moved to waiting state)
- clientB decides to lock record 1 (and is moved to waiting state)

That's a deadlock to me, because 2 threads are waiting on each other.


That's a totally different scenario. But it's not deadlock either, because these two clients can be satisfied. Client A doesn't need record 1 and record 2 at the same time to perform an operation - that is the key point in deadlock.

I'm talking about multiple calls by a client to the lock method on the same record - without an unlock call in between. Most of the threads on here refer to the second call as being deadlocked - when it's not deadlocked.
Matthew Brown
Bartender

Joined: Apr 06, 2010
Posts: 4490
    
    8

I don't think the term used particularly matters. It might not be a strict deadlock, but "waiting for an event that cannot happen because I'm waiting for the event" seems to be close to the general meaning of the word. And a thread waiting for itself fits that description. You could think of it as a deadlock where the "two threads" are actually references to the same thread.

Either way, it's a potential problem. I've not read all the previous threads on this, so you've probably discussed this already, but I think you've got three general approaches.

- Ignore it. Calling lock twice is an error - let the calling code worry about the fact that it will freeze up.

- Write the lock method so that it throws an exception if the same thread tries to get a lock it already owns

- Write the lock method so that if a thread tries to get a lock it already owns it just returns immediately

I went for option 2.
Roel De Nijs
Bartender

Joined: Jul 19, 2004
Posts: 5599
    
  15

Sean Keane wrote:That's a totally different scenario.

Good catch, but according to your initial post "It was mentioned in another thread that multiple calls to the lock-method can result in deadlock - but how can this happen?", so I'll provide such a scenario.

Sean Keane wrote:it's not deadlock either

In my opinion that scenario causes a deadlock, because 2 threads are waiting for each other (to finish) and thus will keep waiting forever.

Sean Keane wrote:I'm talking about multiple calls by a client to the lock method on the same record

If I take Roberto's Data Test Class and I change the UpdatingRecord1Thread and add to calls to lock(1), the program will not finish (because the thread is waiting for itself to be able to finish)
Sean Keane
Ranch Hand

Joined: Nov 03, 2010
Posts: 581

Matthew Brown wrote:I don't think the term used particularly matters. It might not be a strict deadlock,


You still need to think about this problem so in that context it doesn't matter what you call it. But in terms of concurrent programming using a term like deadlock could be confusing as in my understanding it more describes the common referenced example of the dining philosophers.

Matthew Brown wrote:
Either way, it's a potential problem. I've not read all the previous threads on this, so you've probably discussed this already, but I think you've got three general approaches.

- Ignore it. Calling lock twice is an error - let the calling code worry about the fact that it will freeze up.

- Write the lock method so that it throws an exception if the same thread tries to get a lock it already owns

- Write the lock method so that if a thread tries to get a lock it already owns it just returns immediately

I went for option 2.


Did your lock method return a cookie? How did you go about implementing option (2) ?

I prefer option (2) or (3) - so I think I'd like to go with one of these or at least figure out what I'd need to do. My lock method returns a cookie.
Sean Keane
Ranch Hand

Joined: Nov 03, 2010
Posts: 581

Roel De Nijs wrote:In my opinion that scenario causes a deadlock, because 2 threads are waiting for each other (to finish) and thus will keep waiting forever.


The description you gave is not deadlock in your system. The reason being is that your system has no dependency between the two resources to carry out an operation. The two resources in your example are two records\rooms.

What you are describing is simply how locking works. If you lock a share resource, then yes, other threads will have to wait until you unlock it in order to access it. If you never unlock it, then of course they will have to wait forever. But this is not deadlock. Deadlock is a completely different problem.
Matthew Brown
Bartender

Joined: Apr 06, 2010
Posts: 4490
    
    8

Sean Keane wrote:Did your lock method return a cookie? How did you go about implementing option (2) ?

Yes, mine returned a cookie.

My lock mechanism involved creating a lock object (stored in a suitable collection). So I could use that to encapsulate whatever was necessary - in this case a reference to the owning Thread as well as the cookie.

(I also rather gratuitously used it to implement a timeout mechanism, but that's really not necessary)
Sean Keane
Ranch Hand

Joined: Nov 03, 2010
Posts: 581

Matthew Brown wrote:
Sean Keane wrote:Did your lock method return a cookie? How did you go about implementing option (2) ?

Yes, mine returned a cookie.

My lock mechanism involved creating a lock object (stored in a suitable collection). So I could use that to encapsulate whatever was necessary - in this case a reference to the owning Thread as well as the cookie.

(I also rather gratuitously used it to implement a timeout mechanism, but that's really not necessary)


So you mapped a record number to a lock object? Where the lock object contain the owning thread and the cookie, which were two different values?

Did you use RMI? If so, how did you identify the owning thread inside of your lock-method?
Roel De Nijs
Bartender

Joined: Jul 19, 2004
Posts: 5599
    
  15

Sean Keane wrote:But this is not deadlock. Deadlock is a completely different problem.

That all depends on the definition you have for a deadlock and on the internet you'll find plenty of them. Some mentioning some shared resource (also referenced as a Coffman deadlock), other ones don't.
Sean Keane
Ranch Hand

Joined: Nov 03, 2010
Posts: 581

Roel De Nijs wrote:
Sean Keane wrote:But this is not deadlock. Deadlock is a completely different problem.

That all depends on the definition you have for a deadlock.


Of course it depends on your definition or understanding of what deadlock means. I referenced the commonly understood definition of deadlock in concurrent programming - open to correction. So based on this definition the problem we are talking about here is not deadlock - it is simply how locking works.

Anyone can make up their own definition - but that just confuses things because the definition I referenced (and the example of the dining philosophers) would be the commonly understood meaning of deadlock.
Matthew Brown
Bartender

Joined: Apr 06, 2010
Posts: 4490
    
    8

Sean Keane wrote:So you mapped a record number to a lock object? Where the lock object contain the owning thread and the cookie, which were two different values?

That's right.

Sean Keane wrote:Did you use RMI? If so, how did you identify the owning thread inside of your lock-method?


I used RMI, but I was using a thin client. All the relevant lock/process/unlock calls were in a single method of my service interface, so the networking was irrelevant.
Sean Keane
Ranch Hand

Joined: Nov 03, 2010
Posts: 581

Matthew Brown wrote:
Sean Keane wrote:So you mapped a record number to a lock object? Where the lock object contain the owning thread and the cookie, which were two different values?

That's right.


Does that not make your cookie value redundant?

Matthew Brown wrote:I used RMI, but I was using a thin client. All the relevant lock/process/unlock calls were in a single method of my service interface, so the networking was irrelevant.


Cool. So did you adopt the use of the RMI Factory solution?

I currently have my Data class as a singleton. Then I have a business service that the client interacts with.

I took a quick read of the RMI Factory solution (need to look into more). But from what I could gather, you send back a separate instance of the Data class for every client? Is this correct? Which means I would have to not use the singleton. And I'm not quite sure how this will fit with my Business Service. Hmmm...
Roel De Nijs
Bartender

Joined: Jul 19, 2004
Posts: 5599
    
  15

I didn't use the RMI Factory, but I would think you expose a unique instance of your business service to each client. Why would you expose your Data class if you have a business service
Roel De Nijs
Bartender

Joined: Jul 19, 2004
Posts: 5599
    
  15

Sean Keane wrote:I referenced the commonly understood definition of deadlock in concurrent programming

I just referenced to the general definition of a deadlock (see the link in your 1st post)
Sean Keane
Ranch Hand

Joined: Nov 03, 2010
Posts: 581

Roel De Nijs wrote:I didn't use the RMI Factory, but I would think you expose a unique instance of your business service to each client. Why would you expose your Data class if you have a business service


Yeah, that is what I was wondering. I'm going to play around with the solution when I get a chance. Just wondering if someone who had implemented this had any info upfront.
Matthew Brown
Bartender

Joined: Apr 06, 2010
Posts: 4490
    
    8

Sean Keane wrote:Does that not make your cookie value redundant?


Probably, yes . One thing I was trying to do, though, was minimise the constraints my Data class imposed on the rest of the application, as the intention is that that is completely reusable, even in applications that are using a different strategy. It might not be incorrect for a different thread to do the unlocking in another application (though it would be in mine). I just know that it's an error for the same thread to lock twice.

Sean Keane wrote:I took a quick read of the RMI Factory solution (need to look into more). But from what I could gather, you send back a separate instance of the Data class for every client? Is this correct? Which means I would have to not use the singleton. And I'm not quite sure how this will fit with my Business Service. Hmmm...


I must admit, I'm not sure what the RMI Factory solution is. But my Data classes would never be exposed to the client. I could have safely returned a separate instance of the business interface to each client...but from memory I don't think I did. I think there was just one instance, which is stateless and unsynchronized. Multiple instances wouldn't break anything though - it doesn't rely on being a single instance like the Data class.

Sean Keane
Ranch Hand

Joined: Nov 03, 2010
Posts: 581

Roel De Nijs wrote:
Sean Keane wrote:I referenced the commonly understood definition of deadlock in concurrent programming

I just referenced to the general definition of a deadlock (see the link in your 1st post)


Yep, and I can't see anything on that page that contradicts my understanding and the description I gave of deadlock in concurrent programming.

Neither can I see anything that supports calling the scenarios we are talking about here as deadlock. Your system has no dependency between the two resources (rooms\records) to carry out an operation. All you are seeing here is your programming waiting...because that's how locking works. You can carry out the operations of both clients at any point and unlock if you so wish.
Roel De Nijs
Bartender

Joined: Jul 19, 2004
Posts: 5599
    
  15

Sean Keane wrote:Yep, and I can't see anything on that page that contradicts my understanding and the description I gave of deadlock in concurrent programming.

I had no intention at all to say your understanding / description was contradicting.

Sean Keane wrote:Neither can I see anything that supports calling the scenarios we are talking about here as deadlock. Your system has no dependency between the two resources (rooms\records) to carry out an operation. All you are seeing here is your programming waiting...because that's how locking works. You can carry out the operations of both clients at any point and unlock if you so wish.

That's the difference in our opinions. In my opinion you have 2 threads just waiting on each other. You don't need any dependency between 2 recources according to the general definition. And I don't see how you can carry out the operations, because you just have these 2 threads both in the waiting state (because they are waiting on each other) and to carry out any operation your thread should be in the running state. And that's not going to happen for those 2 threads.
Sean Keane
Ranch Hand

Joined: Nov 03, 2010
Posts: 581

Take our DB interface and the update method. Our system is meant to cater for the scenario where you (lock, update, unlock) all on a single record. There is no requirement or necessity for the system to lock more than one resource (i.e. more than one record). There is no operation in the system that requires two resources to be locked at the same time i.e. there is no operation in this system where you require the lock on more than one more in order to carry out the operation.

If you have locked two resources at the same time in our system then you have done something wrong in your implementation.

So back to your concrete example:

- clientA locks record 1
- clientB locks record 2
- clientA decides to lock record 2 (and is moved to waiting state)
- clientB decides to lock record 1 (and is moved to waiting state)


The solution to this is to always ensure that if you make a call to lock, then there is a corresponding call to unlock before any other call to lock on the same record. Problem solved.

I encountered this exact same problem with Robertos test case. I thought I had deadlock in my system. But I didn't. It's just the test case was not calling unlock in a finally block. So when an exception got thrown after I locked (but before unlocking) the record then remained locked forever. I resolved this not by any strategy to resolve deadlock, but by simply implementing it correctly
Roel De Nijs
Bartender

Joined: Jul 19, 2004
Posts: 5599
    
  15

Sean Keane wrote:I resolved this not by any strategy to resolve deadlock, but by simply implementing it correctly

Is implementing it correctly not a strategy to prevent (resolve) deadlock. Just like you should always lock resources in the same order when you need locks on multiple resources (like shown here).
Sean Keane
Ranch Hand

Joined: Nov 03, 2010
Posts: 581

The key point is that the way the system is required to function in this assignment means you couldn't have deadlock i.e. you must lock before operating on Data class and unlock afterwards, all on a single resource. This means that you simply cannot have deadlock in the system.

The example you referenced is a classic example of where a system functions where you could have deadlock depending on how the system is implemented. Why could you have deadlock in the system? Because the operation being carried out requires a process to have access to more than one shared resource - this is where your implementation would have to be aware of solutions that avoid a deadlock scenario or have a means of getting out of such a scenario.

The key point in our system is that no operation requires a process to have access to more than one shared resource at the same time in order to carry out an operation.
Alex Iordanoglou
Greenhorn

Joined: Oct 21, 2004
Posts: 6
Hi Sean,
Just a tiny bit of clarification - confirmation: in your first post, in cases 2) and 5), instead of Client-A, did you really mean to say Client-B?
(Because if not, Client-A would be waiting forever upon himself to finish - release the lock as stated previously etc ect...)
Sean Keane
Ranch Hand

Joined: Nov 03, 2010
Posts: 581

Alex Iordanoglou wrote:Hi Sean,
Just a tiny bit of clarification - confirmation: in your first post, in cases 2) and 5), instead of Client-A, did you really mean to say Client-B?
(Because if not, Client-A would be waiting forever upon himself to finish - release the lock as stated previously etc ect...)


Hi Alex. Nope I meant Client-A in both cases. One of the scenarios people mentioned that they handled was the scenario what a client makes two individual calls to the lock-method one after another. Obviously the second call would, as you mentioned, cause the client to wait forever.
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: How does multiple calls to lock cause Deadlock?