Hi, On Fri, 12 May 2017 14:53:33 +0800 Xunlei Pang <[email protected]> wrote:
> On 05/12/2017 at 01:57 PM, luca abeni wrote: > > Hi again, > > > > (sorry for the previous email; I replied from gmail and I did not > > realize I was sending it in html). > > > > > > On Fri, 12 May 2017 11:32:08 +0800 > > Xunlei Pang <[email protected]> wrote: > > > >> dl_runtime_exceeded() only checks negative runtime, actually > >> when the current deadline past, we should start a new period > >> and zero out the remaining runtime as well. > > In this case, I think global EDF wants to allow the task to run with > > its remaining runtime even also missing a deadline, so I think this > > change is not correct. > > (when using global EDF, tasks scheduled on multiple CPUs can miss > > their deadlines... Setting the runtime to 0 as soon as a deadline > > is missed would break global EDF scheduling) > > Hi Luca, > > Thanks for the comment, looks like I neglected the theoretical > analysis. > > Cited from Documentation/scheduler/sched-deadline.txt: > "As a matter of fact, in this case it is possible to provide an > upper bound for tardiness (defined as the maximum between 0 and the > difference between the finishing time of a job and its absolute > deadline). More precisely, it can be proven that using a global EDF > scheduler the maximum tardiness of each task is smaller or equal than > ((M − 1) · WCET_max − WCET_min)/(M − (M − 2) · U_max) + WCET_m > where WCET_max = max{WCET_i} is the maximum WCET, > WCET_min=min{WCET_i} is the minimum WCET, and U_max = max{WCET_i/P_i} > is the maximum utilization[12]." > > And > "As seen, enforcing that the total utilization is smaller than M > does not guarantee that global EDF schedules the tasks without > missing any deadline (in other words, global EDF is not an optimal > scheduling algorithm). However, a total utilization smaller than M is > enough to guarantee that non real-time tasks are not starved and that > the tardiness of real-time tasks has an upper bound[12] (as > previously noted). Different bounds on the maximum tardiness > experienced by real-time tasks have been developed in various > papers[13,14], but the theoretical result that is important for > SCHED_DEADLINE is that if the total utilization is smaller or equal > than M then the response times of the tasks are limited." > > Do you mean there is some tardiness allowed in theory(global EDF is > not an optimal scheduling algorithm), thus missed deadline is allowed > for global EDF? Right. With the admission test currently used by the kernel (sum of utilizations <= 1), tasks are guaranteed to have a tardiness smaller than a theoretical maximum... But this theoretical maximum can be larger than 0. If you want to strictly respect all of the deadlines, you need a stricter admission test (for example, the one based on WCET_max that is mentioned above). Luca
