wood burning stoves 2.0*
The moose likes Developer Certification (SCJD/OCMJD) and the fly likes Will this locking mechanism be allowed? Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Certification » Developer Certification (SCJD/OCMJD)
Bookmark "Will this locking mechanism be allowed?" Watch "Will this locking mechanism be allowed?" New topic
Author

Will this locking mechanism be allowed?

Nimesh Parmar
Greenhorn

Joined: Jun 07, 2010
Posts: 9
My locking/unlocking scheme works as follows: (I have the B and S assignment)

(1) User 1 chooses to display all records on his screen.
(2) User 2 also chooses to display all records on his screen.
(3) At time T1 User 1 selects record 5 for booking.
(4) At time T2 Record 5 is locked (i.e., an entry with the record number and the cookie is made in the HashMap).
The call made to the lock method is from the client tier.
(5) At time T3, User 2 attempts to book record 5 (so an attempt is first made to lock record 5).
(6) User 2 immediately gets a message saying record 5 is locked, try after some time or try booking a different record.
(7) In the meanwhile, User 1 either (1) books the record, (b) waits for some time to decide whether to book or not to book, or (c) cancels the idea of booking record number 5.
(8) In case (a), User 1 successfully books record 5 and the record is also unlocked. In case (b), a background thread that runs every 1 second removes the lock on record 5
if a certain pre-determined time interval has elapsed after the record was first locked (at step 4 above). This time is configurable via the gui when the system is started
in the "server" mode. In case (c), the record is unlocked.
(9) When User 2, at time T4 tries to lock record 5 again, and if (T4-T3 > the pre-determined time period), User 2 gets to see record 5 with an updated customer number and
also gets to lock the record (if it was not locked by some one else)
(10) In this solution, I have not used locks, wait, notify and notifyAll. I have load tested it with 1000 threads and there has not been any deadlock.

The question is, will this solution be acceptable by SUN-Oracle?
Roel De Nijs
Bartender

Joined: Jul 19, 2004
Posts: 5278
    
  13

So if you don't use locks, wait, notify and notifyAll; how do you make the thread (of user 2) gives up the CPU and consumes no CPU cycles until the record is unlocked.

And I don't know if using a time-out is acceptable by Oracle-Sun, I do know that using a time-out is not required by the instructions

SCJA, SCJP (1.4 | 5.0 | 6.0), SCJD
http://www.javaroe.be/
Nimesh Parmar
Greenhorn

Joined: Jun 07, 2010
Posts: 9
Roel,

Thanks for the reply.

There are two locking methods:

(1) Search ==> Select ==> (Click on the Book button in UI to..) Lock the Record ==> Type cust no ==> (click Confirm on UI and then ){Update ==> Unlock}
(2) Search ==> Select ==> (Click on the Book button in UI) ==> Type cust no ==> (click Confirm in UI and then) {Lock ==> Update ==> Unlock}

Items appearing within curly and burly braces above must happen as a single unit.
Items appearing within round brackets are actions performed by the user.

Now, in case (1), if the think time is more than, say, 15 seconds, the background process unlocks the record and it is made available to any other user who wants it.

In case (2), User 1 wanted to update cust no of record 3 from, say, " " (i.e., 8 spaces) to 31313131. User 2 wanted to update cust no of record 3 also FROM, " " (i.e., 8 spaces) but to 32323232.

I have a lack of understanding in this case (case 2) and following is the scenario:

Time T1: User 1 locks record 3, updates record 3's cust no from " " to 31313131.
Time T1: User 2 tries to lock record 3 to update record 3's cust no from " " to 32323232 but is made to wait.
Time T2: User 1 successfully updates record 3.
Time T3: User 1 successfully unlocks record 3 and therefore User 2 succeeds in getting a lock on record 3.
Time T4: User 2 updates cust no of record FROM "31313131" to "32323232" and thus overrides the updates made by User 1.

Mind well, User 2's intention was to update FROM " " to "32323232" and NOT from "31313131" to "32323232". But User 2 ends up updating FROM "31313131" to "32323232". So, User 2 ends doing something that was not his intention, to begin with. How do we resolve this? Or, does this need to be resolved?

Any thoughts?
Seetharaman Iyer
Ranch Hand

Joined: Jun 25, 2010
Posts: 35
Hi Nimesh,

Time T4: User 2 updates cust no of record FROM "31313131" to "32323232" and thus overrides the updates made by User 1.


Both cases are really good. But on both the cases, you have missed one thing. That's before updating, you should check the availability of the records. Then only you can proceed to update value (override - from "" to "xxxxxxxx")

Because, both the cases, what user sees is not what is actually there. Even if you rapidly refresh your JTable (client from end screen) to keep the status of each record updated, there's a possibility that before you acquire the lock over the database (or record), somebody might have updated (or deleted it - assignment concern updated from "" to some xxx value).

