Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!tut.cis.ohio-state.edu!pt.cs.cmu.edu!MATHOM.GANDALF.CS.CMU.EDU!lindsay
From: lindsay@MATHOM.GANDALF.CS.CMU.EDU (Donald Lindsay)
Newsgroups: comp.arch
Subject: Re: Timers
Message-ID: <10383@pt.cs.cmu.edu>
Date: 4 Sep 90 02:35:52 GMT
References: <5539@darkstar.ucsc.edu> <13285@yunexus.YorkU.CA> <30728@super.ORG> <26012@bellcore.bellcore.com> <11187@alice.UUCP> <1990Aug23.022416.14798@sco.COM> <26196@bellcore.bellcore.com>
Organization: Carnegie-Mellon University, CS/RI
Lines: 79


In article <26196@bellcore.bellcore.com> mo@bellcore.com 
	(Michael O'Dell) writes:
  [describing the timer facilities of the Prisma]
>TOE - Time Of Eternity clock
>	64-bit up-counter, zeroed at machine reset but not randomly
>	loadable, incrementing continuously at the machine cycle clock
>	rate, readable with one alternate-address-space-load-double.
>QCT - Quantum Count-down Timer
>	32-bit down-counter which generates an interrupt when the counter
>	goes to zero.

The upcounter idea is just right. The downcounter, however, has
problems.

To explain why this is so, let me tell you about repetitive
scheduling.  Many real time systems have tasks which must be
performed every T ticks, and schedule creep isn't acceptable.  That
is, the 10th event can happen at 10T + epsilon, but it mustn't happen
at 10T + 10 epsilon. [There are several valid reasons for this.
Perhaps the task will sample data, which we want to graph. Perhaps we
want to FFT the data - which also puts bounds on epsilon.  Perhaps we
have to preserve a statically determined relationship between N such
tasks.]

If the clocks are coarse, repetitive scheduling is impossible or else
easy.  The problem introduced by a fine clock is determining the
_exact_ value to put in the downcounter.  Some software has figured
out the time of the next event: but then we have to know what Now is.

On some machines, Now is hard.  The time Now was scheduled to be, has
gone past: the last interupt's latency has intervened.  Worse, this
latency is affected by interrupt lockout - perhaps the kernel didn't
want to be interrupted.  On some machines, latency even depends on
who was interrupted - e.g. the floating point registers are only
saved if the interrupted task was using them.  Plus, there's the
usual hardware stuff like memory contention.  The crude answer is:

	Now = InterruptScheduledTime + FudgeFactor;

where the fudge factor makes the average about right.  The Prisma
design is obviously better - just consult the TOE register.

But are we out of the woods?  No: if we code something like

	NextTime = ...the minimum of some set of times...;
	DownCountRegister = NextTime - TOE_Register;

then we still get schedule creep.  The assignment takes a nonzero
number of clocks, and worse, it may take a variable number, given
cache misses, bus contention, higher priority interrupts, whatever.
So it's back to

	DownCountRegister = NextTime - TOE_Register - small_fudge_factor;

which will (of course) become wrong when you switch compilers...

We could eliminate the whole headache by scrapping downcounters, and
instead having a comparator on the upcounter.  When the upcounter
equals the value in its Compare Register, then there's an interrupt.
Period.  I'm asking for _very_ simple hardware.  There's no need for
greater-than semantics, because the kernel software can postcheck for
that (if TOE is there to check against):

	NextTime = ...the minimum of some set of times...;
	TOE_CompareRegister = NextTime;                /* COWABUNGA */
	if( NextTime <= TOE_Register ){  	/* check versus Now */
		...unset the compare hardware..
		...mark the process as runnable...
	}

(For five extra points: why code a postcheck, not a precheck?)

In summary: I'm recommending some very simple hardware: an upcounter,
a latch, and an interrupt when they're equal.  But the low price
isn't the virtue: the virtue is that the handler can be Right instead
of just fudged. 
-- 
Don		D.C.Lindsay