Nick Garnett <[EMAIL PROTECTED]> writes: > Sergei Organov <[EMAIL PROTECTED]> writes: > >> Nick Garnett <[EMAIL PROTECTED]> 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
