Elegant solution to waiting without CPU activity?

[Reza Rahman]

I am just curious, but has anyone come up with an effective, elegant way of waiting for a lock to be released and not consuming any CPU without introducing a significant amout of complexity? Have most people simply ignored this requirement? I wonder if this is a potential source of the mystereous 44/80 locking score?

To be honest, I find this to be a very awkward requirement given the Java wait/notify model of handling synchronization, so I am going to ignore it even if it means loosing a few points unless there is simple, elegant and intuitive way of meeting this requirement.

As always, thanks for your valuable insights and lively discussion!

[Daniel Dalton]

My instructions say (and I'm pretty sure they're similar to other peoples too):

If the specified record is already locked, the current thread gives up
the CPU and consumes no CPU cycles until the record is unlocked.

As I read that, it means that your waiting threads should do nothing (ie. just wait) UNTIL the record is unlocked. In most cases, that probably means something like until the record number is removed from whatever internal structure you have chosen to use. At THAT point, the record is not locked, and using 100% CPU to have all waiting threads wake up and fight over who gets the lock next is not prohibited by the instruction.

Also, think about what happens if you use notify() and the thread selected to wake up can't / doesn't actually do anything about the lock.

I think that Sun are simply telling you not to do something really nasty like busy-wait for the lock to become available.

As far as 44/80 scores go, how many people do deadlock detection?

[Darya Akbari]

I agree with Daniel, I see this requirement as a hint to use synchronize and a description on how the thread scheduler works.

Regards,
Darya

[Uwe Schäfer]

concerning deadlock detection:

do you really think it is necessary to get the full score ? even if it is virtually impossible for one thread to aquire 2 locks at the same time ?

and if so. what would be a good pattern to do so ? ThreadLocal stuff sound a bit too heavy to be introduced in this work.

please share your thought about this.

[Darya Akbari]

I am not sure what Daniel means by deadlock detection. Maybe he talks about deadlock prevention which I think all of us must take care otherwise we fail.

Kathy Sierra say in the K&B book's SCJD part:

If there’s even a chance that your design could lead to deadlock (it doesn’t have to actually cause deadlock right before the assessor’s eyes) then you can probably kiss that $400 goodbye.

As far as I know nobody knows where this ominous 44/80 score in locking comes from.

I think for deadlock detection there are patterns (but no design pattern ) that detects potential deadlock traps.

Do a search and you find them.

Regards,
Darya

[Daniel Dalton]

Deadlock's one of those tricky things. I'm not convinced that you can actually prevent it in the general case. For this project, you can specify a contract for clients to follow which (if followed) will avoid deadlock occurring. However, there's nothing in my instructions which say HOW Sun intend to test my implementation. If I were testing an interface like they've asked to have developed, I'd test it in isolation.

What does your implementation do when you invoke:

  
Thread 1              Thread 2
Data.lock(5);         Data.lock(6);
sleep(5000);          sleep(5000);
Data.lock(6);         Data.lock(5);
sleep(5000);          sleep(5000); 
Data.unlock(6);       Data.unlock(5);
Data.unlock(5);       Data.unlock(6);

I'm sure your project code will never do such a stupid thing, but does that mean Sun won't try it to see if you give an error or just sit there and hang?

My implementation detects the problem and throws an RuntimeException - which I think is the best I can do.

That's all I meant about deadlock detection - hope that helps a bit!

[Darya Akbari]

Hi Daniel,

in my implementation the scenario you described can never happen . You describe the typical deadlock scenario. Exactly that thing that we all have to take care that this can not happen :roll: .

Whether Sun's testing code or our own code access the data object, you must prevent this deadlock ever to happen.

The answer can not be a RuntimeException, because a customer or maybe the assessor will never accept it.

Look to my test code result:

  
Thread1: lock 5
Thread1: read 5
Thread1: update 5
Thread1: unlock 5
Thread4: lock 5
Thread4: read 5
Thread4: update 5
Thread7: lock 6
Thread7: read 6
Thread7: update 6
Thread7: unlock 6
Thread4: unlock 5
Thread5: lock 5
Thread5: read 5
Thread5: update 5
Thread8: lock 6
Thread8: read 6
Thread8: update 6
Thread5: unlock 5
Thread8: unlock 6
Thread6: lock 5
Thread6: read 5
Thread6: update 5
Thread6: unlock 5
Thread2: lock 5
Thread2: read 5
Thread2: update 5
Thread2: unlock 5
Thread3: lock 5
Thread3: read 5
Thread3: update 5
Thread3: unlock 5

