linux-kernel - Re: RFC for a new Scheduling policy/class in the Linux-kernel

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: <200907170941.01559.henrik@austad.us>
Date:	Fri, 17 Jul 2009 09:40:59 +0200
From:	Henrik Austad <henrik@...tad.us>
To:	Ted Baker <baker@...fsu.edu>
Cc:	"James H. Anderson" <anderson@...unc.edu>,
	Peter Zijlstra <a.p.zijlstra@...llo.nl>,
	Chris Friesen <cfriesen@...tel.com>,
	Raistlin <raistlin@...ux.it>,
	Douglas Niehaus <niehaus@...c.ku.edu>,
	LKML <linux-kernel@...r.kernel.org>, Ingo Molnar <mingo@...e.hu>,
	Bill Huey <billh@...ppy.monkey.org>,
	Linux RT <linux-rt-users@...r.kernel.org>,
	Fabio Checconi <fabio@...dalf.sssup.it>,
	Thomas Gleixner <tglx@...utronix.de>,
	Dhaval Giani <dhaval.giani@...il.com>,
	Noah Watkins <jayhawk@....ucsc.edu>,
	KUSP Google Group <kusp@...glegroups.com>,
	Tommaso Cucinotta <cucinotta@...up.it>,
	Giuseppe Lipari <lipari@...is.sssup.it>,
	Bjoern Brandenburg <bbb@...unc.edu>
Subject: Re: RFC for a new Scheduling policy/class in the Linux-kernel

On Wednesday 15 July 2009 23:53:05 Ted Baker wrote:
> On Tue, Jul 14, 2009 at 09:28:47PM +0200, Henrik Austad wrote:
> > ... In MC you need to do this the hard way, namely compute the
> > point in time not when the task misses the deadline, but when it
> > will *eventually* fail a deadline. By doing that, you combine
> > deadline, wcet and granted time in one variable, and you have a
> > *single* variable to compare.
>
> This is true in a theoretical sense, and is the basis of some
> "optimal" scheduling algorithms, including the "throwforward
> scheduling" algorithm.  It makes sense in some environments, where
> you actually know the WCET of the task in advance.  However, I
> don't believe a Linux system can expect all applications to
> provide this kind of information.

Why cannot you expect real-time tasks using a deadline scheduler to provide 
some estimate of the execution cost? How can you ever hope to run a deadline 
scheduler without this?

> In a system programmed using process and threads, the decision to
> sleep or wake is embedded in the internal logic of the thread, and
> implemented by system calls.  The existing system calls do not
> convey how long the thread needs to execute before it reaches its
> next suspension point.  Therefore, without a new API you cannot
> use WCET. 

Yes, you would need to introduce a new set of syscalls. 2 in fact. When 
working with PD^2, I added 3 (as reweighing was a special case), but:

sched_dl_update(pid, wcet, period, deadline)
sched_dl_release(pid, abs_releease_time)

How can you use deadlines based on priorities? A priority is a one-way mapping 
of deadlines for a set of tasks.

> If you create a new API for this, you are limiting this 
> form of scheduling to threads that choose to use that API, and are
> able to provide the needed WCET information.  This seems like a
> small number of cases among the full range of real-time Linux
> applications.

Are we going to place all tasks in the kernel into rt-deadline tasks? I had 
the impression that we wanted a class for a special set of tasks. 

> Ted

-- 
     henrik

Download attachment "signature.asc " of type "application/pgp-signature" (190 bytes)