Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!uunet!mcsun!tuvie!vmars!alex
From: alex@vmars.tuwien.ac.at (Alexander Vrchoticky)
Newsgroups: comp.realtime
Subject: Re: Software primitives for real-time programming languages
Message-ID: <1892@tuvie>
Date: 28 Sep 90 14:33:36 GMT
References: <1853@tuvie> <232@srchtec.UUCP> <1889@tuvie> <243@srchtec.UUCP>
Sender: news@tuvie
Lines: 48

johnb@srchtec.UUCP (John Baldwin) writes:

>The possibility I was thinking of is the case where *some* of your
>task set have a safe exit state, and/or some of them can safely miss
>their deadlines under certain circumstances.  It is nice to be able
>to plan beforehand and say: under the following conditions, we know
>that tasks A, B, and R will be preempted indefinately, while tasks
>X and Y are still guaranteed to make their deadlines, which they MUST
>in every circumstance.

One way to do this is by employing a very static approach where the possible
scenarios are pre-planned and where we can guarantee beforehand
that the system will work under the anticipated conditions. 
This is the approach I'd take for such systems.

I can imagine that value functions could be used for this purpose as well.
However the description by David Maynard (dpm@cs.cmu.edu) suggests 
that the on-line scheduling problem (maximizing the overall value) 
is similar to the bin-packing problem and 
therefore NP-hard (correct me if I'm mistaken).  
Considering that it has to be executed in parallel with the `real' work
I guess that sub-optimal schedules are the best one can hope for. 

So in order to be able to employ those in safety-critical systems
one would have to have a-priori quantitative measures for the reliability of
such systems .. i.e. statements like `under the stated circumstances the
probability that this tasks misses its deadline is less than 1e-6'
Can such statements be analytically derived from the description of 
the task system, processor allocation, and value functions? 
If so, how? 

It is obvious that when the requirements are not exactly known 
one simply cannot build a system that is guaranteed to meet all deadlines;
and I agree that research into how to build systems that still provide 
reasonable service under unpredicted circumstances is important. 
But I believe that the techniques necessary for such `best-effort' systems 
are not necessarily the same than those for hard real-time systems.

Of course I go along with David Maynard in hoping for a unified
theory and method for building both types of systems. 
But this is going to be a very difficult goal, to say the least.

-alex

--
Alexander Vrchoticky  Technical University Vienna, Dept. for Real-Time Systems
Voice:  +43/222/58801-8168   Fax: +43/222/569149
e-mail: alex@vmars.tuwien.ac.at or vmars!alex@relay.eu.net  (Don't use 'r'!)