[ECOS] Re: DSR Scheduling Problem

[Sergei Organov <osv@javad.com>]

> On 2006-01-14, Jay Foster <jay@systech.com> wrote:
>> I still think that FIFO queuing of the DSRs is better than
>> LIFO queuing, because in the absence of any DSR priority
>> information, the best that can be done is temporal priority
>> (ie FIFO).

Nick Garnett <nickg@ecoscentric.com> writes:
> The LIFO queueing method was chosen because it is fast, deterministic
> and simple to maintain. I would be very reluctant to see a change to
> this unless a *very* good case is made for FIFO order.

Grant Edwards <grante@visi.com> writes:
> That happens to work for your application, but I don't see how
> you can say that FIFO is best in the general case.

That brought an interesting question, so I've tried to figure out some
numbers. I took IRQ-to-corresponding-DSR latency as the comparison
criteria, and my analysis of rather simple system suggests that LIFO
could be 2 times worse than FIFO at some conditions and is never
better. Though I've tried my best to make the comparison fair, I must
admit that I'm somewhat biased in favor of FIFO (LIFO wait queues just
sound wrong in the first place), and I'd be thankful should somebody
find a mistake in my reasonings below.

For the purpose of comparison I considered rather simple yet usual
system with the following properties:

1. There are N independent asynchronous interrupt sources
   IRQ1-IRQN. IRQ1 has highest priority and IRQN has lowest priority.

2. System load is low and each of interrupts happens so rarely that an
   IRQ never occurs when ISR/DSR corresponding to previous IRQ of this
   particular kind is active.

3. ISRs don't nest.

4. Difference between FIFO and LIFO management overheads is negligible
   compared to ISR + DSR execution times.

Now let's try to calculate *maximum* IRQ-to-DSR latency for IRQ1 that
has the highest priority. For simplicity let's assume every ISR handler
takes roughly the same time Ti for execution and every DSR handler takes
roughly the same time Td.

First consider FIFO case.

If Td => Ti, maximum latency is reached, e.g., when all the IRQs but
IRQ1 happen almost simultaneously, then IRQ1 happens just before the
beginning of DSR2 execution:
             IRQ1 
              v
ISR2,...,ISRN, ISR1,DSR2,...,DSRN,DSR1

and maximum IRQ1-to-DSR1 latency LF1 = Ti + Td * (N - 1)

If Ti >= Td, maximum latency is reached when, say, IRQ2 happens, ISR2
begins to execute, then IRQ1,IRQ3,...,IRQN happen almost immediately (in
whatever order). In this case the order of execution is:

IRQ1
v   
ISR2,ISR1,ISR3,...,ISRN,DSR2,DSR1,...,DSRN,

and LF2 = Ti * (N - 1) + Td

Overall, maximum IRQ1-to-DSR1 latency for FIFO policy is:

        | Td * (N - 1) + Ti, Ti <= Td 
LFmax = |
        | Ti * (N - 1) + Td, Ti >= Td


Now consider LIFO case.

The worst case w.r.t. DSR1 latency is:

IRQ1
v   
 ISR1,ISR2,....,ISRN,DSRN,...,DSR2,DSR1

and LL2 = Ti * N + Td * (N - 1)

and maximum IRQ1-to-DSR1 latency for LIFO policy is:

LLmax = Ti * N + Td * (N - 1)


Please note that:

1. LLmax >= LFmax

2. If Ti = Td,  LLmax/LFmax = 2 - 1/N,

   So, maximum DSR latency for the highest priority IRQ could be nearly
   2(!) times more for LIFO policy than for FIFO one.

3. Minimum latencies are the same and are equal to Ti (FIFO vs. LIFO
   overhead aside).

3. Mean latencies are almost the same for LIFO and FIFO policies for our
   system where interrupts occur so rarely that most probable case is
   single ISR followed by corresponding DSR (Lmean~=Ti).


Overall, the above analysis suggests LIFO is never better than FIFO and
it could be much worse than FIFO.

Isn't it time to finally get rid of LIFO wait queues in eCos? Any
objections?

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