Tasks are not started with shortest deadline first

Message boards : Questions and problems : Tasks are not started with shortest deadline first
Message board moderation

To post messages, you must log in.

AuthorMessage
Rasputin42

Send message
Joined: 12 Jul 09
Posts: 25
Message 43046 - Posted: 15 Mar 2012, 23:16:47 UTC

Hi,
I have been running seti tasks, for example.
However, when a task is finished, it does not pick the next task with the shortest deadline. ( no high priority mode)
This does happen with other projects as well.
Can you fix this?
This is clearly a scheduling issue, not a project issue.
ID: 43046 · Report as offensive
Richard Haselgrove
Volunteer tester
Help desk expert

Send message
Joined: 5 Oct 06
Posts: 5095
United Kingdom
Message 43047 - Posted: 15 Mar 2012, 23:56:51 UTC - in response to Message 43046.  

And it matters not in the slightest.

If there is any danger of a task missing deadline, it will be run in high priority mode, with the earliest deadline first.

If there is no danger of missing deadline, then they will be done in the natural order of arrival, like any normal queue. What's so problematic about that?
ID: 43047 · Report as offensive
Rasputin42

Send message
Joined: 12 Jul 09
Posts: 25
Message 43048 - Posted: 15 Mar 2012, 23:59:33 UTC

The problem is, that it is not clever enough.
I had tasks missing the deadlines, because too many task with a short dead line have been left to wait until HIGH PRIORITY mode engages.
ID: 43048 · Report as offensive
Profile Jord
Volunteer tester
Help desk expert
Avatar

Send message
Joined: 29 Aug 05
Posts: 15509
Netherlands
Message 43052 - Posted: 16 Mar 2012, 6:29:49 UTC - in response to Message 43048.  

But when all work is done in high priority mode, what then when you have one project with short tasks with a 3 day deadline, one with medium tasks with a 14 day deadline and one with a long task with a 9 month deadline? Which project will continuously be busy doing all the work? And crucially, when will the long work start, if ever?

BOINC has redundancy built in. When you can't finish the work in time, it'll be resent to another computer which can. So long until a canonical outcome is reached, work is validated and credits can be divided. Does it say anywhere that you are required to do all the work you get in? Nope.

BOINC will at all times try to finish all the work it has in queue by their deadline. When it can't do so, you either had too much work in the queue in the first place, or you were micromanaging, aka deciding for BOINC what should run next. Just don't do that.
ID: 43052 · Report as offensive
Rasputin42

Send message
Joined: 12 Jul 09
Posts: 25
Message 43067 - Posted: 16 Mar 2012, 22:47:01 UTC

