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, moremath and fundamental explanations would have been good. So please bearwith 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 worldof a difference)So, for each task we keep normalised time normalised time := time/weightusing 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 / weightSo avg ends up being in units of [weight0/weight].Then, in order to allow sleeping, we need to have a global clock to syncwith. 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 itsaccumulating rounding error? (I'm inclined to believe the error willstatistically be 0, but I'll readily accept otherwise if you can show apractical 'exploit')Its not obvious how to do this using modulo logic like Bresenham becausethat 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 != jthis 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 sayit is more so.Also, I think you have an accumulating error on wakeup where you syncwith the global clock but fully discard the fraction.Anyway, as said a more detailed explanation and certainly a proof ofyour math would be nice. Is this something along the lines of what youintended to convey?If so, in the future please use more understandable language, we weretaught math for a reason :-)Regards,Peter-To unsubscribe from this list: send the line "unsubscribe linux-kernel" inthe body of a message to majordomo@vger.kernel.orgMore majordomo info at  http://vger.kernel.org/majordomo-info.htmlPlease read the FAQ at  http://www.tux.org/lkml/`

Last update: 2007-08-01 16:53    [W:0.423 / U:6.052 seconds]
©2003-2018 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site