Re: [RFC patch 1/2] sched: dynamically adapt granularity with nr_running

Peter Zijlstra
2010-09-13T10:45:47Z

On Mon, 2010-09-13 at 11:55 +0200, Peter Zijlstra wrote:
> +/*
> + * Earliest Eligible Virtual Deadline First
> + *
> + * In order to provide latency guarantees for different request sizes
> + * EEVDF selects the best runnable task from two criteria:
> + *
> + * 1) the task must be eligible (must be owed service)
> + *
> + * 2) from those tasks that meet 1), we select the one
> + * with the earliest virtual deadline.
> + *
> + * We can do this in O(log n) time due to an augmented RB-tree. The
> + * tree keeps the entries sorted on service, but also functions as a
> + * heap based on the deadline by keeping:
> + *
> + * se->min_deadline = min(se->deadline, se->{left,right}->min_deadline)
> + *
> + * Which allows an EDF like search on (sub)trees.
> + */

I just realized, this doesn't do what we wanted.. the virtual deadline
stuff is handy when you've got tasks with different QoS, but we don't
have that, they're all the same due to our task model.

What we want is real deadlines, the patch provides the infrastructure,
let me frob something for that.