Messages in this thread | | | Date | Fri, 27 Feb 2004 14:29:06 -0600 | From | Matt Mackall <> | Subject | Re: Why no interrupt priorities? |
| |
On Fri, Feb 27, 2004 at 11:09:14AM -0800, Tim Hockin wrote: > On Fri, Feb 27, 2004 at 12:55:55PM -0600, Matt Mackall wrote: > > Let's imagine you have n sources simultaneously interrupting on a > > given descriptor. Check the first, it's happening, acknowledge it, > > exit, notice interrupt still asserted, check the first, nope, check > > the second, yep, exit, etc. By the time we've made it to the nth ISR, > > we've banged on the first one n times, the second n-1 times, etc. In > > other words, early chain termination has an O(n^2) worst case. > > That is a pretty pathological worst case, and n is (almost?) always small. > I don't know if it would make a lick of difference, or if it is worth the > risk. Someone who has a lot of shared interrupts ought to try it.
For small n, it shouldn't make a difference. With early exit, best case you end up walking half the chain on average, worst case you hit the quadratic behavior. Given that the likelihood of contention rises with chain length, we tend to lean towards the latter for larger n. For try-them-all, we test n in all cases. So we've got [n/2] < n < n^2/2. The try-them-all approach wins by virtue of being deterministic and nicely bounded.
Oh, another concern is that early-exit lets sources in the front of the chain starve the remainder and doing bookkeeping on last-ISR-succeeded so that we can have some sort of fairness is just not worth the trouble. So nix on the whole idea.
-- Matt Mackall : http://www.selenic.com : Linux development and consulting - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
| |