lkml.org 
[lkml]   [2016]   [Nov]   [10]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
SubjectRe: [RFD] sched/deadline: Support single CPU affinity
Hi Henrik,

On Thu, 10 Nov 2016 13:21:00 +0100
Henrik Austad <henrik@austad.us> 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

\
 
 \ /
  Last update: 2016-11-10 13:39    [W:0.096 / U:0.464 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site