Because scheduling ALSO takes into account the resource share, and a bit of
a safety margin.
100 -26.4 - 1 is 72.6 hours. // the -1 is the task scheduling period. If
this is larger, the tasks have to complete earlier. The reason is that the
task scheduling period is the granularity that the CPU scheduler can be
guaranteed to be no larger than.
72.6 * 0.9 is 65.34. // just in case they run a little long
10 tasks * 4 hours each is 40 hours.
Assuming that the resource fraction with other tasks on the system is 0.25
(three other projects with equal share and enough tasks to keep the queue
busy for the 66 hours to deadline - you did NOT specify the other work, so
I have to make this part up), rr_sim will conclude that the tasks will
complete in 160 hours, well PAST the computation deadline in 66.24 hours.
Calculation is for a single CPU. For a dual CPU, rr_sim should calculate
the last task will complete in 80 hours - again past the computation
deadline.
This is why it currently finds the deadline problems.
An EDF check will not find the problem now, but will find it later when the
deadline is closer.
Same assumptions with the added assumption that the deadlines for the other
work are far away.
The EDF check will determine that if run in EDF, the computations will
complete in 40 hours. Nothing special is done. However, after a while of
running in round robin, there will come a time when these tasks will not
have been run enough, and EDF will have to kick in.
On a single CPU system, after 4 hours, one hour would have been devoted to
this project, and it would have 39 hours of CPU time left and (72.6 - 4) *
0.9 = 61.74 hours. EDF has it complete in 39 hours. Still OK.
4 more hours. 38 hours CPU time to go. (72.6 - 8) * 0.9 = 58.14 hours
till computation deadline. Still OK.
4 more hours. 37 hours CPU time to go. (72.6 - 12) * 0.9 = 54.54 hours
till computation deadline. Still OK.
4 more hours. 36 hours CPU time to go. (72.6 - 16) * 0.9 = 50.94 hours
till computation deadline. Still OK.
4 more hours. 35 hours CPU time to go. (72.6 - 20) * 0.9 = 47.34 hours
till computation deadline. Still OK.
4 more hours. 34 hours CPU time to go. (72.6 - 24) * 0.9 = 43.74 hours
till computation deadline. Still OK.
4 more hours. 33 hours CPU time to go. (72.6 - 28) * 0.9 = 40.16 hours
till computation deadline. Still OK.
4 more hours. 32 hours CPU time to go. (72.6 - 32) * 0.9 = 36.54 hours
till computation deadline. Still OK.
4 more hours. 31 hours CPU time to go. (72.6 - 36) * 0.9 = 32.94 hours
till computation deadline. Still OK.
4 more hours. 30 hours CPU time to go. (72.6 - 40) * 0.9 = 29.34 hours
till computation deadline. Sometime during this 4 hours, an EDF check
would have to switch over to EDF in order to complete the tasks on time.
The same exercise can be done on a dual CPU, and the computer will have to
enter EDF later to meet deadlines.
The reason for not doing an elaborate pre-schedule is that things change
over time. New tasks are downloaded, tasks complete early or late, tasks
don't checkpoint anywhere near their switch times,...
What I am proposing is that CPU scheduling still runs an rr_sim check to
see if rr_sim would complete on time. However to avoid unnecessary task
preemptions, it ALSO runs an EDF check (only if there actually are tasks
that run late in the rr_sim check), and only preempts if the EDF check also
determines the task to be late. This has the CPU starting on tasks at the
end of the scheduled times early on, and would avoid early preemption
completely in this case.
In this example, the tasks would run to
jm7
Mikus Grinbergs
<[email protected]>
Sent by: To
boinc_dev-bounces BOINC dev
@ssl.berkeley.edu <[email protected]>
cc
04/28/2009 07:39 Subject
PM Re: [boinc_dev] 6.6.20 and work
scheduling
John wrote
> 1) What should we be working on if we did a task switch now? This
detects
> that cases where we need to trigger a task switch immediately because of
a
> potential missed deadline.
I've seen the following (presumably in chase of a "missed deadline")
- I forget which release of the BOINC client I was using. [I run
off-line; my interval-between-connects is 1.1 days; my additional
work days are 1.x days (for a total ready-queue size of 2+ days).]
From one project, ten tasks (typically taking 4 hours each) get
downloaded. They have deadlines four+ days away. Lo and behold -
several of these new tasks immediately end up running in EDF.
----
I keep advocating 'scheduling across a span of time'. To my mind,
there are 100 hours to run these tasks before deadline. Take away
the interval-between-connects, and that leaves 70+ hours to complete
crunching of all of these tasks. Even if these tasks were run
sequentially, I would expect "scheduling" to conclude that they
could finish in less than two days - that is, *before* deadline.
So why does "scheduling" think there is a potential missed deadline?
The only answer I can come up with is that "resource share" is being
factored in - if this is one of five projects, then 20% (they all
have equal shares) of 70 hours is 14 hours - not enough to do the
estimated 40 hours of work. But this is a four-core system -- so
20% of (70 * 4) is 56 hours of crunching that this project is
"entitled" to in the next three days.
A need to do 40 hours of work in three days will potentially miss
the target if there are actually less than 56 hours available to
this project in that time span. But if they are not available to
*this* project, it must be because there is an even greater need by
another project. Yet none of the other projects are running in EDF.
For me, this case does not add up to a "potential missed deadline".
mikus
_______________________________________________
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.
_______________________________________________
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.
