Lock question!

[Satish Avadhanam]

Hi George, first thanks for the reply.

Originally posted by George Marinkovich:
Hi Satish,
What is it in your application design that you think might lead to a deadlock situation?

I do not see anything in the application that causes a deadlock. There are very few synchronized blocks(4-5) in the total Data class and all are synchronizing on the existingRecords(ArrayList) only and two other synchronized blocks which synchronize on the deletedRecords(ArrayList). That is it. No methods are synchronized. And yeah, I got blocks synchronized on lockedRecords in lock and unlock methods.
Note: There are no synchronized(hmmm...what do we call them?) inner blocks or OK. I give up..I will show it.

synchronized(A) {
    synchronized(B) {
    }
}
synchronized(B) {
    synchronized(A) {
    }
}

There are no blocks like either of them. Do you think its fine?

1) A data access system that provides record locking and a flexible search mechanism.
I provided this two. Am doing record locking and also provided search mechanism for name/location/all(As you suggested, I thought and removed "searchAll" button and allowed to search all using the search button with no field/combo select values.).
2)Your server must be capable of handling multiple concurrent requests, and as part of this capability, must provide locking functionality as specified in the interface provided above.
It seems to be working well George, but I don't know how good it is
3)Locking (80 points)
Yeah, definetely worried about this.
George, I got a couple of questions regarding testing. I'm not aware of any tools like JUnit or others. Can you please guide me which one to use? Or is it ok if we test it on the grounds of Max's testing? I mean like his test programs.
Thanks.

[George Marinkovich]

Hi Satish,

Originally posted by Satish Avadhanam:


I think you meant to say you don't have any nested synchronized blocks like those in the example you gave, right?

synchronized(A) {
    synchronized(B) {
    }
}
synchronized(B) {
    synchronized(A) {
    }
}

There are no blocks like either of them. Do you think its fine?

That sounds good but it wouldn't necessarily be so obvious. I would suggest you sit down with your code and trace what happens during a book operation, paying particular attention to when you enter a synchronized block and when you exit a synchronized block. For example, the first thing I do in a book operation is call lock(). The lock method enters a block synchronized on whatever and then it leaves the block. Then read is called. The read method enters a block synchronized on whatever and then it calls another method. This other method enters a block synchronized on something, etc. If you find that you're never entering nested synchronized blocks the you less to worry about than if you were using nested blocks.

George, I got a couple of questions regarding testing. I'm not aware of any tools like JUnit or others. Can you please guide me which one to use? Or is it ok if we test it on the grounds of Max's testing? I mean like his test programs.

Well JUnit is worth learning just for the sake of your future Java work, but you don't need to use it for this project if you don't have the time to learn it now. Yes, Max's testing harness is a very good starting point for you to develop your own multi-threaded test harness. If you want to take a look at the one I based on Max's testing harness you can look here:Topic: All of URLy Bird 1.1.3 about Junit test

Basically, you can take a two-pronged approach to discovering deadlock in your application. You can trace the code logic looking for lock nesting and other possible problems, and you can test it in a multithreaded environment and hope the application fails the test. If the application fails the test then you can figure out what's going wrong, fix it, and see if the test works correctly. If the test succeeds then you can feel pretty good that you don't have deadlock lurking in your application. Of course, it doesn't prove that you don't have deadlock, but at least if it was difficult for you to find you can hope it will be as difficult for the examiner to find.

[Satish Avadhanam]

Thanks George. I already looked at the thread you pointed and also am using the code you shown for testing. Thanks for that.
Will try to learn and do the testing using JUnit. Thanks.

[Philippe Maquet]

Hi Satish,
1. Am not dealing with dead locks.

George:
Seriously, I think a locking functionality that permits deadlock is inherently a seriously flawed implementation and you can expect to lose points if your implementation allows this to happen.

