Win a copy of The Little Book of Impediments (e-book only) this week in the Agile and Other Processes forum!
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

consumes no CPU cycles solutions...

 
Anton Golovin
Ranch Hand
Posts: 530
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi. Maybe my post will help you to decide on your notify solution. I chose the easy way out. I waited on the Data class and called notifyAll() on the Data class. It is very inefficient. I will describe the three possible solutions to notify later in the post. But I did not get penalized for it. (I got 71/80 because I made a slight error in another issue.)

Solution 1, the simplest: wait and notifyAll on the Data class. Every thread gets woken up. As you can imagine, this can be very slow.

Solution 2, the intermediate: when locking using a Map, use the Integer object (the key) to wait on and notifyAll on. This way, only the threads interested in a particular record will be woken up and compete with each other.

Solution 3, the advanced, the one which actually is the one Sun says should be implemented: use a monitor object per thread and a FIFO data structure per record; each thread waits on its monitor object and the FIFO structure is used to pop a monitor object to call notify on. This is the most efficient implementation, but I can assure you you will not be penalized if you choose the middle ground and go with Solution 2.

This third solution does not preclude using the Thread object itself as that monitor [correction: only in thin clients, but not for rich clients, in RMI environment]

Hope this is helpful in terms of the CPU cycles.
[ November 22, 2004: Message edited by: Anton Golovin ]
 
Jim Janssens
Ranch Hand
Posts: 210
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Peter, if you looked at my version of the pseudo code, can you post your findings here if possible. I also have some other questions regarding this.

As for example: what do you do with the lockCookie in the unlock method ? There is nothing in your pseudo code that does something with it. And actually, can you do something withit in the unlock method ? I'm doing the cookie check not in the lockmanager but in the data class itself..
 
peter wooster
Ranch Hand
Posts: 1033
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Originally posted by Koen Serneels:
Peter, if you looked at my version of the pseudo code, can you post your findings here if possible. I also have some other questions regarding this.

As for example: what do you do with the lockCookie in the unlock method ? There is nothing in your pseudo code that does something with it. And actually, can you do something withit in the unlock method ? I'm doing the cookie check not in the lockmanager but in the data class itself..


I check that the record is locked and that the cookie matches and throw a SecurityException if it doesn't. I left that checking out as it is the same regardless of the locking strategy, and I wanted to concentrate on the queues. I've answered the other thread as well, the boolean does help, I use one in my real code, but its not necessary.
 
Jim Janssens
Ranch Hand
Posts: 210
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Ah ok thanks.
So if I understand it correctly, you also place the lock cookie on the queue ? So if the unlock() method is entered you lookup the queue, and get the lock cookie of the current locked record. If that doesn't match a SecurityException is thrown...

<edit>

Also: How can you guarantee that a lock is removed after a thread dies ?

I see two scenario's where this might happen:

1. One of the threads in the queue (and thus in wait() state) dies. After it died, the lock object is still on the queue and will be popped after some time. When it is popped in the unlock() method , you assign the current lock to the popped value. next you call notify() so that the waiting thread can continue. But, the thread died. What will happen ?


2. One of the threads dies (so abnormal termination) while it is doing a manipulation (and thus owning the lock) . This way the unlock method will not be executed, even if it is in a finaly I think. So you have :


[ November 22, 2004: Message edited by: Koen Serneels ]
 
peter wooster
Ranch Hand
Posts: 1033
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Anton:
My solution is an implementation of your solution #3. The reason to not use the thread itself as the monitor object is that you really need to store the waiting thread, the cookie and an owner, hence the Lock class.

Koen Serneels:
Your 2 scenarios are correct. I didn't include this stuff in my example since it doesn't change much regardless of which of Anton's locking models you chose.

Also: How can you guarantee that a lock is removed after a thread dies ?

I see two scenario's where this might happen:

1. One of the threads in the queue (and thus in wait() state) dies. After it died, the lock object is still on the queue and will be popped after some time. When it is popped in the unlock() method , you assign the current lock to the popped value. next you call notify() so that the waiting thread can continue. But, the thread died. What will happen ?


The thread can't die, since it's in a wait. It will revive when the wait is notified, or hang around as a zombie thread if never notified.


2. One of the threads dies (so abnormal termination) while it is doing a manipulation (and thus owning the lock) . This way the unlock method will not be executed, even if it is in a finaly I think. So you have :


In this case the thread may have ended, but the lock is held. In my code its now the "holder". There is no guarantee that the holding thread is the same as the waiting thread, especially if you use RMI or connectionless socket networking.

The "owner" in my code is an instance of the Data class that represents a single business command such as "book", it represents a Session. My locking code doesn't care what kind of object the owner is, as long as its something that can be used to identify orphans. When my DataImpl times out on the RMI lease time, I close the Data object. That calls a unlockOwned method with the Data object as its argument, this argument was supplied to the lock method.

The unlockOwned method has the following pseudocode


The effect of this is to interrupt any threads that are waiting for records that orphan Data (or Session) instances wanted to lock. Since the networking is lost on these the InterruptedException will never get to the client, but they don't care and the orphan thread will die. Locks that have been obtained by orphan Data instances will simply be unlocked rather uncerimoniously and if there is another thread queued up it will be notified. Testing this part is very difficult, but it's no easier with either of the other solutions Anton enumerated.
[ November 22, 2004: Message edited by: peter wooster ]
 
Anton Golovin
Ranch Hand
Posts: 530
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi, Peter! I haven't thought on the merits of using the Thread object as the monitor. Now that you mention it should not be, I realize that there is no guarantee that the Thread run for lock is the same run for unlock with RMI (if you are using the rich client and exposing Data class to the client). So it is a bad idea. Even though the queue will provide the correct Thread, there is no way to insure there aren't more than one Thread waiting on it... I think. In the thin client, when one Thread runs the business method, it is conceivable, I think, but hardcoding this into the program is unwelcome, since then you are locked into one type of client... so it is a bad idea.

Alternatively, one could just make up a basic Object. Or whatever type of Object, to minimize memory consumption...
[ November 24, 2004: Message edited by: Anton Golovin ]
 
peter wooster
Ranch Hand
Posts: 1033
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Originally posted by Anton Golovin:
Hi, Peter! I haven't thought on the merits of using the Thread object as the monitor. Now that you mention it should not be, I realize that there is no guarantee that the Thread run for lock is the same run for unlock with RMI (if you are using the rich client and exposing Data class to the client). So it is a bad idea. Even though the queue will provide the correct Thread, there is no way to insure there aren't more than one Thread waiting on it... I think. In the thin client, when one Thread runs the business method, it is conceivable, I think, but hardcoding this into the program is unwelcome, since then you are locked into one type of client... so it is a bad idea.

Alternatively, one could just make up a basic Object. Or whatever type of Object, to minimize memory consumption...

[ November 24, 2004: Message edited by: Anton Golovin ]


While they are waiting the threads that started the waits are the correct threads, since they are suspended on the wait() method. The problem occurs as soon as the wait ends and the logical lock is obtained. At that point the original thread may end, or may be reused by RMI, you have no control over this. If you are using a connectionless socket solution, the thread that locks is guaranteed to be different from the one that updates or the one that unlocks. The main reason for not using the thread itself as the monitor for the wait-notify is that you probably need to keep some additional information such as the cookie, and the object that owns the lock.
 
Anton Golovin
Ranch Hand
Posts: 530
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
So the Thread is a part of an informational package, of sorts?
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic