[TUHS] 32V memory management: not quite V7 style swapping

[TUHS] 32V memory management: not quite V7 style swapping

[Paul Ruizendaal via TUHS]

Received wisdom is that 32V used V7 style swapping for memory management. Over the past days I’ve come to the conclusion that this is a very partial truth and only holds true for 32V as it existed in the first half of 1978. In the second half of ’78 it implemented something that is referred to as “scatter loading” which is an interesting halfway house on the road to demand paging. It was also used in the VAX version of Sys III (and presumably in SysV R1 and early R2).

In the 32V report from July 1978 it says:

"Like the UNIX system for the PDP-11, the current implementation for the VAX-11/780 maintains each process in contiguous physical memory and swaps processes to disk when there is not enough physical memory to contain them all. Reducing external memory fragmentation to zero by utilizing the VAX- 11/780 memory mapping hardware for scatter loading is high on the list of things to do in the second implementation pass. To simplify kernel memory allocation, the size of the user-segment memory map is an assembly parameter which currently allows three pages of page table or 192K bytes total for text, data, and stack.” (https://www.bell-labs.com/usr/dmr/www/otherports/32v.pdf).

It turns out that scatter loading was added in the next months, and it was this version that was used as the basis for 3BSD and SysIII.

Babaoglu & Joy write:

"Except for the machine-dependent sections of code, UNIX for the VAX was quite similar to that for the PDP-11 which has a 16-bit address space and no paging hardware. It made no use of the memory-management hardware available on the VAX aside from simulating the PDP-11 segment registers with VAX page table entries. The main-memory management schemes employed by this first version of the system were identical to their PDP-11 counterparts -- processes were allocated contiguous blocks of real memory on a first-fit basis and were swapped in their entirety. A subsequent version of the system was capable of loading processes into noncontiguous real memory locations, called scatter loading, and was able to swap only portions of a process, called partial swapping, as deemed necessary by the memory contention. This would become the basis for the paging system development discussed in this paper.” (https://www.researchgate.net/publication/247924813_Converting_a_swap-based_system_to_do_paging_in_an_architecture_lacking_page-referenced_bits)

The 32V code on the TUHS website (e.g. here https://www.tuhs.org/cgi-bin/utree.pl?file=32V) is actually this later scatter loading code, and not the early 1978 code that used V7 style memory management. The 32-bit Sys III code is closely related (see https://www.tuhs.org/cgi-bin/utree.pl?file=SysIII/usr/src/uts/vax).

===

My current understanding of how scatter loading worked (based on a brief code review) is as follows:

(Note that on the VAX pages/frames are 512 bytes and the page list is essentially single level; page lists grow quickly. It is also unusual in the sense that user page table entries point to kernel virtual memory, but kernel page table entries point to physical memory).

- Each process keeps a list of pages in its u-area (a page table prototype, if you will). This list is fixed size and allows up to 512KB per process in 32V and ~2.5MB per process in Sys III (i.e up to 1024 resp. 5120 pages).

- The kernel keeps a bitmap of free/used frames in physical memory.

- When a process loads/grows, the bitmap is scanned for free frames, these are marked as in-use, and added to the u-area list. If there are not enough free pages a process is selected for swapping out. Swapping out is gradual, in 8KB chunks in 32V and 32KB chunks in SysIII. When a process shrinks or completes, its pages are added back to the bitmap.

- When a partially swapped out process needs to run, the swapped out part is loaded back similar to the above. Partial swap-outs truncate the process, so everything above the remaining size needs to re-load.

- The user process page table is not swapped, but recreated from the u-area data instead.

- When switching between user processes, the kernel needs to update 16 (32V) or 40 (SysIII) kernel page table entries to update the user memory map.

Scatter loading and partial swapping seem to be a major improvement over V7 style swapping, although it of course falls short of demand paging. So far I have not seen bits of code that suggest ‘lazy loading’ or copy-on-write functionality in 32V or Sys III, but these things would not seem impossible to do in this memory management scheme.

In short, the view that “32V used V7 style swapping” seems to be an oversimplification.