Re: [RFD] sched/deadline: Support single CPU affinity

[luca abeni]

Hi Henrik,

On Thu, 10 Nov 2016 13:21:00 +0100
Henrik Austad <henrik@xxxxxxxxx> wrote:
> On Thu, Nov 10, 2016 at 09:08:07AM +0100, Peter Zijlstra wrote:
[...]
> > We define the time to fail as:
> > 
> >   ttf(t) := t_d - t_b; where
> > 
> > 	t_d is t's absolute deadline
> > 	t_b is t's remaining budget
> > 
> > This is the last possible moment we must schedule this task such
> > that it can complete its work and not miss its deadline.  
> 
> To elaborate a bit on this (this is a modified LLF approach if my
> memory serves):
> 
> You have the dynamic time-to-failure (TtF), i.e. as the task
> progresses (scheduled to run), the relative time-to-failure will
> remain constant. This can be used to compare thasks to a running task
> and should minimize the number of calculations required.
> 
> Then you have the static Time-of-failure (ToF, which is the absoulte
> time when a task will no longer be able to meet its deadline. This is
> what you use for keeping a sorted list of tasks in the runqueue. As
> this is a fixed point in time, you do not have to dynamically update
> or do crazy calculation when inserting/removing threads from the rq.

Sorry, I am missing something here: if ttf is defined as
	ttf_i = d_i - q_i
(where d_i is the deadline of thask i and q_i is its remaining budget),
then it also is the time before which you have to schedule task i if
you do not want to miss the deadline... No? So, I do not understand the
difference with tof.


> > If we then augment the regular EDF rules by, for local tasks,
> > considering the time to fail and let this measure override the
> > regular EDF pick when the time to fail can be overran by the EDF
> > pick.  
> 
> Then, if you do this - do you need to constrict this to a local CPU?
> I *think* you could do this in a global scheduler if you use ToF/TtF
> for all deadline-tasks, I think you should be able to meet deadlines.
I think the ToF/TtF scheduler will be equivalent to LLF (see previous
emails)... Or am I misunderstanding something? (see above)
And LLF is not optimal on multiple CPUs, so I do not think it will be
able to meet deadlines if you use it as a global scheduler.

> 
> I had a rant about this way back [1,2 Sec 11.4], I need to sit down
> and re-read most of it, it has been a few too many years, but the
> idea was to minimize the number of context-switches (which LLF is
> prone to get a lot of) as well as minimize the computational overhead
> by avoiding re-calculating time-of-failre/time-to-failre a lot.
> 
> > That is, when:
> > 
> > 	now + left_b > min(ttf)  
> 
> Why not just  use ttf/tof for all deadline-tasks? We have all the 
> information available anyway and it would probably make the internal
> logic easier?
I think LLF causes more preemptions and migrations than EDF.


				Luca