lists.openwall.net   lists  /  announce  owl-users  owl-dev  john-users  john-dev  passwdqc-users  yescrypt  popa3d-users  /  oss-security  kernel-hardening  musl  sabotage  tlsify  passwords  /  crypt-dev  xvendor  /  Bugtraq  Full-Disclosure  linux-kernel  linux-netdev  linux-ext4  linux-hardening  linux-cve-announce  PHC 
Open Source and information security mailing list archives
 
Hash Suite: Windows password security audit tool. GUI, reports in PDF.
[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-ID: <20140127120938.3a8d40fb@gandalf.local.home>
Date:	Mon, 27 Jan 2014 12:09:38 -0500
From:	Steven Rostedt <rostedt@...dmis.org>
To:	Luca Abeni <luca.abeni@...tn.it>
Cc:	Juri Lelli <juri.lelli@...il.com>, peterz@...radead.org,
	tglx@...utronix.de, mingo@...hat.com, oleg@...hat.com,
	fweisbec@...il.com, darren@...art.com, johan.eker@...csson.com,
	p.faure@...tech.ch, linux-kernel@...r.kernel.org,
	claudio@...dence.eu.com, michael@...rulasolutions.com,
	fchecconi@...il.com, tommaso.cucinotta@...up.it,
	nicola.manica@...i.unitn.it, dhaval.giani@...il.com,
	hgu1972@...il.com, paulmck@...ux.vnet.ibm.com, raistlin@...ux.it,
	insop.song@...il.com, liming.wang@...driver.com, jkacur@...hat.com,
	harald.gustafsson@...csson.com, vincent.guittot@...aro.org,
	bruce.ashfield@...driver.com, linux-doc@...r.kernel.org,
	rob@...dley.net
Subject: Re: [PATCH] sched/deadline: Add sched_dl documentation

On Mon, 27 Jan 2014 17:56:07 +0100
Luca Abeni <luca.abeni@...tn.it> wrote:
 
> > > +
> > > +    then, if the scheduling deadline is smaller than the current
> > > time, or
> > > +    this condition is verified, the scheduling deadline and the
> > > +    current budget are re-initialised as
> > > +
> > > +         scheduling deadline = current time + deadline
> > > +         current runtime = runtime
> > > +
> > > +    otherwise, the scheduling deadline and the current runtime are
> > > +    left unchanged;
> > 
> > I've been trying to wrap my head around this a bit. I started writing
> > an email about this when I first examined the patches and never sent
> > it out :-p
> > 
> > Lets take a case where deadline == period. It seems that the above
> > would be true any time there was any delay to starting the task or the
> > task was interrupted by another SCHED_DEADLINE task.
> Not sure about this... Notice that above only applies when a task wakes
> up (moving from a "sleeping" state to a "ready to run" state). Not when
> an already ready task is scheduled.
> Or did I misunderstand your comment?

No no, you understood, I missed that this only happens on wakeup. But
then I have to ask, what happens if the task blocks on a mutex? Would
that cause this check to happen then? It may be nice to add some
comments about exactly when this check is performed.

> 
> 
> > For example, lets say we have two SD tasks. One that has 50ms runtime
> > and a 100ms period. The other has a 1ms runtime and a 10ms period.
> > 
> > The above two should work perfectly fine together. The 10ms period
> > task will constantly schedule in on the 100ms task.
> > 
> > When the 100ms task runs, it could easily be delayed by 1ms due to the
> > 10ms task. Then lets look at the above equation
> See above: the check for the 100ms task is only performed when the task
> unblocks (at the beginning of its period), not when it's scheduled
> (after the 10ms taks).
> 
> This check is designed to take care of the following situation:
> - consider a task with runtime 10ms and period equal to deadline equal
>   to 100ms
> - assume the task wakes up at time t, and is assigned "remaining
>   runtime" 10ms and "scheduling deadline" t+100ms
> - assume the task blocks after executing for 2ms. The "remaining
>   runtime" is now 8ms
> - can the task use "remaining runtime" 8ms and "scheduling deadline"
>   t+100ms when it wakes up again?
>   Answer: if it wakes up before t+20ms, it can. Otherwise, it cannot,
>   because it would consume a fraction of CPU time larger than 10%,
>   causing missed deadlines in other tasks.

Ah, you answered my question here. The check happens every time the
task blocks as well. I still need to read the papers, and even more
importantly, start running more tests with tracing on to review what
exactly happens in the implementation.

> 
> [...]
> > > + SCHED_DEADLINE can be used to schedule real-time tasks
> > > guaranteeing that
> > > + the jobs' deadlines of a task are respected. In order to do this,
> > > a task
> > > + must be scheduled by setting:
> > > +
> > > +  - runtime >= WCET
> > > +  - deadline = D
> > > +  - period <= P
> > > +
> > > + IOW, if runtime >= WCET and if period is >= P, then the
> > > scheduling deadlines
> > > + and the absolute deadlines (d_j) coincide, so a proper admission
> > > control
> > > + allows to respect the jobs' absolute deadlines for this task
> > > (this is what is
> > > + called "hard schedulability property" and is an extension of
> > > Lemma 1 of [2]).
> > 
> > I wonder if we should state the obvious (which is never obvious). That
> > is the user must also have the following.
> > 
> >   runtime < deadline <= period
> > 
> > Although it is fine for deadline = period, runtime should be less than
> > deadline, otherwise the task will take over the system.
> I think if "runtime < deadline <= period" is not respected, then the
> admission control will fail... But yes, repeating it here can be
> useful. If needed I'll add it to the document.

Yeah, it's one of those things that you should know, but I can see
users screwing it up ;-)

-- Steve

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

Powered by blists - more mailing lists

Powered by Openwall GNU/*/Linux Powered by OpenVZ