• Post Reply Bookmark Topic Watch Topic
  • New Topic

Prioritizing a Thread based on when it went in the wait state  RSS feed

 
Seema Kekre
Ranch Hand
Posts: 35
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I have been learning about multi-threading in Java for some months and have practiced them with examples. From what I know, when using wait/notify, if n threads are waiting on an object, one random thread is notified when notify() is called. Recently, for an interview I was asked this question:

If there are 10 threads T1 to T10, and T2-T10 are dependent on a result from T1 and are waiting for that object. Now the first thread that enters wait for this object should be given higher priority than the next and so on. So eg: T4 calls wait() before T3, then when the notify is called T4 should be notified and should run before T3.

I think you can use a static volatile member which has some value say 10 and you can setPriority for every Thread just before going into wait() by using this static value and then reduce the value by 1. Then use notifyAll. Since it is guaranteed that the thread with the highest priority will always be selected to run before the thread with the lowest priority, this should work right?
Or is there another technique to solve this problem?

<Edit> Already see a problem with this since priority can be 1-10 or 1-5 depending on the OS, so this solution does not work and does not even scale to more threads. Another solution I thought of was to put the Threads in a queue in the order of them calling wait() but then how to select them.
 
Mike Simmons
Ranch Hand
Posts: 3090
14
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Well, the easiest solution I know of is to use a java.util.concurrent.locks.ReentrantLock, and use the constructor that allows you to specify fair = true. Then create a newCondition() with that to represent when the first thread finishes. Thread 1 will signalAll() on this condition, while all other threads await() the condition. The fairness parameter will cause longer-waiting threads to be given priority.

Alternately (if you don't trust the unspecified fairness algorithm, or if your interviewer just wants to make life more difficult by rejecting use of the java.util.concurrent packages), you can manage this explicitly yourself. For every other thread after the first, create a new Object of some sort whose purpose is just to serve as a monitor for that particular thread. Let the new thread call monitor.wait(), and put this newly-created monitor object in a FIFO structure of some sort. Like say a LinkedList where you add() new objects from the end, and remove(0) them from the beginning. This way when you call notify() on a given monitor, you know that it will always notify the thread you wanted, because only one thread ever waits for a given monitor. And you always have a way to find the longest-waiting thread that has not yet been notified.
 
Seema Kekre
Ranch Hand
Posts: 35
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thanks Mike. I was aware of Lock, but unaware of the fair boolean in the constructor of ReentrantLock or what it did. Your second solution is great as well. I need to learn and practice multi-threading a lot more.
 
xsunil kumar
Ranch Hand
Posts: 147
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi Mike,

I am also facing this type of problem.As you have already explained how to acheive it but it is not clear completely to me. If you have some code snippnet for your approach 2 then it will be very helpful for me.

Please share some code so that i can also understand and write my own implementations.

-Sunil
 
Sergey Babkin
author
Ranch Hand
Posts: 50
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
In practice notify() probably already does what you need, at least most of the time. Thinking of how the implementation would work internally, the easiest way would be to make a list of waiting threads, so the wakeup would also go in sequence. Whether the priority would be taken into the account is a separate question, it depends on whether this list building would take the priority into account. And the easiest way is to list the threads regardless of priority :-)

Remember, the scheduler priority matters only between the threads that are ready to run. When the threads are waiting, and one of them is notified, the scheduler policy doesn't apply. It's the internal policy of notify() that matters.

My guess is that the manual says "random thread" to allow the notify() implementations that do or don't take the priority into account.

Try to write a simple program and see what happens. Most likely it already does what you wants (though maybe with some degree of fuzziness).

If you really, really want a strict ordering, you can try something like this:



This way each thread gets its individual notification, and they go in a guaranteed order. The single flag for notification becomes also split per thread. Note that it must be set to false under the common list synchronization to avoid a race.
 
It is sorta covered in the JavaRanch Style Guide.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!