Re: [ECOS] Re: DSR Scheduling Problem

[Nick Garnett <nickg at ecoscentric dot com>]

Sergei Organov <osv@javad.com> writes:

> Nick Garnett <nickg@ecoscentric.com> writes:
> [...]
> > Stefan's patch, give or take a bit of tidying and name changing, looks
> > just fine.
> 
> Please consider documentation worries I have in the reply to Grant's
> objections I'm going to post in a few minutes.

You have some valid points there. The issues of making the tradeoffs
apparent to the user and how the config options actually work are
tricky, but not insoluble.

> 
> > Adding and removing DSRs remains deterministic, if not quite
> > constant-time, and resolves any reservations I might have about adding
> > FIFO queueing.
> 
> What's less constant-time in FIFO w.r.t. LIFO? Did I miss something?

The LIFO code is straight-line with no tests. Its execution time is
therefore very predictable. The FIFO code contains tests in both the
post and call routines that introduce several different execution
paths that depend on factors outside the control of the current
caller. This introduces more jitter into the execution time. It also
accesses more data in RAM, allowing more scope for cache effects to
change execution time.

In both cases an upper bound on the execution time can be calculated,
so they are both deterministic.

However, the difference in the number of cycles is small and any
application that is sensitive to such a small jitter in DSR post/call
times probably has other more important timing problems to deal with.

> 
> > Most systems do not have interrupts occuring at the sort of rate that
> > would make DSR queueing order make any difference.
> 
> I'm confused. Did you miss in my analysis that maximum DSR latency
> doesn't depend on the rate of interrupts? It was in fact one of my
> primary assumptions that interrupts are rare. I.e., FIFO wins at low
> interrupt rates.

The queueing order only ever matters when there is more than one DSR
on the queue. In the vast majority of systems, interrupts do not occur
at such a high rate. Where multiple DSRs do get queued they are for
unrelated interrupts (e.g. serial+timer+exthernet) and the order in
which they are handled does not matter. What's more important is the
order in which any subsequent threads execute, which is determined by
priority.

The order only really matters when the DSRs are related in some
way. The serial driver problem that kicked this off is an example, and
the CAN driver is another one. Both of these are unusual in various
ways, and I believe could be fixed by a bit of recoding of the ISRs
and DSRs to deal with all pending events on each call.

> 
> > So we should default to the very simplest approach and document the
> > tradeoffs of each mechanism. Subsytems and drivers that really want
> > FIFO queueing can always have a "requires" statement in their CDL for
> > this option.
> 
> If the above indeed were the case, I'd have no objections, but I still
> fail to see *real* trade-offs of FIFO w.r.t. to LIFO.

The main advantage of the LIFO approach over FIFO is its lower
jitter. However, I admit that this is a relatively small effect.

I still think that the LIFO mechanism should be present as an
option. However I would be reasonably happy to see the FIFO mechanism
become the default. The code can be determined correct by inspection,
and the runtime effects of using it are minimal at best.


-- 
Nick Garnett                                          eCos Kernel Architect
http://www.ecoscentric.com                     The eCos and RedBoot experts
Besuchen Sie uns vom 14.-16.02.06 auf der Embedded World 2006, Stand 11-222
Visit us at Embedded World 2006, NÃrnberg, Germany, 14-16 Feb, Stand 11-222


--
Before posting, please read the FAQ: http://ecos.sourceware.org/fom/ecos
and search the list archive: http://ecos.sourceware.org/ml/ecos-discuss