I'm taking the OS prelim this fall, which means I have to read ~100 papers this summer for background material. Since repetition aids retention, I'm putting notes for papers I read up on my blog. The topics are wide-ranging, so I'm trying to start with the fundamentals and then move on up to the whole-system papers.

I'm kicking it off with "Virtual Memory, Processes, and Sharing in MULTICS" by Daley and Dennis (1968) and "The Multics Virtual Memory: Concepts and Design" by Bensoussan, Clingen, and Daley (1972). Learn about the joys of segmentation and dynamic linking from classic papers from the 70s! These are slightly infamous papers for some systems students here at Berkeley, due to a certain past OS prelim examiner grilling them on exactly these details.

Background Review

Some people consider segmentation to be the most natural way of structuring a program. Most programs are basically a collection of libraries (something really true in modern software engineering). In a segmented virtual memory system, each distinct library is placed in its own separate segment such that it has its own address space. They're still all mapped unto the same flat physical memory address space, but through per-segment base and offset addresses.

This isn't actually used much in modern operating systems for reasons I'm not entirely aware of (I'd guess simplicity and performance), but it's a pleasingly abstract and indirect way of organizing a program (a hallmark of Multics).

Virtual Memory, Processes, and Sharing in MULTICS

Multics structured its programs in terms of segments, which could be read/write/execute protected. Segmentation is great for doing memory protection (and something that only recently reemerged as the NX bit for flat memory models), since it's easy to do a compare on any (base+offset) calculation and see if it falls into a protected range. Segments can still of course be paged, and segmentation and paging are complementary: segmentation for protection, and paging for working set management.

Addressing in Multics is done in terms of a generalized address: (segment num + word num). The segment number of the currently executing segment is stored in the procedure base register, so most instructions just need to specify a word number. Indirect addressing (i.e. referencing an address stored at an address) is done with a pair of instructions to have enough bits: one for the segment number, one for the word number.

A descriptor table is kept of all the segments in a program to map them to hardware addresses. This table maps seg nums to a physical address, and then adds the word num as the offset. This is similar to a page table: virtual to physical address translation. A pointer to the descriptor table is saved as part of the context information of the process.

Now for the complicated bits: dynamic linking. Clearly, we don't want each program to have to have its own copy of shared segments (say, libc), and we want some abstraction so we aren't hardcoding word numbers into our program. This also needs to work for segments linking to other segments which link to other segments, etc., so it gets a little hairy. We also want this to be reasonably fast, e.g. don't do multiple memory accesses for every dynamically linked call, at least after the first time. In list form:

• Dynamically linked accesses are specially marked in the program text
• Dynamically linked segments are present at a well-know path name, e.g. in Linux /usr/lib/ld-linux.so.2, that the system can search for and find (see LD_LIBRARY_PATH).
• Each segments presents a symbol table, which defines the call-in points for the segment (static vars, functions, etc)
• Initially, all calls to an external function are to an indirect reference stored as link data in a per-segment linkage table. This table is initially set to trap to an OS lookup function.
• A linkage pointer to the linkage table is maintained to switch around the table as context changes to different segments.
• On the first reference, the OS lookup function finds the file of the external segment, examines its symbol table, and then links the two segments by updating the link data in the linkage table. Future references use that indirect address to go straight to the external segment.
• A further complication enters when switching the linkage pointers between linked segments. To determine the new value for the linkage pointer, the calling procedure actually calls into the new segment's linkage table, which has special instructions to fixup the linkage pointer and then call the called procedure.
  • Thus: Caller -> Caller's linkage table ~> Callee's linkage table ~> Callee
  • This is direct -> indirect -> indirect, plus a fixup, seems expensive...

This really isn't that different from how Linux does it, the basic idea of "keep a well-known table that fixes itself on the first reference" is a winner. I feel like there are a lot of memory accesses required to traverse all these layers of indirection, since you are calling through multiple layers of indirect addressing, each of which is a pair of instructions.

The Multics Virtual Memory: Concepts and Design

It's weird to hear that back in the days of yore, files could not be easily loaded as program text, and the idea of virtual memory for protection, abstraction, and programmer benefit was a new idea. Users were just allocated a range of memory, or core image, with no sharing between users; if you wanted to work on a "shared file", that meant doing I/O to copy it into your range, and then another I/O to put it back into the filesystem. Each user's core image was also an unstructured jumble of instructions and data, which makes system-level sharing and memory protection basically impossible.

These two goals motivated the design of virtual memory in Multics: sharing and protection. This led to the segmentation, where each segment appears as a flat, linear namespace to the user program, with read/write/execute/append access rights attached as metadata to the segment.

Segments are also paged to ease the allocation problem and to support large segments. Descriptor segments (aka descriptor tables) are also paged for good reason, meaning 4 memory lookups to access a memory location, going through two page tables (one for the descriptor, one for the segment). TLBs work here, but it still sounds slow. Page tables are also a static size, not a tree.

This paper is a decent overview of Multics, probably would have made sense to read it before the dynamic linking one.