Date: Fri, 26 Sep 1997 03:41:33 +0000 (GMT) From: Terry Lambert <tlambert@primenet.com> To: gibbs@plutotech.com (Justin T. Gibbs) Cc: tlambert@primenet.com, gibbs@plutotech.com, dg@root.com, ccsanady@bob.scl.ameslab.gov, current@FreeBSD.ORG Subject: Re: TCP timers (Was: Re: new timeout routines) Message-ID: <199709260341.UAA28703@usr05.primenet.com> In-Reply-To: <199709260312.VAA00273@pluto.plutotech.com> from "Justin T. Gibbs" at Sep 25, 97 09:11:49 pm
next in thread | previous in thread | raw e-mail | index | archive | help
> >How would you handle RT events and priority-lent non-RT events > >for processes blocking RT required resources, without using a > >time/priority ordered list, where the RT events were inserted first? > > This wasn't your original question, but I would probably pay the price of > doing that sort during expiration processing using a bucket sort. All > events in the bucket you're working on are supposed to expire, so you need > to touch them all anyway, so performing an O(n) sort doesn't seem > inappropriate. This is especially true if, as would probably be the case > in a high resolution system, few entries are expected to expire at the > exact same time. If there are few entries, this is happy. If there are more than one or two entries, this becomes less happy. By putting the sort at the time the timer expires, you delay starting the callout for the highest priority RT event. This isn't disasterous, given that there is a hell of a lot of indeterminate slack in the kernel elsewhere, but it would push out the "maximum possible time to process". Ideally, all of the indeterminate slack everywhere will go away, at some point in the (realistically, not near) future. This is one of the places which would have to change at that point anyway. Sorted insertion makes this a non-issue, since you process the insertions after the softclock callouts are processed. Insertion still looks, to the external caller, to be O(1), and priority is established before processing. This may be possible to handle by making another wheel where the actual queueing is done O(1), and then handling one "spoke" of ordered insertions per softclock one softclock ahead. This fits the multiwheel approach, and the sorting is kind of like an event that is scheduled to take place every softclock. 8-). Logically, though, theres no real difference between a seperate wheel vs. a seperate head on a single wheel. The one-ahead fixes the problem of events scheduled for exactly one softclock later (randomly scheduled events always occur 0 <= x < 1 softclocks early... anything that ups this slack is only more of a problem). Regards, Terry Lambert terry@lambert.org --- Any opinions in this posting are my own and not those of my present or previous employers.
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?199709260341.UAA28703>