Thanks for the effort though. :)
I know I'm not the best explaining these things, so I really appreciate
the questions, so I know what to concentrate on.
I think I've sent you off into the wrong direction somehow. Sorry. :)
Let's ignore the average for a second, normalized time is maintained as:
normalized time := time * (2^16 / weight)
The important point is that I keep the value in full resolution of 2^-16
vsec units (vsec for virtual second or sec/weight, where every tasks gets
weight seconds for every virtual second, to keep things simpler I also
omit the nano prefix from the units for a moment). Compared to that CFS
maintains a global normalized value in 1 vsec units.
Since I don't round the value down I avoid the accumulating error, this
means that
time_norm += time_delta1 * (2^16 / weight)
time_norm += time_delta2 * (2^16 / weight)
is the same as
time_norm += (time_delta1 + time_delta2) * (2^16 / weight)
CFS for example does this
delta_mine = calc_delta_mine(delta_exec, curr->load.weight, lw);
in above terms this means
time = time_delta * weight * (2^16 / weight_sum) / 2^16
The last shift now rounds the value down and if one does that 1000 times
per second, the resolution of the value that is finally accounted to
wait_runtime is also reduced appropriately.
The other rounding problem is based on that this term
x * prio_to_weight[i] * prio_to_wmult[i] / 2^32
doesn't produce x for most values in that tables (the same applies to the
weight sum), so if we have chains, where the values are converted from one
scale to the other, a rounding error is produced. In CFS this happens now
because wait_runtime is maintained in nanoseconds and fair_clock is a
normalized value.
The problem here isn't that these errors might have a statistical
relevance, as they are usually completely overshadowed by measurement
errors anyway. The problem is that these errors exist at all, this means
they have to be compensated somehow, so that they don't accumulate over
time and then become significant. This also has to be seen in the context
of the overflow checks. All this adds a number of variables to the system
which considerably increases complexity and makes a thorough analysis
quite challenging.
So to get back to the average, if you look for this
rq_time := sum(time)/sum(weight)
you won't find it like this, this basically produces a weighted average
and I agree this can't really be maintained via the modulo logic (at least
AFAICT), so I'm using a simple average instead, so if we have:
time_norm = time/weight
we can write your rq_time like this:
weighted_avg = sum_{i}^{N}(time_norm_{i}*weight_{i})/sum_{i}^{N}(weight_{i})
this is the formula for a weighted average, so we can aproximate the value
using a simple average instead:
avg = sum_{i}^{N}(time_norm_{i})/N
This sum is now what I maintain at runtime incrementally:
time_{i} = sum_{j}^{S}(time_{j})
time_norm_{i} = time_{i}/weight_{i}
= sum_{j}^{S}(time_{j})/weight_{i}
= sum_{j}^{S}(time_{j}/weight_{i})
If I add this up and add weigth0 I get:
avg*N*weigth0 = sum_{i}^{N}(time_norm_{i})*weight0
and now I have also the needed modulo factors.
The average probably could be further simplified by using a different
approximation. The question is how perfect this average has to be. The
average is only used to control when a task gets its share, currently
higher priority tasks are already given a bit more preference or a sleep
bonus is added.
In CFS the average already isn't perfect due to above rounding problems,
otherwise the sum of all updated wait_runtime should be 0 and if a task
with a wait_runtime value different from 0 is added, fair_clock would have
to change too to keep the balance.
So unless someone has a brilliant idea, I guess we have to settle for the
approximation of a perfect scheduler. :) My approach is insofar different
that I at least maintain an accurate fair share and approximate based on
this the scheduling decision. This has IMO the advantage that the
scheduler function can be easily exchanged, one can do it the quick and
dirty way or one can put in the extra effort to get it closer to
perfection. Either way every task will get its fair share.
The scheduling function I used is rather simple:
if (j >= 0 &&
((int)(task[l].time_norm - (task[j].time_norm + SLICE(j))) >= 0 ||
((int)(task[l].time_norm - task[j].time_norm) >= 0 &&
(int)(task[l].time_norm - (s + SLICE(l))) >= 0))) {
So a new task is selected if there is a higher priority task or if the
task has used up its share (unless the other task has lower priority and
already got its share). It would be interesting to use a dynamic (per
task) time slice here, which should make it possible to control the
burstiness that has been mentioned.
The complexity is different, IMO the basic complexity to maintain the fair
share is less and I can add arbitrary complexity to improve scheduling on
top of it. Most of it comes now from maintaining the accurate average, it
depends now on how the scheduling is finally done what other optimizations
are possible.
I hope not, otherwise the checks at the end should have triggered. :)
The per task requirement is
time_norm = time_avg * weight0 + avg_fract
I don't simply discard it, it's accounted to time_norm and then synced to
the global average.
bye, Roman
-
