This week's book giveaway is in the Servlets forum.
We're giving away four copies of Murach's Java Servlets and JSP and have Joel Murach on-line!
See this thread for details.
The moose likes Developer Certification (SCJD/OCMJD) and the fly likes I passed, but I suffered the 44/80 locking penalty. Why? Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Murach's Java Servlets and JSP this week in the Servlets forum!
JavaRanch » Java Forums » Certification » Developer Certification (SCJD/OCMJD)
Bookmark "I passed, but I suffered the 44/80 locking penalty. Why?" Watch "I passed, but I suffered the 44/80 locking penalty. Why?" New topic
Author

I passed, but I suffered the 44/80 locking penalty. Why?

Paul Goh
Greenhorn

Joined: Sep 14, 2004
Posts: 16
I would like to thank everyone here for helping me out, I would not have passed without your help...

Score: 350
General Considerations (maximum = 100): 96
Documentation (maximum = 70): 69
O-O Design (maximum = 30): 30
GUI (maximum = 40): 31
Locking (maximum = 80): 44
Data store (maximum = 40): 40
Network server (maximum = 40): 40

1 month ago, I got so sick of doing SCJD that I literally forced myself to finish up and submit. If any expert is willing to take a look at my Data class to see why I did so badly in the locking, I would really apprecaite it.
[ October 04, 2004: Message edited by: Paul Goh ]
Paul Goh
Greenhorn

Joined: Sep 14, 2004
Posts: 16
I think it would benefit other people if I post my lock method. Regarding unlocking after the record is deleted, I guess it is okie if the RecordNotFoundException is not thrown, as there are no side effects other than the unlock method removing the lock from the record. Actually, right after I submit the programming assignment, I realized that I have a problem in the lock method: I should have checked for deleted records again right after the thread wakeup, maybe this is why I lost so many points?


[ October 05, 2004: Message edited by: Paul Goh ]
Paul Goh
Greenhorn

Joined: Sep 14, 2004
Posts: 16
Hey...to tell you the truth, I was shattered when I realized the mistake after I submit my programming assignment, but then, checking again for deleted record after the thread wakeup might be graded under the Data class rather than locking/unlocking (I got full marks for the Data class.). Also, I believe my GUI sucked big time (you might be shocked if you see how crappy my GUI is.), and my design considerations and documentation is nothing compared to the high standards that I have been reading in this forum, but it still turned out pretty okie. During the written exam, I was asked to name and justify my design choices, and quote some advantages/disadvantages of my design, and I turned cold, as I didn't even discuss about any disadvantages of my design in my programming assignment documentation.

However, I guess the one thing I did right is to read the assignment over and over again (Perhaps more than 30 times in total.) to make sure that I don't fail immediately. If you have been deligent in reading the assignment, I guess your chances of passing is very high.
[ October 05, 2004: Message edited by: Paul Goh ]
Steve Taiwan
Ranch Hand

Joined: Jul 01, 2003
Posts: 166
Dear Paul.

Thank you very much for sharing your source code.
I am correcting my code according to your post.
And also thank Anton to clarify it.


Steve Taiwan<br />SCJP 1.2, SCJD 1.4, SCWCD 1.3, SCBCD 1.3, OCP 8i DBA, SCEA
James Turner
Ranch Hand

Joined: May 10, 2004
Posts: 194
Hi Anton,

The code you showed where after waiting for ownership of the record lock you re-check if the record still exists.

If you has the wait code in the same function, i.e. you don't go to a different method to wait, you would not need the second check as the waiting thread, when notified, would start the method from the beginning which starts with the initial check.

I hope you get what I'm saying...

I'd like to hear your comments...

James.


James<br />SCJP 1.4 - 92%<br />SCJD - 93%<br />SCWCD 1.4 - 95%<br />SCBCD 1.3 - 100%<br />SCEA - 92%
James Turner
Ranch Hand

Joined: May 10, 2004
Posts: 194
Actually, now that i think about it, I believe I am wrong about that....sorry!

