• 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
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

consumes no CPU cycles?

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

I am completing my choices.txt but found that it seems my lock design below violated the "consumes no CPU cycles" rule.

Because when some other threads successfully locked a record, the notifyAll() method will be called, then the while(lockedRecordHash.containsKey(recNoInt) will consume CPU cycle.

What do you think about my design?

Thanks.

Regards,
Zhang Jin

while (lockedRecordHash.containsKey(recNoInt)) {
try {
lockedRecordHash.wait();
} catch (InterruptedException ie) {
}
}
lockedRecordHash.put(recNoInt, new Long(cookie));
lockedRecordHash.notifyAll();
 
Greenhorn
Posts: 18
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
The notifyAll() problem has been debated before in
this topic. In one of his replies Andrew states that

It seems that candidates are not being penalised for using notifyAll() even though it does go against the "consume no CPU cycles" requirement.


So I guess it's 'safe' to use notifyAll().
 
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 Jin,

It looks like you are calling notifyAll() from within your lock method (as well as from your unlock method). Is that correct? If so, why are you doing this?

Regards, Andrew
 
Ranch Hand
Posts: 124
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
i guess you will have to call notify() instead from your unlock() method, cause it will wake only one thread waiting for the lock, instead of every thread waiting for the lock which will cause more threads to run and try to lock the synchronized object. It will be more inefficient this way.

Just my 2 cents

Rgds,
Clivant
 
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 Clivant,

Originally posted by Clivant Yeo:
i guess you will have to call notify() instead from your unlock() method, cause it will wake only one thread waiting for the lock, instead of every thread waiting for the lock which will cause more threads to run and try to lock the synchronized object. It will be more inefficient this way.

Just my 2 cents

Rgds,
Clivant



Most people write their locking code such that they cannot directly replace the call to notifyAll() with a call to notify() - doing so may result in threads remaining in wait state even after the record they are waiting for has been unlocked.

There is at least one solution that will ensure that only the correct thread gets woken up, thereby meeting the requirement that the waiting thread consumes no CPU cycles. However this is considerably more complex than most locking solutions, and may be harder to understand by our fictitious "junior programmer".

This is one area where we have contradictory requirements, and we have to make a design decision as to which way to go about solving it (and then document that decision ).

Regards, Andrew
 
Ranch Hand
Posts: 531
1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hi, Jin! If you are concerned about notifyAll() waking up too many threads, you may wish to consider locking on the Integer object denoting the record number in your Map, which enables the locking. That way, notifyAll() will only wake up the threads waiting on that particular record. Still, notify() would be even more efficient, but I right off can not come up with a solution... I think it is too complicated for this assignment.

The question with locking on the Integer object becomes that once unlocked, the object is not available from the Map. Therefore, it is necessary to have a Set that contains references to these Integer objects. (You may wish to have lazy instantiation to gradually fill the set with record numbers as they are requested.) In your lock method, you would get the Integer object from the set, synchronize on the Integer object, wait for it to become unlocked, and then enter it into the Map along with the cookie value, then exit synchronized block. In the unlock method, you would synchronize on the Integer object, remove it from the Map, and call notifyAll() on it, then exit the synchronized block.

I am not sure right off which issues this solution may raise, such as deadlock... but it seems to cut down on the number of threads called when a particular record is freed.

In addition to synchronizing on various Integer objects at any given time, you would also have to synchronize on the Map object, to insure data integrity. If you use a thread-safe Map, this should work. Your code would have to acquire the lock on an Integer object, acquire the lock on the Map object, then release the lock on the Map object, then release the lock on the Integer object - for both lock and unlock methods. It does not seem possible for deadlock to occur since all these operations are in same order for all threads.
[ November 16, 2004: Message edited by: Anton Golovin ]
 
Jin Zhang
Greenhorn
Posts: 28
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hi Andrew,

It looks like you are calling notifyAll() from within your lock method (as well as from your unlock method). Is that correct? If so, why are you doing this?



Yes, I am calling the notifyAll() from within my lock and unlock method. By doing that, I just want to wake up those waiting thread. Is there any problem?

Also, thanks for your kindly help. Since it seems that SUN will not penalize the "notifyAll()", I will stick to it. Do not want to make my program too complex.

Cheers,
Zhang Jin
 
Jin Zhang
Greenhorn
Posts: 28
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hi Andrew,

Yes, I am calling the notifyAll() from within my lock and unlock method. By doing that, I just want to wake up those waiting thread. Is there any problem?



Oops, after a second look, I think I made a mistake. I should only put the notifyAll() from within my unlock() method, but NOT in the lock() method. Right?

Once again, thanks all for your kindly help.

Cheers,
Zhang Jin
 
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 Jin,


Oops, after a second look, I think I made a mistake. I should only put the notifyAll() from within my unlock() method, but NOT in the lock() method. Right?



Correct.

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

Hi Clivant,


quote:
--------------------------------------------------------------------------------
Originally posted by Clivant Yeo:
i guess you will have to call notify() instead from your unlock() method, cause it will wake only one thread waiting for the lock, instead of every thread waiting for the lock which will cause more threads to run and try to lock the synchronized object. It will be more inefficient this way.

Just my 2 cents

Rgds,
Clivant
--------------------------------------------------------------------------------



Most people write their locking code such that they cannot directly replace the call to notifyAll() with a call to notify() - doing so may result in threads remaining in wait state even after the record they are waiting for has been unlocked.

There is at least one solution that will ensure that only the correct thread gets woken up, thereby meeting the requirement that the waiting thread consumes no CPU cycles. However this is considerably more complex than most locking solutions, and may be harder to understand by our fictitious "junior programmer".

This is one area where we have contradictory requirements, and we have to make a design decision as to which way to go about solving it (and then document that decision ).

Regards, Andrew



Hi Andrew,

By going by the sequence lock() -> update/delete -> unlock, the first thread to lock the record will not have to wait. The other threads waiting on the record will form a queue for the record. After the first thread finished its job, it will call unlock which contains notify() to notify a thread at the queue to lock the record again. This process is repeated until no threads are waiting for the record, and hence this method is more efficient as to my opinion.

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

Originally posted by Clivant Yeo:

Hi Andrew,

By going by the sequence lock() -> update/delete -> unlock, the first thread to lock the record will not have to wait. The other threads waiting on the record will form a queue for the record. After the first thread finished its job, it will call unlock which contains notify() to notify a thread at the queue to lock the record again. This process is repeated until no threads are waiting for the record, and hence this method is more efficient as to my opinion.

Rgds,
Clivant



This design is a good one for a real production system, but is probably overkill for this assignment. I've actually implemented this in the past in a procedural system. At present I'm using notifyAll in unlock, I may give the Queue solution a try if I get time.

Note it is quite complex, it will require code coverage testing to be sure it actually works. I've found Emma to be quite good for coverage testing.
 
Ranch Hand
Posts: 210
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I do not understand why notifyAll voilates the 'uses no cpu cycles' contstraint ? Can someone explain this to me please ?
My implementation is also done using notifyAll and it goes like this:

3 threads wanting to perform an update on record x, the sequence followed;

-lock record 3
-update record 3
-unlock record 3
-notifyAll

One of the three threads will enter the synchronized lock method (lets say thread number 2) and hereby requires the records lock. The two other threads will also go into the lock method sequentially, after thread 2 left it. But the code in the lock method detects that the record is allready locked so it will invoke the wait() method (releases the objects monitor and waits without consuming cpu cycles, if I'm not wrong...) .

So the result is that record 2 is beging updated by thread 2 while thread 1 and thread 3 are in the wait() state. After thread 2 updated the record, it calls the unlock method which removes the record from the lock map and calls notifyAll().

thread 1 and thread 3 try to aqcuire the objects monitor for further execution of the lock method. One of the two threads will acquire the monitor and lock the record and then update the record etc ...

As long as all the other threads are in wait(), there is no cpu usage by those threads. What has this to do with the notifyAll ? ...

The code to illustrate this:

public synchronized long lock(int recNo)
{
while (dataManager.isLocked(recNo)) {
try {
wait();
} catch (InterruptedException e) {
//Do nothing
}
}
return dataManager.placeLock(recNo);
}

public synchronized void unlock(int recNo, long cookie)
{
dataManager.unLock(recNo, cookie);
notifyAll();
}


public void update()
{
long lockCookie = lock(recNo);
try {
//do update thing
} finally {
unlock(recNo, lockCookie);
}
}
[ November 21, 2004: Message edited by: Koen Serneels ]
 
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 ,

The problem is in the case where you have multiple threads waiting for locks to become available. For this example I am going to have three threads competing for the same lock, but the same rules apply when you have two sets of two threads trying for locks or ...



In that example, Thread C consumed CPU cycles the second time it attempted (and failed) to get the lock on record 5.

Admitedly the CPU cycles consumed are minimal, and candidates do not appear to be penalised for this. But technically it does go against the instructions.

Clivant's solution where he will have a queue of threads waiting for record 5's lock, and only one of those threads will be woken, will solve this issue (assuming I have read Clivant's solution correctly). The disadvantage is that you have to have queues per record - not a big disadvantage, but it does make the code more complex.

Regards, Andrew
 
Anton Golovin
Ranch Hand
Posts: 531
1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hi, Andrew. I think I understand this solution. But I think it is ironic that the thread is going to be responsible for entering itself into the queue Instead of competition, acquiescence
[ November 21, 2004: Message edited by: Anton Golovin ]
 
peter wooster
Ranch Hand
Posts: 1033
  • 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:
Hi ,

Admitedly the CPU cycles consumed are minimal, and candidates do not appear to be penalised for this. But technically it does go against the instructions.

Clivant's solution where he will have a queue of threads waiting for record 5's lock, and only one of those threads will be woken, will solve this issue (assuming I have read Clivant's solution correctly). The disadvantage is that you have to have queues per record - not a big disadvantage, but it does make the code more complex.

Regards, Andrew



I've coded up a version of the queue per locked record solution. It's not as bad as I had remembered. It takes 120 lines of real code as measured by Emma.

I've been able to successfully test it with the following scenarios:
- LockTest with 4 records, 20 threads, 2000 loops, lock-delay-unlock
- DataTest with 200 records, 20 threads, 1000 loops, random DBAccess operations
- manual testing with a server, 2 booking clients and a maintenance client.

This has resulted in 100% method coverage and 90% block coverage on the LockManager. The only unexecuted areas are 3 blocks that throw SecurityException.

To do this I used a LockManager class and 2 private classes, a Lock class representing a single lock and a WaitQueue class representing a queue of waiting locks and the lock holder. Here's the pseudocode:



I have a lot more code, to take care of things like removing orphan locks and waiting threads when connections are lost. Orphan locks are identified by an owner object and the waiting thread.

This does involve nested synchronization in the unlock method. It's safe since its the only place it's done.
 
Jim Janssens
Ranch Hand
Posts: 210
  • 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:
Hi ,

The problem is in the case where you have multiple threads waiting for locks to become available. For this example I am going to have three threads competing for the same lock, but the same rules apply when you have two sets of two threads trying for locks or ...

Regards, Andrew



Ok, thanks for clearing this up. So, if I understand it correctly (please tell me if I'm wrong) the problem with the notifyAll implementation is that a thread may be woken to get the objects monitor (along with the other waiting threads) but that only ONE of the woken threads will actually gain the objects monitor (and hereby gain the logical record lock) . So the other threads are woken (= uses cpy cycles) without any result, since they still end up in the waiting state.

Can't you resolve this issue very easy by calling notify() instead of notifyAll() in the unlock method ? Agreed, its still not bulletproof, since the record could be locked again by a new thread while the notify() is called and the waiting() thread tries to gain the monitor... but at least only one thread consumed cpu cycles and not all the other waiting threads.

PS.

I didn't think of it THIS far. I just thought sun meant with 'uses no cpu cycles' that you must use the appropriate syncrhonization and notify system. You could for example also implement it in a loop that polls every x milliseconds if the record is locked or not...
 
Jim Janssens
Ranch Hand
Posts: 210
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator


[QB]<hr></blockquote>

If I'm correct, you have a lockMap which has a queue per locked recNo. When more then one thread is locking the same recNo, you add the created lock objects to the queue. In the unlock method you pop() a lock object and notify on it so only that thread will get notified (and will always obtain the record's lock).

Now, when I step through your pseudo code:



You only push the lock when a queue allready exists, no ? Like, if no queue exist, create the queue. When the next lock request comes in for the same recNo, you see that the queue exists, so you add the lockObject to the queue.




How do you decide if the wait() is called or it should continue ? Do you check the queue on the lockamp ? And if so, this is out of the synchrnized(lockMap) block, isnt't this bad ? ...

<edit>

My pseudo code:


[ November 22, 2004: Message edited by: Koen Serneels ]
 
peter wooster
Ranch Hand
Posts: 1033
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Yes, I left the details of how to determine if the lock was the holder to the reader. The holder field is part of the waitQueue object, so if there was no waitQueue the new lock becomes the holder in the new waitQueue.

The holder could be the first element in the queue, but its easier to have it as a seperate field. In my actual code I have a flag that works much like the one you have in your pseudocode. It could be determined by its presence in the holder field.
 
Clivant Yeo
Ranch Hand
Posts: 124
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Hi ,

The problem is in the case where you have multiple threads waiting for locks to become available. For this example I am going to have three threads competing for the same lock, but the same rules apply when you have two sets of two threads trying for locks or ...

code:


Thread A Thread B Thread C
========================= ========================= =========================
Gains synchronized mutex
Blocked state
Blocked state
Locks record 5
Exits synchronized block
Gains synchronized mutex
Fails to lock record 5
Enters wait state
(synchronized mutex released)
Gains synchronized mutex
Fails to lock record 5
Enters wait state
(synchronized mutex released)
Gains synchronized mutex
Unlocks record 5
Calls notifyAll()
Enters Blocked state
Enters Blocked state
Exits synchronized block

Gains synchronized mutex
Locks record 5
Exits synchronized block
Gains synchronized mutex
Fails to lock record 5
Enters wait state
(synchronized mutex released)



In that example, Thread C consumed CPU cycles the second time it attempted (and failed) to get the lock on record 5.

Admitedly the CPU cycles consumed are minimal, and candidates do not appear to be penalised for this. But technically it does go against the instructions.

Clivant's solution where he will have a queue of threads waiting for record 5's lock, and only one of those threads will be woken, will solve this issue (assuming I have read Clivant's solution correctly). The disadvantage is that you have to have queues per record - not a big disadvantage, but it does make the code more complex.

Regards, Andrew



Hi Andrew,

My pseudocode is as follows:

1) search for record using record number
2) using the searched record,
synchronized(record) {
if (record is locked)
wait
procede with desired function

}
updateRecord
synchronized(record) {
record.notify()
}
My definition of queue here is the queue maintained by java implicitly on the synchronized object. Waiting threads will form a queue on the record object and when the record object's notify method is called, a thread on the waiting list(queue) will be called to continue with its process.

Correct me if i am wrong.

Rgds,
Clivant
 
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 Koen,

Can't you resolve this issue very easy by calling notify() instead of notifyAll() in the unlock method ? Agreed, its still not bulletproof, since the record could be locked again by a new thread while the notify() is called and the waiting() thread tries to gain the monitor... but at least only one thread consumed cpu cycles and not all the other waiting threads.



Perhaps

This is where the discussion on queue's is leading us (oops, shouldn't give away that too soon ). Somewhere earlier in this topic I made mention that just changing a notifyAll() to a notify() might cause temporary thread starvation if you did not have per record queues (or at least I hope I did ).

Consider the following scenario where we have four threads competing for two different record locks using notifyAll() on the common mutex:



Now if that gets changed to a notify(), Thread D will temporarily be starved, because Thread B was woken by the notify() and it just went back to wait state:



Note that the thread starvation is only temporary since eventually thread A will unlock record 1, which will wake up either thread B or thread D. Worst case it will wake thread B, so thread D will remain sleeping until thread B unlocks it's record. Regardless, this thread starvation is still a bad thing.

Which brings us back around to the concept of queueing - if you had a queue of threads just waiting on record 2 in the above example, you could have called notify() on that queue, and only woken a thread which really wanted record 2.

Regards, Andrew
 
peter wooster
Ranch Hand
Posts: 1033
  • 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:
Which brings us back around to the concept of queueing - if you had a queue of threads just waiting on record 2 in the above example, you could have called notify() on that queue, and only woken a thread which really wanted record 2.



The queue algorithm I described above actually has a queue of waiting threads for each locked record. This allows us to wake up the thread that has been waiting the longest for the record when we unlock it, by calling notify on the top entry on the queue, not on the whole queue.
 
Greenhorn
Posts: 23
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
一定要使用notify,不要用notifyAll。否则会被扣除很多分。
 
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 Zhong Bo Li

Originally posted by Zhong Bo Li:
一定要使用notify,不要用notifyAll。否则会被扣除很多分。



Rough translation: "Certainly must use notify, do not have to use notifyAll. Otherwise small amounts can be deducted"

Is that correct?

We have seen that the great majority of candidates use notifyAll without loosing marks. So this does not appear to be something the examiners are too strict on.

We seem to be having this discussion in about three threads at the moment and I have mentioned before that getting a perfect solution is not absolutely required. But it is certainly interesting to try and get the best solution and it is fun to do.

I also mentioned at the start of this thread that getting a perfect solution may require more code and/or more complex code which may violate other requirements for simple to read/maintain code. So this is really up to individual candidates: as long as they document their decisions, they should be OK.

Back to the rough translation of your response: Please remember that although this web site is accessible all over the world, we need a common language so everyone can benefit. We have standardised on English (it is the language of the owners of the web site, and the majority of users know it). If you do want to post in Chinese, please also provide a translation so that others can benefit.

Thanks and regards, Andrew
 
Zhongbo Li
Greenhorn
Posts: 23
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Sorry,my english is very pool, I may reading and understand some discussion, but I feel defficulty to writing my point of view in english.

I guess that maybe the owner of the thread is a chinaman, so I post reply in cinese.

I'm sorry, I don't know here have standardised on English, I'll be in english later.
 
reply
    Bookmark Topic Watch Topic
  • New Topic