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

[Henrik Austad <henrik@austad.us>]

[-- Attachment #1: Type: text/plain, Size: 2149 bytes --]

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

[-- Attachment #2: This is a digitally signed message part. --]
[-- Type: application/pgp-signature, Size: 189 bytes --]