• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Tim Cooke
  • paul wheaton
  • Jeanne Boyarsky
  • Ron McLeod
Sheriffs:
  • Paul Clapham
  • Liutauras Vilda
  • Devaka Cooray
Saloon Keepers:
  • Tim Holloway
  • Roland Mueller
Bartenders:

B&S: Locking

 
Ranch Hand
Posts: 86
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hi,

I'm writing a LockManager class, and have come up with a design of a "lock(int lockNumber)" method, but it seems a bit dodgy and convoluted. It works (at least from my limited testing), but the code isn't "elegant".

Right, this is going to take some explaining...

Firstly I have a "Lock" class which is like ReentrantLock, but if the lock isn't available then it blocks, but releases the monitor its instance. So, if we have the following in the lock method, where myLock is an instance of Lock (Note this is a simplified version of my actual code, which is more exmplained below. In this version there is no apparant need to have the synchronized blocks here, but this is only to explain how part of my code works, which I think does need the synchronized blocks):

And also we have something like

in the unlock method. If thread A has the lock, but thread B want to get the lock, it will block in myLock.lock(). However, it will release the monitor on myLock, leaving thread A free to enter the synchronized section in the unlock method, and unlock the lock.

However: I want to have some collection of "Lock"s - one for each record, and so the code above gets more complicated.

My current plan is to not let the LockManager know anything about what records there are, which are deleted, or anything like that. It just acts as a mutual exclusion lock for each possible integer. This means that it is to have some sort dynamically updatable collection of Locks within it. Thus I have:


A map of Locks, (with the keys as Integers), called "locks" below
A lock of the map, called "locksLock"

In the lock(int lockNumber) method:

1. Call locksLock.lock()
2. If in locks, there isn't a lock corresponding to the lockNumber, create one and add it to the collection.
3. Retrieve the Lock from the collection corresponding to the lockNumber
4. Begin synchronized block on the retrieved Lock
5. Call locksLock.unlock()
6. Call lock() on the retrieved lock.
7. End the synchronized block on the retrieved Lock.

The unlock method has a similar structure, except that it holds the lockLock lock for the entire method, and that in the synchronized block on the retrieved lock, it not only unlocks the lock, but if there are no other threads waiting to get the lock, it removes it from the collection. The number of threads waiting to get the lock is stored internally in Lock.


As far as I can tell, this seems to work fine. However, I don't like the fact that the lock in step 1. is unlocked in step 5, but between the two a synchronized block starts, and doesn't end until step 7. This "overlapping" seems a bit dodgy to me.

However I can't think of another way of doing it. Is my way dodgy? Is there a better way?

If anything could do with clarification I would be happy to do so.

Michal.
 
author
Posts: 580
5
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Michal:

You are on the right track, your code just needs a little bit of refinement. I'll give you two hints to think about (I think you would enjoy solving this on your own):

1. Remember that Reentrantock is an effective substitute for synchronized blocks. You don't need both (I realize you are just trying to be safe. But think about if it is really getting you anything critically useful).
2. Remember that corresponding lock and unlock calls could be nested to make your logic a little more crisp. I think thinking abot step #1 will automatically clarify this.

Let me know if you really need much more help on this. Again, it looks like you are on the right track.

Reza
[ June 12, 2005: Message edited by: Reza Rahman ]
 
Michal Charemza
Ranch Hand
Posts: 86
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Originally posted by Reza Rahman:

2. Remember that corresponding lock and unlock calls could be nested to make your logic a little more crisp.


What do you mean? (by the way you are right... I would enjoy solving this on my own... although some help is appreciated.) At the minute I'm thinking about some sort of "hand-over-hand" solution to this problem... is this what you mean?

Michal
 
Ranch Hand
Posts: 2937
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Here is another hint: the code in lock() is exactly 4 lines long. If you have a cookie requirement, it'll make it the total of 6 lines (one line to create a cookie and one line to return it). If you have the "entire database locking" requirement, throw in 4 more lines. If you have a RecordNotFoundException as part of the specified signature, that's another two lines.
[ June 12, 2005: Message edited by: John Smith ]
 
Ranch Hand
Posts: 118
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator


If you call lock() for a record which is deleted or invalid (past the end-of-file), do you have to throw a RecordNotFoundException? It doesn't exactly say so in the description, but this is what the RecordNotFoundException means in other contexts (e.g. the read() or update() method.

