Re: [PATCH v2 2/3] sched/deadline: Throttle the task when missing its deadline
On 05/13/2017 at 04:58 AM, luca abeni wrote: > On Fri, 12 May 2017 15:19:55 +0800 > Xunlei Pangwrote: > [...] "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). >> Understood. >> >> I think in Patch 3, it is still worthy to add the accounting in >> dl_runtime_exceeded(), to track the dl scheduling tardiness(after all >> tardiness is not a good thing) like: if >> (dl_time_before(dl_se->deadline, rq_clock(rq)) && dl_se->runtime > 0) >> ++dl_se->nr_underrun_sched; >> >> Maybe changing the name to use "nr_underrun_tardy" is better, large >> value does need our attention. What do you think? > I do not know, I never used statistics like these... > > If there are enough people having a good usecase for these statistics, > it might be worth adding them, but I do not know other people's > opinions about this. > Hi Luca, Thanks for the feedback. I think I can defer the statistics patch after Daniel's "sched/deadline: Use the revised wakeup rule for suspending constrained dl tasks", since there will be another underrun case in the fix, let's wait for other's opinions then. Regards, Xunlei
Re: [PATCH v2 2/3] sched/deadline: Throttle the task when missing its deadline
On 05/13/2017 at 04:58 AM, luca abeni wrote: > On Fri, 12 May 2017 15:19:55 +0800 > Xunlei Pang wrote: > [...] "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). >> Understood. >> >> I think in Patch 3, it is still worthy to add the accounting in >> dl_runtime_exceeded(), to track the dl scheduling tardiness(after all >> tardiness is not a good thing) like: if >> (dl_time_before(dl_se->deadline, rq_clock(rq)) && dl_se->runtime > 0) >> ++dl_se->nr_underrun_sched; >> >> Maybe changing the name to use "nr_underrun_tardy" is better, large >> value does need our attention. What do you think? > I do not know, I never used statistics like these... > > If there are enough people having a good usecase for these statistics, > it might be worth adding them, but I do not know other people's > opinions about this. > Hi Luca, Thanks for the feedback. I think I can defer the statistics patch after Daniel's "sched/deadline: Use the revised wakeup rule for suspending constrained dl tasks", since there will be another underrun case in the fix, let's wait for other's opinions then. Regards, Xunlei
Re: [PATCH v2 2/3] sched/deadline: Throttle the task when missing its deadline
On Fri, 12 May 2017 15:19:55 +0800 Xunlei Pangwrote: [...] > >> "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). > > Understood. > > I think in Patch 3, it is still worthy to add the accounting in > dl_runtime_exceeded(), to track the dl scheduling tardiness(after all > tardiness is not a good thing) like: if > (dl_time_before(dl_se->deadline, rq_clock(rq)) && dl_se->runtime > 0) > ++dl_se->nr_underrun_sched; > > Maybe changing the name to use "nr_underrun_tardy" is better, large > value does need our attention. What do you think? I do not know, I never used statistics like these... If there are enough people having a good usecase for these statistics, it might be worth adding them, but I do not know other people's opinions about this. Luca
Re: [PATCH v2 2/3] sched/deadline: Throttle the task when missing its deadline
On Fri, 12 May 2017 15:19:55 +0800 Xunlei Pang wrote: [...] > >> "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). > > Understood. > > I think in Patch 3, it is still worthy to add the accounting in > dl_runtime_exceeded(), to track the dl scheduling tardiness(after all > tardiness is not a good thing) like: if > (dl_time_before(dl_se->deadline, rq_clock(rq)) && dl_se->runtime > 0) > ++dl_se->nr_underrun_sched; > > Maybe changing the name to use "nr_underrun_tardy" is better, large > value does need our attention. What do you think? I do not know, I never used statistics like these... If there are enough people having a good usecase for these statistics, it might be worth adding them, but I do not know other people's opinions about this. Luca
Re: [PATCH v2 2/3] sched/deadline: Throttle the task when missing its deadline
On 05/12/2017 at 03:01 PM, luca abeni wrote: > Hi, > > On Fri, 12 May 2017 14:53:33 +0800 > Xunlei Pangwrote: > >> 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 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). Understood. I think in Patch 3, it is still worthy to add the accounting in dl_runtime_exceeded(), to track the dl scheduling tardiness(after all tardiness is not a good thing) like: if (dl_time_before(dl_se->deadline, rq_clock(rq)) && dl_se->runtime > 0) ++dl_se->nr_underrun_sched; Maybe changing the name to use "nr_underrun_tardy" is better, large value does need our attention. What do you think? Regards, Xunlei
Re: [PATCH v2 2/3] sched/deadline: Throttle the task when missing its deadline
On 05/12/2017 at 03:01 PM, luca abeni wrote: > Hi, > > On Fri, 12 May 2017 14:53:33 +0800 > Xunlei Pang 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 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). Understood. I think in Patch 3, it is still worthy to add the accounting in dl_runtime_exceeded(), to track the dl scheduling tardiness(after all tardiness is not a good thing) like: if (dl_time_before(dl_se->deadline, rq_clock(rq)) && dl_se->runtime > 0) ++dl_se->nr_underrun_sched; Maybe changing the name to use "nr_underrun_tardy" is better, large value does need our attention. What do you think? Regards, Xunlei
Re: [PATCH v2 2/3] sched/deadline: Throttle the task when missing its deadline
Hi, On Fri, 12 May 2017 14:53:33 +0800 Xunlei Pangwrote: > 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 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
Re: [PATCH v2 2/3] sched/deadline: Throttle the task when missing its deadline
Hi, On Fri, 12 May 2017 14:53:33 +0800 Xunlei Pang 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 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
Re: [PATCH v2 2/3] sched/deadline: Throttle the task when missing its deadline
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 Pangwrote: > >> 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? > > Which kind of issue is this patch fixing? If it is something you saw > with deadline-constrained tasks, maybe you can add a check for > deadline!=period? No, It's an issue(I thought so back then) during making the last patch. Regards, Xunlei > > Luca >> This patch improves dl_runtime_exceeded() to achieve that. >> >> Fixes: 269ad8015a6b ("sched/deadline: Avoid double-accounting in case >> of missed deadlines") Cc: Luca Abeni >> Signed-off-by: Xunlei Pang >> --- >> kernel/sched/deadline.c | 9 +++-- >> 1 file changed, 7 insertions(+), 2 deletions(-) >> >> diff --git a/kernel/sched/deadline.c b/kernel/sched/deadline.c >> index d3d291e..5691149 100644 >> --- a/kernel/sched/deadline.c >> +++ b/kernel/sched/deadline.c >> @@ -729,8 +729,13 @@ static inline void >> dl_check_constrained_dl(struct sched_dl_entity *dl_se) } >> >> static >> -int dl_runtime_exceeded(struct sched_dl_entity *dl_se) >> +int dl_runtime_exceeded(struct rq *rq, struct sched_dl_entity *dl_se) >> { >> +bool dmiss = dl_time_before(dl_se->deadline, rq_clock(rq)); >> + >> +if (dmiss && dl_se->runtime > 0) >> +dl_se->runtime = 0; >> + >> return (dl_se->runtime <= 0); >> } >> >> @@ -781,7 +786,7 @@ static void update_curr_dl(struct rq *rq) >> dl_se->runtime -= delta_exec; >> >> throttle: >> -if (dl_runtime_exceeded(dl_se) || dl_se->dl_yielded) { >> +if (dl_runtime_exceeded(rq, dl_se) || dl_se->dl_yielded) { >> dl_se->dl_throttled = 1; >> __dequeue_task_dl(rq, curr, 0); >> if (unlikely(dl_se->dl_boosted >> || !start_dl_timer(curr)))
Re: [PATCH v2 2/3] sched/deadline: Throttle the task when missing its deadline
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 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? > > Which kind of issue is this patch fixing? If it is something you saw > with deadline-constrained tasks, maybe you can add a check for > deadline!=period? No, It's an issue(I thought so back then) during making the last patch. Regards, Xunlei > > Luca >> This patch improves dl_runtime_exceeded() to achieve that. >> >> Fixes: 269ad8015a6b ("sched/deadline: Avoid double-accounting in case >> of missed deadlines") Cc: Luca Abeni >> Signed-off-by: Xunlei Pang >> --- >> kernel/sched/deadline.c | 9 +++-- >> 1 file changed, 7 insertions(+), 2 deletions(-) >> >> diff --git a/kernel/sched/deadline.c b/kernel/sched/deadline.c >> index d3d291e..5691149 100644 >> --- a/kernel/sched/deadline.c >> +++ b/kernel/sched/deadline.c >> @@ -729,8 +729,13 @@ static inline void >> dl_check_constrained_dl(struct sched_dl_entity *dl_se) } >> >> static >> -int dl_runtime_exceeded(struct sched_dl_entity *dl_se) >> +int dl_runtime_exceeded(struct rq *rq, struct sched_dl_entity *dl_se) >> { >> +bool dmiss = dl_time_before(dl_se->deadline, rq_clock(rq)); >> + >> +if (dmiss && dl_se->runtime > 0) >> +dl_se->runtime = 0; >> + >> return (dl_se->runtime <= 0); >> } >> >> @@ -781,7 +786,7 @@ static void update_curr_dl(struct rq *rq) >> dl_se->runtime -= delta_exec; >> >> throttle: >> -if (dl_runtime_exceeded(dl_se) || dl_se->dl_yielded) { >> +if (dl_runtime_exceeded(rq, dl_se) || dl_se->dl_yielded) { >> dl_se->dl_throttled = 1; >> __dequeue_task_dl(rq, curr, 0); >> if (unlikely(dl_se->dl_boosted >> || !start_dl_timer(curr)))
Re: [PATCH v2 2/3] sched/deadline: Throttle the task when missing its deadline
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 Pangwrote: > 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) Which kind of issue is this patch fixing? If it is something you saw with deadline-constrained tasks, maybe you can add a check for deadline!=period? Luca > > This patch improves dl_runtime_exceeded() to achieve that. > > Fixes: 269ad8015a6b ("sched/deadline: Avoid double-accounting in case > of missed deadlines") Cc: Luca Abeni > Signed-off-by: Xunlei Pang > --- > kernel/sched/deadline.c | 9 +++-- > 1 file changed, 7 insertions(+), 2 deletions(-) > > diff --git a/kernel/sched/deadline.c b/kernel/sched/deadline.c > index d3d291e..5691149 100644 > --- a/kernel/sched/deadline.c > +++ b/kernel/sched/deadline.c > @@ -729,8 +729,13 @@ static inline void > dl_check_constrained_dl(struct sched_dl_entity *dl_se) } > > static > -int dl_runtime_exceeded(struct sched_dl_entity *dl_se) > +int dl_runtime_exceeded(struct rq *rq, struct sched_dl_entity *dl_se) > { > + bool dmiss = dl_time_before(dl_se->deadline, rq_clock(rq)); > + > + if (dmiss && dl_se->runtime > 0) > + dl_se->runtime = 0; > + > return (dl_se->runtime <= 0); > } > > @@ -781,7 +786,7 @@ static void update_curr_dl(struct rq *rq) > dl_se->runtime -= delta_exec; > > throttle: > - if (dl_runtime_exceeded(dl_se) || dl_se->dl_yielded) { > + if (dl_runtime_exceeded(rq, dl_se) || dl_se->dl_yielded) { > dl_se->dl_throttled = 1; > __dequeue_task_dl(rq, curr, 0); > if (unlikely(dl_se->dl_boosted > || !start_dl_timer(curr)))
Re: [PATCH v2 2/3] sched/deadline: Throttle the task when missing its deadline
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 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) Which kind of issue is this patch fixing? If it is something you saw with deadline-constrained tasks, maybe you can add a check for deadline!=period? Luca > > This patch improves dl_runtime_exceeded() to achieve that. > > Fixes: 269ad8015a6b ("sched/deadline: Avoid double-accounting in case > of missed deadlines") Cc: Luca Abeni > Signed-off-by: Xunlei Pang > --- > kernel/sched/deadline.c | 9 +++-- > 1 file changed, 7 insertions(+), 2 deletions(-) > > diff --git a/kernel/sched/deadline.c b/kernel/sched/deadline.c > index d3d291e..5691149 100644 > --- a/kernel/sched/deadline.c > +++ b/kernel/sched/deadline.c > @@ -729,8 +729,13 @@ static inline void > dl_check_constrained_dl(struct sched_dl_entity *dl_se) } > > static > -int dl_runtime_exceeded(struct sched_dl_entity *dl_se) > +int dl_runtime_exceeded(struct rq *rq, struct sched_dl_entity *dl_se) > { > + bool dmiss = dl_time_before(dl_se->deadline, rq_clock(rq)); > + > + if (dmiss && dl_se->runtime > 0) > + dl_se->runtime = 0; > + > return (dl_se->runtime <= 0); > } > > @@ -781,7 +786,7 @@ static void update_curr_dl(struct rq *rq) > dl_se->runtime -= delta_exec; > > throttle: > - if (dl_runtime_exceeded(dl_se) || dl_se->dl_yielded) { > + if (dl_runtime_exceeded(rq, dl_se) || dl_se->dl_yielded) { > dl_se->dl_throttled = 1; > __dequeue_task_dl(rq, curr, 0); > if (unlikely(dl_se->dl_boosted > || !start_dl_timer(curr)))
[PATCH v2 2/3] sched/deadline: Throttle the task when missing its deadline
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. This patch improves dl_runtime_exceeded() to achieve that. Fixes: 269ad8015a6b ("sched/deadline: Avoid double-accounting in case of missed deadlines") Cc: Luca AbeniSigned-off-by: Xunlei Pang --- kernel/sched/deadline.c | 9 +++-- 1 file changed, 7 insertions(+), 2 deletions(-) diff --git a/kernel/sched/deadline.c b/kernel/sched/deadline.c index d3d291e..5691149 100644 --- a/kernel/sched/deadline.c +++ b/kernel/sched/deadline.c @@ -729,8 +729,13 @@ static inline void dl_check_constrained_dl(struct sched_dl_entity *dl_se) } static -int dl_runtime_exceeded(struct sched_dl_entity *dl_se) +int dl_runtime_exceeded(struct rq *rq, struct sched_dl_entity *dl_se) { + bool dmiss = dl_time_before(dl_se->deadline, rq_clock(rq)); + + if (dmiss && dl_se->runtime > 0) + dl_se->runtime = 0; + return (dl_se->runtime <= 0); } @@ -781,7 +786,7 @@ static void update_curr_dl(struct rq *rq) dl_se->runtime -= delta_exec; throttle: - if (dl_runtime_exceeded(dl_se) || dl_se->dl_yielded) { + if (dl_runtime_exceeded(rq, dl_se) || dl_se->dl_yielded) { dl_se->dl_throttled = 1; __dequeue_task_dl(rq, curr, 0); if (unlikely(dl_se->dl_boosted || !start_dl_timer(curr))) -- 1.8.3.1
[PATCH v2 2/3] sched/deadline: Throttle the task when missing its deadline
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. This patch improves dl_runtime_exceeded() to achieve that. Fixes: 269ad8015a6b ("sched/deadline: Avoid double-accounting in case of missed deadlines") Cc: Luca Abeni Signed-off-by: Xunlei Pang --- kernel/sched/deadline.c | 9 +++-- 1 file changed, 7 insertions(+), 2 deletions(-) diff --git a/kernel/sched/deadline.c b/kernel/sched/deadline.c index d3d291e..5691149 100644 --- a/kernel/sched/deadline.c +++ b/kernel/sched/deadline.c @@ -729,8 +729,13 @@ static inline void dl_check_constrained_dl(struct sched_dl_entity *dl_se) } static -int dl_runtime_exceeded(struct sched_dl_entity *dl_se) +int dl_runtime_exceeded(struct rq *rq, struct sched_dl_entity *dl_se) { + bool dmiss = dl_time_before(dl_se->deadline, rq_clock(rq)); + + if (dmiss && dl_se->runtime > 0) + dl_se->runtime = 0; + return (dl_se->runtime <= 0); } @@ -781,7 +786,7 @@ static void update_curr_dl(struct rq *rq) dl_se->runtime -= delta_exec; throttle: - if (dl_runtime_exceeded(dl_se) || dl_se->dl_yielded) { + if (dl_runtime_exceeded(rq, dl_se) || dl_se->dl_yielded) { dl_se->dl_throttled = 1; __dequeue_task_dl(rq, curr, 0); if (unlikely(dl_se->dl_boosted || !start_dl_timer(curr))) -- 1.8.3.1