|
From: Jeremy F. <je...@go...> - 2002-11-22 02:53:21
|
On Thu, 2002-11-21 at 15:31, Julian Seward wrote:
> Ha, that sounds like it might work well enough. I sometimes wondered
> how OSs implement the pseudo-LRU stuff for VMs. Is there a standard
> description of this, that you know of?
This is called the one-hand clock algorithm. The two-hand variant is
used when the scan over the whole of memory would take too long, and you
want to test before a complete pass has been made. I don't know what
the standard reference is, but I think pretty much all OS books talk
about it (Tannenbaum, for example).
> Yes, that is the simplest thing, but I fear it would be very expensive.
> A less radical similar scheme is to randomly discard some fraction of
> the translations. Then you get into schemes where you randomly move
> some fraction of the translations into a "victimisation cache" (in
> hardware speak). If they turn out to be needed again soon, they can
> be moved back from the cache back into the main set of active translations.
> If the V-cache gets full _it_ then is flushed. This scheme has the
> effect of somewhat mitigating the situation where a translation is
> randomly selected for demotion and then used again soon afterwards.
> But it's all a bit complex.
Dynamo doesn't quite dump everything when the cache gets full. It keeps
track of the rate of creation of new basic blocks, and dumps the cache
when this starts getting high, on the grounds that the program is
entering a new working set and the cache is stale anyway. You could
define "too high" in terms of how full the cache is in proportion to the
size you'd like it to be, since you'd obviously like a high cache fill
rate when the cache is empty.
A generational caching scheme sounds good, so long as it doesn't
actually involve physically moving the code.
J
|