Messages in this thread | | | Subject | Re: CFS review | From | Peter Zijlstra <> | Date | Wed, 01 Aug 2007 16:49:56 +0200 |
| |
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
- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
| |