🚀 go-pugleaf

In article <3398@cbnewsh.ATT.COM> dwc@cbnewsh.ATT.COM (Malaclypse the Elder) writes:

   i've been doing work on demand paging for unix system v for quite
   some time [ ... ] 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.

The non monotonicity of fifo is not terribly worrying. As long as you can
show that it does not occur frequently.

My own favorite page replacement policy is (local) page fault
frequency, as it automatically balances the load between memory and
and disc. The great advantage of ws over pff is that ws performance is
not very sensitive to its parameters, so tuning is not difficult, while pff
is not so lucky. Pff, by the way, is non monotonical.

A very interesting, forgotten article by Dijkstra argues for
essentially what is essentially pff.  The argument is compelling;
ws minimizes the space time integral, and pff balances the load
between disc and memory. That is ws is optimal only if the
configuration is optimally balanced for the job mix running on
it, because the lowest space time integral gives the lowest cost
only in that case.  Example: assume that memory is scarce
relatively to disc bandwidth; it may well pay to allow higher
page fault rates, up to filling the disc bandwidth.

Another interesting idea contained in Dijkstra's paper is that it
would be nice, actually very very nice, if the hw had ways to
cheaply calculate the page fault rate with one page more and one
page less than those allocated to the current job. This would
improve working set selection very much.

   however, the other "problem" is that based on some simulations with some
   reference strings, fifo seems not to do as well as lru. 

Fifo is bad because usage frequency does not really feed back, of course,
and locality info is not exploited very well.

   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.

There are shortcuts. A paper I remember on SIGOPS detailed the
design of the Univac 80 (IBM lookalike, ex RCA) ws pager. It
tried hard to minimize such overheads, and to provide an
efficient proxy to the true ws rule of time based victim
selection. Seemed well done. Another interesting (old as well) paper
seems to be that describing the VM ws pager done at Grenoble.

The current situation is that clock pagers in BSD and system V
are not nice.

The BSD pager was designed very very well by an extremely
competent person with a specialization in performance analysis of
virtual memory; unfortunately it was developed on a machine with
512Kbytes. On today's machines with 8-16-32 Mbytes, a clock scan
may take several minutes, making the well designed algorithm
essentially useless. A good example of how unanticipated changes
of scale make algorithms inappropriate.

   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.

The system V pager also uses clock, with the same problem. Too bad that
the system V pager interacts with one of the worst swappers around. I would
really like AT&T to redesign the system V swapper. Even Bach says it stinks.

   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.

I hope that system V.4 has a better pager and swapper. It is not
true like many people assume that memory is infinite and all
machines are single user, so paging essentially never occurs and
swapping should never occur.  On top of that, the SUN vm
architecture is not the most smooth around; it was designed with
the SUN hacker's principle in mind, "as long as it performs/works
in some frequent enough cases, people will buy it".
--
Piercarlo "Peter" Grandi           | ARPA: pcg%cs.aber.ac.uk@nsfnet-relay.ac.uk
Dept of CS, UCW Aberystwyth        | UUCP: ...!mcvax!ukc!aber-cs!pcg
Penglais, Aberystwyth SY23 3BZ, UK | INET: pcg@cs.aber.ac.uk