Path: utzoo!utgpu!watserv1!watmath!att!pacbell!pacbell.com!decwrl!uunet!mcsun!ukc!reading!minster!ken
From: ken@minster.york.ac.uk
Newsgroups: comp.realtime
Subject: Re: Technical Details (was Re: Measuring timing of Realtime Systems)
Message-ID: <652724186.2468@minster.york.ac.uk>
Date: 7 Sep 90 16:16:26 GMT
References: <9724@tekigm2.MEN.TEK.COM> <12582@netcom.UUCP> <182@srchtec.UUCP> <1990Aug29.152604.28573@zip.eecs.umich.edu>
Reply-To: ken@SoftEng.UUCP (ken)
Organization: Department of Computer Science, University of York, England
Lines: 47
Status: R

In article <182@srchtec.UUCP> johnb@srchtec.UUCP (John Baldwin) writes:
>Not to start flames, but I must comment that it is about time we had some
>*real* real-time postings....

Quite agree. Get sick of all these "Our Real-Time Unix runs NFS" postings.

In article <1990Aug29.152604.28573@zip.eecs.umich.edu> walden@dip.eecs.umich.edu (Eugene Marvin Walden) writes:
>   No, there really aren't. If an algorithm is proven to be optimal, as the RM
>scheduling algorithm has been, then there is no "better" algorithm. In the case
>of scheduling periodic tasks with priorities that remain constant through their
>lifetime ("static" scheduling) on a single processor, the RM algorithm is op-
>timal. Period.

It is important to state what "optimal" means. Optimal here means "all
deadlines are met".

>[...] The hottest open topic in real-time scheduling re-
>search is the problem of scheduling real-time tasks on a multiprocessor system.
>This problem has been proven to be NP-complete (unsolvable) in the general
>case. This means that no "optimal" algorithm will be possible with a reasonable
>amount of computing time. 

"Optimal" here means something else, like "best load balance", or "lowest
network bandwidth", in addition to "all deadlines are met".

NP-Complete does _not_ mean unsolvable! There are techniques for finding
optimal or very near optimal solutions to these problems! I have a program
which takes a communicating set of tasks and allocates them to a number of
processors, guaranteeing that deadlines are met. It produces results that
are very good. I can't check them as being optimal, except by enumerating
all solutions. With 9 tasks and 5 processors it takes 450 seconds to check
them all (my program got the optimal one straight off). With the big problem
I have (38 tasks, 4 task replicas, 8 processors) it would take 10^28
years to check!  The program takes a bit of time to run (40 seconds) so
you can't use it on-line, so tasks have static properties (fixed
period, fixed CPU time, fixed memory). It will handle aperiodics via
deferable servers. I've got a paper on this, but I'm looking for a
journal without a backlog of 10^28 years...

>   - Eugene Walden (walden@dip.eecs.umich.edu)

--
Ken Tindell             UUCP:     ..!mcsun!ukc!minster!ken
Computer Science Dept.  Internet: ken%minster.york.ac.uk@nsfnet-relay.ac.uk
York University,        Tel.:     +44-904-433244
YO1 5DD
UK