Date: Thu, 25 Sep 1997 21:11:49 -0600 From: "Justin T. Gibbs" <gibbs@plutotech.com> To: Terry Lambert <tlambert@primenet.com> Cc: gibbs@plutotech.com (Justin T. Gibbs), dg@root.com, ccsanady@bob.scl.ameslab.gov, current@FreeBSD.ORG Subject: Re: TCP timers (Was: Re: new timeout routines) Message-ID: <199709260312.VAA00273@pluto.plutotech.com> In-Reply-To: Your message of "Fri, 26 Sep 1997 02:53:28 -0000." <199709260253.TAA23134@usr05.primenet.com>
next in thread | previous in thread | raw e-mail | index | archive | help
>> Archie's design is similar to having a set of hierarchical timing wheels >> which would handle large loads of timers with varying lifespans and >> chances of expiration better than the single level wheel we have now. >> I think that this is a better approach than having an ordered/unordered >> list for each bucket. > >I still like the ordered list for the O(n+1) event processing for n >events in the process of expiring for a given tick. You would get this with the hierarchical approach. The bottom timing wheel only stores entries that will expire on the tick represented by the next bucket to process. The next timing wheel up needs to have one of it's hash chains "re-inserted" into the lower timing wheel every "lower timing wheel size" ticks. The further out from expiring an entry is, the less often it needs to be touched. In the Linux implementation of this, there are 5 wheels, so an entry will be touched at most 5 times by "softclock" and each insertion takes O(1). >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. >> See the G.Varghese and A. Lauck paper I referenced yesturday: >> >> http://dworkin.wustl.edu/~varghese/PAPERS/twheel.ps.Z > >Will do, as soon as I get ghostscript compiled up... is there a >readable version of the paper anywhere meanwhile? Not that I know of. > Regards, > Terry Lambert > terry@lambert.org >--- >Any opinions in this posting are my own and not those of my present >or previous employers. > -- Justin T. Gibbs =========================================== FreeBSD: Turning PCs into workstations ===========================================
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?199709260312.VAA00273>