Even if most people here (AFAIK) think that dealing with deadlocks is overkill, I fully agree with George.
Anyway, it cannot hurt if you do it, I think.
I basicaly see 4 solutions in that area:
1. What you are doing now: any client cannot own more than one lock at a time. Deadlocks are impossible, obviously.
2. Allowing multiple locks per client, but publish a locking contract (in your Javadoc) that requires from clients that multiple locks are claimed in some specific order (ascending on recNo for instance). And you don't enforces the contract by code (the only thing you do is writing 2 sentences in your Data javadoc.
3. Same as 2, but with that contract enforced.
4. Data (or LockManager if you have one) detects deadlocks when they occur, and breaks a dealock by choosing a "looser" (typically the client who is claiming the new lock).
Critiques:
1. No dealock, but only "thanks" to a huge restriction in the use of the DBAccess interface as documented (OK poorly) by SUN, and I think such a restriction is not acceptable.
2. The easier solution. And as I think that's what Ken did (and he got a perfect locking score) it is advisable I think.
3. Comparable to 2, with more work . Besides, - and you'll probably find it weird - but 2 is better then 3 (IMO). OOH, forcing clients to get locks in some predefined order is also a restriction in the use of the DBAccess interface as documented by SUN, and OTOH dealocks are rare. In other words, let's say that your LockManager class detects that a client doesn't respect the contract and throws some RuntimeException. You prevent a potential deadlock which is very improbable anyway. And you prevent clients which simply code to the DBAccess interface (ignoring completely your Data implementation and its locking contract) to work at all.
4. The best solution IMO. No restriction on the use of the interface and deadlocks are broken in case they occur. BTW, 4 is not incompatible with 2.
2. Am not dealing with crashed clients.
I also agree with George here, though it's so easy to handle (much easier than deadlock detection anyway), that it could be worthy to do it.
Regards,
Phil.

[Satish Avadhanam]

Hi Phil, I thought you will not read my posts after asking you sooooooo many questions
Actually been testing the application regarding locking issues and found out that there are a couple of dead lock situations. Working from quite sometime, still could'nt resolve Somebody please help me out...no no. Still working, hoping to resolve them soon.

Originally posted by Philippe Maquet:
Hi Satish,
Even if most people here (AFAIK) think that dealing with deadlocks is overkill, I fully agree with George.
Anyway, it cannot hurt if you do it, I think.

Yes Phil, I too thought the same after Geroge and you said, working on it now.

I basicaly see 4 solutions in that area:
1. What you are doing now: any client cannot own more than one lock at a time. Deadlocks are impossible, obviously.

This is my case, but still have some dead lock cases. Please see at the bottom.

2 & 3

For now, I think I will stick to condition -- each client cannot own more than one lock.

4. Data (or LockManager if you have one) detects deadlocks when they occur, and breaks a dealock by choosing a "looser" (typically the client who is claiming the new lock).

In my situation deadlocks are occuring for a different reason. Will detail below.

Critiques:
1. No dealock, but only "thanks" to a huge restriction in the use of the DBAccess interface as documented (OK poorly) by SUN, and I think such a restriction is not acceptable.

Phil, please tell that my locking mechanism has atleast one good/better quality

2. The easier solution. And as I think that's what Ken did (and he got a perfect locking score) it is advisable I think.

Phil, are you saying that Ken allowed mulitple locks? I could'nt see that in his design. I have gone through Ken's locking again and will deatail it below.

3. Comparable to 2, with more work

It seems that you don't want me to complete assignment soon ...Just kidding.

4. The best solution IMO. No restriction on the use of the interface and deadlocks are broken in case they occur. BTW, 4 is not incompatible with 2.

Maybe I will end up with this only Phil. I don't know. First I did'nt have any lock manager, locking is taken care in lock/unlock. Now, lock manager is added...and still issues. Will look at some more past posts on lock manager to get a good idea.

2. Am not dealing with crashed clients.
I also agree with George here, though it's so easy to handle (much easier than deadlock detection anyway), that it could be worthy to do it.

I have gone through some posts regarding this issue, but could'nt figure out exactly how to do. So will spend some more time reading and try to implement this also. I think WeakHashMap is one option. Am I right?

Regards,
Phil.

Here is quote from Ken's locking mechanism: I am editing it as point wise so that it will be easy to discuss.

Locking
======
1. The implementation of the Services book method in ServicesImpl is the only user of the locking API.

2. I specified a contract in the Javadoc that calls for any potential users of the locking API to invoke lock/process/unlock as a sequence within the context of a single method call which guarantees it will happen within a single thread of execution.
3. When lock is invoked, a check is made to see if the Contractor already has been locked by another thread.
4. If it has, the current thread will wait until notified that it has been unlocked.
5. If not, a Lock object is created that has a reference to the current thread and it is put in the locking Map with the Contractor as the key.
6. The protected processing operation is performed and then the Lock is removed from the Map and destoyed by the unlock method call.
7. It is vital that any exception that occurs during processing is caught and rethrown after the Contractor has been unlocked.
8. Deadlock is prevented by specifying a locking order to be used by programmers.

Here's mine...it almost looks same.

