Date: Tue, 23 Sep 1997 02:33:39 -0700 (PDT) From: Julian Elischer <julian@whistle.com> To: "Justin T. Gibbs" <gibbs@plutotech.com> Cc: Terry Lambert <tlambert@primenet.com>, nate@mt.sri.com, bde@zeta.org.au, current@FreeBSD.ORG Subject: Re: cvs commit: src/sys/conf files src/sys/dev/vx if_vx.c if_vxreg.h src/sys/i386/apm apm.c src/sys/i386/conf GENERIC files.i386 Message-ID: <Pine.BSF.3.95.970923013950.9006B-100000@current1.whistle.com> In-Reply-To: <199709230630.AAA13505@pluto.plutotech.com>
next in thread | previous in thread | raw e-mail | index | archive | help
On Tue, 23 Sep 1997, Justin T. Gibbs wrote: > >> >Queue the entry for ordered insertion when timeout() is called, but > >> >delay the ordered insertion until softclock(). his was one of the things I have been wondering about. if each spoke of the wheel had an orderd and an unordered queue, then items would USUALLY be removed before their bucket was accessed. Any remaining ones could be moved to the ordered "long term" queue. In fact it might be arguable that they could be removed from the wheel entirely after surviving a full rotation of the softclock. They could be inserted into a timeout queue not disimilar to that we already run. The point is that there are several distinct usage models for the timeout facility. They have differnt characteristics.. HARDWARE FAILURE TIMEOUTS: nearly ALWAYS expected to be removed very quickly. Ordering these is a complete waste of time. PERIODIC EVENTS: nearly always time out. These tend to be of duration of a large fraction of a second. Possibly it might be more efficient to have a different mechanism for periodic events. LONG TERM EVENT timing: These tend to be longer in duration, but are not recuring. These will be hit by the softclock several times. This could be considered a waste of resources, if we could hold them off for a while we should. > >> > >> Sounds like it will take additional space. I guess that's unarguable. But a large wheel implies a lot of processes which implies a lot of RAM :) > Two pointers is additional space. It also makes softclock become > q * O(h) + O(c) where q is the number of defered insertion entries, > h is the hash chain length and c is the number of empty buckets > that are traversed to find the next timeout for scheduling the next > one shot. I see it as being (on each softclock) O(H x C)+1 where H is the unexpired (remaining) unorderd entries and C is the length of the unordered queue for that bucket. The hope is that MOST short term items are removed BEFORE the softclock gets to them, and that any remaining items are probably long term items that should not be examined at every following rotation. I would even consider that there should be 3 (!) entries at each bucket. Items move in un-sorted order from 1 to 2 and are then inserted in order into 3. Items going into 3 are Guarenteed to have survived at LEAST one full rotation, and can be assumed to be long-term. If the wheel is very sparcely populated it doesn't gain much, but then again it isn't that much more expensive than what you have now. When the wheel get's heavily populated, or when there are a lot of long-term entries it saves time. > Then there is the additional code in softclock to ensure > that none of the timeouts queued while softclock is running are > supposed to expire in the current tick which you would need to > check every time softclock drops from splhigh to let other interrupts > run as there is nothing to prevent a timeout handler or interrupt > handler from scheduling such an entry. Sure, it's do-able, but > the current implementation doesn't have any of this mess and still > gets the O(1) insertion and softclock pays a single O(h). Moving the items from queue 1 to queue 2 to queue 3 can make the whole thing less susceptible to spl issues. first, check the ordered queue. O(1) Then move items from 2 into the orderded queue (3). (hopefully few) Then move items from the head of 1 to the tail of 2. (moving being not much more expensive than checking) These were my thoughts while reading the paper. I was a little dissapointed that you didn't implement the compatible interface that they originally wrote. WHat is the right answer will depend greatly on the particular usage model. A method of trying to handle these different models is probably worth working for. Especialy as networking code switches to using more generic timeouts. If you disconnect a network, we suddenly get hundreds of actual networking timeouts..... > > > 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?Pine.BSF.3.95.970923013950.9006B-100000>