[TUHS] Early Unix paging

[Paul Ruizendaal]

Following the recent discussion on this list about early paging systems and John Reiser’s work in this area, I succeeded in reaching out to him. It is all very long ago, but John’s recollection is that his paging system work was initially done late in 1979 or maybe 1980. This matches with Rob Pike’s memory of seeing it demoed in early 1981.

John’s recollection confirms that his design implemented mmap and copy-on-write, and was integrated with the file buffer cache (all features that Norman Wilson also remembered).

I have appended John’s message below (with permission). I am not sure I understand - at this time - how John’s code was multiplexing page table entries with kernel data structures beyond what is mentioned, but I think it might be an interesting summer project to see how much of the design can be resurrected using related code, old documents and memories.

Paul

====

> I joined Bell Labs department 1135 ("Interactive Computer Systems Research")
> at Holmdel, NJ in Feb.1977.  I soon gained fame by re-writing the C pre-processor,
> which was bug-infested and slow.  (" 1.e4 " was recognized as an opportunity
> to expand the macro "e4", instead of as a floating-point constant.)
> cpp used to take 15% to 18% of total CPU compile time.  My replacement code
> was 2% to 3%.  The average improvement was a factor of 7; the minimum:
> a factor of 5; the best: a factor of 11 or 12.
> During the rest of 1977, I became dissatisfied with our PDP-11/45 (and other's
> PDP-11/70), having spent a few student years at Stanford Univ and its AI Lab,
> where PDP-6 and PDP-10 reigned.  So Tom London and I wrote an "internal grant"
> for $250,000 to get a new machine, with a "research goal" of exploring CCD
> (charge coupled device) which was promised to replace spinning harddrive.
> Actual CCD  product never appeared until flash memory devices in 1990s
> and SSD (current solid state drive) later.
> 
> Our VAX-11/780, the first one delivered to a customer, arrived Feb.12, 1978
> (Lincoln's Birthday).  Tom and I had been preparing using PDP-11/45 since
> December, and we achieved "login: " on the console DECwriter by April 15
> (the deadline for US income tax filing).  The rest of 1978 was "tuning",
> and preparing for the release of "UNIX-32/V" to UC Berkeley.  My annual
> performance review in early 1979 said "Well done; but don't ever do it again"
> because it was not regarded as "Research".
> So what did I do?  I did it again; this time, with demand paging.
> I designed and implemented mmap() based on experience with PDP-10/Tenex
> PMAP page mapping system call.  I fretted over introducing the first
> UNIX system call with 6 arguments.
> 
> The internal design of the paging mechanism "broke the rules" by having a
> non-hierarchical dependency:  A1 calls B1 calls A2 calls B2 where {A1, A2}
> are parts of one subsystem, and {B1, B2} are parts of another subsystem.
> (One subsystem was the buffer cache; I forget what was the other subsystem.)
> Our machine started with 512KB of RAM, but within a few months was upgraded
> to 4 MB with boards that used a new generation of RAM chips.
> The hardware page size was 512 bytes, which is quite small.  Strict LRU
> on 8,192 pages, plus Copy-On-Write, made the second reference to a page
> "blindingly fast".  It was impressive, running sometime in 1979 or 1980,
> I think.  But it was not "Research", so I got many fewer accolades.
> My internal design strategy was to use the hardware page table entry
> (4 bytes per page, with "page not present" being one bit which freed
> the other 31 bits for use by software) as the anchor to track everything
> about a page.  This resulted in a complicated union of bitfield structs,
> which became a headache.  When other departments took over the work,
> the first thing they did was use 8 bytes per page, which meant shuffling
> between the software and the hardware descriptors: its own mess.
> I wasn't interested in maintaining a paging system, so I moved on
> to other things such as design of integrated circuits using
> Carver-Mead methodology.