[ECOS] Re: DSR Scheduling Problem

[Sergei Organov <osv@javad.com>]

Nick Garnett <nickg@ecoscentric.com> writes:
> Sergei Organov <osv@javad.com> writes:
>
>> Nick Garnett <nickg@ecoscentric.com> writes:
>> [...]
[...]
>> 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.

Thanks for the precise explanation, -- now I see what you mean.

>> > 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.

Sure.

> In the vast majority of systems, interrupts do not occur at such a
> high rate.

???

If you mean that in most systems the probability of more than one DSR
being active at any given time is low, I agree. However, the maximum
possible number of simultaneously posted DSRs is still not less than the
number of asynch interrupt sources in the system.

> 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.

The order by itself doesn't matter, but the IRQ-to-DSR latency does
matter as we still talk about real-time systems, isn't it? And it's
IRQ-to-DSR latency where the FIFO wins as I've hopefully shown in my
analysis.

The fact that FIFO schedules DSRs in more "natural" order than LIFO is
IMHO nice, but it's not primary advantage of the FIFO and has not been
taken into account for the analysis I've made, nevertheless FIFO won.

> What's more important is the order in which any subsequent threads
> execute, which is determined by priority.

By your own logic, the order of execution of otherwise independent
threads also should not matter. What indeed does matter is minimizing
IRQ-to-thread latency, and it's true that either highest priority or
most long waiting thread should (and does) win in this race. Sorry, but
I fail to see why you consider IRQ-to-thread latency to be essential and
IRQ-to-DSR latency not to be that essential.

> The order only really matters when the DSRs are related in some
> way.

Once again, I don't care about the order of DSRs by itself. The
essential thing is that FIFO scheduling policy happens to minimize
maximum IRQ-to-DSR latency making it possible to meet some deadlines
that could be impossible to meet with LIFO policy.

[...]
>> > 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.

Here I do agree. What I've been trying to say is that probably this
relatively small main advantage is too small to excuse addition of yet
another configuration option, but if you guys insist it must be there,
it's OK with me.

> 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.

At the risk of being considered too annoying, here is my last attempt to
change your mind. What do you say if I suggest a patch that will add
CYGIMP_KERNEL_SCHED_LIFO_QUEUES option in addition to existing
CYGIMP_KERNEL_SCHED_SORTED_QUEUES and to the implicit default FIFO using
your own arguments about trade-offs of FIFO vs LIFO ;)

Well, I think we now in fact all understand each other, and whatever the
final decision will be, it's OK with me.

Still not wishing anybody to end up being put into a LIFO wait queue in
the real life ;)

-- Sergei.


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