Hope it helps.

Seetha...
Nimesh Parmar
Greenhorn

Joined: Jun 07, 2010
Posts: 9
Seetharaman,

Thanks for going through the scenarios.

before updating, you should check the availability of the records


Does this mean that in the scenario that I described, User 2 must NOT be allowed to book record 3?

In that scenario, both User 1 and User 2 have the "Enter Cust No" dialog on their respective screens. User 1 has typed "31313131" as the cust no. User 2, has typed "32323232" as the customer number. At time T1, both proceed to book record 3. The thread acting on behalf of User 1 grabs the lock BEFORE the thread acting on behalf of User 2 can grab the lock.

Any thoughts?
Seetharaman Iyer
Ranch Hand

Joined: Jun 25, 2010
Posts: 35
Buddy,

Obviously, that's what why we are using lock mechanism. Think about if Railway reservation dept using your code (logic), what will happen? The ticket booked by Passenger 1 will be overridden by Passenger 2. And both passenger will be fighting each other in the coach till ...........
Roel De Nijs
Bartender

Joined: Jul 19, 2004
Posts: 5278
    
  13

{Lock ==> Update ==> Unlock}
Items appearing within curly and burly braces above must happen as a single unit.

If I understand correctly you call lock, update and unlock as a single unit (is atomic operation). So when you send some output to the console you will always see the same pattern (and this is not a multi-threaded server):

client1 locks rec4, updates rec4, unlocks rec4
client2 locks rec5, updates rec5, unlocks rec5
client3 locks rec6, updates rec6, unlocks rec6
...

but the output of a real multi-threaded server would look like this (of course this output is not guaranteed, because order can change):

client1 locks rec4
client2 locks rec5
client1 updates rec4
client3 locks rec6
client3 updates rec6
client1 unlocks rec4
client2 updates rec5
client2 unlocks rec5
client3 unlocks rec6

And if a similar output is not possible with your current code, I think you'll fail because your locking mechanism is not according to the instructions.

And Seetharaman is correct: you expect no double bookings of the same room. So when 2 clients try to book the same room, only one of them will have a valid booking and the other has to choose another room. Think about yourself: how would you feel if you show up at a hotel and your room is already taken by someone else...
Nimesh Parmar
Greenhorn

Joined: Jun 07, 2010
Posts: 9
Roel, Seetharaman,

Great. Just as I thought. So, User 2 must not be allowed to book record 3.

This means that the moment User 2's thread executes the wait method inside the lock method, User 2's thread already knows that this record is likely to be updated by someone else. In that case, following are the questions:

(1) Should the method used inside the lock method be wait()?
(2) Should the method used inside the lock method be wait (long timeout), in which case, what should be the value of timeout?
(3) Whether we use wait or whether we use wait (long timeout), the User 2 is going to have to search, lock, update and unlock all over again. Correct?

Any thoughts?
Roel De Nijs
Bartender

Joined: Jul 19, 2004
Posts: 5278
    
  13

User2 can select record 3 and choose book. Just like user1 can. But when this occurs at the same time, it will be the decision of the almighty java thread scheduler which thread gets the CPU and thus which thread will lock record 3. The other thread has to wait until the other thread unlocks record 3 (and until this moment happens it should not consume any CPU cycles).

When in my application user2 tries to book an already booked room, he will get an error message "room already booked". And thus he will need to search for another room or just pick some other one out of the list. But because the user is a CSR, he will have to inform his customer for who he is making this booking. Maybe this customer says: "I just wanted that room, and it's already taken, so not interested in other rooms. Thanks and goodbye". If he wants another room, the CSR will have to select another room and start the booking process from scratch.

I just used a call to wait() in my lock-method.
Nimesh Parmar
Greenhorn

Joined: Jun 07, 2010
Posts: 9
Roel,

Thanks for taking the time to read my posts and also patiently replying. I will get to the point soon. In the meanwhile,
the other thread has to wait until the other thread unlocks record 3
.

When User 2's thread is waiting, what happens on User 2's terminal? Do you show a busy cursor, implying to User 2 that "the system is busy doing something" or do you "return" control back after "some" time to User 2 saying (s)he is free to search/book other records because record 3 has already been updated?

So, "some" here would equate to the timeout parameter in wait(long timeout). In case of wait(), the return would happen ONLY IF User 2 updates or decides not to update. The point is, whether you use wait() or wait(long timeout), control would NEVER return immediately back to User 2.

And my current thinking is "control MUST return immediately back to User 2 as soon as Thread T2 encounters the wait method"

That is the MOST important issue that I am struggling with.
Mxolisi Veco
Ranch Hand

Joined: Jan 14, 2010
Posts: 59
Good day.

