Messages in this thread | | | Date | Thu, 10 Nov 2016 13:27:05 +0100 | From | luca abeni <> | Subject | Re: [RFD] sched/deadline: Support single CPU affinity |
| |
Hi Peter,
On Thu, 10 Nov 2016 11:59:18 +0100 Peter Zijlstra <peterz@infradead.org> wrote:
[...] > > > MIXED CRITICALITY SCHEDULING > > > > > > Since we want to provide better guarantees for single CPU affine > > > tasks than the G-EDF scheduler provides for the single CPU tasks, > > > we need to somehow alter the scheduling algorithm. > > > > > > The trivial layered EDF/G-EDF approach is obviously flawed in > > > that it will result in many unnecessary deadline misses. The > > > trivial example is having a single CPU task with a deadline after > > > a runnable global task. By always running single CPU tasks over > > > global tasks we can make the global task miss its deadline even > > > though we could easily have ran both within the alloted time. > > > Ok; the layered approach clearly causes some unneeded deadline > > misses on global tasks... But those tasks risk to miss deadlines > > anyway (with the corrent scheduler, they are guaranteed to have a > > limited tardiness, not to respect all of the deadlines). I think > > this is related to the question about which guarantees are provided > > to the global tasks. > > Right, so I wanted to limit the impact. Basically, given a stronger > admission test for the GEDF scheduler that would guarantee deadlines, > I would like the new scheduling function to still guarantee all > deadlines. Ok; this is interesting... I do not know if it is possible, but it is definitly something interesting to look at.
> > > Therefore we must use a more complicated scheme. By adding a > > > second measure present in the sporadic task model to the > > > scheduling function we can try and distinguish between the > > > constraints of handling the two cases in a single scheduler. > > > > > > 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 > > > Ok; I think this is similar to what is called "pseudo-deadline" in > > some papers. > > If I understand well, it is equal to the current time + the task > > "laxity" (or slack time). So, scheduling the task with the smaller > > ttf is equivalent to the "least laxity first" (LLF) algorithm. > > Giving precedence to tasks with 0 laxity is a technique that is > > often used to improve the schedulability on multi-processor > > systems. > > Right, similar to LLF. Initially I was using the term laxity here, but > Hendrik convinced me that this is called time-to-fail. I'll let him > explain :-) Well, if I understand well "time-to-fail" is equal to "laxity + current time"... So, they are two different quantities but the final scheduling algorithm is the same (and using ttf simplifies the implementation a lot :).
> But yes, a pure TTF based scheduler should be equivalent to LLF which > itself is fairly similar to EDF in that its optimal for UP etc.. (I > think). Right
> > I _suspect_ that the migration rules must also be changed (when a > > task migrates from a runqueue, it currently selects as a target the > > runqueue having the largest earliest deadline... Maybe it should > > also consider the presence of rq-local tasks - or the LLF-ordered > > heap - on the target?) > > Quite possible, I didn't think about that. > > > Did you find this scheduling strategy on some paper? Otherwise, I > > think we need to develop some theoretical analysis for it... (which > > is of course another interesting thing! :) > > No, I cooked this up myself. There might of course still be a paper on > this, but if so, I'm blissfully unaware. Ok; I'll try to have a look at the theoretical analysis.
Thanks, Luca
| |