James.
mike acre
Ranch Hand

Joined: Sep 23, 2003
Posts: 197
Originally posted by Anton Golovin:
This thread should be very useful to current test-takers: we have located the common mistake about the locking mechanism. It is in the lock method and comes after the record to lock comes unlocked and is available for locking. Then, before locking, one should check if the record still exists, as the previous thread might have deleted it. Hope this helps people who have not turned their assignment in, and also those who failed but could pass with their locking getting more points.


Actually a better method is to lock the resource instantly on entry to the lock method whether it exists or not and catch exceptions to unlock if things aren't well.

Also I would advise against posting entire lock/unlock methods whether correct or not - this violates the well documented policies of the site.


SCJP 1.4, SCJD
Anton Golovin
Ranch Hand

Joined: Jul 02, 2004
Posts: 476
I sent an email to Sun asking to resubmit since it was only since yesterday that they have it. Let's see if they let me.


Anton Golovin (anton.golovin@gmail.com) SCJP, SCJD, SCBCD, SCWCD, OCEJWSD, SCEA/OCMJEA [JEE certs from Sun/Oracle]
Paul Goh
Greenhorn

Joined: Sep 14, 2004
Posts: 16
Hey Anton, if I read the SCJD terms and condition correctly, I don't think you stand a chance for resubmit.

Mike: I didn't realize that I have violated the policies of this forum If you could kindly point me to a link where I could read up on the policies, I would really appreciate it as I do not want to make similar mistakes again.
Lasse Koskela
author
Sheriff

Joined: Jan 23, 2002
Posts: 11962
    
    5
Originally posted by Paul Goh:
If you could kindly point me to a link where I could read up on the policies, I would really appreciate it as I do not want to make similar mistakes again.

The link to the SCJD FAQ can be found from the top of this forum's front page.


Author of Test Driven (2007) and Effective Unit Testing (2013) [Blog] [HowToAskQuestionsOnJavaRanch]
Paul Goh
Greenhorn

Joined: Sep 14, 2004
Posts: 16
Ok, I have removed the code for my unlock method, which is not relevant to the discussion anyway...

Thanks for the link!
Mogens Nidding
Ranch Hand

