On Wed, Jul 4, 2012 at 8:32 AM, Peter Zijlstra <a.p.zijls...@chello.nl> wrote:
> On Wed, 2012-06-27 at 19:24 -0700, Paul Turner wrote:
>> Instead of tracking averaging the load parented by a cfs_rq, we can track
>> entity load directly. With the load for a given cfs_Rq then being the sum of
>> its children.
>>
>> To do this we represent the historical contribution to runnable average
>> within each
>> trailing 1024us of execution as the coefficients of a geometric series.
>>
>> We can express this for a given task t as:
>> runnable_sum(t) = \Sum u_i * y^i ,
>> load(t) = weight_t * runnable_sum(t) / (\Sum 1024 * y^i)
>>
>> Where: u_i is the usage in the last i`th 1024us period (approximately 1ms)
>> ~ms
>> and y is chosen such that y^k = 1/2. We currently choose k to be 32 which
>> roughly translates to about a sched period.
>>
>> Signed-off-by: Paul Turner <p...@google.com>
>> ---
>> include/linux/sched.h | 8 +++
>> kernel/sched/debug.c | 4 ++
>> kernel/sched/fair.c | 128
>> +++++++++++++++++++++++++++++++++++++++++++++++++
>> 3 files changed, 140 insertions(+), 0 deletions(-)
>>
>> diff --git a/include/linux/sched.h b/include/linux/sched.h
>> index 9dced2e..5bf5c79 100644
>> --- a/include/linux/sched.h
>> +++ b/include/linux/sched.h
>> @@ -1136,6 +1136,11 @@ struct load_weight {
>> unsigned long weight, inv_weight;
>> };
>>
>> +struct sched_avg {
>> + u32 runnable_avg_sum, runnable_avg_period;
>> + u64 last_runnable_update;
>> +};
>
>
> So we can use u32 because:
>
> n 1
> lim n->inf \Sum y^i = --- = ~ 46.66804636511427012122 ; y^32 = 0.5
> i=0 1-y
>
> So the values should never be larger than ~47k, right?
Yes -- this is made explicit later in the series.
>
> /me goes add something like that in a comment.
>
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
