Path: utzoo!utgpu!jarvis.csri.toronto.edu!rutgers!tut.cis.ohio-state.edu!att!cbnewsh!dwc
From: dwc@cbnewsh.ATT.COM (Malaclypse the Elder)
Newsgroups: comp.arch
Subject: Re: Memory utilization & inter-process contention
Message-ID: <3398@cbnewsh.ATT.COM>
Date: 28 Aug 89 22:35:15 GMT
References: <3332@blake.acs.washington.edu> <261500008@S34.Prime.COM> <2389@auspex.auspex.com>
Organization: The Legion of Dynamic Discord
Lines: 36


i've been doing work on demand paging for unix system v for quite
some time and one of the more interesting papers i came across was
a paper by some dec people on a "segmented fifo" approach to local
page replacement.  i don't know if it is what they use in vms but
the gist of the approach is that fifo is not too bad since a replacement
page can be found very quickly.  it has been labeled "bad" by academia
because of belady's "fifo anomaly" which showed that with fifo, there
exist "some reference strings" in which having more memory will lead
to more faults than with smaller allocations.

now this is only my opinion, but i believe that it does not pay to
worry about such situations as long as, in general, giving more memory
leads to less page faults.  and fifo does exhibit this trend.  however,
the other "problem" is that based on some simulations with some reference
strings, fifo seems not to do as well as lru.  the "segmented fifo" attempts
to approximate lru performance by setting the page table entries for a
"small number" of pages at the head of the fifo to fault on reference.
this fault results in the page moving to the back of the queue (ie no
longer a candidate for stealing) and thus approximates lru.

anyway, in my studies, i have also come to the conclusion that a reference
bit may not be that desirable anyway since you don't necessarily want to do
a linear scan of all the page table entries of either a process (local
stealing) or the system (global stealing) in order to find a page to steal.
and there are people here who were looking at working set schedulers
for system v that attempt to address the issues presented by the original
poster.  but we have to re-engineer those ideas for sun's VM architecture
which makes its system v debut in release 4 and it remains to be seen if
those ideas are compatible with the VM architecture.

of course, this is only my view of things and i can't speak for any
of the people who make the actual decisions about what gets in.

danny chen
att!hocus!dwc