🚀 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 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, but apparently this is not too bad. There
is some paper comparing pff and ws in some oldish issue of an ieee journal.

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, that is a non optimal space time
integral, for the sake of exploiting the disc's bandwidth.

Admittedly, given that knees are pronounced in many quantity vs. performance
curves, this is is not expected to give much better performace; but the real
point is that probably pff is more flexible that ws, as the job mix changes.
Moreover, paging device bandwidth is often *the* bottleneck, and pff is
driven by it directly.

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, especially with pff.

   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