I am just trying to understand, how boinc determines, which task to start next.
There does not seem to be any any logic to that at all.
Would it not be a good idea, to start a task with the shortest deadline first?
So, if i am only running seti tasks, why is i picking a task with a deadline one month down the road instead of one that has a deadline of 6 days (given same run times for the tasks?
If you know, how boinc works out, which task to pick next please let me know.

High priority mode has its own problems.
If tasks do go to high priority mode, there is no understandable system to it, that i can see.
For example, it starts a task in high priority, runs it to 90% or so, and starts the next task of the same project in high priority mode and so on and so on.
Ending up with a lot of partially finished tasks of the same project (switching between tasks set to a very high value) and this with no further tasks downloading.
In which universe does that make sense?
ID: 43067 · Report as offensive
Profile Jord
Volunteer tester
Help desk expert
Avatar

Send message
Joined: 29 Aug 05
Posts: 15509
Netherlands
Message 43069 - Posted: 16 Mar 2012, 23:07:01 UTC - in response to Message 43067.  

So, if i am only running seti tasks, why is i picking a task with a deadline one month down the road instead of one that has a deadline of 6 days (given same run times for the tasks?

BOINC recalculates the round robin values of all tasks every 10 seconds, to see if tasks will make their deadline. It will check this by doing a quick calculation of the floating point operations value that comes with each task, against the flops that the CPU or GPU can do.

It will start tasks with a further away deadline, as these will come with a different (much higher) value of flops than tasks with an earlier deadline. This tells BOINC how long tasks may take by estimate. Tasks from the same project with a 4 week deadline will run for longer than tasks with a one week deadline.

For example, it starts a task in high priority, runs it to 90% or so, and starts the next task of the same project in high priority mode and so on and so on.

This is done to make sure that these tasks will end by their deadline. As said, BOINC will do its utmost best to finish all work before deadline. If a lot of work has a same deadline and a same run time, it'll run as much of this work to almost finished time, before switching to the next task(s) to do the same there, to try to make sure to finish as much of that work by their deadline.

It may not finish all of them by deadline, but then it learns and just won't download as much work the next time as it did last time. That is, as long as you do not interfere and let BOINC do it on its own. If you force BOINC to have 20 days worth of work and it has a deadline of 14 days, then how's it going to do that? Added to that, are you allowing BOINC to run 24/7/365? When you reboot, how long does it take before BOINC continues to run? Does BOINC only run for several (cheaper electricity) hours a day? Do you switch off when nasty weather passes over? Do you stop BOINC when you start a game of Skyrim? etc. etc.
ID: 43069 · Report as offensive
Rasputin42

Send message
Joined: 12 Jul 09
Posts: 25
Message 43072 - Posted: 16 Mar 2012, 23:36:32 UTC

Thanks Ageless.
I appreciate your response.
Has the project any influence of of the urgency of any task?
Boinc is running 24/7/365.
I usually restart every week or two.
(not including power cuts)
ID: 43072 · Report as offensive
Profile Gundolf Jahn

Send message
Joined: 20 Dec 07
Posts: 1069
Germany
Message 43073 - Posted: 17 Mar 2012, 0:36:11 UTC - in response to Message 43069.  
Last modified: 17 Mar 2012, 0:36:45 UTC

Added to that, are you allowing BOINC to run 24/7/365?

Shouldn't that read "24/7/52"? (Awfully many weeks in a year otherwise ;-)

Gruß,
Gundolf
ID: 43073 · Report as offensive
Richard Haselgrove
Volunteer tester
Help desk expert

Send message
Joined: 5 Oct 06
Posts: 5095
United Kingdom
Message 43105 - Posted: 17 Mar 2012, 22:00:51 UTC - in response to Message 43096.  

24/7/52.14285714

And a day off in leap years...
ID: 43105 · Report as offensive
Rasputin42

Send message
Joined: 12 Jul 09
Posts: 25
Message 43155 - Posted: 25 Mar 2012, 10:15:07 UTC

Yes, it is 24/7/52.
That is beside the point.

Important is , that the way boinc picks the next task is wrong.
If there are too many tasks with a short deadline,some tasks will miss the deadline.However running several tasks partially is stupid, as, if they cannot be finished in time, they will not get any credits.
If a task reaches the deadline, without being started,it will expire and i would not have wasted any computing time.
If boinc just runs the tasks with the shortest dealine first and finishes it, before starting the next one, is the only reasonable way.
ID: 43155 · Report as offensive
Profile Jord
Volunteer tester
Help desk expert
Avatar

Send message
Joined: 29 Aug 05
Posts: 15509
Netherlands
Message 43159 - Posted: 25 Mar 2012, 14:42:32 UTC - in response to Message 43155.  

If boinc just runs the tasks with the shortest dealine first and finishes it, before starting the next one, is the only reasonable way.

Until you run multiple projects with different deadlines, and find that the project with the shortest deadline will exclusively be run, while the others will just have to wait and time out.

Think outside your box of one project and see how many projects are out there.
Or do you really believe that work with a deadline of 8 months or more can easily be run within a week? As that's what your BOINC with earliest deadline first runs will try to do to things like the CPDN models, and fail to do.

BOINC has the redundancy that any work not finished by you by deadline will time out and be sent to another computer to be finished.

If you feel that you are so important that you have to finish all the work that gets appointed to you, then be reasonable and give BOINC the chance to do that:
- Don't force it to run a cache that's bigger than the deadline (e.g. connect to of 10 + additional days of 10 = 20 days, which is difficult to do on a 14 days deadline).
- Don't micromanage it, telling which tasks should run next.
- Allow it to learn. When tasks go over the deadline, BOINC won't ask so much work again next time, unless of course you micromanage it and force it to do so.

And if you still feel so strongly about BOINC needing to do things your way, then follow http://boinc.berkeley.edu/trac/wiki/CompileClient to get the source code, adjust it to your liking and compile it so it works like that for you.
ID: 43159 · Report as offensive
Rasputin42

Send message
Joined: 12 Jul 09
Posts: 25
Message 43160 - Posted: 25 Mar 2012, 16:36:59 UTC

Thanks for the reply.
There is simply no scenario, where it is more effective to calculate the tasks with the shortest deadline first.
Prove me wrong.
ID: 43160 · Report as offensive
Profile Jord
Volunteer tester
Help desk expert
Avatar

Send message
Joined: 29 Aug 05
Posts: 15509
Netherlands
Message 43163 - Posted: 25 Mar 2012, 17:22:55 UTC - in response to Message 43160.  

BOINC comes with the redundancy that any task not finished by the deadline --be that due to a too big a cache, broken hardware, dropped connections, people uninstalling BOINC, meteor strikes, cosmic rays, an attack by the Empire or whatever else is new-- will be sent out to another computer, and this ever so long until a canonical result has been reached, validation can take place and credits be given to those that actually did the work and did it correctly.

There is simply no scenario, where it is more effective to calculate the tasks with the shortest deadline first.

You are right, there is simply no scenario where BOINC should run constantly in EDF - earliest deadline first. Which is why it doesn't do this, but instead runs in FIFO, first in - first out, unless any task comes in with a FLOP estimate that's too big for BOINC to handle in the short time between now and the deadline, then BOINC will run that task in EDF.
ID: 43163 · Report as offensive
wiyosaya

Send message
Joined: 12 Feb 12
Posts: 17
United States
Message 43185 - Posted: 27 Mar 2012, 14:59:47 UTC

Rasputin,

I've had the same problem. Here is my work around for it http://boinc.berkeley.edu/dev/forum_thread.php?id=7275&nowrap=true#43171

ID: 43185 · Report as offensive

Message boards : Questions and problems : Tasks are not started with shortest deadline first

Copyright © 2024 University of California.
Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.