Java Forum / First Aid / June 2005
How to run tasks with priority?
George George - 29 May 2005 10:03 GMT Hello everyone,
I want to run tasks with priority, i.e. among several simultaneous running tasks, the task with the higher priority will have more chances to occupy CPU time. I have the following 2 issues dealing with the implementation of such feature.
- To define each task as a thread or as a method? How to change the priority of each task dynamically when they are running?
- The priority feature of Java thread does not meet my requirement, since I can not define priority precisely. For example, I want to define that a task with priority A will occupy CPU time 3 times than a task with priority B.
I am wondering whether I can find similar open source projects or tutorials?
Thanks in advance, George
Boudewijn Dijkstra - 31 May 2005 18:03 GMT > Hello everyone, > [quoted text clipped - 4 lines] > > - To define each task as a thread or as a method? It would generally be wise to allocate a thread for each task. How you define the tasks, doesn't matter much.
> - How to change the > priority of each task dynamically when they are running? Thread#setPriority(int)
> - The priority feature of Java thread does not meet my requirement, since I > can not define priority precisely. For example, I want to define that a > task with priority A will occupy CPU time 3 times than a task with priority > B. You can accomplish this behaviour with the Thread#yield() method.
> I am wondering whether I can find similar open source projects or tutorials? Similar to what?
George George - 01 Jun 2005 03:33 GMT Thanks Boudewijn,
Your reply is very helpful! I found that if I use priority feature of Java thread, then I can only have (MAX_PRIORITY - MIN_PRIORITY) different priorities, which may limit my application. I am wondering whether there are any alternate solutions which may have more different priorities.
> You can accomplish this behaviour with the Thread#yield > () method. How can I utilize utilize yield? Could you please give me a simple sample?
regards, George
Boudewijn Dijkstra - 01 Jun 2005 17:54 GMT > Thanks Boudewijn, > > Your reply is very helpful! I found that if I use priority feature of Java > thread, then I can only have (MAX_PRIORITY - MIN_PRIORITY) different > priorities, which may limit my application. I am wondering whether there > are any alternate solutions which may have more different priorities. It sounds like you need to use synchronization, not priorities. With synchronized{} blocks you can make threads wait for eachother at fixed points.
>> You can accomplish this behaviour with the Thread#yield >> () method. > > How can I utilize utilize yield? Could you please give me a simple sample? If two threads have the same priority and execute the same code, adding a yield call to one of those, could make it run about twice as slow.
George George - 02 Jun 2005 03:44 GMT Thanks Boudewijn,
> It sounds like you need to use synchronization, not > priorities. With synchronized{} blocks you can make > threads wait for eachother at fixed points. It is a very good idea! I am not quite familar with the technology you mentioned. Could you please provide me a simple sample?
> If two threads have the same priority and execute the > same code, adding a yield call to one of those, could > make it run about twice as slow. I am wondering why should I use yield to make one thread run slower than another one. I think thread with equal priority should have the same chance to run. What is your purpose of using yield?
regards, George
Boudewijn Dijkstra - 02 Jun 2005 17:48 GMT > Thanks Boudewijn, > [quoted text clipped - 4 lines] > It is a very good idea! I am not quite familar with the technology you > mentioned. Could you please provide me a simple sample? Upon entry of a synchronized block, the thread waits to acquire a lock on the specified object. Only one thread can hold the same lock at the same time. Upon exit of the synchronized block, the lock is released. At this point, other threads waiting to acquire the lock, may acquire the lock and then continue execution. In the following (untested) example, Task1 will execute 3 times as slow as Task2.
class LockHolder { private static final Object lock = new Object(); public static Object getLock() { return lock; } } class Task1 implements Runnable { private static final Object lock = LockHolder.getLock(); public void run() { while (true) { synchronized (lock) { stuff(1); } synchronized (lock) { stuff(2); } synchronized (lock) { stuff(3); } } } } class Task2 implements Runnable { private static final Object lock = LockHolder.getLock(); public void run() { while (true) { synchronized (lock) { stuff(1); stuff(2); stuff(3); } } } }
>> If two threads have the same priority and execute the >> same code, adding a yield call to one of those, could [quoted text clipped - 3 lines] > another one. I think thread with equal priority should have the same chance > to run. What is your purpose of using yield? To make the thread give away it's cycle to other threads with the same priority. In other words, to reduce the execution time without reducing the priority.
George George - 03 Jun 2005 04:20 GMT Thanks Boudewijn,
Your sample is very helpful. But I think there is an issue in your sample, which is that we must hardcode the number of sections that a code block will be divided into. For example, in your sample, you hardcoded that Task1 is divided into 3 sections. I am wondering whether there are any approaches which can flexibly define the number of sections in which a thread will be divided into.
> To make the thread give away it's cycle to other > threads with the same priority. In other words, to > reduce the execution time without reducing the > priority. Are there any practical uses that we should give away it's cycle to other threads with the same priority? Should we do it in this approach (yield) manually or simply let JVM to do this.
Have a nice weekend, George
Boudewijn Dijkstra - 03 Jun 2005 17:30 GMT > Thanks Boudewijn, > [quoted text clipped - 4 lines] > which can flexibly define the number of sections in which a thread will be > divided into. You don't actually have to define your code into sections. It should even be possible to change the number of synchronized accesses dynamically, by using a loop inside your main loop:
for (int i = syncCount; i >= 0; ) { synchronized (lock) { i--; } }
> Are there any practical uses that we should give away it's cycle to other > threads with the same priority? Yes. You can use it in a lot of cases when you're using the sleep method, but without the chance of actually idleing the CPU.
> Should we do it in this approach (yield) > manually or simply let JVM to do this. That is a decision that I cannot make for you. ;)
George George - 04 Jun 2005 14:21 GMT Thanks Boudewijn,
>> Thanks Boudewijn, >> [quoted text clipped - 11 lines] > } >} Do you mean that when the current thread leaves a synchronized block, it will release the lock and then other threads will have chances to obtain the lock?
>> Are there any practical uses that we should give away it's cycle to other >> threads with the same priority? > >Yes. You can use it in a lot of cases when you're using the sleep method, but >without the chance of actually idleing the CPU. Do you mean using yield method will idle the CPU? If it is true, do you know how to write a simple program to test that sleep method will not idle CPU, and at the same time yield method will idle CPU?
Have a nice weekend, George
Boudewijn Dijkstra - 04 Jun 2005 21:15 GMT > Thanks Boudewijn, > [quoted text clipped - 18 lines] > will release the lock and then other threads will have chances to obtain > the lock? Yes. And if you've read a primer about Java synchronization, you wouldn't have to ask that question. ;)
>>> Are there any practical uses that we should give away it's cycle to other >>> threads with the same priority? [quoted text clipped - 3 lines] > > Do you mean using yield method will idle the CPU? No. I said that with yield, there wasn't a chance of actually idling the CPU (as long as there are other threads ready).
George George - 06 Jun 2005 06:07 GMT Thanks Boudewijn,
>[quoted text clipped - 3 lines] >> >> Do you mean using yield method will idle the CPU? > >No. I said that with yield, there wasn't a chance of actually idling the CPU >(as long as there are other threads ready). Sorry that I do not express myself very clearly. I mean yield method will make current thread idle on CPU (current thread will not occupy CPU time) and it will give chances to other threads to run on CPU. Am I correct?
regards, George
Boudewijn Dijkstra - 06 Jun 2005 16:47 GMT > Thanks Boudewijn, > [quoted text clipped - 8 lines] > make current thread idle on CPU (current thread will not occupy CPU time) > and it will give chances to other threads to run on CPU. Am I correct? That is correct. But yield will have no effect if the current thread is the only 'ready' one with the same priority.
George George - 07 Jun 2005 08:50 GMT Thanks Boudewijn,
>> Thanks Boudewijn, >> [quoted text clipped - 4 lines] >That is correct. But yield will have no effect if the current thread is the >only 'ready' one with the same priority. Your reply is very helpful! I am wondering how can I write a simple program to verify that the difference behavior of yield method and sleep method. Do you have any good ideas?
regards, George
Boudewijn Dijkstra - 08 Jun 2005 17:25 GMT > Thanks Boudewijn, > [quoted text clipped - 10 lines] > to verify that the difference behavior of yield method and sleep method. Do > you have any good ideas? Make a thread that increments a variable as fast as it can. After every increment it calls an abstract myWait() method that waits a number of milliseconds. One implementation loops yield() until it reaches the wait time. The other implementation simply calls sleep(long).
George George - 09 Jun 2005 10:32 GMT Thanks Boudewijn,
>> Thanks Boudewijn, >> [quoted text clipped - 6 lines] >milliseconds. One implementation loops yield() until it reaches the wait >time. The other implementation simply calls sleep(long). I am wondering whether your testing method will work. Since if there is only one thread in the system, yield will have no effect. But in your description, there are only one thread. Our testing purpose is to verify that yield method will idle CPU (if there are more than one threads running) , while sleep will not idle CPU.
Maybe it is my mis-understanding of your description. It is highly appreciated if you could write down your ideas into sample source codes.
regards, George
Boudewijn Dijkstra - 09 Jun 2005 21:30 GMT > Thanks Boudewijn, > [quoted text clipped - 12 lines] > I am wondering whether your testing method will work. Since if there is > only one thread in the system, yield will have no effect. In this case "no effect" means that it will continue running, i.e. not sleeping.
> But in your > description, there are only one thread. Our testing purpose is to verify [quoted text clipped - 3 lines] > Maybe it is my mis-understanding of your description. It is highly > appreciated if you could write down your ideas into sample source codes. Agreed, but only because I became curious myself. ;) Running the following test application should be accompanied by a CPU-usage monitor program. First it will do a yield-test for 10 seconds, then it will do a sleep-test for 10 seconds. Observe the difference in CPU usage. The getFinalScore method doesn't really serve any purpose, besides maybe the calculation of (TEST_TIME / WAIT_TIME).
public abstract class WaitTest extends Thread { public static void main(String[] args) { WaitTest[] waitTest = new WaitTest[] { new YieldWaitTest(), new SleepWaitTest() }; long TEST_TIME = 10000L;
try {
for (int i = 0; i < waitTest.length; i++) { WaitTest wt = waitTest[i]; System.out.print(wt.getTestName() + ": "); wt.start(); Thread.sleep(TEST_TIME); System.out.println(wt.getFinalScore()); }
} catch (InterruptedException ie) { System.err.println("Interrupted"); System.exit(1); } }
static final int WAIT_TIME = 80; boolean running = true; int count = 0;
public void run() { int i = count; while (running) { try { myWait(); } catch (InterruptedException ie) { break; } i++; } count = i; }
public int getFinalScore() throws InterruptedException { running = false; join(); return count; }
// wait 80 ms public abstract void myWait() throws InterruptedException;
public abstract String getTestName(); }
class YieldWaitTest extends WaitTest { public void myWait() throws InterruptedException { long now = System.currentTimeMillis(); long target = now + WAIT_TIME; while (true) { Thread.yield(); if (target <= now) break; now = System.currentTimeMillis(); } }
public String getTestName() { return "Yield"; } }
class SleepWaitTest extends WaitTest { public void myWait() throws InterruptedException { Thread.sleep(WAIT_TIME); }
public String getTestName() { return "Sleep"; } }
George George - 10 Jun 2005 04:30 GMT Thanks Boudewijn,
>> Thanks Boudewijn, >> [quoted text clipped - 17 lines] >getFinalScore method doesn't really serve any purpose, besides maybe the >calculation of (TEST_TIME / WAIT_TIME). Your sample program is great! You mentioned that I should use CPU monitor program. So I have tried and used performance monitor of task manager of Windows XP (invoked from "My Computer") to monitor CPU usage. Am I correct?
I have found that when yield is running, the CPU usage is very high, and when sleep is running, te CPU usage is very slow. Do you know why when running yield, CPU usage is high? What is CPU busy doing at that time (in my mind, I think CPU has nothing to do when running yield, just as when running sleep)?
Another small issue is that, why you use join method in your getFinalScore method? I have not seen its special functons yet.
Have a nice weekend, George
Boudewijn Dijkstra - 12 Jun 2005 01:07 GMT > Thanks Boudewijn, > [quoted text clipped - 23 lines] > program. So I have tried and used performance monitor of task manager of > Windows XP (invoked from "My Computer") to monitor CPU usage. Am I correct? That is fine for this example. ;)
> I have found that when yield is running, the CPU usage is very high, and > when sleep is running, te CPU usage is very slow. Do you know why when > running yield, CPU usage is high? What is CPU busy doing at that time (in > my mind, I think CPU has nothing to do when running yield, just as when > running sleep)? The API documentation description of yield() is a bit cumbersome. But it is enough for those who are educated in the most important concepts of task scheduling. Sensing that you are not, I will explain what happens when yield() is called.
1. The current thread is paused, but remains ready to run. 2. The task scheduler checks the current priority queue for threads (other than the current one) that are ready to run. 3a. If there are, then perform a task-switch to the first one. 3b. If there aren't, then un-pause the current thread.
Note that, although the current thread is suspended, the CPU always has something to run during steps 1,2,3.
> Another small issue is that, why you use join method in your getFinalScore > method? I have not seen its special functons yet. When 'running' is set to false, the thread does not immediately exit. By calling join(), the thread that executes getFinalScore() waits for it to exit so that it can fetch the *final* score.
George George - 12 Jun 2005 10:16 GMT Thanks Boudewijn,
>> Thanks Boudewijn, >> [quoted text clipped - 23 lines] >Note that, although the current thread is suspended, the CPU always has >something to run during steps 1,2,3. Your description is very helpful and it has answered my question. Do you know whether there exists a tool which can monitor what threads are running on a VM and how much running time they have allocated from VM, just like the performance monitor of task manager of Windows XP (invoked from "My Computer")? If there exists such a tool in Java, it will make our work very convenient, isn't it? :-)
>> Another small issue is that, why you use join method in your getFinalScore >> method? I have not seen its special functons yet. > >When 'running' is set to false, the thread does not immediately exit. By >calling join(), the thread that executes getFinalScore() waits for it to exit >so that it can fetch the *final* score. Your idea of using join is very intelligent!
regards, George
Boudewijn Dijkstra - 12 Jun 2005 17:01 GMT >>The API documentation description of yield() is a bit cumbersome. But it is >>enough for those who are educated in the most important concepts of task [quoted text clipped - 11 lines] > > Your description is very helpful and it has answered my question. Thanks.
> Do you > know whether there exists a tool which can monitor what threads are running > on a VM and how much running time they have allocated from VM, just like > the performance monitor of task manager of Windows XP (invoked from "My > Computer")? If there exists such a tool in Java, it will make our work very > convenient, isn't it? :-) Such a tool is called a profiler. I've never used one, so I don't know which one you should get.
>>> Another small issue is that, why you use join method in your getFinalScore >>> method? I have not seen its special functons yet. [quoted text clipped - 4 lines] > > Your idea of using join is very intelligent! Alas, it wasn't my idea. It is actually a very common pattern, and according to some people, THE pattern.
George George - 13 Jun 2005 03:56 GMT Thanks Boudewijn,
>>>The API documentation description of yield() is a bit cumbersome. But it is >>>enough for those who are educated in the most important concepts of task [quoted text clipped - 22 lines] >Alas, it wasn't my idea. It is actually a very common pattern, and according >to some people, THE pattern. I think you have answered all of my questions. You are too kind. Hope you could still help me in the future. :-)
regards, George
Boudewijn Dijkstra - 13 Jun 2005 16:59 GMT > Thanks Boudewijn, > > I think you have answered all of my questions. You are too kind. Hope you > could still help me in the future. :-) Great, thanks. I think this was a nice example of properly asked questions followed by clear answers. 8-)
George George - 14 Jun 2005 03:40 GMT Thanks Boudewijn,
>> Thanks Boudewijn, >> [quoted text clipped - 3 lines] >Great, thanks. I think this was a nice example of properly asked questions >followed by clear answers. 8-) You are one of the most warm-hearted talent I have ever met with on the Web. You are very experienced and I think you have been working for Java for 10 years! :-)
regards, George
blmblm@myrealbox.com - 06 Jun 2005 06:56 GMT >> Thanks Boudewijn, >> [quoted text clipped - 25 lines] > >That is a decision that I cannot make for you. ;) Doesn't it depend to some extent on whether the JVM implementation tries to do timeslicing if there's more than one thread with the same priority? As far as I know, some do and some don't. Then again, it's probably best to write in a way that will work for any standard-conforming implementation ....
(And -- clever idea. My initial reaction was that it wasn't going to be possible to do what the OP wanted without a lot more knowledge of exactly how long various parts of his code took and/or of how the JVM schedules threads. But after thinking more -- yeah, I think what you're proposing might actually work, though I wonder whether there isn't some strange way a JVM could do scheduling that would defeat your scheme.)
| B. L. Massingill | ObDisclaimer: I don't speak for my employers; they return the favor. George George - 07 Jun 2005 08:39 GMT Thanks B. L. Massingill,
>>> Thanks Boudewijn, >>> [quoted text clipped - 18 lines] >| B. L. Massingill >| ObDisclaimer: I don't speak for my employers; they return the favor. Your reply is very helpful! From your reply, I think you are an expert in this topic. I am very junior in the testing how JVM thread timeslice and scheduling approach work. Could you provide some sample source codes to test it?
Another issue is that, do you know where can I find resources (papers, tutorials or open source projects) dealing with the internal operations of JVM timeslice and scheduling approach?
regards, George
blmblm@myrealbox.com - 11 Jun 2005 01:16 GMT >Thanks B. L. Massingill, > [quoted text clipped - 29 lines] >tutorials or open source projects) dealing with the internal operations of >JVM timeslice and scheduling approach? Not expert by any means, just dimly aware that different implementations do take different approaches to scheduling when there's more than one thread with the same priority. Below is a quickly-hacked-together little program that should give some clues about what a particular implementation does. If the implementation is doing timeslicing at all, then for a "large enough" value of N you should observe that the messages produced by the first loop ("no yield") in both threads are interspersed. If it's not doing timeslicing, then the first message from thread "pong" won't show up until after thread "ping" has finished that first loop.
As for getting into the details of how particular implementations do scheduling -- I'm not sure I'd advise this unless you need very precise control over the scheduling of your threads and/or don't care about portability. The standard advice is to write your code to work with any implementation that meets the published specs, which are probably available at Sun's Web site, somewhere. Sorry I don't have time to track down more details.
/* No claims are made about the beauty or generality of this code, only that it compiles and executes for me and I think produces some useful information. */
public class PingPong {
public static void main(String[] args) {
if (args.length < 1) { System.err.println("usage: PingPong count"); System.exit(1); } int count = Integer.parseInt(args[0]);
new Thread(new CodeForThread(count, "ping")).start(); new Thread(new CodeForThread(count, "pong")).start(); }
private static class CodeForThread implements Runnable {
private int count; private String name;
public CodeForThread(int count, String name) { this.count = count; this.name = name; }
public void run() { System.out.println("thread " + name + " will now print " + count + " messages without using Thread.yield"); for (int i = 0; i < count; ++i) { System.out.println("in thread " + name + " (no yield)"); } System.out.println("thread " + name + " will now print " + count + " messages using Thread.yield"); for (int i = 0; i < count; ++i) { System.out.println("in thread " + name + " (yield)"); Thread.yield(); } } } }
| B. L. Massingill | ObDisclaimer: I don't speak for my employers; they return the favor. George George - 12 Jun 2005 10:55 GMT Thanks B. L. Massingill!
>>Thanks B. L. Massingill, >> [quoted text clipped - 68 lines] >| B. L. Massingill >| ObDisclaimer: I don't speak for my employers; they return the favor. Your reply and your sample are both very helpful.
have a nice week, George
Free MagazinesGet these publications absolutely FREE for up to 12 months. There are no hidden fees and no obligation. Simply choose a title, complete the application form and submit it. Read more ...
|
|
|