When User 2's thread is waiting, what happens on User 2's terminal? Do you show a busy cursor, implying to User 2 that "the system is busy doing something" or do you "return" control back after "some" time to User 2 saying (s)he is free to search/book other records because record 3 has already been updated?


You don't have to display anything on user 2's screen.
You do not return control to user two until the booking is sucesfull or an error message is displayed.
Computers are fast these days, its unlikely that user two will even notice the delay.
User 2's thread has to wait until it is nitified to attempt to book the room.

So, "some" here would equate to the timeout parameter in wait(long timeout). In case of wait(), the return would happen ONLY IF User 2 updates or decides not to update. The point is, whether you use wait() or wait(long timeout), control would NEVER return immediately back to User 2.


You must NOT use wait(milliseconds) because you will get automatic failure. You must use wait(). Your requirements specification states that it is a MUST that your thread consume no CPU cycles when waiting for a resource.
It does not matter to which thread control returns to, if you implement your locking class right, then all the waiting threads/users will have a chance on the specified record. So user 2's thread will eventually get a chance to try to book the specified record. If by the time user 2's thread gets a chance to book the room, you must throw an RoomBookedAlreadyException ("This room is booked already"). If the room is not booked, update the record number and update user 2's front-end accordingly.

And my current thinking is "control MUST return immediately back to User 2 as soon as Thread T2 encounters the wait method"


You will be complicating your solution for no reason. Rather let user 2 wait until user 2's thread is notified to attempt to book/update the record.
That is, a user must only be able to do one thing at a time. If users are allowed to do many things at a time, that will not help with getting you more marks, instead you are likely to fail because of code complexity that you will be introducing.
Try to keep simple things simple.
Mxolisi Veco
Ranch Hand

Joined: Jan 14, 2010
Posts: 59
By the way Nimesh Parmar


1) Search ==> Select ==> (Click on the Book button in UI to..) Lock the Record ==> Type cust no ==> (click Confirm on UI and then ){Update ==> Unlock}
(2) Search ==> Select ==> (Click on the Book button in UI) ==> Type cust no ==> (click Confirm in UI and then) {Lock ==> Update ==> Unlock}


The above scenario (2) is more correct than scenario(1). Scenario (2) will take milli seconds to release the lock since by the time the end user clicks the confirm button all the details are available, so no time will spent waiting for the customer ID.
Scenario (1) will take longer to release the lock since while the user is typing the customer ID, the record is locked already.
Nimesh Parmar
Greenhorn

Joined: Jun 07, 2010
Posts: 9
Hello Mxolisi Veco,

I have implemented scenario 1.

But the time that the user gets between the "Lock the record" event and the "Click confirm on UI" event is configurable via GUI in the -server mode (only). Lets say that this period is set to 15,000 milliseconds. Then, the user who has locked a record gets 15 seconds to book the locked record. If he does not, then this record is unlocked by a background service that wakes up every 1 second and removes stale records from the HashMap that stores locked record data. Then, if this user confirms the booking after 15 seconds seconds have elapsed post the "Lock Record" event, this user gets a "Time out" error. Of course, he can book the record within 15 seconds without a problem.

After User 1 locks the record, if User 2 tries to lock the record, he immediately gets an error saying record is locked and he is free to search/lock/book other records.

This method needs no wait/notify.

This method too results in no CPU cycles being consumed. Also has advantages mentioned by George here...

http://www.coderanch.com/t/185091/java-developer-SCJD/certification/NX-Locking#899962

Any thoughts...
Roel De Nijs
Bartender

Joined: Jul 19, 2004
Posts: 5278
    
  13

In my opinion: the time a record is locked should be as little as possible (so I favor scenario 2)

After User 1 locks the record, if User 2 tries to lock the record, he immediately gets an error saying record is locked and he is free to search/lock/book other records.

I wonder how you do that, because the thread related to user2 should consume no CPU cycles at all (until the record is unlocked), so in thread terminology: this thread has to enter the waiting state (and will be back in the runnable state when the record is unlocked)
Nimesh Parmar
Greenhorn

Joined: Jun 07, 2010
Posts: 9
Roel,

In my lock method, this is (pseudo)code:


The code that generates new cookies is a simple Random.newLong() which ensures that the random number is never negative and never 0.

So every time that the lock method is called and it returns 0, the calling code knows that this record is already locked by some other user and there is no point in waiting because at the end of the waiting period, it is likely that the record will be booked. In the event that User 1 decides to abandon the booking for record 3, User 2 will always be able to lock that record 3 after some time (this time is configurable via GUI when app is launched in the -server mode).

If the calling code gets a return value that is non-zero, it knows that this record just got locked and the calling code is the lock owner and has some time to book the record before it is released (this "some" time is configurable via GUI when the app is launched in the -server mode).

So, when the lock method returns immediately, it consumes no cpu cycles on the server. The user is then free to search and book other contractors.

