From owner-freebsd-current Thu Sep 25 20:41:57 1997 Return-Path: Received: (from root@localhost) by hub.freebsd.org (8.8.7/8.8.7) id UAA03998 for current-outgoing; Thu, 25 Sep 1997 20:41:57 -0700 (PDT) Received: from usr05.primenet.com (tlambert@usr05.primenet.com [206.165.6.205]) by hub.freebsd.org (8.8.7/8.8.7) with ESMTP id UAA03992 for ; Thu, 25 Sep 1997 20:41:55 -0700 (PDT) Received: (from tlambert@localhost) by usr05.primenet.com (8.8.5/8.8.5) id UAA28703; Thu, 25 Sep 1997 20:41:33 -0700 (MST) From: Terry Lambert Message-Id: <199709260341.UAA28703@usr05.primenet.com> Subject: Re: TCP timers (Was: Re: new timeout routines) To: gibbs@plutotech.com (Justin T. Gibbs) Date: Fri, 26 Sep 1997 03:41:33 +0000 (GMT) Cc: tlambert@primenet.com, gibbs@plutotech.com, dg@root.com, ccsanady@bob.scl.ameslab.gov, current@FreeBSD.ORG In-Reply-To: <199709260312.VAA00273@pluto.plutotech.com> from "Justin T. Gibbs" at Sep 25, 97 09:11:49 pm X-Mailer: ELM [version 2.4 PL23] Content-Type: text Sender: owner-freebsd-current@FreeBSD.ORG X-Loop: FreeBSD.org Precedence: bulk > >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.