If you need to throw a RecordNotFoundException if the record is invalid, then you need to know which records are valid. I didn't see a check for that in your pseudo-code.
 
author and jackaroo
Posts: 12200
280
Mac IntelliJ IDE Firefox Browser Oracle C++ Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hi Michal,

Let me start by saying that it is possible to get a perfect score in locking without going to this much trouble.

But then, this is an interesting problem, and I have included a section on it in The Sun Certified Java Developer Exam with J2SE 5, Second Edition (I really must get my bio fixed :roll: ).

At the minute I'm thinking about some sort of "hand-over-hand" solution to this problem...

Then I suspect you are nearly there. Keep going with that thought .

When you have gotten a little further with that thought, some other ideas for you to think about:
  • If your key is an Integer, then you are using an immutable object as your key. Does this have any ramifications on your design?
  • Do you really need to exclusively lock the entire collection of locks? Or could you have a read-only lock on the collection, and a write lock on the key for your record? What benefit would that give you?

  • Regards, Andrew
     
    John Smith
    Ranch Hand
    Posts: 2937
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    But then, this is an interesting problem, and I have included a section on it in The Sun Certified Java Developer Exam with J2SE 5, Second Edition (I really must get my bio fixed ).

    Which part of your bio needs fixing? Congratulations on the book. Seems like a fine tradition -- every SCJD bartender has the memoirs published on the account of the locking woes.
     
    Andrew Monkhouse
    author and jackaroo
    Posts: 12200
    280
    Mac IntelliJ IDE Firefox Browser Oracle C++ Java
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    Hi John,

    Thanks for the congratulations.

    It is good to see you posting in this forum again after such a long absence. Seems the last time I was involved in one of your posts was the "absolute right and wrong" post in MD .

    As for my bio, oh the part about who I work for, and where I am living (Sydney was 2 cities ago), and generally getting the bio fixed so that my bio does not appear to be part of Terry's.

    Regards, Andrew
     
    John Smith
    Ranch Hand
    Posts: 2937
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator

    Originally posted by Andrew Monkhouse:

    It is good to see you posting in this forum again after such a long absence. Seems the last time I was involved in one of your posts was the "absolute right and wrong" post in MD .



    Yeah, good to be back. Now that I've figured what is "right" and what is "wrong", I am back full time to Java programming.
     
    Michal Charemza
    Ranch Hand
    Posts: 86
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator

    Originally posted by Lara McCarver:

    If you need to throw a RecordNotFoundException if the record is invalid, then you need to know which records are valid. I didn't see a check for that in your pseudo-code.


    I do need to throw that... but I was hoping to have a separate LockManager class that doesn't know anything about the records themselves. The bulk of the locking code would be in lock manager, but I was going to have a separate check in Data (which would have an instance of LockManager as a private member variable) for the RecordNotFoundException.

    Michal
     
    Michal Charemza
    Ranch Hand
    Posts: 86
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator

    Originally posted by Andrew Monkhouse:

  • If your key is an Integer, then you are using an immutable object as your key. Does this have any ramifications on your design?
  • I saw this on another thread... however, I though about it then, and now, and I just can't see
    a) How to even get to the key to change it... using a HashMap I didn't think you have access to the key object itself.
    b) What possible purpose it could serve to change it.

    Originally posted by Andrew Monkhouse:

  • Do you really need to exclusively lock the entire collection of locks? Or could you have a read-only lock on the collection, and a write lock on the key for your record? What benefit would that give you?
  • I thought about this one as well. My problem is in locking a record I think need to 1) retrieve the lock from the collection (or create and add it if it doesn't exist), and then 2) "lock" it.

    However, without locking the collection somehow, between for a thread between steps 1) and 2), another thread that owns the locked record could unlock it, see that there are no threads waiting for the lock, and then remove it from the collection. Then a third thread could come in and and create another lock in the collection. Then the first and third threads would both be able to lock the same record at the same time.

    Sorry if I'm being a bit slow!

    Michal.
     
    Michal Charemza
    Ranch Hand
    Posts: 86
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator

    Originally posted by Andrew Monkhouse:
    I have included a section on it in The Sun Certified Java Developer Exam with J2SE 5, Second Edition


    Good plug... if only it was out now! I would probably buy it.

    Any chance of an advanced copy?

    Michal
     
    Reza Rahman
    author
    Posts: 580
    5
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    Michal:

    Sorry about the long delay. Mondays and Fridays are the worst for me.

    You are not being slow at all. If anything, you are being extra careful (which is great...).

    If you still need someone to talk through the problem, could we start with the following questions:

    1. Is there a compelling reason to remove the lock objects from the collection at all? Simply creating the lock objects, retrieving them and using lock and unlock semantics like ReentrantLock would be easier and less error prone, right?

    2. Is there a compelling reason not to use ReentrantLock instead? It is part of the JDK and virtually guaranteed to be bug-free and effective in transforming concurrent requests to sequential ones. In addition, you get a free pass on lock ownership check and errant unlock calls.

    Sorry again for the late response...

    Reza
    [ June 13, 2005: Message edited by: Reza Rahman ]
     
    Andrew Monkhouse
    author and jackaroo
    Posts: 12200
    280
    Mac IntelliJ IDE Firefox Browser Oracle C++ Java
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    Hi Michal,

    Sorry for taking so long to respond - I have had a few other things keeping me busy.

    Regarding the "Integer is an immutable object" issue - I am glad that this does not affect you. Some previous attempts to do similar things to what you are doing have started with the thought that they would change the integer, forgetting that this would put a brand new object into the map, which would cause major problems for the design. It seems that in trying to help you avoid a problem I have seen in other's designs, I have only helped to confuse use Sorry.

    I thought about this one as well. My problem is in locking a record I think need to 1) retrieve the lock from the collection (or create and add it if it doesn't exist), and then 2) "lock" it.

    However, without locking the collection somehow, between for a thread between steps 1) and 2), another thread that owns the locked record could unlock it, see that there are no threads waiting for the lock, and then remove it from the collection. Then a third thread could come in and and create another lock in the collection. Then the first and third threads would both be able to lock the same record at the same time.



    This is where your hand-over-hand locking comes in. You will need a write lock on the collection first, then get a write lock on the record key, then you can release the write lock on the collection.

    By the way - have you thought about what happens if a record is deleted in your solution?

    Also - instead of having locks on different record keys, have you considered having different notification objects?

    Regards, Andrew

    P.S. You are not being slow, you are just dealing with people like me who are deliberately only giving really vague hints and questions. At the moment there are several ways you could go, and I am trying to avoid giving too many details on any one idea.
     
    Michal Charemza
    Ranch Hand
    Posts: 86
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator

    Originally posted by Reza Rahman:
    Sorry about the long delay. Mondays and Fridays are the worst for me.


    Originally posted by Andrew Monkhouse:
    Sorry for taking so long to respond - I have had a few other things keeping me busy.


    It's fine! I am grateful for any help, even if delayed. Ok... end of sucking up.

    Originally posted by Reza Rahman:

    1. Is there a compelling reason to remove the lock objects from the collection at all?


    I was hoping to have a separate lock manager that would just deal with the locking - a lock for each integer, and also not have any public methods (or arguments in the constructor) to add or remove locks objects from the collection. This is so the public "interface" for the class is as simple as possible.

    If then it is not possible to remove lock objects from the collection by a client class, I do feel it should maintain as small a collection of objects internally as possible. In this instance it is not that important if the lock objects, once they are created, are never delted. For one reason the database is small. Another would be if deleted records were re-used, then the lock objects would be re-used.

    However, I wanted the lock manger to be a "general utility", that could potentially be used for some, at the time of writing, unforseen problem (of course it can't deal with all unforseen problems, but if it's relatively easy to write it so it does, then I think it should be written that way). Also, I thought the general idea of classes were that they were to do one thing, but do them well.

    Say for some reason we wanted to do some "hand over hand" locking on all of the integers from 0 - 1000000000. Not removing the lock objects from the collection would result in 1000000001 objects that were potentally not being used at all, wasting memory in my eyes.

    Ok... now coming to think of it. This is describing a case where using as little memory as possible is more important. However, there could also be cases where speed is more important, so the objects don't have to be needlessly recreated. Hmmm.... I may have just unconvinced myself. Although "speed" is not mentioned at all in the specs.

    Originally posted by Reza Rahman:
    2. Is there a compelling reason not to use ReentrantLock instead?


    In my original design (in my first post), I needed to have the monitor on the Lock object itself released if a call to lock() blocks waiting for another thread to unlock. This is not guaranteed in the API (i.e. if calling ReentrantLock.lock() does not necessarily release the monitor on the ReentrantLock object itself if it blocks waiting for another thread to unlock it).

    However...I think I need some way of recording if some threads are waiting (or will be waiting) for a lock. Reentrant lock has some methods to get these but they in the API they say things like "this should not be used for synchronization control, only for system monitering". If I am to remove lock objects - something needs to store this (I think this is where Andrew's mutable objects come in... yes?).

    Originally posted by Andrew Monkhouse:

    Also - instead of having locks on different record keys, have you considered having different notification objects?


    I am considering something like this. However, if I understand you correctly, this would entail having a syncronized block in the lock method, as well as having a write lock on the locks collection that overlaps with the syncrhonized block, which I'm not keen on (as in my first post). Is this what would be necessary?

    Originally posted by Andrew Monkhouse:

    By the way - have you thought about what happens if a record is deleted in your solution?


    I think that in Data I will always try to get the lock on the record from LockManager... and only then check if it is deleted and throw the appropriate exception if it's deleted (remembering to always follow with unlock() in a finally block in the calling class of course - and documenting this necessity in the calling class in Data).

    I considered doing the check before getting the lock, but if my access methods aren't syncronized (which they are definitely not), another thread could leap in between the check and the lock and delete the record.

    Right... after all that, here is my current lock(int lockNumber) method. There are a few things to be worked out, where and how to store certain information, and the "write locks on the ReentrantLocks", but I may sublcass/encaspulate ReentrantLock in my own class. Hmmm... a bit complex maybe


    1. Writelock the collection of locks
    2. If in the collection a ReentrantLock corresponding to lockNumber doesn't exist, then create and add it.
    3. write lock the ReentrantLock corresponding to lockNumber
    4. Unlock the collection of locks
    5. Store somewhere (details to be worked out!) that there is another thread wanting to get the lock (increase some counter by 1)
    6. unlock the ReentrantLock
    7. Call lock on the ReentranLock.

    The unlock method I will omit, but mention that I will still have a write lock on the ReentrantLock, but I think a read lock on the collection of locks so to allow concurrent unlocks of different locks. I think this will be fine using a ConcurrentHashMap (or whatever collection I end up using).


    This does seems a bit complex still... I will still think about.

    Michal
    [ June 15, 2005: Message edited by: Michal Charemza ]
     
    Reza Rahman
    author
    Posts: 580
    5
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    Michal:

    Not to beat a dead horse, but remember that performance is not the only relevant metric for the exam. Me, personally, would write simpler code that is more easily maintainable any day. Just for the purposes of evaluation, you might want to consider the fact that you really don't need the "hand-over-hand" approach you are mentioning if there is no possibilty of locks being ever deleted.

    Hypothetically, in this scenario, you could simply uses ReentrantLocks as "gate keepers" to each record, effectively giving you synchronization, thread monitoring, and requests queueing all in one for free. Something you might also take into consideration is that fact that Sun generally would prefer you to use existing packages whenever possible instead of inventing your own (If you really wanted to do someting neat/challenging, you could always join an open-source project or better yet, create one of your own instead of investing your onergies here on code that is unlikely to be ever used in a production environment - please take this advise as my own highly subjective personal opinion. ).

    Taking your current course though (which I fully respect taking by the way), I don't readily see any way of simplifying your code such further due to the possibilty of referenced locks being unexpectedly deleted mid-operation, thus creating some strange results. You might also want to consider the much simpler synchronized-wait-notify model discusssed on this forum many times. It seems using "ReetrantLock" is making your life harder rather than easier...

    Reza
    [ June 15, 2005: Message edited by: Reza Rahman ]
     
    Andrew Monkhouse
    author and jackaroo
    Posts: 12200
    280
    Mac IntelliJ IDE Firefox Browser Oracle C++ Java
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    Hi Michal,

    Originally posted by Andrew Monkhouse:
    Also - instead of having locks on different record keys, have you considered having different notification objects?

    Originally posted by Michal Charemza:
    I am considering something like this. However, if I understand you correctly, this would entail having a syncronized block in the lock method, as well as having a write lock on the locks collection that overlaps with the syncrhonized block, which I'm not keen on (as in my first post). Is this what would be necessary?



    Actually, I would get rid of synchronized blocks altogether, and use java.util.concurrent.locks.ReentrantLock in combination with multiple java.util.concurrent.locks.Condition - one condition for each record.

    Originally posted by Andrew Monkhouse:
    By the way - have you thought about what happens if a record is deleted in your solution?


    I was thinking more about your comment that records would be removed from the map at some point - in this case, are they removed after the deletion? Or are they left there until after every thread has locked the record / found that the record has been deleted / *** something important happens here *** / throws the appropriate exception.

    And yes, I am being obscure (yet again :roll: ) with my "*** something important happens here ***", but it is not relevant to my question to you about what happens in your solution. It is, however, very relevant to the overall locking scheme and might be the cause of the 44/80 locking score.

    Regards, Andrew
     
    Michal Charemza
    Ranch Hand
    Posts: 86
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator

    Originally posted by Reza Rahman:
    but remember that performance is not the only relevant metric for the exam. Me, personally, would write simpler code that is more easily maintainable any day.


    I on the whole agree. It's just that I don't like having an object that in its possible "normal" use can use more and more memory without it ever being freed (unless you are to make the object itself eligible for garbage collection).

    Originally posted by Reza Rahman:
    You might also want to consider the much simpler synchronized-wait-notify model discusssed on this forum many times. It seems using "ReetrantLock" is making your life harder rather than easier...


    Originally posted by Andrew Monkhouse:
    Actually, I would get rid of synchronized blocks altogether, and use java.util.concurrent.locks.ReentrantLock in combination with multiple java.util.concurrent.locks.Condition - one condition for each record.


    I did consider the Condition/await() approach before... and dismissed it as I misunderstood the point of it. Looking at its API again I see now that you can use it as a slightly more complicated version of the standard "synchronized-wait-notify model" - but with a difference. You can do the equivalent of "synchronize" but only on the condition object corresponding to the record, and thus the Condition equivalent of nofifyAll(), i.e. signalAll(), only wakes the threads waiting on that condition, i.e. waiting for that record, and so fully fulfils the "no cpu cycles" condition... which is what I wanted all along!

    Originally posted by Andrew Monkhouse:
    I was thinking more about your comment that records would be removed from the map at some point - in this case, are they removed after the deletion? Or are they left there until after every thread has locked the record / found that the record has been deleted / *** something important happens here *** / throws the appropriate exception.


    I'm still not sure I understand your senario - especially when you say "every thread" above.

    One possible thing is that I must make sure that if an exception is going to be thrown, especially something that means the server should carry on as normal, e.g. a RecordNotFoundException or somethin similar, then I must make sure that whatever the current thread has locked, must be unlocked (either before the exception is thrown, or in a finally clause).

    Is this what you mean? (I know you may not answer, but if I'm completely on the wrong track I would appreciate yet another nudge!)

    But anyway... thanks a lot everyone who replied to me in this thread. You've helped a lot.

    Michal.
     
    Reza Rahman
    author
    Posts: 580
    5
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    Michal:

    Actually, using a Condition object per record will still cause an artibrarily chosen thread to wake up. I am not sure if this really is any better in terms of CPU consumption (I don't think the selection is based on a queue, so some selection process does still happen under the hood - at least that's my reading of the spec).

    You do realize, you will still need to establish an acceptable boolean condition for the await() call, putting you right back to keeping a map of records to track locks somehow, in this case all you would have accomplished is semantically replacing synchronized blocks with lock/unlock and wait-notify with await/signal. What's more, this will still keep the dilemma of when/whether to delete the conditions still active

    I just think using Locks as gate-keepers to records outright is a little bit neater and a bit different that the usual synchronized-wait-notify (which is what I am using by the way) .

    Reza
     
    Andrew Monkhouse
    author and jackaroo
    Posts: 12200
    280
    Mac IntelliJ IDE Firefox Browser Oracle C++ Java
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    Hi Michal

    One possible thing is that I must make sure that if an exception is going to be thrown, especially something that means the server should carry on as normal, e.g. a RecordNotFoundException or somethin similar, then I must make sure that whatever the current thread has locked, must be unlocked (either before the exception is thrown, or in a finally clause).

    Is this what you mean? (I know you may not answer, but if I'm completely on the wrong track I would appreciate yet another nudge!)



    Exactly! And, when you unlock it again, you must ...

    Regards, Andrew
     
    Andrew Monkhouse
    author and jackaroo
    Posts: 12200
    280
    Mac IntelliJ IDE Firefox Browser Oracle C++ Java
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    Hi Reza

    Actually, using a Condition object per record will still cause an artibrarily chosen thread to wake up.



    It will choose one of the threads awaiting on that condition to be woken. So a thread awaiting for the lock on record 5 to be released will not wake up if the lock on record 3 is released. Which should be much better for CPU consumption.

    If you were worried about which thread awaiting on a particular lock will be woken, you could specify a fairness policy in the lock constructor.

    Regards, Andrew
     
    Reza Rahman
    author
    Posts: 580
    5
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    Andrew:

    To be honest, I am taking the "CPU consumption" statement as loosely as possible in my own solution. My locking implementation is ridiculously simple, boring and unoriginal. It also doesn't hurt that my assignment specifically states a preference to simplicity over efficiency (within reason, of course, I wouldn't go about creating O/S file handles, open ports or keeping redundant copies of non-trivially large objects in the name of simplicity, for example - not a knock on anyone who chooses to do so though - I'm all for diversity of opinion).

    That said, I definitely like the idea of using ReentrantLock, but I won't implement it in my persuit to streamline the project (I wish I could do the same for my ever-expanding waistline ).

    It's fun to explore these ideas anyway though (and maybe help out a bit). As I said, a collection of ReentrantLocks as "gate keeper" to records particularly strickes me as innovative instead of the tired old way. It just seems like such a natural fit for the job!

    Reza

    [ June 16, 2005: Message edited by: Reza Rahman ]
    [ June 16, 2005: Message edited by: Reza Rahman ]
     
    Reza Rahman
    author
    Posts: 580
    5
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    Michal:

    As I mentioned, I would be very cautious about lock/condition removal (if you go this route). As you pointed out a few posts back, I don't think detecting deletion and throwing an exception if it occurs is very obvious given your implementation and might very, very tricky, especially if you do any deletion in the unlock method (it's a bit easier on record delete but might still wind up in awkward behaviour such as two threads getting access to a lock when neither should).

    Once you crystalize your logic, it might be worthwhile to post back and put the pseudocode up to some scrutiny again.

    Reza
     
    Michal Charemza
    Ranch Hand
    Posts: 86
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator

    Originally posted by Reza Rahman:
    Actually, using a Condition object per record will still cause an artibrarily chosen thread to wake up.


    I agree with Andrew that if you have a a Condition object per record, then a signalAll() on one record will only wake up the threads waiting for that record, and not any other.

    Originally posted by Reza Rahman:
    You do realize, you will still need to establish an acceptable boolean condition for the await() call, putting you right back to keeping a map of records to track locks somehow, in this case all you would have accomplished is semantically replacing synchronized blocks with lock/unlock and wait-notify with await/signal. What's more, this will still keep the dilemma of when/whether to delete the conditions still active


    Originally posted by Reza Rahman:
    My locking implementation is ridiculously simple, boring and unoriginal.


    Originally posted by Reza Rahman:
    Once you crystalize your logic, it might be worthwhile to post back and put the pseudocode up to some scrutiny again.


    What I take to be your "boring" solution is something along the lines of:


    Have some map that contains objects corresponding to locked records, say lockedRecords. This can actually be a map containing Threads as owners of the map. Thus the map can be Integer->Thread.

    1. Synchronize on lockedRecords
    2. A while loop with the condition that the map contains a mapping for the current record
    2a.wait on lockedRecords (this releases the monitor on lockedRecords and allows other threads to access syncrhonized blocks)
    3. Add the current thread to the map
    4. End synchronzed block

    The unlock method is synchronized on lockedRecords, and removes the mapping Integer->Thread from the map for the current record (if the current thread is the owner) and notifies all those waiting on lockedRecords.


    The method of using Condition objects is very similar in terms of logic (as far as I can tell), but just a little more complicated


    Have some map that contains Conditions corresponding to locked records, say "conditions". Thus the map can be Integer->Condition
    Have some map to store the owners. Thus the map can be Integer->Thread
    Have a single ReentrantLock to control access to the maps, say "lock"

    1. Lock "lock"
    2. If there isn't a mapping for the current record, create a condition object for it. If there is a mapping for the current record, then retrieve the condition object
    3. A while loop with the condition that the current record is in the map
    3a.await on the condition object (this releases the lock on "lock" and allows other threads to lock "lock")
    4. Add the condition object / current threads to the map.
    5. Unlock "lock"

    The unlock method locks "lock" on entry. and unlocks it on exit. In between it removes the mappings from the current record to Thread/Condition objects (if the thread is the current owner). It also signalsAll the threads waiting on this condition object


    I think I prefer this method to the "hand-over-hand" approach with the gatekeeper ReentrantLocks - the logic seems simpler, and seems just a variation on a very traditional theme. Having all those locks seems more error prone to me, which not getting much of an advantage.

    A small disadvantage of this to "hand-over-hand" seems like there may be less concurrency of locks and unlocks, however this seems quite insignificant in this case.

    The only reason that I am not going with the standard way is that I do feel it violates the spec in such a clear way. I know people have gotten full marks on locking doing it, but if a relatively simple way exists to acheive it (and not violate the "junior programmer" requirement) then I think I should do it.

    Actually it's less "I think I should" more "I can't bring myself not to", if you know what I mean.

    Originally posted by Andrew Monkhouse:

    Exactly! And, when you unlock it again, you must ...


    I've been thinking about this and reading the "any methods that throw RecordNotFoundException should do so if a specified record does not exist or is marked as deleted in the database file".

    I have just realise that a thread would want to do this:

    lock a record
    -> delete a record
    -> unlock a record

    When unlock is called, the record has been deleted. To me it seems ludicrous to abide by the spec and have it throw a RecordNotFoundException, as it doesn't seem to be in this case an exceptional circumstance - it is the "standard and necessary" running of the program. Is this what you mean though?

    (Note: in my design unlock() will throw some sort of documented RuntimeException if it is called by a thread that doesn't own the lock)

    Thanks,

    Michal

    edit: corrected numbering and added unlock step to psuedocode
    [ June 17, 2005: Message edited by: Michal Charemza ]
     
    Michal Charemza
    Ranch Hand
    Posts: 86
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    Actually I could design it so that a thread would just call:

    lock()
    ->read() to check that the record hasn't changed (I left this out in the last post - I always seem to forget posting it)
    ->delete()

    And then no call to unlock, as if we are "locking records" having to unlock a record that no longer exists does seem a bit pointless. Inside delete() I could check that the current thread has the lock, delete the record, and then "unlock it".

    I still don't know if this is what you mean though.

    Michal
     
    Andrew Monkhouse
    author and jackaroo
    Posts: 12200
    280
    Mac IntelliJ IDE Firefox Browser Oracle C++ Java
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    Hi Reza & Michal,

    Originally posted by Reza Rahman:
    To be honest, I am taking the "CPU consumption" statement as loosely as possible in my own solution.

    Sounds good to me. As I said when I first got involved in this topic:

    Originally posted by Andrew Monkhouse:Let me start by saying that it is possible to get a perfect score in locking without going to this much trouble.



    Originally posted by Andrew Monkhouse:
    Exactly! And, when you unlock it again, you must ...

    Originally posted by Michal Charemza:
    I've been thinking about this and reading the "any methods that throw RecordNotFoundException should do so if a specified record does not exist or is marked as deleted in the database file".

    I have just realise that a thread would want to do this:

    lock a record
    -> delete a record
    -> unlock a record

    When unlock is called, the record has been deleted. To me it seems ludicrous to abide by the spec and have it throw a RecordNotFoundException, as it doesn't seem to be in this case an exceptional circumstance - it is the "standard and necessary" running of the program. Is this what you mean though?

    (Note: in my design unlock() will throw some sort of documented RuntimeException if it is called by a thread that doesn't own the lock)

    Actually, that wasn't what I was being obscure about, although it is a good topic anyway.

    One idea that has been tossed around in this forum in the past is having the delete method release the lock, relieving the need for the client to call unlock. If that is documented (design decisions and JavaDoc) then users of the Data class should know not to call the unlock method themselves in the sequence you showed, and if they do, then they deserve the RecordNotFoundException that will be thrown .

    What I was suggesting is that as part of the deletion method, you would presumably want to ensure that no threads will remain waiting for the lock. Consider for example:
  • Thread A locks the record
  • Thread B attempts to locks the record - wait state
  • Thread C attempts to locks the record - wait state
  • Thread A deletes the record (somewhere an unlock happens, either implicit or explicit)
  • Thread B wakes up because of the unlock - finds that the record has been deleted and throws RecordNotFoundException
  • I think that in step 5 you are locking the record, throwing the exception, and unlocking it in a finally statement - which would presumably wake up thread C. But I was trying to find out if this is what is happening in your solution.

    Regards, Andrew
     
    Reza Rahman
    author
    Posts: 580
    5
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    Michal:

    Just as reaffirmation, the current logic you posted does seem sound and does seem to be effectively replacing wait/notify with ReentrantLock/Condition and hence should be fine (with the additional effect of masking "CPU consumption" in your own code - Incidentally, you do realize you can accomplish the same with a small twist of the basic, simplest algorithm?).

    As for the RecordNotFoundException being thrown in the unlock method, I still do this check but "prepend" it with the condition that the record is currently not being locked. To reiterante, I throw this exception in unlock only if I don't see that the current caller holds the record lock and the record, in fact, does not exist. This is also a well-discussed past topic, you might want to check it out for additional details; otherwise, let me know, I will be happy to clarify.

    I still think it is shame you are not pursuing the approach of limiting or elimiting lock deletion (hence getting rid of the need to do "had-over-hand" synchronization) and use a set of persistent ReentrantLocks for synchronization. Who knows, maybe someone else will try it. It just seems too neat not to attempt . However, I won't be a hypocrit in professing it and not doing it myself .

    By the way, did you check out my post some time ago about CPU consumption in wait-notify? I outlined an algorithm there you might find interesting...

    Cheers,
    Reza
    [ June 17, 2005: Message edited by: Reza Rahman ]
     
    Ranch Hand
    Posts: 357
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator

    I think that in step 5 you are locking the record, throwing the exception, and unlocking it in a finally statement - which would presumably wake up thread C. But I was trying to find out if this is what is happening in your solution.



    This is exactly where I made the most major mistake in my assignment: B would not successfully lock the record and would therefore never unlock it, leaving C unnotified and thus waiting for ever.

    However this did not lead to the famous 44/80 locking score, as Andrew speculated, but to the more uncommon 65/80 score. So I guess you have to mess up even more in order to receive the 44/80 score

    Frans.
     
    Michal Charemza
    Ranch Hand
    Posts: 86
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator

    Originally posted by Andrew Monkhouse:
    What I was suggesting is that as part of the deletion method, you would presumably want to ensure that no threads will remain waiting for the lock. Consider for example:


    I don't really have anything in my delete method that does this. However, if we assume that unlock() is always called either in delete() or by the client class (as in what was discussed earlier)...

    In my lock() method in Data I have

    1. Lock the "record" in my LockManager instance. This will happen whatever integer value is sent, and whatever the actual state of the record in the database file.
    2. Now check the record is not deleted in the database file. If it is, then unlock the "record" and throw an Exception.

    As far as I can tell, the unlocking of the "record" will signal to other threads waiting for the lock. They will progress, complete Step 1, and then find the record is deleted in step 2, unlock the "record", signal to other waiting threads, throw an exception etc...

    I think that this means the senario that Andrew desribes cannot happen.

    Actually... this is an argument for unlocking a record in delete(): if a client class "forgets" to call unlock() after deleting a record, then other threads may be kept waiting forever for the lock on it.

    Originally posted by Reza Rahman:
    I still think it is shame you are not pursuing the approach of limiting or elimiting lock deletion


    Sorry!

    Phew! I think I have some close to having my locking solution finished. Goodness it's taken long enough.

    Michal
     
    Reza Rahman
    author
    Posts: 580
    5
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    Michal:

    All good things are worth the wait...at least you are able to validate your ideas againts others, right?

    Reza
     
    You don't know me, but I've been looking all over the world for. Thanks to the help from this tiny ad:
    Smokeless wood heat with a rocket mass heater
    https://woodheat.net
    reply
      Bookmark Topic Watch Topic
    • New Topic