[TUHS] Evolution of Unix (demand) paging 1980-1985

[TUHS] Evolution of Unix (demand) paging 1980-1985

[Paul Ruizendaal via TUHS]

As an offshoot of looking more closely at 32V, SysIII and 8th Edition I got interested in how each managed memory.

I’ve not deep-dived into the code yet, but from cursory inspection and searching past posts on this list, I get to the following summary:

- As has been documented widely, 32V essentially retained the V7 swapping architecture, merely increasing the maximum process size a bit versus the PDP-11 version.

- SysIII appears to have retained this, just cleaning up the source code a bit. I assume that all the V7/SysIII derivatives of the early 80’s were swapping systems.

- John Reiser further developed 32V memory management into a (reportedly elegant) demand paging system in 1980-1981, but this code appears lost.

- 3BSD/4BSD/4.1BSD developed 32V memory management into a full demand paging setup as well. This code base was dominant in the 1980-1985 era.

- 8th Edition pulled in the BSD VM code and is essentially identical to that in 4.1BSD. This choice was made because it was not a research interest and using a maintained code base freed up scarce time.

- SysV R1 appears to have retained the SysIII memory system.

- SysV R2 (floating about on the net, eg. here https://github.com/ryanwoodsmall/oldsysv) seems to have used a new implementation.


Questions:

Is that about correct, or am I missing major elements?

Several places mention that there was also a setup that was still swapping in nature, but did not require allocations in core to be contiguous (“scatter paging”). Did this get used much in the era?

At first glance, the SysV R2 code seems shorter and cleaner than the early BSD code (~2000 vs. ~3000 sloc). Is this implementation perhaps a derivative of John Reiser’s work?

Re: [TUHS] Evolution of Unix (demand) paging 1980-1985

[Clem Cole]

[-- Attachment #1: Type: text/plain, Size: 3545 bytes --]

On Sat, May 1, 2021 at 6:09 AM Paul Ruizendaal via TUHS <
tuhs@minnie.tuhs.org> wrote:

> Questions:
>
> Is that about correct, or am I missing major elements?
>
I'm going to stretch your time frame a little, but this is what I remember:


SRV3 was an alternative that was more widely distributed than SVR2.  This
is described in Maury Bach's book.   It was the basis that the VM in the
Stellar machine (we would do a bit of a rewrite to make it reentrant and
multi-threaded).   SVR4 would eventually do that as well (not nearly as
well in IMO - but alas Stellix is lost to winds I fear).

Sun did their own, which Rob and Larry can describe.  I don't think they
cribbed much from anyone, but I would ask.

DG/UX was a scratch kernel rewrote with its own VM code.  Probably the
nicest scheme I ever saw.   Extremely clean and easy to understand the
locks.  I've often wondered what happened to that code case.  It's too bad
it not to be found these days.

The CMU Mach code would be very widely used and is still in the wide in Mac
OSx and iOS.   Tru64 and the Intel paragon were also based on the system.

By the time of the Linux VM, the Mach code was what many people were
comparing things to.   The Mach VM code was extremely flexible and could
handle a number of different types of HW and paging/backing store schemes
(had a 'plugin' called the pager) and of course worked well on SMP's from
time t0, but if you look that codebase was huge and noted to be slow.
 Even when the OSF/1 and CMU folks created the Mach ukernel, it was a bit
of joke as the Mach 386/uk was over 1.2M of memory before any of the
servers started to run (at one point they talked about creating a
nanokernel and moving the MMU code out of the UK but I don't think anyone
ever did).

The Chorus folks had something different yet that A&T was excited about as
an alternative to Mach, but I don't think it went very far.


> Several places mention that there was also a setup that was still swapping
> in nature, but did not require allocations in core to be contiguous
> (“scatter paging”). Did this get used much in the era?
>
Depends on the code base and if the kernel could use the FS for paging or
needed a dedicated paging file.   In that era, most systems had a dedicated
area (either disk partition or reserved file on the FS).  If it uses the
FS, then it tended to be able to handle the pages being scattered.   We did
that on Stellix and IIRC, DG could also.

Masscomp and the Intel Paragon did not because predictable performance on a
fault was important, although Masscomp cheated later on since we had
contiguous files support and eventually allow those files to be used for
paging also.


> At first glance, the SysV R2 code seems shorter and cleaner than the early
> BSD code (~2000 vs. ~3000 sloc).

At the time, the SysV VM code was often considered easier to work, a tad
less Vax dependent.  Which again, ask Rob or Larry, I think is why Sun
rewrote the BSD for their use.   We used a BSD base at Masscomp because it
worked, but ... Tom, Terry, and I had long memories of making the original
BSD code MP-safe for the MC-500/DP [which was the first commercial MP
UNIX].   So by Stellar time, since we had a 'do over,' we started with the
SVR3 code and thread it for exactly this reason.


> Is this implementation perhaps a derivative of John Reiser’s work?

I don't know, but you might ask someone like Steve Rago, who I believe was
part of the implementation team.
ᐧ

[-- Attachment #2: Type: text/html, Size: 7097 bytes --]

Re: [TUHS] Evolution of Unix (demand) paging 1980-1985

[Paul Ruizendaal via TUHS]

> On 1 May 2021, at 16:42, Clem Cole <clemc@ccc.com> wrote:

Thanks for that context Clem!
 
>> Is this implementation perhaps a derivative of John Reiser’s work?
> I don't know, but you might ask someone like Steve Rago, who I believe was part of the implementation team.

I did a bit more googling and this list and the AUUGN archive gave some interesting results. It would seem that Keith Kellman and Steven Buroff are the key people for more insight into the Reiser paging system (see below for some quotes).

Based on the below my hypothesis would be that when looking at the surviving SYSV R2.4 paging code, Kellman and Buroff mainly added the “Region” abstraction (~900 sloc), and that the actual paging (~1100 sloc) probably is a close derivative of the Reiser code.

A more speculative hypothesis would be that moving that actual paging code to SysIII, replacing the Region abstraction with the classic shared text abstraction (as present since the V4 days), would result in something close to what Rob and Norman recall.

As you already pointed out, the paging code in R2.4 carries through to R3 and is described in the Bach book.

Paul

====

TUHS list (Rob Pike, Aug 2019)

I think it was slightly later. I joined mid-1980 and VAXes to replace the
11/70 were being discussed but had not arrived. We needed to convert a lab
into a VAX machine room and decide between BSD and Reiser, all of which
happened in the second half of 1980.

Reiser Unix got demand paging a little later, and it was spectacularly
fast. I remember being gobsmacked when I saw a demo in early 1981.

Dead ends everywhere.

====

TUHS list (Norman Wilson, Aug 2019)

John Reiser did do his own paging system for UNIX 32/V.
I heard about it from friends at Bell Labs ca. 1982-83,
when I was still running systems for physicists at Caltech.
It sounded very interesting, and I would love to have had
my hands on it--page cache unified with buffer cache,
copy-on-write from the start.

The trouble is that Reiser worked in a different group
from the original UNIX crowd, and his management didn't
think his time well spent on that work, so it never got
released.

I remember asking, either during my interview at the Labs
or after I started work there, why the 4.1 kernel had been
chosen instead of Reiser's.  It had to do with maintainability:
there were already people who could come in and hack on the
Berkeley system, as well as more using it and maintaining it,
whereas Reiser's system had become a unicorn.  Nobody in
1127 wanted to maintain a VM system or anything much close
to the VAX hardware.  So the decision was to stick with a
kernel for which someone else would do those things.

Once I'd been there for a year or so and settled in, I found
that I was actually looking after all that stuff, because I
was really interested in it.  (Which seemed to delight a lot
of people.)  Would we have ended up using Reiser's kernel had
I been there a couple of years earlier?  I don't know.

It is in any case a shame that jfr's code never saw the light
of day.  I really hope someone can find it on an old tape
somewhere and we can get it into the archive, if only because
I'd love to look at it.

====

AUUGN Vol 5.1 (Keith Kellman, Dec 1983)

Two research derivatives of the UNIX system have supported paging for several years: Reiser 32V, and BSD. Work is under way at AT&T Bell Labs to bring together the features of both of these systems [and others] to form a demand paged kernel for UNIX System V. This talk will discuss three areas of this work: requirements, architecture, and implementation.

The primary requirement of the paging system is that it be upward compatible with its predecessor. This means that old objects must execute unchanged, and that the meaning of system calls should not be changed. For example, fork(2) should be made efficient rather than inventing a new type of call. A second requirement is that the paging system be based on a general machine-independent architecture.

As part of the paging kernel development, a UNIX system memory management architecture is being defined. The architecture is general enough to support both paging and swapping kernels and many different memory management units. The fundamental component of the architecture is the "region." A region is a kernel data structure that represents a potential virtual address space. The basic operations defined for regions are: create/destroy, attach/detach, copy, change size, and load a file. The defined architecture can support potential new UNIX system features such as shared libraries and mapped files.

====

AUUGN Vol 5.3 (Keith Kellman, Feb 1984)

Work is currently underway at AT&T Bell Laboratories to develop a demand paged kernel for UNIX System V. It is hoped that it will utilize the best features of both 32V and BSD.

Some of the requirements for the System V paging is that it will require no program changes -- it will not change system calls. A priority is to not hurt those who don’t need paging -- there should be no performance loss. Also, as part of the development, there will be a definition of memory management architecture -- the architecture must be general enough to support many different memory management units, paging and swapping kernels. A main component of the architecture is the "region." A region is a data structure within a system that represents a potential virtual address space.

The reason for not merely supporting Berkeley paging is because AT&T feels it is too complex and too specific to the VAX (not portable enough). They also do not like the vfork call, and claim there is no well-defined architecture.

The status of the project is that there is currently a prototype implemented on the 3B20 computer. The performance is good relative to System V, Release 2. They are currently porting it to a VAX

====

AUUGN Vol 5.6 (Steven Buroff, Nov 1984)

Two research derivatives of the UNIX system have supported paging for several years: Reiser 32V, and BSD. Work is under way at AT&T Bell Labs to bring together the features of both of the systems [and others] to form a demand paged kernel for UNIX System V. This talk will discuss three areas of this work: requirements, architecture, and implementation.

The requirements are: there should be no user program changes for either binary or source; the system must not hurt users who don’t require paging, this means that if you want to use a paging system because it is faster, then you can do so; and the system should provide the capability of large address spaces if that is wanted.

The idea was to generate a general model of memory management in the UNIX kernel and to abstract all the code which deals with it into one generalised set of routines. Different memory allocation methods can then be used because a clean internal interface has been designed. The main primitive in the design is a Region, which is an area of memory. It can be shared or private and is manipulated by a set of well defined operations. These operations are: create, delete, attach, detach, grow, load and copy. The system allows copy on write by adroit use of the page descriptors.

====