Path: utzoo!utgpu!jarvis.csri.toronto.edu!cs.utexas.edu!uunet!mcsun!ukc!dcl-cs!aber-cs!pcg
From: pcg@aber-cs.UUCP (Piercarlo Grandi)
Newsgroups: comp.arch
Subject: Re: 64-bit addresses
Summary: Two problems with reverse map page tables, easily cured.
Message-ID: <1662@aber-cs.UUCP>
Date: 23 Feb 90 14:42:42 GMT
Reply-To: pcg@cs.aber.ac.uk (Piercarlo Grandi)
Organization: Dept of CS, UCW Aberystwyth
	(Disclaimer: my statements are purely personal)
Lines: 63

In article <43367@ames.arc.nasa.gov> lamaster@ames.arc.nasa.gov (Hugh LaMaster) writes:
  In article <6998@celit.fps.com> ps@fps.com (Patricia Shanahan) writes:
  >In article <29718@brunix.UUCP> phg@cs.brown.edu (Peter H. Golde) writes:
  >>One might note that implementing a 64-bit address space
  >>with 64 KB pages and 8 bytes/page in the page table requires
  >>2 billion megabytes of page-table space.  Hmmmmm.....
  >If the real memory is small compared to the address space, don't use page
  >tables. If you must use page tables, design them as sparse arrays.
  
  1) Several posters have mentioned that there is some unspecified but obvious
  (to them) major problem with using inverted page tables together with
  memory mapped files.  I wonder if someone could enlighten us regarding
  this problem, since apparently it isn't obvious to every system architect :-)

There actually two problems:

A) to do address translation you want to have a direct map. This means that
to fill the TLB you have to scan the reverse map until you find the wanted
virtual addr. This scan can be organized in many ways, of course.

B) You have difficulty supporting shared pages. A physical page cannot
contain an arbitrarily long list of virtual addresses mapped to it.  There
are two workarounds, to forbid shared memory entirely (the best solution, as
I have already argued, also from a logical point of view), and sharing
*segments* using indirect segment capabilities (which slows down things a
bit on every reference). There is a third workaround, which is to change the
virtual address associated to every shared page, on every context switch.
This is practical only for relatively small memories, or with hardware
assist, or anyhow is not desirable because it raises the cost of context
switching.

The p.r. problem with reverse map MMUs is that the ROMP reverse MMU caused
more than a few pains to the CMU people porting MACH, which is heavvily
shared memory oriented.

  2) It isn't apparent to me that page size is really a function of physical
  memory size so much as it is of processing speed. [ .... ]

Page size ought to be *only* determined by what makes the working set
smallest, and this points to very small page sizes, indeed it points to
object memory, like the Burroughs. In practice you also have that fine
granularity is swamped by high overheads, mainly the IO ones, so you have to
make do with coarser granularity than you'd like.

The solution is not to make pages larger to amortize overheads over a larger
granule; this is the Berkeley/SUN style hack. Nice people try to reduce
overheads (CCDs and bubbles were hailed as what could make object virtual
memory practical) or try to use dynamic, adaptive groupingof small objects.

A large page size implies coarse, static grouping of objects, and
approximates the correct policy, and poorly, only in the case of sequential
access, for which it also approximates prefetching. Otherwise it is
a loss, as observed in Ritchie (or Thompson's) observation in "The UNIX
IO system" (or "The UNIX system") paper as to the issue of whether to
double the block size to 1024 bytes.

The eight kilobyte page size of SUNs (one of the two nasty consequences of
their regrettable MMU design) is probably one of the two major factors
in the extremely poor memory-wise performance of SunOS 4.
-- 
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