From: Tommaso Cucinotta <tommaso.cucinotta@sssup.it>
To: Peter Zijlstra <peterz@infradead.org>
Cc: Luca Abeni <luca.abeni@unitn.it>, Raistlin <raistlin@linux.it>,
Ingo Molnar <mingo@elte.hu>, Thomas Gleixner <tglx@linutronix.de>,
Steven Rostedt <rostedt@goodmis.org>,
Chris Friesen <cfriesen@nortel.com>,
oleg@redhat.com, Frederic Weisbecker <fweisbec@gmail.com>,
Darren Hart <darren@dvhart.com>,
Johan Eker <johan.eker@ericsson.com>,
"p.faure" <p.faure@akatech.ch>,
linux-kernel <linux-kernel@vger.kernel.org>,
Claudio Scordino <claudio@evidence.eu.com>,
michael trimarchi <trimarchi@retis.sssup.it>,
Fabio Checconi <fabio@gandalf.sssup.it>,
Juri Lelli <juri.lelli@gmail.com>,
Nicola Manica <nicola.manica@disi.unitn.it>,
Dhaval Giani <dhaval@retis.sssup.it>,
Harald Gustafsson <hgu1972@gmail.com>,
paulmck <paulmck@linux.vnet.ibm.com>
Subject: Re: [RFC][PATCH 18/22] sched: add reclaiming logic to -deadline tasks
Date: Sat, 13 Nov 2010 02:49:34 +0100 [thread overview]
Message-ID: <4CDDEEAE.9060706@sssup.it> (raw)
In-Reply-To: <1289608988.2084.501.camel@laptop>
Il 13/11/2010 01:43, Peter Zijlstra ha scritto:
> On Fri, 2010-11-12 at 19:07 +0100, Tommaso Cucinotta wrote:
>> -) the specification of a budget every period may be exploited for
>> providing deterministic guarantees to applications, if the budget =
>> WCET, as well as probabilistic guarantees, if the budget< WCET. For
>> example, what we do in many of our papers is to set budget = to some
>> percentile/quantile of the observed computation time distribution,
>> especially in those cases in which there are isolated peaks of
>> computation times which would cause an excessive under-utilization of
>> the system (these are ruled out by the percentile-based allocation); I
>> think this is a way of reasoning that can be easily understood and used
>> by developers;
> Maybe, but I'm clearly not one of them because I'm not getting it.
My fault for not having explained. Let me see if I can clarify. Let's
just consider the simple case in which application instances do not
enqueue (i.e., as soon as the application detects to have missed a
deadline, it discards the current job, as opposed to keep computing the
current job), and consider a reservation period == application period.
In such a case, if 'C' represents the (probabilistically modeled)
computation time of a job, then:
Prob{deadline hit} = Prob{enough runtime for a job instance} = Prob{C
<= runtime}.
So, if runtime is set as the q-th quantile of the `C' probability
distribution, then:
Prob{deadline hit} = Prob{C <= runtime} = q
This is true independently of what else is admitted into the system, as
far as I get my runtime guaranteed from the scheduler.
Does this now make sense ?
If, on the other hand, task instances enqueue (e.g., I keep decoding the
current frame even if I know a new frame arrived), then the probability
of deadline-hit will be lower than q, and generally speaking one can use
stochastic analysis & queueing theory techniques in order to figure out
what it actually is.
>> -) setting a budget equal to (or too close to) the average computation
>> time is *bad*, because the is almost in a meta-stable condition in which
>> its response-time may easily grow uncontrolled;
> How so? Didn't the paper referenced just prove that the response time
> stays bounded?
Here I was not referring to GEDF, but simply to the case in which we are
reserved from the kernel a budget every period (whatever the scheduling
algorithm): as the reserved budget moves from the WCET down towards the
average computation time, the response time distribution moves from a
shape entirely contained below the deadline, to a more and more flat
shape, where the probability of missing the deadline for the task
increases over and over. Roughly speaking, if the application instances
do not enqueue, then with a budget = average computation time, I would
expect a ~50% deadline miss, something which hardly is acceptable even
for soft RT applications.
If instances instead enqueue, then the situation may go much worse,
because the response-time distribution flattens with a long tail beyond
the deadline. The maximum value of it approaches +\infty with the
reserved budget approaching the average computation time.
> Setting it lower will of course wreak havoc, but that's what we have
> bandwidth control for (implementing stochastic bandwidth control is a
> whole separate fun topic though -- although I've been thinking we could
> do something by lowering the max runtime every time a job overruns the
> average, and limit it at 2*avg - max, if you take a simple parametrized
> reduction function and compute the variability of th resulting series
> you can invert that and find the reduction parameter to a given
> variability).
I'd need some more explanation, sorry, I couldn't understand what you're
proposing.
>> -) if you want to apply the Mills& Anderson's rule for controlling the
>> bound on the tardiness percentiles, as in that paper (A Stochastic
>> Framework for Multiprocessor
>> Soft Real-Time Scheduling), then I can see 2 major drawbacks:
>> a) you need to compute the "\psi" in order to use the "Corollary 10"
>> of that paper, but that quantity needs to solve a LP optimization
>> problem (see also the example in Section 6); the \psi can be used in Eq.
>> (36) in order to compute the *expected tardiness*;
> Right, but do we ever actually want to compute the bound? G-EDF also
> incurs tardiness but we don't calculate it either.
I was assuming you were proposing to keep an admission test based on
providing the parameters needed for checking whether or not a given
tardiness bound were respected. I must have misunderstood. Would you
please detail what is the test (and result in the paper) you are
thinking of using ?
>> If you really want, you
>> can disable *any* type of admission control at the kernel-level, and you
>> can disable *any* kind of budget enforcement, and just trust the
>> user-space to have deployed the proper/correct number& type of tasks
>> into your embedded RT platform.
> I'm very much against disabling everything and letting the user sort it,
> that's basically what SCHED_FIFO does too and its a frigging nightmare.
Sure, I agree. I was simply suggesting it as a last-resort option
(possibly usable by exploiting a compile-time option of the scheduler
compiling out the admission test), useful in those cases in which you do
have a user-space complex admission test that you made (or even an
off-line static analysis of your system) but the simple admission test
into the kernel would actually reject the task set, being the test
merely sufficient.
Bye,
T.
--
Tommaso Cucinotta, Computer Engineering PhD, Researcher
ReTiS Lab, Scuola Superiore Sant'Anna, Pisa, Italy
Tel +39 050 882 024, Fax +39 050 882 003
http://retis.sssup.it/people/tommaso
next prev parent reply other threads:[~2010-11-13 1:49 UTC|newest]
Thread overview: 135+ messages / expand[flat|nested] mbox.gz Atom feed top
2010-10-29 6:18 [RFC][PATCH 00/22] sched: SCHED_DEADLINE v3 Raistlin
2010-10-29 6:25 ` [RFC][PATCH 01/22] sched: add sched_class->task_dead Raistlin
2010-10-29 6:27 ` [RFC][PATCH 02/22] sched: add extended scheduling interface Raistlin
2010-11-10 16:00 ` Dhaval Giani
2010-11-10 16:12 ` Dhaval Giani
2010-11-10 22:45 ` Raistlin
2010-11-10 16:17 ` Claudio Scordino
2010-11-10 17:28 ` Peter Zijlstra
2010-11-10 19:26 ` Peter Zijlstra
2010-11-10 23:33 ` Tommaso Cucinotta
2010-11-11 12:19 ` Peter Zijlstra
2010-11-10 22:17 ` Raistlin
2010-11-10 22:57 ` Tommaso Cucinotta
2010-11-11 13:32 ` Peter Zijlstra
2010-11-11 13:54 ` Raistlin
2010-11-11 14:08 ` Peter Zijlstra
2010-11-11 17:27 ` Raistlin
2010-11-11 14:05 ` Dhaval Giani
2010-11-10 22:24 ` Raistlin
2010-11-10 18:50 ` Peter Zijlstra
2010-11-10 22:05 ` Raistlin
2010-11-12 16:38 ` Steven Rostedt
2010-11-12 16:43 ` Peter Zijlstra
2010-11-12 16:52 ` Steven Rostedt
2010-11-12 19:19 ` Raistlin
2010-11-12 19:23 ` Steven Rostedt
2010-11-12 17:42 ` Tommaso Cucinotta
2010-11-12 19:21 ` Steven Rostedt
2010-11-12 19:24 ` Raistlin
2010-10-29 6:28 ` [RFC][PATCH 03/22] sched: SCHED_DEADLINE data structures Raistlin
2010-11-10 18:59 ` Peter Zijlstra
2010-11-10 22:06 ` Raistlin
2010-11-10 19:10 ` Peter Zijlstra
2010-11-12 17:11 ` Steven Rostedt
2010-10-29 6:29 ` [RFC][PATCH 04/22] sched: SCHED_DEADLINE SMP-related " Raistlin
2010-11-10 19:17 ` Peter Zijlstra
2010-10-29 6:30 ` [RFC][PATCH 05/22] sched: SCHED_DEADLINE policy implementation Raistlin
2010-11-10 19:21 ` Peter Zijlstra
2010-11-10 19:43 ` Peter Zijlstra
2010-11-11 1:02 ` Raistlin
2010-11-10 19:45 ` Peter Zijlstra
2010-11-10 22:26 ` Raistlin
2010-11-10 20:21 ` Peter Zijlstra
2010-11-11 1:18 ` Raistlin
2010-11-11 13:13 ` Peter Zijlstra
2010-11-11 14:13 ` Peter Zijlstra
2010-11-11 14:28 ` Raistlin
2010-11-11 14:17 ` Peter Zijlstra
2010-11-11 18:33 ` Raistlin
2010-11-11 14:25 ` Peter Zijlstra
2010-11-11 14:33 ` Raistlin
2010-11-14 8:54 ` Raistlin
2010-11-23 14:24 ` Peter Zijlstra
2010-10-29 6:31 ` [RFC][PATCH 06/22] sched: SCHED_DEADLINE handles spacial kthreads Raistlin
2010-11-11 14:31 ` Peter Zijlstra
2010-11-11 14:50 ` Dario Faggioli
2010-11-11 14:34 ` Peter Zijlstra
2010-11-11 15:27 ` Oleg Nesterov
2010-11-11 15:43 ` Peter Zijlstra
2010-11-11 16:32 ` Oleg Nesterov
2010-11-13 18:35 ` Peter Zijlstra
2010-11-13 19:58 ` Oleg Nesterov
2010-11-13 20:31 ` Peter Zijlstra
2010-11-13 20:51 ` Peter Zijlstra
2010-11-13 23:31 ` Peter Zijlstra
2010-11-15 20:06 ` [PATCH] sched: Simplify cpu-hot-unplug task migration Peter Zijlstra
2010-11-17 19:27 ` Oleg Nesterov
2010-11-17 19:42 ` Peter Zijlstra
2010-11-18 14:05 ` Oleg Nesterov
2010-11-18 14:24 ` Peter Zijlstra
2010-11-18 15:32 ` Oleg Nesterov
2010-11-18 14:09 ` [tip:sched/core] " tip-bot for Peter Zijlstra
2010-11-11 14:46 ` [RFC][PATCH 06/22] sched: SCHED_DEADLINE handles spacial kthreads Peter Zijlstra
2010-10-29 6:32 ` [RFC][PATCH 07/22] sched: SCHED_DEADLINE push and pull logic Raistlin
2010-11-12 16:17 ` Peter Zijlstra
2010-11-12 21:11 ` Raistlin
2010-11-14 9:14 ` Raistlin
2010-11-23 14:27 ` Peter Zijlstra
2010-10-29 6:33 ` [RFC][PATCH 08/22] sched: SCHED_DEADLINE avg_update accounting Raistlin
2010-11-11 19:16 ` Peter Zijlstra
2010-10-29 6:34 ` [RFC][PATCH 09/22] sched: add period support for -deadline tasks Raistlin
2010-11-11 19:17 ` Peter Zijlstra
2010-11-11 19:31 ` Raistlin
2010-11-11 19:43 ` Peter Zijlstra
2010-11-11 23:33 ` Tommaso Cucinotta
2010-11-12 13:33 ` Raistlin
2010-11-12 13:45 ` Peter Zijlstra
2010-11-12 13:46 ` Luca Abeni
2010-11-12 14:01 ` Raistlin
2010-10-29 6:35 ` [RFC][PATCH 10/22] sched: add a syscall to wait for the next instance Raistlin
2010-11-11 19:21 ` Peter Zijlstra
2010-11-11 19:33 ` Raistlin
2010-10-29 6:35 ` [RFC][PATCH 11/22] sched: add schedstats for -deadline tasks Raistlin
2010-10-29 6:36 ` [RFC][PATCH 12/22] sched: add runtime reporting " Raistlin
2010-11-11 19:37 ` Peter Zijlstra
2010-11-12 16:15 ` Raistlin
2010-11-12 16:27 ` Peter Zijlstra
2010-11-12 21:12 ` Raistlin
2010-10-29 6:37 ` [RFC][PATCH 13/22] sched: add resource limits " Raistlin
2010-11-11 19:57 ` Peter Zijlstra
2010-11-12 21:30 ` Raistlin
2010-11-12 23:32 ` Peter Zijlstra
2010-10-29 6:38 ` [RFC][PATCH 14/22] sched: add latency tracing " Raistlin
2010-10-29 6:38 ` [RFC][PATCH 15/22] sched: add traceporints " Raistlin
2010-11-11 19:54 ` Peter Zijlstra
2010-11-12 16:13 ` Raistlin
2010-10-29 6:39 ` [RFC][PATCH 16/22] sched: add SMP " Raistlin
2010-10-29 6:40 ` [RFC][PATCH 17/22] sched: add signaling overrunning " Raistlin
2010-11-11 21:58 ` Peter Zijlstra
2010-11-12 15:39 ` Raistlin
2010-11-12 16:04 ` Peter Zijlstra
2010-10-29 6:42 ` [RFC][PATCH 19/22] rtmutex: turn the plist into an rb-tree Raistlin
2010-10-29 6:42 ` [RFC][PATCH 18/22] sched: add reclaiming logic to -deadline tasks Raistlin
2010-11-11 22:12 ` Peter Zijlstra
2010-11-12 15:36 ` Raistlin
2010-11-12 16:04 ` Peter Zijlstra
2010-11-12 17:41 ` Luca Abeni
2010-11-12 17:51 ` Peter Zijlstra
2010-11-12 17:54 ` Luca Abeni
2010-11-13 21:08 ` Raistlin
2010-11-12 18:07 ` Tommaso Cucinotta
2010-11-12 19:07 ` Raistlin
2010-11-13 0:43 ` Peter Zijlstra
2010-11-13 1:49 ` Tommaso Cucinotta [this message]
2010-11-12 18:56 ` Raistlin
[not found] ` <80992760-24F2-42AE-AF2D-15727F6A1C81@email.unc.edu>
2010-11-15 18:37 ` James H. Anderson
2010-11-15 19:23 ` Luca Abeni
2010-11-15 19:49 ` James H. Anderson
2010-11-15 19:39 ` Luca Abeni
2010-11-15 21:34 ` Raistlin
2010-10-29 6:43 ` [RFC][PATCH 20/22] sched: drafted deadline inheritance logic Raistlin
2010-11-11 22:15 ` Peter Zijlstra
2010-11-14 12:00 ` Raistlin
2010-10-29 6:44 ` [RFC][PATCH 21/22] sched: add bandwidth management for sched_dl Raistlin
2010-10-29 6:45 ` [RFC][PATCH 22/22] sched: add sched_dl documentation Raistlin
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=4CDDEEAE.9060706@sssup.it \
--to=tommaso.cucinotta@sssup.it \
--cc=cfriesen@nortel.com \
--cc=claudio@evidence.eu.com \
--cc=darren@dvhart.com \
--cc=dhaval@retis.sssup.it \
--cc=fabio@gandalf.sssup.it \
--cc=fweisbec@gmail.com \
--cc=hgu1972@gmail.com \
--cc=johan.eker@ericsson.com \
--cc=juri.lelli@gmail.com \
--cc=linux-kernel@vger.kernel.org \
--cc=luca.abeni@unitn.it \
--cc=mingo@elte.hu \
--cc=nicola.manica@disi.unitn.it \
--cc=oleg@redhat.com \
--cc=p.faure@akatech.ch \
--cc=paulmck@linux.vnet.ibm.com \
--cc=peterz@infradead.org \
--cc=raistlin@linux.it \
--cc=rostedt@goodmis.org \
--cc=tglx@linutronix.de \
--cc=trimarchi@retis.sssup.it \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).