And because there is no wait in lock, I don't need a notify in unlock.
Matthew Workman
Greenhorn

Joined: Jul 01, 2010
Posts: 7
If your assignment has: "the current thread gives up the CPU and consumes no CPU cycles until the record is unlocked." then you are breaking that rule. Returning an error message requires CPU cycles.
sarvesh meens
Ranch Hand

Joined: Mar 31, 2006
Posts: 43

Hi Nimesh,

Interesting problem.

Let me summarize my understanding of the requirement.

  • There is a booking system
  • HashMap is the core data-structure used
  • I assume room number as key & customer ID as value
  • Rooms may be booked from a number of threads
  • Room booking should happen in a consistent manner in this multi-threaded environment.


  • Can think of three ways to meet this requirement.

    +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
    Approach I - Simple hashmap

  • Use a simple hash-map
  • synchronize every action on it (i.e read, write, iteration, etc)
  • No two threads will be acting on the map at the same time.
  • When a thread is writing on HashMap, another thread cannot read and vice-versa
    Hence, no inconsistencies


  • Advantages:
  • Consistent behavior
  • Easy to understand solution


  • Dis-Advantages:
  • Only one thread can book at a time - performance bottle neck
  • Need to synchronize each and every action on HashMap - Tedious programing construct, Error-prone


  • ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

    Approach II - Synchronized hashmap

  • Use a synchronized hashMap


  • No need to synchronize every action on hashmap since all methods in synchronizedHashMap are implicitly synchronized.
  • Iteration is the only activity for which manual synchronization is required.
  • No two threads will be acting on the map at the same time.
  • When a thread is writing on HashMap, another thread cannot read and vice-versa.
    Hence, no inconsistencies


  • Advantages:
  • Consistent behavior
  • No need for manual synchronization on every action


  • Dis-Advantages:
  • Only one thread can book at a time - performance bottle neck


  • +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

    Approach III - ConcurrentHashMap

  • Use ConcurrentHashMap as the core data structure
  • ConcurrentHashMap assures consistent behavior in a concurrent environment & blocking is kept to a minimum
  • When a room has to be booked, use concurrentHashMap.putIfAbsentkey,value).
  • Behavior of putIfAbsent is given below:
    If the specified key is not already associated with a value, associate it with the given value. This is equivalent to


  • except that the action is performed atomically.

  • putIfAbsent returns the old value
    i.e it returns null if there was nothing there earlier
    returns old value if there is already a value
  • Booking logic should be as given below:




  • Advantages:
  • Consistent behavior
  • No performance bottle neck. Rooms can be booked from all threads.
  • No blocking


  • Dis-Advantages:
  • None I could think of


  • +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

    Am curious, why do you try to avoid Java's concurrency tools?

    I hope you find this useful.

    Nimesh Parmar
    Greenhorn

    Joined: Jun 07, 2010
    Posts: 9
    Sarvesh: Thanks for the post and apologies for the delay.

    Roel: Thanks a lot for all the valuable input. I thought my lock/unlock design would work. It did work. I tested it with 800 threads. It did not hang. The processing was interspersed as you had mentioned earlier. But when I read the post from Matthew Workman, I realized that my design would be violating one MUST requirement -
    he current thread gives up the CPU and consumes no CPU cycles until the record is unlocked
    .

    In order to avoid an automatic failure, I decided to abandon that design and stick to wait/notify. Guess what? I just finished testing the code with 2000 threads and no problems.

    I am going to upload today and may be appear for the exam later this week or early next week.

    Roel, Matthew: A BIG thank you to you guys for the eye-openers.
    Roel De Nijs
    Bartender

    Joined: Jul 19, 2004
    Posts: 5278
        
      13

    Glad to hear you were able to clear your doubts and solve your issues
    Nimesh Parmar
    Greenhorn

    Joined: Jun 07, 2010
    Posts: 9
    Roel,

    I just got a mail from Sun. I have cleared the SCJD exam. The actual certificate will be in post in the next 4 to 6 weeks' time.

    Mate, I must thank you and all the others who displayed immense patience with my questions.

    Timelines:

    Assignment submitted: 30 July 2010
    Appeared for essay: 03 AUG 2010
    Results Received: 17 AUG 2010
    Certificate: In the next 4 to 6 weeks

    Thanks.

    Roel De Nijs wrote:Glad to hear you were able to clear your doubts and solve your issues
    Roel De Nijs
    Bartender

    Joined: Jul 19, 2004
    Posts: 5278
        
      13

    Congratulations Nimesh!

    Also happy to see it took just 2 weeks for grading your assignment. Nowadays the grading process seems a lot faster than before the acquisition, for Oracle
     
    I agree. Here's the link: http://aspose.com/file-tools
     
    subject: Will this locking mechanism be allowed?