On August 25, 2001 01:03 am, Rik van Riel wrote:
> On Fri, 24 Aug 2001, Daniel Phillips wrote:
>
> > > Actually, no. FIFO would be ok if you had ONE readahead
> > > stream going on, but when you have multiple readahead
> > > streams going on you want to evict the data each of the
> > > streams has already used, and not all the readahead data
> > > which happened to be read in first.
> >
> > We will be fine up until the point that the set of all readahead
> > fills the entire cache, then we will start dropping *some* of
> > the readahead. This will degrade gracefully: if the set of
> > readahead is twice as large as cache then half the readahead
> > will be dropped. We will drop the readahead in coherent chunks
> > so that it can be re-read in one disk seek. This is not such
> > bad behaviour.
>
> The problem is that it WON'T degrade gracefully. Suppose we
> have 5 readahead streams, A B C D and E, and we can store
> 4 readahead windows in RAM without problems. A page which has
> not yet been read is marked with a capital letter, a page
> which has already been read is marked with a small letter.
>
> The queue looks like this, with new pages being added to the
> front and old pages being dropped off the right side:
> AAaaBBbbCCccDDdd
>
> With the current use-once thing, we will end up dropping ALL
> pages from file D, even the ones we are about to use (DDdd).
I call that gracefull. Look, you only lost 2 pages out of 16, and when you
have to re-read them it will be a clustered read. It's just not that big a
deal.
> With drop-behind we'll drop four pages we have already used,
> without affecting the pages we are about to use (dcba).
Well, yes, but you will also drop that header file your compiler wants to
read over and over. How do you tell the difference? There are lots of nice
things you can do if your algorithm can assume omniscience.
> > That said, I think I might be able to come up with something
> > that uses specific knowledge about readahead to squeeze a little
> > better performance out of your example case without breaking
> > loads that are already working pretty well. It will require
> > another lru list - this is not something we want to do right
> > now, don't you agree?
>
> Ummm, if you're still busy trying to come up with the idea,
> how do you already know your future idea will require an extra
> LRU list? ;)
Because it's still in the conceptual stage. Point taken about the readahead,
it wants to have a higher priority than used-once pages. If marked in some
way, the readahead pages could start on the active ring then be moved
immediately to the inactive queue when first used, or after being fully aged
if unused. Write pages on the other hand want to start on the inactive list.
With our current page cache factoring this is a bit of a pain to implement.
My point is, even with the case you supplied the expected behaviour of the
existing algorithm is acceptable. There is no burning fire to put out, not
here anyway.
-- Daniel-- Daniel - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
This archive was generated by hypermail 2b29 : Fri Aug 31 2001 - 21:00:16 EST