1. CSRDataAdapter is the only user of locking mechanism. To be precise, only the book method uses the locking functionality here. Am providing only two methods in CSRDataAdapter -- book & find.
2. He also specified a contract. But you were saying that he did'nt mentioned any in your 2'nd point, right?
3. Same as 3 above.
4. Same as 4 above.
5. Instead of using the reference am using the Random.nextLong(). I think you know who gave this advice
6. In unlock, it will be removed.
7. I think am stuck here with dead lock problem. Will explain below.
8. Will provide a locking order to follow, but I have to deal with 7.

The issue in my design is like this:
1. Suppose update method has locked the record say.
2. In update I again check whether the record is present or not, if not throw RNFE.
3. The problem is the thread did'nt unlock record 100 and so other threads will be waiting like that.
4. Result deadlock
I am working on this and hoping to solve this issue soon
Any comments on locking mechanism in general other than deadlock issue? Thanks.

[Javini Javono]

Hi,
In general, and keeping in mind that I don't know yet that my
code is free of dead-locks, I'd give the hint that update()
need not call lock() and unlock() at all.
The client is the one who uses lock() and unlock(). The only
exception to this rule is during the "create in place" operation,
wherein your method would, if it decides to implement
"creation in place," would need to grab a lock.
As far as JUnit; it's not that hard to learn. Right now I'm organizing
my tests, that is, outlining what tests I've done so far, so I can then
think about what tests need yet to be written. The power of JUnit
is that I can change my implementation, and in 5 to 10 seconds
verify that everything still works as before.
There is no doubt that JUnit testing adds time; for instance, I've had
to re-organize my tests once (actually, I'm not done with this re-organization).
For instance, I've had to re-organize them to fit into a new paradigm
where the database can be re-initialized appropriately, and to set
the primary key and the immutable key on the fly, and the like; but,
this is good, for it forces another design work job: getting these objects
that create the database coordinated (gradually).
I can sleep better knowing that my system is testable. But, in so doing it,
I explore the requirements and an ready for future enhancements. I can also
create very specific tests. And, when you think about "what JUnit tests
come next," you are implicitly deciding whether or not you want or need
that functionality.
All in all, JUnit is a plus for any real world project. For instance, for this
project specifically, I know, in advance, that I will have to refactor the
database, server-side functionality; and, I don't plan on retesting everything
by hand.
Finally, I've found JUnit particularly helpful in that writing databases is not
something I have done before. JUnit allows me to be the user, and allows me
to see flaws in my conceptual knowledge and how I will change the design
to meet them (for instance, what does it mean, if anything, to call data.isLocked
on a deleted record).
Thanks,
Javini Javono
[ March 19, 2004: Message edited by: Javini Javono ]

[Don Wood]

Javini,

In general, and keeping in mind that I don't know yet that my
code is free of dead-locks, I'd give the hint that update()
need not call lock() and unlock() at all.

Sounds risky at the very least.
So if you are not locking the record on update, how do you know:

that no other client has modified the record,

that no other client has deleted the record,

that no other client has deleted the record and added a new record back into the same slot.

It seems likely that you will have one thread destroy changes that another thread has made. This is not a dead lock issue, it is an issue of how do you keep the data consistent?
And if you have a magic bullet that allows updates without locking, are you confident that you can convince the reviewer that a lock-less update is thread safe? If the reviewer is not convinced, your locking score will suffer.
[ March 19, 2004: Message edited by: Don Wood ]

[Satish Avadhanam]

Hi Javini, Good to see you participate here

Originally posted by Javini Javono:
Hi,
In general, and keeping in mind that I don't know yet that my
code is free of dead-locks, I'd give the hint that update()
need not call lock() and unlock() at all.

How did you came to this conclusion? I mean, the instructions clearly state:

// Modifies the fields of a record. The new value for field n
// appears in data[n]. Throws SecurityException
// if the record is locked with a cookie other than lockCookie.

Don't you think we need to use the protocol of lock/doSomething/unlock here?

The client is the one who uses lock() and unlock().

Do you mean CSR here? Am using server side locking and all locking is in adapter class only.

Thanks,
Javini Javono
[ March 19, 2004: Message edited by: Javini Javono ]

Finally, thanks somuch for sharing your views on JUnit. Will try to learn and test in it. But I was worrying about the time limit...its already way getting late :roll:

[Philippe Maquet]

Hi Don and Satish,
I think that when Javin writes

I'd give the hint that update()
need not call lock() and unlock() at all.

he means that lock() and unlock() shouldn't be called *from* update(). And that's right.

"creation in place," would need to grab a lock.

It depends on your design. I didn't need it for instance.

The client is the one who uses lock() and unlock().
Do you mean CSR here? Am using server side locking and all locking is in adapter class only.

Not the CSR but any object which is garanteed to be unique per client. BTW do you have one Data instance per client in your design?
Regards,
Phil.

[Satish Avadhanam]

Originally posted by Philippe Maquet:
Hi Don and Satish,
he means that lock() and unlock() shouldn't be called *from* update(). And that's right.

Oh! Then its ok.

Not the CSR but any object which is garanteed to be unique per client. BTW do you have one Data instance per client in your design?

Yep, am having one instance per client. No static RAF.

Regards,
Phil.

And Phil, no comments on my locking design mentioned in the previous post above? Is it that good or that bad

[Philippe Maquet]

Oops! I missed it, sorry.
I'll read it now and reply a little later.

[Satish Avadhanam]

Originally posted by Philippe Maquet:
Oops! I missed it, sorry.
I'll read it now and reply a little later.

Thanks Phil. Also, its time for me to sleep

[Philippe Maquet]

Hi Satish,
I didn't study Ken's locking design in detail (and there is not enough information in his post to do it BTW).
I just remembered what you mention as point 8:

8. Deadlock is prevented by specifying a locking order to be used by programmers

But it looks like that contradicts point 5:

5. If not, a Lock object is created that has a reference to the current thread and it is put in the locking Map with the Contractor as the key.

Indeed, if the key is not the recNo, how could a given client own more than one lock?
Good catch of you!

5. Instead of using the reference am using the Random.nextLong(). I think you know who gave this advice

I wonder if you don't mix two concepts. The reference to the current thread Ken is talking about is probably used to handle crashed clients. While your Random.nextLong() concern cookies.
Now your questions:

About the crashed clients detection:
I have gone through some posts regarding this issue, but could'nt figure out exactly how to do. So will spend some more time reading and try to implement this also. I think WeakHashMap is one option. Am I right?

It's one option indeed. And I remember that I wrote a thread on that topic: see here.

The issue in my design is like this:
1. Suppose update method has locked the record say.
2. In update I again check whether the record is present or not, if not throw RNFE.
3. The problem is the thread did'nt unlock record 100 and so other threads will be waiting like that.
4. Result deadlock

Does lockRecord() throw RecordNotFoundException like in my instructions?
If it's the case, I don't understand how the issue you mention could happen, because as delete() cannot execute without a lock, it's impossible that a record is deleted by another thread in the middle of a lock() - update() sequence.
Now if it's not the case, let me know and we could see how to solve it.
Regards,
Phil.
[ March 20, 2004: Message edited by: Philippe Maquet ]

[Satish Avadhanam]

Hey Phil, sorry for the late reply.

Originally posted by Philippe Maquet:
Hi Satish,
Does lockRecord() throw RecordNotFoundException like in my instructions?

Yes.

If it's the case, I don't understand how the issue you mention could happen, because as delete() cannot execute without a lock, it's impossible that a record is deleted by another thread in the middle of a lock() - update() sequence.

I think I did not explain the problem correctly. How exactly locking works is as deatailed below.

Now if it's not the case, let me know and we could see how to solve it.
Regards,
Phil.
[ March 20, 2004: Message edited by: Philippe Maquet ]

Phil, here is the protocol for update/delete methods in adapter.

cookie = lock(recNo);
data.update(recNo, cookie) or data.delete(recNo, cookie);
data.unlock(recNo, cookie);

As I was testing for multiple clients, here's one scenario. BTW, the above sequence is called in try catch block in adapter.
Suppose T1, T2, T3 are the threads.
T1 wants to delete record 100.
T2 wants to delete record 100.
T3 wants to update record 100.
T1 locks the record.
T2 sees that the record is locked and waits.
T3 also waits to lock the record.
T1 deletes the record.
T1 notifies.
T2/T3 tries locks the record(Not existing).
In update/delete methods they throw RNFE.
So because of this, unlock is not called in the adapter(Poor design )
The result was deadlock.
I changed it now. Whenever an exception occurs in delete/update then in the catch block in adapter am also calling the unlock. So now if any exception occurs also, its working properly without any deadlocks for now Still testing though
Do you think that's it not a good idea of unlocking in the above manner. Actually thought of another option which would unlock right away in delete/update if RNFE occurs.
Phil, the thread you pointed out, does it really talk about locking mechanism? Frankly I could not understand anything over there other than your first post with the lock manager code comparision and that is what is required Thanks for that. I think the post you referred is mostly talking about efficiency on which collection class to use.
Am going through the idea of using lockmanager like you showed, but still Lots of things to understand in there. Will try and post any questions if I have any. Thanks once again.

[Satish Avadhanam]

Hi Phil

Originally posted by Philippe Maquet:
Hi Satish,
Indeed, if the key is not the recNo, how could a given client own more than one lock?
Good catch of you!

No no, the key is the recNo only Phil. And clients cannot own multiple locks in my design.

Regards,
Phil.
[ March 20, 2004: Message edited by: Philippe Maquet ]

[Satish Avadhanam]

Hi Phil

Originally posted by Philippe Maquet:
Hi Satish,
Indeed, if the key is not the recNo, how could a given client own more than one lock?
Good catch of you!

No no, the key is the recNo only Phil. And clients cannot own multiple locks in my design.

Regards,
Phil.
[ March 20, 2004: Message edited by: Philippe Maquet ]

[Philippe Maquet]

Hi Satish,

As I was testing for multiple clients, here's one scenario. BTW, the above sequence is called in try catch block in adapter.
Suppose T1, T2, T3 are the threads.
T1 wants to delete record 100.
T2 wants to delete record 100.
T3 wants to update record 100.
T1 locks the record.
T2 sees that the record is locked and waits.
T3 also waits to lock the record.
T1 deletes the record.
T1 notifies.
T2/T3 tries locks the record(Not existing).
In update/delete methods they throw RNFE.
So because of this, unlock is not called in the adapter(Poor design )
The result was deadlock.

1. "In update/delete methods they throw RNFE."
Why, as lockRecord() is not called *from* update/delete?
2. "So because of this, unlock is not called in the adapter"
Why should unlock() be called as no lock was grabbed?
I wonder whether your issue doesn't come from a bad implementation of lock(). lock() throws RecordNotFoundException in case the record doesn't exist or recNo is invalid. But of course, if the case happens, lock() *SHOULD NOT* grab the logical lock on the record. In other words, when lock() throws RNFE and does its job correctly, you shouldn't need any unlock() call.
Does it make sense?

Phil, the thread you pointed out, does it really talk about locking mechanism? Frankly I could not understand anything over there other than your first post with the lock manager code comparision and that is what is required Thanks for that. I think the post you referred is mostly talking about efficiency on which collection class to use.

It's not the thread I've been the luckiest with...

Am going through the idea of using lockmanager like you showed, but still Lots of things to understand in there. Will try and post any questions if I have any.

You're welcome to do! You may even reopen that thread if you like, so there will be at least 2 posts dedicated to locking within in.
Best regards,
Phil.
[ March 21, 2004: Message edited by: Philippe Maquet ]

[Satish Avadhanam]

Hi Phil, I think it is because of me not expressing exactly what am doing in the locking. Will try to post the pseudo-code.
The following is the locking code:
Note to Andrew/Mark: This is not a working code. Its just a pseudo-code for discussion. Thanks.

public long lock(long recNo) throws RNFE{
//Test if the recNo is present, if not throw RNFE
//synchronize on lockedRecords
    synchronized (lockedRecords) {
//check if the record is already locked. If its already locked then wait on
// the locked object itself
      if (lockedRecords.containsKey(recNo)) {
//As the record is locked, we can synchronize on the object, else it gives
//NullPointerException. The if statement is present for that reason
         synchronized (lockedRecords.get(recNo)) {
//while the record is already locked, wait on the record itself, instead of
// waiting on the lockedRecords HashMap. Therefore in the unlock method, I
// can [B]notify[/B] on the object itself. I believe this satisfies the 
//statement, [B]don't waste CPU cycles while the record is locked[/B]
            while(lockedRecords.containsKey(recNo)) {
       lockedRecords.get(recNo).wait();
    }
// The reason to check here whether the record is present or not is simple
//While a "update" thread is waiting for lock, while the "delete" thread 
// locked, then the 'delete" thread will delete the record. Therefore the 
// check to see if the record is present
         if(!existingRecords.contains(recNo))   {
    throw new RecordNotFoundException();
         }
//If the record is present, the lock the record
         lockedRecords.put(recNo, cookie);
//This else corresponds to the first if above. When the record is not 
// locked, the if statement returns false. So the record is locked here.
      } else {
         lockedRecords.put(recNo, cookie);
      }
   }
   return cookie;
}

Unlock code:

public void unlock(recNo, cookie) throws SecurityException{
//Checks for SecurityException here
//Obtain lock on lockedRecords
   synchronized(lockedRecords.get(recNo)) {
      lockedRecords.get(recNo).notify();
      lockedRecords.remove(recNo);
   }
}

Actually this is what I want to do in the locking, to wait on the record itself instead of on the lockedRecords HashMap. But as there are a couple of issues in this which I could'nt resolve now changed the implementation to where it waits on the lockedRecords itself and notifies on lockedRecords. The reason why don't want to do like to wait on lockedRecords is that, in unlock if you notify on lockedRecords then all the threads gets notified. Say if the record 100, 200 and 300 are locked, then if you notify on lockedRecords in unlock that record 100 is removed from lockedRecords and is available to obtain a lock, then all the threads which are waiting on records 200, 300 are also notified only to again wait. If I wait on the record itself as shown in the code, then I can notify on the record itself instead of lockedRecords.
Do you think the idea sounds right? If you think there might be a chance of working this out, then I have a couple of issues to discuss. Or you want to say, "Satish, enough of your doubts, lets cut it out now"? In that case will stick with current lockedRecords solution only(i.e. waiting & notifying on lockedRecords).
Thanks.

[Don Wood]

Hi Satish,
The pseudocode for locking seems to have some serious issues.
Firstly, the code uses nested synchronized blocks. The literature that I have seen says, if your design has nested synchronized blocks then you are doing something wrong and you should redesign it.
Secondly, the code is sleeping in the inner synchronized block which means the thread is still holding the outer lock. Sleeping while holding a lock pretty much a no-no in any application. But in this case things are worse yet. The outer synchronized block holds the lock to lockedRecords! No other thread can get or release record locks including the thread that is holding the record lock you are waiting on. In other words, the first time you have contention on a record lock, the application will deadlock.
I like the goal of waking up only the threads that are waiting for the specific record lock being released. I haven't started on the locking code yet but you definitely have me thinking about it.
[ March 22, 2004: Message edited by: Don Wood ]

[Satish Avadhanam]

Hi Don, Thanks for the reply. The issues you mentioned are the issues that I want't do discuss. The reason why I did'nt post them before-hand is to let know whether this solution is possible or not. If anyone responds then I thought of posting the issues and you spotted them.
The main concern which am worried about is:

When the thread waits on the object itself in the second synchronized block, it is taking away the lock on lockedRecords(outer synchronized object) with it. But if I don't use the outer synchronized block, then I cannot make sure that only one thread is testing the if/else statement. I cannot wait on two objects, is'nt it? So I was thinking about this problem for so much time and could'nt come up with a solution

I think the application actually does "record-locking", if the above issue is solved. I think waiting on lockedRecords and notifying does'nt exactly do record locking as non-interested threads are also notified(But it seems that I may have to stick with this only ).
Guys, any arguments about the design? Or anyone thinking to say "Satish, you are out of your mind. This does'nt work"?

[Andrew Monkhouse]

Hi Satish,
I agree with Don: having the nested synchronized code is a big mistake. I suspect you haven't tested this in a scenario where multiple threads are waiting for the same record - you will probably find that not only will they never wake up, but it will stop your entire server from processing any other records.
(By the way - I recommend you set up such a test now, and prove to yourself that there is a problem. Then when you fix it, you will have a test to prove you have fixed it. )
Most candidates do not seem to go to this level of adherence to the specification - they simply allow threads to wake up whenever any lock is released. But it is possible to have a thread only wake up when the lock it is interested in is released, and you are nearly there.
Hint: At present you are using the contents of lockedRecords as a marker for whether a record is locked or not. You are not using the contents for any other purpose. If the contents were some mutable object, then it would not have to be destroyed each time you unlock a record - just change it's contents. Can you think of whether that might help you?
Regards, Andrew

[Philippe Maquet]

Hi Satish,
Sorry to be unable to pursue our interesting discussion about locking. I won't be able to follow this thread before thursday (it wouldn't be reasonable for compelling professional reasons ) , but I'll come back soon.
Regards,
Phil.
[ March 23, 2004: Message edited by: Philippe Maquet ]

[Satish Avadhanam]

Hi Andrew,

Originally posted by Andrew Monkhouse:
Hi Satish,
I agree with Don: having the nested synchronized code is a big mistake. I suspect you haven't tested this in a scenario where multiple threads are waiting for the same record - you will probably find that not only will they never wake up, but it will stop your entire server from processing any other records.

This was the reason I was worried about at first in this design.

(By the way - I recommend you set up such a test now, and prove to yourself that there is a problem. Then when you fix it, you will have a test to prove you have fixed it. )

Thanks for the tip Andrew. Will do maximum stress testing then.

Most candidates do not seem to go to this level of adherence to the specification - they simply allow threads to wake up whenever any lock is released. But it is possible to have a thread only wake up when the lock it is interested in is released, and you are nearly there.

I am particulary worried about the locing scores of 44/80. That is why I was trying to make it do exaclty record matching.

Hint: At present you are using the contents of lockedRecords as a marker for whether a record is locked or not. You are not using the contents for any other purpose. If the contents were some mutable object, then it would not have to be destroyed each time you unlock a record - just change it's contents. Can you think of whether that might help you?
Regards, Andrew

One good thing: Was able to do record locking today. And only "notify"'s when that particular record lock is released. Its working well till now
Actually, am getting an idea of the approach you mentioned in the Hint above, but I am not sure whether my approach in the same as what you were saying.
One question Andrew: In the above Hint you mentioned, is it "mutable object" or "Immutable object" you were saying?
Thanks.

[Satish Avadhanam]

Hi Phil

Originally posted by Philippe Maquet:
Hi Satish,
Sorry to be unable to pursue our interesting discussion about locking. I won't be able to follow this thread before thursday (it wouldn't be reasonable for compelling professional reasons ) , but I'll come back soon.
Regards,
Phil.
[ March 23, 2004: Message edited by: Philippe Maquet ]

