From owner-freebsd-current Thu Sep 25 20:12:48 1997 Return-Path: Received: (from root@localhost) by hub.freebsd.org (8.8.7/8.8.7) id UAA02746 for current-outgoing; Thu, 25 Sep 1997 20:12:48 -0700 (PDT) Received: from pluto.plutotech.com (root@mail.plutotech.com [206.168.67.137]) by hub.freebsd.org (8.8.7/8.8.7) with ESMTP id UAA02739 for ; Thu, 25 Sep 1997 20:12:44 -0700 (PDT) Received: from narnia.plutotech.com (narnia.plutotech.com [206.168.67.130]) by pluto.plutotech.com (8.8.5/8.8.5) with ESMTP id VAA00273; Thu, 25 Sep 1997 21:12:02 -0600 (MDT) Message-Id: <199709260312.VAA00273@pluto.plutotech.com> X-Mailer: exmh version 2.0zeta 7/24/97 To: Terry Lambert 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) In-reply-to: Your message of "Fri, 26 Sep 1997 02:53:28 -0000." <199709260253.TAA23134@usr05.primenet.com> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Date: Thu, 25 Sep 1997 21:11:49 -0600 From: "Justin T. Gibbs" Sender: owner-freebsd-current@FreeBSD.ORG X-Loop: FreeBSD.org Precedence: bulk >> 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 ===========================================