Joined: Mar 08, 2004
Posts: 77
So the following strategy would be adequate for locking a record:

  • Enter monitor (synhronized)
  • wait() until no client holds the lock on the desired record number
  • verify that the record indeed exists and is not deleted, throw an exception if not
  • grab hold of the lock on the desired record number
  • Exit monitor


  • Correct?
    Andy Zhu
    Ranch Hand

    Joined: May 26, 2004
    Posts: 145
    Yes.

    Anton: I think you have made a very important point. No matter what sun says back to you or how it grades you, I think you already have the knowledge, which is more important than the score, IMHO.


    --------<br />Andy Zhu<br />scjp 1.4<br />scjd 1.4<br />SAS Certified Programmer 9.0
    Andy Zhu
    Ranch Hand

    Joined: May 26, 2004
    Posts: 145
    Hey, Paul:

    in your code there is a check of flag for validity. You used readUnsignedShort from RAF, I think. Or should it be just readShort? (I don't think there is a writeUnsignedShort). Is this relevant to correct check flag?

    Thanks for anyone having an answer.
    Paul Goh
    Greenhorn

    Joined: Sep 14, 2004
    Posts: 16
    Hi Andy,

    The check flag of 0x8000 is a flag for deleted records, required by the assignment. I found out that when I use writeShort(0x8000) on the RAF, I have to use readUnsignedShort() to get back the correct value. I didn't analyze this issue any further to see why this is the case, because it works, and it is good enough for me...

    Anton: Please post to this thread when you get your results, I want to confirm if this is indeed the problem in my lock method.
    Mogens Nidding
    Ranch Hand

    Joined: Mar 08, 2004
    Posts: 77
    Originally posted by Anton Golovin:
    1) Check that the record exists. If not, RecordNotFoundException.
    2) while (record is locked by someone else AND (|) the record is not deleted) loop waiting
    3) Once the loop exits, it could be the record is unlocked or it has been deleted. So, check for record not being deleted. If it is deleted, throw RecordNotFoundException. Otherwise, lock it.

    In 2) this would prevent your method waiting needlessly on a locked record that is deleted. Ordinarily, if another thread deleted it, yours cuts in, checks it is locked, and continues waiting when it should not. With this code, it stops waiting a little bit sooner.


    Ahh... I think your strategy is quite right, although I think step 1 is superfluous (if the record is deleted, we will get to step 3 very quickly).
    The assumption I was working under earlier was that a locked record cannot be deleted (since it is not permitted to lock a deleted record). But assuming that a locked record can be deleted, your strategy is more efficient. I think the strategy I posted is correct too, but it waits until the record gets unlocked.

    The issue of deleting a locked record is all new to me. In my opinion, it is perfectly reasonable to allow it since the documentation for the delete method does not specify otherwise. My question, however, is whether we should explicitly unlock the record number when this happens? The pros of doing so is that
  • 1. We obtain the invariant that a locked record is always valid (non-deleted)
  • 2. The contracts for lock and unlock state that the record gets locked, not the record number. So if a locked record gets deleted, that lock becomes unimportant.

  • I'm not sure there are any cons.
    (Edit: I had a con once, but I don't think it holds)
    [ October 05, 2004: Message edited by: Nicky Bodentien ]
    mike acre
    Ranch Hand

    Joined: Sep 23, 2003
    Posts: 197
    You seem to be missing something fundamental.

    You must lock the record as the very first thing you do in lock().
    Otherwise someone else may grab the lock and change the record.
    It does not matter if the record is valid or not, you only have a number or two in a Collection to represent the record, it does not matter if that record is invalid. What does matter is that the record is locked while you make your checks.

    Any other approach will be over synchronised.

    The code I have seen posted is unnecessarily complex.

    Ignore me if you will, since I only got 44/80 for locking myself, but I am quite sure of this aspect, I have noted where I think I made an oversight.
    Mogens Nidding
    Ranch Hand

    Joined: Mar 08, 2004
    Posts: 77
    Originally posted by mike acre:

    You must lock the record as the very first thing you do in lock().
    Otherwise someone else may grab the lock and change the record.


    I can't lock the record as the very first thing, because it might be locked by another client. So first thing must be to wait for the lock to become available. Then yes, I can grab the lock before checking for validity, but I can't see that it would give me any advantage.


    It does not matter if the record is valid or not

    Originally I didn't check, but then I saw in the instructions that methods that throw RecordNotFoundException should do so if the record does not exist/is marked deleted. So I guess it would be fair to make the check.


    Any other approach will be over synchronised.

    I am not sure I understand what approach you are suggesting, but I don't hope it involves accessing shared variables outside of a synchronized block.
    In my opinion, if you do all the checks and grab the lock in one synchronized block, then the code is "so simple that it obviously contains no deficiencies", whereas if you grab the lock in a synchronized block and start accessing it outside the synchronized block, then the code is "so complex that it contains no obvious deficiencies" (OK, I'm admittedly exaggerating, but that gave me a chance to quote Hoare :-)).
    Marlene Miller
    Ranch Hand

    Joined: Mar 05, 2003
    Posts: 1391
    Hi Paul,

    Here is something I noticed in your lock method. It�s about a case where an invalid record number is passed.

    I assume a valid recNo >= 1, since you subtract 1. I also assume recordOffset is the length of a record including the delete field.

    If recNo == 0, at (1) fileOffset is firstRecordOffset � recordOffset.
    Therefore fileOffset is probably > 0. An exception is not thrown.

    If recNo == -1, at (1) fileOffset is firstRecordOffset � 2 * recordOffset
    Therefore fileOffset is probably still > 0. An exception is not thrown.

    By probably I mean, it is true if
    the length of the metadata > record length (case recNo == 0) or
    the length of the metadata > 2 * record length (case recNo == -1).

    Marlene
    [ October 05, 2004: Message edited by: Marlene Miller ]
    Mogens Nidding
    Ranch Hand

    Joined: Mar 08, 2004
    Posts: 77
    Originally posted by Paul Goh:
    Hi Andy,
    The check flag of 0x8000 is a flag for deleted records, required by the assignment. I found out that when I use writeShort(0x8000) on the RAF, I have to use readUnsignedShort() to get back the correct value. I didn't analyze this issue any further to see why this is the case, because it works, and it is good enough for me...


    The reason is this: 0x8000 interpreted as a short is a negative value. 0x8000 interpreted as an int is a positive value (0x00008000). So, if you have something like this in your code



    then DELETED_FLAG is the positive int value 0x00008000, which is different from the negative short value 0x8000 returned from file.readShort(), although the rightmost 16 bits are the same for both values.

    Basically, by using file.readUnsignedShort() which returns a positive int, you get 0x00008000 on both sides of ==, effectively fixing the problem.

    If you would prefer not converting the flag to int values, then instead do this:



    ... voila, you have 0x8000 on both sides on ==, also fixing the problem.
    Paul Goh
    Greenhorn

    Joined: Sep 14, 2004
    Posts: 16
    Originally posted by Marlene Miller:
    Hi Paul,

    Here is something I noticed in your lock method. It�s about a case where an invalid record number is passed.

    I assume a valid recNo >= 1, since you subtract 1. I also assume recordOffset is the length of a record including the delete field.

    If recNo == 0, at (1) fileOffset is firstRecordOffset � recordOffset.
    Therefore fileOffset is probably > 0. An exception is not thrown.

    If recNo == -1, at (1) fileOffset is firstRecordOffset � 2 * recordOffset
    Therefore fileOffset is probably still > 0. An exception is not thrown.

    By probably I mean, it is true if
    the length of the metadata > record length (case recNo == 0) or
    the length of the metadata > 2 * record length (case recNo == -1).

    Marlene

    [ October 05, 2004: Message edited by: Marlene Miller ]


    Hey Marlene, I think you are absolutely right, very sharp. Luckily the examiners are not as sharp as you...
    peter wooster
    Ranch Hand

    Joined: Jun 13, 2004
    Posts: 1033
    Originally posted by mike acre:
    You seem to be missing something fundamental.

    You must lock the record as the very first thing you do in lock().
    Otherwise someone else may grab the lock and change the record.
    It does not matter if the record is valid or not, you only have a number or two in a Collection to represent the record, it does not matter if that record is invalid. What does matter is that the record is locked while you make your checks.

    Any other approach will be over synchronised.

    The code I have seen posted is unnecessarily complex.

    Ignore me if you will, since I only got 44/80 for locking myself, but I am quite sure of this aspect, I have noted where I think I made an oversight.


    Mike is right on this one, I don't even lock records, I simply lock numeric resources in my LockManager. My record locking code in the Data class works as follows

    - lock resource, waiting until its available
    - check if locked resource is a valid record
    - unlock resource if not a valid record.

    My delete code unlocks the resource when it deletes a record.
    Andy Zhu
    Ranch Hand

    Joined: May 26, 2004
    Posts: 145
    Hey, Paul, I think Nicky answered the question. At least in my project, I used writeShort and have no problem.
    Mogens Nidding
    Ranch Hand

    Joined: Mar 08, 2004
    Posts: 77
    Mike is right on this one, I don't even lock records, I simply lock numeric resources in my LockManager. My record locking code in the Data class works as follows

    - lock resource, waiting until its available
    - check if locked resource is a valid record
    - unlock resource if not a valid record.

    My delete code unlocks the resource when it deletes a record.


    Sorry, but I still don't get it! I also only lock numeric resources. But if I have this: (very pseudocode written in 2 mins, only focus on relative order of monitor, lock and validity check)



    what could possibly go wrong, and why should it be any better to swap the putLock and isValid calls?

    [ October 06, 2004: Message edited by: Nicky Bodentien ]

    [Andrew: Removed unlock() method, as we do not allow the posting of both lock() and unlock() methods. This policy is described in the question "What is the policy on posting questions I saw on the exam / details of how to do the assignment?" in the JavaRanch SCJD FAQ.]
    [ October 06, 2004: Message edited by: Andrew Monkhouse ]
    peter wooster
    Ranch Hand

    Joined: Jun 13, 2004
    Posts: 1033
    Originally posted by Nicky Bodentien:


    what could possibly go wrong, and why should it be any better to swap the putLock and isValid calls?

    [ October 06, 2004: Message edited by: Nicky Bodentien ]
    [ October 06, 2004: Message edited by: Andrew Monkhouse ]


    Checking record validity within the synchronized lock method will involve nested synchronized blocks if you synchronize on the file when doing I/O. This can result in deadlock, if for example the delete code is synchronized on the file and tries to unlock the deleted record.
    [ October 06, 2004: Message edited by: Andrew Monkhouse ]
    Paul Goh
    Greenhorn

    Joined: Sep 14, 2004
    Posts: 16
    Hey Marlene, after a night's sleep, I just realized that the "0" and "-1" recNo bug is actually not important in my application, because I am using a thin client approach (all locking is done on the database server side.), and the GUI client is never able to specify any recNo. So, all recNo are calculated by me, and they are always valid. No wonder the examiners failed to find any problem with that...
    Mogens Nidding
    Ranch Hand

    Joined: Mar 08, 2004
    Posts: 77
    Originally posted by peter wooster:

    Checking record validity within the synchronized lock method will involve nested synchronized blocks if you synchronize on the file when doing I/O. This can result in deadlock, if for example the delete code is synchronized on the file and tries to unlock the deleted record.


    I can see your concern about deadlock, but how would it be possible? For a deadlock to occur, there must be a circular hold-and-wait situation, but there is nothing circular about the nested synchronizations in this case.
    Let me "inline" the call to isValid to illustrate (again very pseudo):


    A thread can attempt to get the synchronization lock on "file" while holding the synchronization lock on "this" (the Data instance), but not the other way around. So there is no circularity, and no deadlock.

    To understand you right, is this what you are proposing?

    I think it would work perfectly (assuming that isValid(recNo) is thread safe, which it likely is). I just don't think there's anything wrong with the other approach (I don't synchronize on a new lock inside isValid). Correct me if I'm wrong.
    [ October 07, 2004: Message edited by: Nicky Bodentien ]
    Jason Hocker
    Ranch Hand

    Joined: Jul 23, 2003
    Posts: 132
    Did anyone that passed do something similar? I'm wondering if others who got 44/80 fell into the same mistake?
    Marlene Miller
    Ranch Hand

    Joined: Mar 05, 2003
    Posts: 1391
    Hi Paul. What would happen if a client called lock() twice without calling unlock() in between? Marlene
    Andy Zhu
    Ranch Hand

    Joined: May 26, 2004
    Posts: 145
    Hey, Marlene: I think the same client/object will gain the lock but different objects will wait.
    Paul Goh
    Greenhorn

    Joined: Sep 14, 2004
    Posts: 16
    Hey Marlene, I think the same thread that obtained a lock is able to obtain the same lock again, no problems, however, based on my thin client design, this is also not an issue as the server determines how the record is locked, not the client, so the lock method will never be called twice by the same client (my GUI client is single threaded.).

    Here is an example of a remote method on the server:


    Actually I love the thin client approach as I don't have to worry about the security of the lock cookie, and also what will happen if the client accidentally disconnect halfway and I have to timeout and unlock the locked record.
    [ October 06, 2004: Message edited by: Paul Goh ]
    Marlene Miller
    Ranch Hand

    Joined: Mar 05, 2003
    Posts: 1391
    Hi Paul.

    Okay and thank you. Since you�re in the thin-client camp, it�s not an issue. (I think maybe on a second call to lock(), a thread would find recNo in the table and go into waiting mode. If true, even so, it�s not an issue for you). Thank you very much.
    Actually I love the thin client approach as I don't have to worry about the security of the lock cookie, and also what will happen if the client accidentally disconnect halfway and I have to timeout and unlock the locked record.

    With a thin client, do all the records as a result of a single search go across the wire in one chunk (one invocation from the client)? Unless you return an iterator?

    Regards, Marlene
    [ October 06, 2004: Message edited by: Marlene Miller ]
    Paul Goh
    Greenhorn

    Joined: Sep 14, 2004
    Posts: 16
    I return the search result in an ArrayList for convenience, here is an example of a method on the server (The find() and read() methods are wrappers of the same method in the Data class, except that I do lock/unlock when necessary in methods like delete() and update().):

    [ October 07, 2004: Message edited by: Paul Goh ]
    Marlene Miller
    Ranch Hand

    Joined: Mar 05, 2003
    Posts: 1391
    Thank you again Paul. Regards, Marlene
    Raj Nagappan
    Ranch Hand

    Joined: May 26, 2004
    Posts: 38
    My two cents on the locking problem:

    The solution proposed above assumes that there is no circumstance under which you can lock a deleted row, but we need to think carefully if such a need could arise. In my spec (UrlyBird 1.3.2) the doc for create() clearly states that it can reuse a deleted row. So in this case at least we need to be able to lock such a row. (Also you need to find an empty row and lock it in an atomic operation but that is another issue.)

    I believe that this solution is mixing concerns. The responsibility of locking code is to lock/unlock only. What to do with the locked row is the responsibility of the operation being performed. For example, in my update() and read() methods I throw a RecordNotFoundException if the row is deleted, not in lock(). My delete() just returns if the row is already deleted.

    I've JUnit tested this with up to 5000 threads and it seems to work ok
    IMHO I think there is another reason why 44/80 keeps getting dished out, I suspect it has to do with time slices between locating a suitable row (e.g. for create) and locking that row...


    Raj Nagappan<br />SCJP, SCJD, PhD
    Raj Nagappan
    Ranch Hand

    Joined: May 26, 2004
    Posts: 38
    Originally posted by Anton Golovin:


    I think the lock method is the reason for points taken off. It just must check for deleted record after it determines the record is unlocked (after the wait loop exits.) Otherwise, it could try to update a deleted record, and it would throw a RecordNotFoundException... So the easies way would be for the lock method to fail in the first place.

    [ October 09, 2004: Message edited by: Anton Golovin ]


    Hi Anton,

    There are situations that you want to write to a deleted record, e.g. create(). If the lock method cannot lock a deleted record then this is not possible. Like I said, responsiblity for what to do with a locked deleted record rests with the calling operation, not with the lock. I could, for example, extend the system with an insert method that can overwrite rows - deleted or not - and I'd have to be able to lock the specific row number under any circumstance for this method to work.

    Raj.
    Robert Chisholm
    Ranch Hand

    Joined: Jul 18, 2004
    Posts: 69
    Just to add my 2 cents to the thread...

    A "delete operation" should be an atomic transaction consisting of lock+delete+unlock. In my mind, a create() should not infinge on a delete's atomicity. Ie: just because the create() method doesn't use the same lock() as delete() or update(), doesn't mean it should be able to reuse any deleted record at any time. If the above atomic delete operation hasn't finished then, IMO, create() shouldn't be allowed to reuse that deleted record.

    In my project, I use a deletedRecordList collection. The create() method must go here to reuse a deleted record. When the atomic delete operation has completed, it puts the newly deleted recNo in the collection. To add, the following is my atomic+synchronized create operation: determine recNo to create+create the record+remove the recNo from the deleted list. So it's not possible for two threads to create() the same record at the same time.


    SCJP 1.4<br />(WIP) SCJD B&S v2.3.3
     
    It is sorta covered in the JavaRanch Style Guide.
     
    subject: I passed, but I suffered the 44/80 locking penalty. Why?
     
    Similar Threads
    Passed SCJD
    Passed SCJD with 346
    Passed SCJD but ...
    passed
    passed at 354