As you can see, you never get a second lock on record 5 unless you previously unlock record 5.

So it's a question of deadlock prevention and not detection. I think the keyword here is synchronize and adapting it in the right way so that no deadlock can ever happen.

Regards,
Darya

[Daniel Dalton]

Agreed. Looking at your test results, no single thread ever holds a lock on more than one record at a time. I ensure the same in my project. And I agree, this prevents deadlock occurring in your project.

Now - hypothetically, given that the only thing Sun knows for certain without even looking at a line of code is that you will have a class called Data which implements a certain interface, wouldn't you write a test to hammer that class? I would. I would write a bunch of multi-threaded tests that threw all sorts of things at Data just to see if anything broke. One of the the things I'd try would be to deliberately cause a deadlock - just to see what happened. implementations which do nothing about detecting deadlock will hang.

Notice that I'm not suggesting your application would hang - it wouldn't create a deadlock in the first place!

As for scoring those classes, who knows? Personally, I think its worth doing and might affect the score - but that's just my opinion.

Regards,

Daniel.

[Darya Akbari]

Hi Daniel,

I understand your fear . And your fear is right. I'm sure they will try to create a deadlock situation.

But against what can they test? They can only test against your data interface (in my B&S case it's DB.java). And you are the one who implement this interface. So you take care of all that fell into your Data.java class.

One of the things you care in Data.java is exactly the locking mechanism and deadlock prevention.

Good luck!

Regards,
Darya

[Daniel Dalton]

Actually, you might be right. I was about to disagree and say that all a testing method has to do is instantiate an instance of Data (DB in your case) and create a couple of threads that directly invoke lock() on that instance. If you can do that, you can deliberately create a deadlock (by having each thread lock more than one record appropriately).

However, you just made me realise that they don't know how to instantiate your class, because all they supplied was an interface - it could use a factory method and have no public constructor for instance. Thanks for the insight!

Regards,

[Reza Rahman]

Just to summarize, I take it no one takes the "consumes no CPU" requirement literally and focus on deadlocks instead?

[Lara McCarver]

If the specified record is already locked, the current thread gives up
the CPU and consumes no CPU cycles until the record is unlocked.

I think they are requiring you to handle thread synchronization via wait() and notifyAll() instead of using sleep() and polling. In The SCJD Exam book, by Habibi, I looked at how he is doing his reserveDVD() method, which is conceptually the same as lock(). This is on p. 129. He uses wait() and notifyAll(), but he is synchronizing and waiting on the entire vector of reservedDVDs.

I think this is close to fulfilling the requirements, but not quite: Suppose that there are 5 existing clients waiting to update various DVDs. They would all be stopped at the wait line. While they are waiting, they aren't using any CPU, but let's say that the client who currently owns the active reservedDVD is one who is updating the Eric Clapton DVD. Every one of the 5 clients is going to be notified, and they are all going to have to execute the while() clause, which entails doing a search of the vector of reservedDVDs. So you can't really say that they don't use any CPU.

So suppose that you lock individual DVDs, but you use the same type of synchronize-wait logic. Then you can have a loop like this:

synchronized (oneDVD)
    while ( oneDVD.canLock() == false )
        oneDVD.wait();

Waiting on the individual DVDs is better than waiting on a vector of them but there are still some CPU cycles in the oneDVD.canLock() call... though not very many.

The only way I can see to improve on this is to keep track of all the individual clients that are waiting for a particular record, and then notify the next in line. Though I haven't thought about out how to do that yet. And I think I remember reading in this forum about at least one person who tried to do that. I guess if you were doing that, there would be no question that you were fulfilling the requirement, and he did say that he passed The client thread really would not use any CPU until it was ready to. Although obviously, the mechanism that was managing all the waiting clients would consume some CPU.

[Lara McCarver]

I was trying to figure out whether you really need a thread manager, so here is the exact text for my lock method, once again:

// Locks a record so that it can only be updated or deleted by this client.
// If the specified record is already locked, the current thread gives up
// the CPU and consumes no CPU cycles until the record is unlocked.
public void lock(int recNo) throws RecordNotFoundException;

This does not say that the current thread cannot consume CPU cycles "until the recNo is locked as requested". It does say "until the record is unlocked". So if you have code for a specific record like I showed above:

synchronized (oneDVD)
    while ( oneDVD.canLock() == false )
        oneDVD.wait();

Once this code starts to wait(), it is not going to use any more CPU cycles until oneDVD.notifyAll() is called, and as long as that only happens when the record is unlocked, I think you are safe.

[Reza Rahman]

Lara:

Thank you very much for sharing your thoughts. I have come to essentially the same conclusions myself. FYI, you could arrive at the exact solution with the following (extremely ugly) algorithm that essentially almost undermines Java's built-in capabilities:

Synchronize on the list of record locks:
 
    If the record you currently seek is locked:
        Get yourself a "ticket" and add yourself to the end of the queue of 
        Objects waiting for this record.
        Wait for your "ticket" to be called. In Java terms, simply call 
        "wait" on your "ticket" object.
        When your turn is here:
            Lock the object.
            Do your stuff.
            Unlock the object.
            Get the next poor sap's ticket and let him know it's his turn. 
            In Java terms, call the notify method on the last item on the 
            "wait" queue.
 
    If the record is not locked,
        Lock the object.
        Do your stuff
        unlock the record.
        Get the next poor sap's ticket and let him know it's his turn. In 
        Java terms, call the notify method on the last item on the "wait" 
        queue.

While this "deli line" style algorithm is neat and all, I would raise an eyebrow at a real-world client who would actually be interested in such contortion to save a few milliseconds of CPU time!!

I honesty don't think this is what Sun has in mind given the relatively elegant build-in wait-notify model of Java. Personally, I think I am favoring the simplest and most intuitive aproach (all waiting threads get woken up and check the record they are interested in as long as any record is unlocked).

Hopefully the moderators won't whack me for posting too much pseudocode Thanks all.

Reza

[Reza Rahman]

Correction to the code posted above: the synchronization is meant to be on each "logical" unit of work that needs isolation, not the entire pseudocode. Typically, this is the methods that the algorithm above can be broken down into that deal with the criticially thread safe elements (lock, unlock; but not doStuff method). Thanks.

Reza

[Lara McCarver]

More locking notes...

An interesting thing I noticed is that Java seems to has a built-in Lock interface and a couple of implementations... though we probably aren't suppose to use it, it's not perfectly suitable, etc. I have the Java 1.5 documentation, so I don't know when this was added, but it would be interesting to look at the source for it, though I'm probably too lazy.

I have also been thinking about how to do locking for the create() method (I am currently leaning towards having CREATING be a lock state), and how to test locking (no good ideas yet... but I like junit-style testing, and in theory you could do that if you somehow introduced artificial pauses in your DB methods, for testing only of couse).

[Reza Rahman]

Lara:

The new locking and concurrency features you are mentioning were added as a part of the concurrent package in J2SE 5.0 (Tiger). I don't think you are obliged to use them if you are using Java 5.0, in fact, I don't think the additional featues offered would add to anything for the assignment (as far as I know).

Reza

[John Smith]

I second Lara -- it's hard to think of anything more elegant than the standard wait()/notify() mechanism when it comes to efficient CPU utillization.

[Reza Rahman]

Lara:

Sorry about not fully addressing your previous post, I was not quite sure if that was a queue for me to share my own ideas...

In regards to synchronizing the "create" method, the particular assignment I have makes matters a little bit tricky (what a huge surprise, right?). Unlike the delete and update method, the create method does NOT require a lock cookie, meaning that there is no implicit design contract for the client code to obtain a lock (hence de facto synchronize on the record). As far as I can see, this means the create method is left to its own recourse to accomplish synchronization (poor old fellow!). This might be accomplished in two ways:

1. Declare the method to be synchronized and let the JVM deal with it (this is what I am currently doing, but I am re-evaluating my choice -- in the end I might stick to this).

2. Lock on an "invisible" record, as you mentioned, such as -1, negative infinity, etc. This would essentially mean wrapping the "meat" of the method within the boundaries of a lock-unlock sequence. Conceptually, this would translate to locking a "operation" instead of a physical record. Incidentally, a table lock would follow similar lines. I am currently not leaning towards this solution as I am trying to keep all lock/unlock invocations out of my data class (maybe because of little more than code-geek vanity).

As for testing locks, I don't see any effective methods other than old-fashioned debugging log statements. Let me know if you find anything better...

Hope this helps.

Reza
[ June 01, 2005: Message edited by: Reza Rahman ]