Path: utzoo!attcan!uunet!lll-winken!ames!mailrus!tut.cis.ohio-state.edu!ucbvax!agate!saturn!mcvax!cs.aber.ac.uk!pcg@uunet.UU.NET
From: mcvax!cs.aber.ac.uk!pcg@uunet.UU.NET
Newsgroups: comp.os.research
Subject: Inverted page tables
Message-ID: <6527@saturn.ucsc.edu>
Date: 28 Feb 89 11:31:49 GMT
Sender: usenet@saturn.ucsc.edu
Organization: Dept of CS, UCW Aberystwyth
Lines: 37
Approved: comp-os-research@jupiter.ucsc.edu

While IBM claimed in advertisements that they invented virtual memory
(gasp), the first virtual memory machine was the Atlas from Manchester
University. It did have an inverted page table scheme, with a single (small,
20 bit) address space. There are several papers that describe that.

Manchester people took up again inverted page tables for their 64 bit MU6
mini supercomputer, and there are some papers and thesises on that as well.
If you want any information not in published papers, I am sure that Dr. A.
Knowles or Dr. V. Woods of the CS Dept., U. of Manchester, Oxford Rd.,
Manchester, GB, will be able to help.

I have several years ago written a paper on the ins and outs of inverted
page tables, and especially on a fairly original inverted page table design
I made, especially suitable for high performance microprocessors, and its
implications; I have been unable to find the time to revise it for
publication, though.

    Also, I have been very wary of publishing it, because apparently IBM has
    "invented" and patented inverted page tables just a few years ago (ROMP
    and S/38), and I do not want to run into troubles with their claims and
    their well funded lawyers [IBM could patent *you*, and then make you
    find the money to prove in court that you do not belong to them].  In
    other words, all research work on inverted page tables, from Atlas
    (1965) onwards, may elicit IBM's attentions. Be Warned!

Inverted page tables are extremely good for operating systems, as they are
very much more efficient than straight ones, especially for large sparse
address spaces. It is somewhat laborious to implement shared memory with
them, but then of course an operating system need not rely on or support
shared memory (or messsage passing), like MUSS.  On the other hand the
really good use for inverted page tables is for single address space
machines with capability (and not multiple address space) based protection.

An inverted page table MMU can be built out of a few Kbytes of RAM and
of ROM, very easily and cheaply (more so than a traditional one, I guess);
if you have associative RAM, that can only help, and then the ROM for the
hashing becomes unnecessary.