Notifying a particular client

[Manish Kumar]

Hi everyone,
I'm implementing the lock by using an ArrayList and adding a wrapped recordNumber in this arryalist. I call wait() over the ArrayList object if the record is already locked.
now I want to implement the unlock(int recNum) method so that it can only (directly) notify one of those threads (clients) which are waiting for this recNum.
because taking the lock over the whole collection object doesn�t guarantee that a client, who is holding a particular record lock, will be notified..
Is it possible??
any idea will be appreciated
Regards,
-Manish

[Robin Underwood]

I'd recommend searching through this site for information on locking and unlocking. You can lock just one record, and have a client wait until it is notified that a lock has been released by another client.

[Marcus Beale]

I am also trying to figure out how to notify only clients that are interested in the record that was just unlocked. I have a solution that works by synchronizing, waiting, and notifyAll on a LockManager class. This does not seem terribly efficient, because every time any record is unlocked any client currently waiting will be notified. In all likelihood they won't care that record x was unlocked when they are waiting on record y, so they will simply go to waiting again.

I have a hashmap of LockObjects associated with each record, however I can not think of a way to only wait only the LockObject associated with the record of interest (and of course only notify threads waiting on that particular LockObject). I believe this is impossible to do!

My LockManager needs synchronized public methods to operate correctly; there is no getting around that. I believe that when I enter a second synchronized block on the associated LockObject (to wait on it or notifyAll on it) I create a deadlock situation. Thread 1 locks record A. Thread 2 attempts to lock record A, but can’t. Thread 2 does NOT given up the monitor on the LockManager and goes into waiting on the LockObject. Boom, nobody can do anything with the LockManager now, because Thread 2 keeps the LockManager monitor! Thread 1 can not unlocking the LockObject Thread 2 is waiting on, because it can’t use the LockManager.

I can not figure out how to give up the lock on the LockManager when waiting on the LockObject. If I use a synchronized blocks I will always either have both monitors, or at some point have no monitors. Either situation is bad.

Any suggestions? I would post some code, but it's probably easier to understand my question from the description. I've heard people casually mention in other posts that they had a solution similar to what I’m describing. I'm beginning to question if they had actually tested their solution. Or maybe I’m missing some big piece of the puzzle. Anyone care to comment?

Thanks,
Marcus

[Serkan Yazici]

Hi Marcus,

I've solved the problem you've mentioned by not synchronising on the hashmap but using an already synchronised hashmap (by creating the hashmap with Collections.synchronizedMap()). This type of hashmap guarantees individual containsKey/get/put method calls are thread-safe (serialised).

Have a look at my locking design at this thread.

[Marcus Beale]

Serkan,

I believe your locking mechanism is flawed.

 
1)    Object lockObj = lockList.get(key);
2)    if (value != null) {
3)        lockObj.wait();
4)    }

Consider the following scenario. Thread A locks record X. Thread B attempts to lock record X and finds that it is already locked (statement 1 is finished but statement 2 had not been executed).
Thread B is swapped out of the processor. Thread A unlocks record X. Thread B is swapped back in the processor. Thread B waits on lockObj object. Thread B will never wake up, because the lockObj was taken out of the hashMap by thread A (the notifyAll will never be called on this object). Event if you reuse the lockObj in the hashmap, there is no guarentee that anyone will ever attempt to lock and unlock record A again (which would be necessary to wake Thread B back up).

This problem arises because your operations are not atomic. Without a synchronized block or method you can not quarantine that things will not change in between statements (and sometime even during them, statements are not necessarily atomic).

Admittedly maybe you are willing to take this risk for the efficiency improvement, but I don't believe it's correct.

,Marcus

[Marcus Beale]

To clarify a little:

I can not figure out how to give up the lock on the LockManager when waiting on the LockObject. If I use a synchronized blocks I will always either have both monitors, or at some point have no monitors. Either situation is bad.

I believe Serkan's solutions falls under the "no monitors" category, which is bad for the previous stated reasons.

The "both monitors" category is bad, because it can lead to dead lock.

,Marcus

PS. Does anyone know how to edit postings?

[Jason Hocker]

If this is a bad idea, how did Serkan receive 80/80 for locking?

I would think a solution that could lead to deadlocks should not get full credit.

[Marcus Beale]

Even graders make mistakes, maybe that's not on their list of things to check. Either way I think it's still incorrect. If you think it's correct, find a hole in my logic. I'd like to know if I'm wrong.

I was thinking about the issue and believe I've come up with a solution.

1) Create an attomic operation that generates a new lockObj assoicated with a record or returns an existing lockObj. Reuse existing lockObjs. Call this operation getOrCreateLockObj().

2) As soon as you enter a lock method you get the associated lockObj. Then you synchronize on that object.

Object lockObj = locks.getOrCreateLockObj(recNo);
synchronized (lockObj) {
  ...
}

