From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1756772AbdELHBd convert rfc822-to-8bit (ORCPT ); Fri, 12 May 2017 03:01:33 -0400 Received: from mail.santannapisa.it ([193.205.80.98]:59227 "EHLO mail.santannapisa.it" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1756554AbdELHBc (ORCPT ); Fri, 12 May 2017 03:01:32 -0400 Date: Fri, 12 May 2017 09:01:58 +0200 From: luca abeni To: Xunlei Pang Cc: Xunlei Pang , linux-kernel@vger.kernel.org, Peter Zijlstra , Juri Lelli , Ingo Molnar , Steven Rostedt , Daniel Bristot de Oliveira , Luca Abeni Subject: Re: [PATCH v2 2/3] sched/deadline: Throttle the task when missing its deadline Message-ID: <20170512090158.15c94ae8@nowhere> In-Reply-To: <59155BED.7090406@redhat.com> 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> Organization: Scuola Superiore S.Anna X-Mailer: Claws Mail 3.13.2 (GTK+ 2.24.30; x86_64-pc-linux-gnu) MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8BIT Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org 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