From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1757248AbdELHSj (ORCPT ); Fri, 12 May 2017 03:18:39 -0400 Received: from mx1.redhat.com ([209.132.183.28]:60502 "EHLO mx1.redhat.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1757051AbdELHSh (ORCPT ); Fri, 12 May 2017 03:18:37 -0400 DMARC-Filter: OpenDMARC Filter v1.3.2 mx1.redhat.com E8E5B7AE83 Authentication-Results: ext-mx01.extmail.prod.ext.phx2.redhat.com; dmarc=none (p=none dis=none) header.from=redhat.com Authentication-Results: ext-mx01.extmail.prod.ext.phx2.redhat.com; spf=pass smtp.mailfrom=xpang@redhat.com DKIM-Filter: OpenDKIM Filter v2.11.0 mx1.redhat.com E8E5B7AE83 Reply-To: xlpang@redhat.com Subject: Re: [PATCH v2 2/3] sched/deadline: Throttle the task when missing its deadline References: <1494559929-11462-1-git-send-email-xlpang@redhat.com> <1494559929-11462-2-git-send-email-xlpang@redhat.com> <20170512075724.0167e9cd@nowhere> <59155BED.7090406@redhat.com> <20170512090158.15c94ae8@nowhere> To: luca abeni Cc: Xunlei Pang , linux-kernel@vger.kernel.org, Peter Zijlstra , Juri Lelli , Ingo Molnar , Steven Rostedt , Daniel Bristot de Oliveira , Luca Abeni From: Xunlei Pang Message-ID: <5915621B.8050606@redhat.com> Date: Fri, 12 May 2017 15:19:55 +0800 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:38.0) Gecko/20100101 Thunderbird/38.2.0 MIME-Version: 1.0 In-Reply-To: <20170512090158.15c94ae8@nowhere> Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 8bit X-Greylist: Sender IP whitelisted, not delayed by milter-greylist-4.5.16 (mx1.redhat.com [10.5.110.25]); Fri, 12 May 2017 07:18:37 +0000 (UTC) Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org 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