This approach allows you to grow your number of lockObj dynamically. The only problem I can see is that the number of lockObj in memory will grow (up to the number of records). I'm thinking the solution would be to every so often remove old/unused lockObj. I haven't figured out how to tell if a lockObj is unused. Does anyone know a way to find out if threads are waiting on an object? I guess you could duplicate the wait information.

Does anyone see an error in this approach?

,Marcus

[Andrew Monkhouse]

Hi Marcus,

Originally posted by Marcus Beale:
To clarify a little:

I can not figure out how to give up the lock on the LockManager when waiting on the LockObject. If I use a synchronized blocks I will always either have both monitors, or at some point have no monitors. Either situation is bad.

Deviating from Serkan's idea a little, if you used a mutable object in your map, then your code can become two separate synchronized blocks:

synchronized (mapObject) {
    getMutableObjectForRecord(x);
}
 
synchronized (mutableObjectX) {
    while (mutableObjextX.isLocked()) {
        wait();
    }
    mutableObjectX.lock();
}

So you no longer have the potential deadlock of owning two mutexs at once.

There is a period where you do not own any mutex, but there is no state that can change during that period, so this will not cause a problem.

Originally posted by Marcus Beale:
PS. Does anyone know how to edit postings?

If you would like to edit any of your posts you can click on the button that is just above your post.

Regards, Andrew

[Andrew Monkhouse]

Hi Marcus,

Seems you posted about the same time as I was preparing my post.

Your new solution looks very similar to mine.

Originally posted by Marcus Beale:
The only problem I can see is that the number of lockObj in memory will grow (up to the number of records). I'm thinking the solution would be to every so often remove old/unused lockObj. I haven't figured out how to tell if a lockObj is unused. Does anyone know a way to find out if threads are waiting on an object? I guess you could duplicate the wait information.

Perhaps you should look at what WeakReferences or SoftReferences can do for you . You can just ignore the memory issue - if the JVM needs the memory and you are not using an object at the time, then it will be automagically removed. Then the next time you need the object, you will just create a new one.

(Although this is hardly likely to be a huge drain on your memory. Consider how many records you would have to be storing key/value pairs for before you even get a noticable amount of memory use. And how much memory does a standard server come with?)

Regards, Andrew

[Marcus Beale]

Andrew,

Thanks for the sanity check. That's a very good point about the weak references. I knew about them, but have little experience using them. I haven't quite reached the point yet where I know when to use them.

Now the only question left is weather to actually implement this change since I already have a fully functioning solution. This is a good example of when the simpler solution works and the better solution is just more efficient. Of course I think it's a lot more efficient, so I will probably use it, but I can see the argument both ways. Even if I don't use the new lock manager in my certification, I'll probably still code it up for practice. I'll have to see if this solution complicates the code very much. My hunch is that it won't.

A clear design, such as will be readily understood by junior programmers, will be preferred to a complex one, even if the complex one is a little more efficient.

Thanks again,
Marcus

[Serkan Yazici]

Hi Marcus and all,

If you have noticed I didn't post the whole locking code in my previous post:

  
if (lockList.containsKey(key)) {
   Object value = lockList.get(key);
   [B]...[/B]
}

I called wait() inside a synchronised block similar to your second solution (otherwise wait() would have thrown IllegalMonitorStateException).

My post was merely a pointer to get people thinking, and your second solution was very close to what I've done

  
Object value = lockList.get(key);
 
while (value != null) {
    RecordLock recordLock = (RecordLock) value;
    // Check if caller already owns the lock; if so silently return
    ...    
    // Check for deadlock (is the owner also waiting for me?)
    ...
    // Otherwise, wait on the record lock object...
    synchronized (recordLock.getLock()) {
        try {
            recordLock.getLock().wait();
        } catch (InterruptedException ie) { }
    }
    value = lockList.get(key);
}
 
// Waiting is over... Lock the record if it still exists
...

And like Andrew said, unused RecordLock object will be slowly discarded by the garbage collector (after unlocking I don't keep them in the lockList anymore).

[Marcus Beale]

Serkan,

Your code is still incorrect. You should read my previous post more carefully.

1)    Object lockObj = lockList.get(key);
2)    if (value != null) {
3)        synchronized (lockObj) {
4)            lockObj.wait();
5)        } 
6)    }

The reason the above code is flawed (as Andrew pointed out) is because you are depending on state information between statements 1 and 2 to remain the same and they are not inside a synchronized block.

You must go into the synchronized block right away. Another subtle point is that that the lockList.get method MUST return an object and it MUST reuse a lock object if it already exists. If it returns null then you are in trouble even if you go into a synchronized block right away (This is because you are now depending on the record value not to be locked in between your statements.) I could explain in more detail, but it's going to look a lot like my previous post. This has been a very good thread so far - make sure you READ (not glance over) what has been previously posted.

I'm not saying your solution was not helpful - it was a nice incremental step to a solution that worked. Your input was helpful to me. I just want to return the favor, by making sure you understand why the above solution is wrong and the solution posted by myself and andrew is correct.

,Marcus