Re: [patch] CFS scheduler, -v8

William Lee Irwin III
2007-05-02T17:48:10Z

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

On Wed, May 02, 2007 at 11:06:34PM +0530, Srivatsa Vaddagiri wrote:
> 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)?

l_i and w_i are both functions of the priority. You essentially arrange
l_i to express QoS wrt. latency, and w_i to express QoS wrt. bandwidth.

On Tue, May 01, 2007 at 10:57:14PM -0400, Ting Yang wrote:
>> 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.

On Wed, May 02, 2007 at 11:06:34PM +0530, Srivatsa Vaddagiri wrote:
> 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.

Virtual time is time from the task's point of view, which it has spent
executing. ->wait_runtime is a device to subtract out time spent on the
runqueue but not running from what would otherwise be virtual time to
express lag, whether deliberately or coincidentally. ->wait_runtime
would not be useful for EEVDF AFAICT, though it may be interesting to
report.

-- wli