It seems that I worked it out and I think am now able to do record locking and notifying on only the threads waiting on a record. Feels a bit happy for now Don't know if it works like this till I submit Will be testing for some more time. Once you are back we can discuss further. Looking forward to Thursday :roll: Thanks.
[ March 24, 2004: Message edited by: Satish Avadhanam ]

[Andrew Monkhouse]

Hi Satish

One question Andrew: In the above Hint you mentioned, is it "mutable object" or "Immutable object" you were saying?

I would recommend a mutable object (one whose contents can change without replacing the object).
Regards, Andrew

[Javini Javono]

Hi,
Don Wood said:

Firstly, the code uses nested synchronized blocks. The literature that I have seen says,
if your design has nested synchronized blocks then you are doing something wrong
and you should redesign it.

The above comment didn't apply to my code or design; but, it motivates to ask a question.
How fixed is this rule? In my synchronized MicroData.create() method, when I create a
new record which over-writes an inactive (i.e., deleted) record, the create() method carries
out these steps:
1. Gets a lock on the LockManager.
2. Gets a lock on MicroData.
3. Then carries out its processing:
a. Request that the record number to become "undeleted" be locked.
b. Write to this record making it a new record with new contents.
c. Unlock this new record.
Before the processing steps can be carried out, it's essential that
the LockManager and then MicroData are locked (in that order),
for LockManager has methods which call back into MicroData. Without
this double synchronized lock, there would be a dead-lock (because other
threads would attempt to lock LockManager, try to gain a lock on MicroData,
but another thread held MicroData waiting for a lock on LockManager).
Dead-locks are avoided by following the locking order rules: always
lock LockManager, then lock MicroData.
By the way, MicroData is the low level class which reads and writes to
the database file, and it is called from Data. All of MicroData's methods
are synchronized (though later I will refactor so that not all portions
of each method are synchronized to increase concurrency.
The design seems simple enough; it just happens that MicroData.create()
becomes a client needing to use the lock manager, and then needing to
call back into another method in it's class. Usually, of course, clients are
operating outside of MicroData, first using the lock manager, then calling
Data.someMethod() which in turn calls the appropriate methods in MicroData.
Given that the design is simple enough if I specify the locking order rules,
it seems acceptable to me. However, I am open to other design ideas on
this topic.
Thanks,
Javini Javono

[Don Wood]

Hi Javini,
Whenever you are dealing with nested locks, you must always get them in the same order. Apparently, know this as you said the following:

Dead-locks are avoided by following the locking order rules: always
lock LockManager, then lock MicroData.

Since you are using nested locks correctly (always in the same order) you are using one of the classic deadlock avoidance mechanisms. You still have several issues to be evaluated.

[list]Is the flow of code obvious enough that a junior programmer will not miss the significance of lock ordering? If I understand the code right, you have nested locks that are acquired in different methods. This is much harder for anyone (much less a junior programmer) to pick up on than if both synchronized blocks were in one method.

What happens to the concurrency when the inner lock is not available? The thread goes to sleep still owning the outer lock. The sleeping thread can block other threads from doing any useful work and things come to a screeching halt until the locks are cleared.

When you say in step 1, Gets a lock on the LockManager., does this mean a lock on the LockManager object? If so, when the inner lock is busy, then the thread goes to sleep owning the LockManager lock. I don't see how the thread that wants to release the inner lock will be able to do so since the LockManager is locked and the owner is asleep. This can't be right so I must not be understanding what the LockManager lock is.
Perhaps its just my reading of this that is faulty but when you say

Usually, of course, clients are
operating outside of MicroData, first using the lock manager, then calling
Data.someMethod() which in turn calls the appropriate methods in MicroData.

Do you mean that the clients have the lock manager locked when they call MicroData? If so, it seems that you can be holding the lock manager lock for duration of doing I/O. That would seem like the system is overlocking and concurrency is reduced.
The alternative interpretation that I see is that the clients use the lock manager and release its lock before calling Data.someMethod() which in turn calls the appropriate methods in MicroData. But since MicroData can then call the LockManager that would be a violation of your contract that says the locks are always locked in the same order.
Nested locks can be used in a deadlock safe manner. However, when you do use them you have to answer a lot of questions. Does it truly avoid deadlock? What are the performance implications, especially when the thread goes to sleep holding the outer lock while waiting for the inner lock to become free? How hard is it for someone else maintaing the code to understand the nested locks?
My understanding of the avoid nested locks rule, is that it can be done but it will probably save you time and a lot of headaches to redesign the code to avoid nested locks.
[ March 24, 2004: Message edited by: Don Wood ]

[Satish Avadhanam]

Hi Don

Originally posted by Don Wood:
Hi Javini,
especially when the thread goes to sleep holding the outer lock while waiting for the inner lock to become free?

Yeah this is a real issue as you cannot wait on two objects. So as long as you wait on the inner object, you obvioulsy are taking the lock of outer object with you. I'm just wondering is there anyway of "wait"ing on two objects? I mean to realease locks on both outer and inner objects. I could'nt think of a way of doing this. Threading Gurus have to shed some light on this issue

[ March 24, 2004: Message edited by: Don Wood ]

[Satish Avadhanam]

Hello again, Guys
I think I got lost few steps to cross the barrier from "still doing" to "completed". Please help me cross it. Thanks
I have seen and got the idea of a maitainance thread running while the server is up and doing the "unlocking" thing if any clients crashes. Lets put my understanding here so that you can comment. One thread will be running always and checks every 10 seconds or so whether the number of the records locked, say lockCount(say a variable holding the count) is equal to the number of records present in the lockedRecords map. If they are not equal, notifyAll on the lockedRecords map or if you're using lockManager, notifyAll on it. This only works if you are waiting on the lockManager or lockedRecords. Now if you are waiting on the "record", its a different issue. Now suppose if lockCount is not equal to the lockedRecords size then, have to synchronize on each record and notifyAll on each record object. Is this the way to do if we are doing record level locking?
Because as I see if client crashes after locking the record, the only way to get others out of waiting is to notifyAll on the record.
Now another issue is you cannot notifyAll on all the records while looping. You have to keep track of lockCount for each record and while looping for maintainance, check if each record lockCount is equal to the actual number of locked records and if any record lockCount does'nt match then notifyAll on that particular record. Is that right?
Guys, there's a lot going on while dealing with record locking.

[Philippe Maquet]

Hi Satish,
I have nothing to add to previous comments, and reading your last post, I think you're on the right track.
*But* do you really think that keeping the record-level-locking technique is worth while?
As it's a position I defended myself, and reading your comment in the code you posted above, I understand your goal:

//Therefore in the unlock method, I
// can notify on the object itself. I believe this satisfies the
//statement, don't waste CPU cycles while the record is locked

Look at what I wrote here about it a few day ago.
Wouldn't be much easier (and as defendable) to use the solution mentioned as 1.2 in the Notification Issues thread?
Moreover, dead clients detection included, with the help of the technique you just mentioned?
Regards,
Phil.
[ March 25, 2004: Message edited by: Philippe Maquet ]

[Satish Avadhanam]

Hi Phil

Originally posted by Philippe Maquet:
Hi Satish,
I have nothing to add to previous comments, and reading your last post, I think you're on the right track.
*But* do you really think that keeping the record-level-locking technique is worth while?

I am not sure Phil. I don't want to get surprised once I see the score that my locking did'nt get full marks because of that reason. So only sticking to the true meaning of the instructions.

Look at what I wrote here about it a few day ago.

Thanks Phil. I had a look at it.

Wouldn't be much easier (and as defendable) to use the solution mentioned as 1.2 in the Notification Issues thread?

Easier, yes. But I told you before only that am much worried about score.

Moreover, dead clients detection included, with the help of the technique you just mentioned?

If I use 1.2 solution then dead client detection would be easy compared with what am doing now. But I really don't know if I want to change the locking and go to solution 1.2.

Regards,
Phil.
[ March 25, 2004: Message edited by: Philippe Maquet ]

Actually, I have a couple of questions regarding safe server shutdown and client crashes. I will start a new thread about those two topics.
Thanks alot for the great discussion and for sharing your ideas. Please comment on the issues in the new thread. Thanks.