Re: [patch] CFS scheduler, -v8

Srivatsa Vaddagiri
2007-05-02T17:28:34Z

On Tue, May 01, 2007 at 10:57:14PM -0400, Ting Yang wrote:
> "A Proportional Share REsource Allocation Algorithm for Real-Time,
> Time-Shared Systems", by Ion Stoica. You can find the paper here:
> http://citeseer.ist.psu.edu/37752.html

Good paper ..thanks for the pointer.

I briefly went thr' the paper and my impression is it expect each task
to specify the length of each new request it initiates. Is that correct?

If we have to apply EEVDF to SCHED_NORMAL task scheduling under CFS, how
would we calculate that "length of each new request" (which is reqd
before we calculate its virtual deadline)?

> EXAMPLE: assume the system runs at 1000 tick/second, i.e. 1ms a tick,
> and the granularity of pre-exemption for CFS is 5 virtual ticks (the
> current setting). If, at time t=0, we start 2 tasks: p1 and p2, both
> have nice value 0 (weight 1024), and rq->fair_clock is initialized to 0.
> Now we have:
> p1->fair_key = p2->fair_key = rq->fair_clock = 0.
> CFS breaks the tie arbitrarily, say it executes p1. After 1 system tick
> (1ms later) t=1, we have:
> rq->fair_clock = 1/2, p1->fair_key = 1, p2->fair_key = 0.
> Suppose, a new task p3 starts with nice value -10 at this moment, that
> is p3->fair_key=1/2. In this case, CFS will not schedule p3 for
> execution until the fair_keys of p1 and p2 go beyond 5+1/2 (which
> translates to about 10ms later in this setting), _regardless_ the
> priority (weight) of p3.

There is also p->wait_runtime which is taken into account when
calculating p->fair_key. So if p3 had waiting in runqueue for long
before, it can get to run quicker than 10ms later.

--
Regards,
vatsa