Messages in this thread | | | Date | Thu, 10 Nov 2016 13:38:40 +0100 | From | luca abeni <> | Subject | Re: [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
| |