From owner-freebsd-current Mon Sep 22 11:37:18 1997 Return-Path: Received: (from root@localhost) by hub.freebsd.org (8.8.7/8.8.7) id LAA07576 for current-outgoing; Mon, 22 Sep 1997 11:37:18 -0700 (PDT) Received: from godzilla.zeta.org.au (godzilla.zeta.org.au [203.2.228.19]) by hub.freebsd.org (8.8.7/8.8.7) with ESMTP id LAA07569 for ; Mon, 22 Sep 1997 11:37:15 -0700 (PDT) Received: (from bde@localhost) by godzilla.zeta.org.au (8.8.5/8.6.9) id EAA25518; Tue, 23 Sep 1997 04:34:51 +1000 Date: Tue, 23 Sep 1997 04:34:51 +1000 From: Bruce Evans Message-Id: <199709221834.EAA25518@godzilla.zeta.org.au> To: bde@zeta.org.au, gibbs@plutotech.com 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 src/sys/i386/eisa 3c5x9.c aha1742.c aic7770.c bt74x.c eisaconf.c eisaconf.h if_fea.c if_vx_eisa.c src/sys/i386/i386 autoconf.c ... Cc: current@FreeBSD.ORG, nate@mt.sri.com Sender: owner-freebsd-current@FreeBSD.ORG X-Loop: FreeBSD.org Precedence: bulk >>>And runs in roughly O(n) time every time the interval timer expires. You >> >>No, it is O(1) in the usual case where the hardware has not timed out, >>and O(n/32) (sic) otherwise (the bitmap can be scanned 32 bits at a time, >>so 630 entries can be scanned in < 1us on a P5). > >Don't you have to look at each transaction when the interval timer goes >off to see which, if any, of the transactions have expired? Remember No, I kept 2 "queues" and expect all the transactions on the head queue to complete before their timeouts expire. >that different transactions can have different timeout intervals. In >the current SCSI system some tape operations have hour long timeouts >while most disk activity is 10s, etc. I cheated here by assuming only one timeout interval (and slop of one more timeout interval) . The pair of queues would have to be repeated for each timeout interval. SCSI timeout intervals are fairly arbitrary, so it might be enough to have timeouts for 1, 10, 100, 1000 and 10000 seconds. >>>also leave out the part about being able to index to transaction whose >>>timer actually expired which will take additional space. >> >>Maybe. I know the drive number and the transaction number, and there's >>presumably at worst a linked list of transactions attached to the drive >>somehow (at best there's an array), and a linear search of this list >>shouldn't take too long for an exceptional action. > >But it does take space. Don't you have to keep the transactions somewhere already? Bruce