Hi Roman,
Took me most of today trying to figure out WTH you did in fs2.c, more
math and fundamental explanations would have been good. So please bear
with me as I try to recap this thing. (No, your code was very much _not_
obvious, a few comments and broken out functions would have made a world
of a difference)
So, for each task we keep normalised time
normalised time := time/weight
using Bresenham's algorithm we can do this prefectly (up until a renice
- where you'd get errors)
avg_frac += weight_inv
weight_inv = X / weight
avg = avg_frac / weight0_inv
weight0_inv = X / weight0
avg = avg_frac / (X / weight0)
= (X / weight) / (X / weight0)
= X / weight * weight0 / X
= weight0 / weight
So avg ends up being in units of [weight0/weight].
Then, in order to allow sleeping, we need to have a global clock to sync
with. Its this global clock that gave me headaches to reconstruct.
We're looking for a time like this:
rq_time := sum(time)/sum(weight)
And you commented that the /sum(weight) part is where CFS obtained its
accumulating rounding error? (I'm inclined to believe the error will
statistically be 0, but I'll readily accept otherwise if you can show a
practical 'exploit')
Its not obvious how to do this using modulo logic like Bresenham because
that would involve using a gcm of all possible weights.
What you ended up with is quite interesting if correct.
sum_avg_frac += weight_inv_{i}
however by virtue of the scheduler minimising:
avg_{i} - avg_{j} | i != j
this gets a factor of:
weight_{i}/sum_{j}^{N}(weight_{j})
( seems correct, needs more analysis though, this is very much a
statistical step based on the previous constraint. this might
very well introduce some errors )
resulting in:
sum_avg_frac += sum_{i}^{N}(weight_inv_{i} *
weight_{i}/sum_{j}^{N}(weight_{j}))
weight_inv = X / weight
sum_avg = sum_avg_frac / sum(weight0_inv)
= sum_avg_frac / N*weight0_inv
weight0_inv = X / weight0
sum_avg = sum_avg_frac / N*weight0_inv
= sum_{i}^{N}(weight_inv_{i} *
weight_{i}/sum_{j}^{N}(weight_{j})) / N*weight0_inv
= sum_{i}^{N}(X/weight_{i} *
weight_{i}/sum_{j}^{N}(weight_{j})) / N*(X/weight0)
= N*X / sum_{j}(weight_{j}) * weight0/N*X
= weight0 / sum_{j}(weight_{j})
Exactly the unit we were looking for [weight0/sum(weight)]
( the extra weight0 matching the one we had in the per task normalised
time )
I'm not sure all this is less complex than CFS, I'd be inclined to say
it is more so.
Also, I think you have an accumulating error on wakeup where you sync
with the global clock but fully discard the fraction.
Anyway, as said a more detailed explanation and certainly a proof of
your math would be nice. Is this something along the lines of what you
intended to convey?
If so, in the future please use more understandable language, we were
taught math for a reason :-)
Regards,
Peter
-
