The problem with least slack is that we do not always have good estimates,
and sometimes a tasks run time is grossly over estimated, and the slack is
negative. Thus all tasks will have to have a negative slack to run, thus
all tasks with an earlier deadline are condemned to be late. Least slack
may work if the run times are known exactly, but it has a tendency to come
apart when the slack times are not known very well. Least slack will not
solve the problem I am seeing on my machine at the moment.
The EDF simulation was suggested in order to not do preemption in many
cases where it was not needed. EDF is still needed in these cases, but
preemption is not. There are a couple of reasons for this.
1) I have watched CPDN get 15 second time slices because tasks from a
different project needed EDF immediately after download. They would
complete on time if they waited for something else to finish its normal
time slot, but they do preempt and get instant CPU.
2) I have a large number of tasks with 0 to 5 seconds of CPU time left
from the other project taking up swap file space. These could very well
have been completed. Note that when a task is running, the project is
getting 100% of a CPU, even if that is more than the resource fraction for
that project. This means that the task will exit the deadline danger
sometime during its run even without an overestimate of the run time.
My point is that a non EDF task should never move ahead of an EDF task -
even if it means leaving some resources idle. Deadlines are important to
both the users and to the projects. A missed deadline means that the user
has possibly wasted a bunch of CPU time doing something that will be thrown
out, and it means that some other user will possibly have to waste a bunch
of CPU time doing replacement work that could have been avoided. The
project gets its work done later (important to some but not all projects).
A multi CPU EDF task should not move ahead of an EDF task with an earlier
deadline. Even if it means running some later deadline single CPU work or
even leaving a CPU idle (see note above on the importance of deadlines).
In my opinion, a multi CPU non EDF task should not move ahead of higher STD
non edf tasks unless it would mean leaving CPUs idle. In this case,
keeping the CPUs busy is more important than short term balancing of the
STDs.
jm7
David Anderson
<[email protected]
ey.edu> To
John McLeod
01/14/2010 05:13 <[email protected]>, BOINC
PM Developers Mailing List
<[email protected]>
cc
Subject
job scheduling continued
My previous email points out that no policy is both efficient and optimal,
but that certainly doesn't mean the current policies can't be improved a
bit.
For example:
- a non-EDF multi-CPU job should not be moved ahead
of an EDF 1-CPU job if there are enough other 1-CPU jobs to fill the CPUs.
- use least slack time first or some other policy to schedule
jobs that miss deadlines under RR.
(there are a numbers of policies that do better than EDF on average).
- use intelligence (e.g., least slack time first)
in ordering the execution of a group of jobs that arrive simultaneously
(Richard H's AQUA example).
I'd prefer to not add a 2nd simulator (EDF) to the client unless
it's really clear that it's needed.
Anyway: we're unlikely to make any of these changes for a couple of months;
things like the credit system have priority.
If anyone wants to implement these or other changes,
and prove using the client simulator that they improve things,
we could incorporate them.
-- David
_______________________________________________
boinc_dev mailing list
[email protected]
http://lists.ssl.berkeley.edu/mailman/listinfo/boinc_dev
To unsubscribe, visit the above URL and
(near bottom of page) enter your email address.
