Chapter 23: Background

This page is a generated reference surface for selective reading. It exists to keep the learner apps guide-first while still preserving source access.

Learning objectives

• Explain the main ideas and vocabulary in Background.
• Work through the source examples for Background without depending on raw chunk order.
• Use Background as selective reference when learner modules point back to Ostep.

Prerequisites

• Earlier prerequisite concepts leading into Chapter 23: Background.

Module targets

• module-02-memory-management-virtual-memory

AI companion modes

• Explain simply
• Socratic tutor
• Quiz me
• Challenge my understanding
• Diagnose my confusion
• Generate extra practice
• Revision mode
• Connect forward / backward

Source-of-truth note

This unit is anchored to Ostep and the source chapter "Chapter 23: Background". Use external resources only to clarify, extend, or modernize details without replacing the chapter's conceptual spine.

External enrichment

No chapter-specific enrichment resources are curated yet. Add them in the unit manifest when a source clearly improves learning.

Source provenance

• Primary source: Ostep
• Source chapter 23: Chapter 23: Background
• Raw source file: 112-23-1-background.md
• Raw source file: 114-23-4-page-replacement.md
• Raw source file: 115-23-5-other-neat-vm-tricks.md

Merged source

Background

23.1 Background

23 The VAX/VMS Virtual Memory System

Before we end our study of virtual memory, let us take a closer look at one particularly clean and well done virtual memory manager, that found in the VAX/VMS operating system [LL82]. In this note, we will discuss the system to illustrate how some of the concepts brought forth in earlier chapters together in a complete memory manager.

The VAX-11 minicomputer architecture was introduced in the late 1970's byDigital Equipment Corporation(DEC). DEC was a massive player in the computer industry during the era of the mini-computer; unfortunately, a series of bad decisions and the advent of the PC slowly (but surely) led to their demise [C03]. The architecture was realized in a number of implementations, including the VAX-11/780 and the less powerful

VAX-11/750.

The OS for the system was known as VAX/VMS (or just plain VMS), one of whose primary architects was Dave Cutler, who later led the effort to develop Microsoft's Windows NT [C93]. VMS had the general problem that it would be run on a broad range of machines, including very inexpensive VAXen (yes, that is the proper plural) to extremely high-end and powerful machines in the same architecture family. Thus, the OS had to have mechanisms and policies that worked (and worked well) across this huge range of systems.

THECRUX: HOWTOAVOIDTHECURSEOFGENERALITY

Operating systems often have a problem known as "the curse of generality", where they are tasked with general support for a broad class of applications and systems. The fundamental result of the curse is that the

OS is not likely to support any one installation very well. In the case of

VMS, the curse was very real, as the VAX-11 architecture was realized in a number of different implementations. Thus, how can an OS be built so as to run effectively on a wide range of systems?

1

As an additional issue, VMS is an excellent example of software innovations used to hide some of the inherent flaws of the architecture. Although the OS often relies on the hardware to build efficient abstractions and illusions, sometimes the hardware designers don't quite get everything right; in the VAX hardware, we'll see a few examples of this, and what the VMS operating system does to build an effective, working system despite these hardware flaws.

23.2 Memory Management Hardware

The VAX-11 provided a 32-bit virtual address space per process, divided into 512-byte pages. Thus, a virtual address consisted of a 23-bit

VPN and a 9-bit offset. Further, the upper two bits of the VPN were used to differentiate which segment the page resided within; thus, the system was a hybrid of paging and segmentation, as we saw previously.

The lower-half of the address space was known as "process space" and is unique to each process. In the first half of process space (known asP0), the user program is found, as well as a heap which grows downward.

In the second half of process space (P1), we find the stack, which grows upwards. The upper-half of the address space is known as system space (S), although only half of it is used. Protected OS code and data reside here, and the OS is in this way shared across processes.

One major concern of the VMS designers was the incredibly small size of pages in the VAX hardware (512 bytes). This size, chosen for historical reasons, has the fundamental problem of making simple linear page tables excessively large. Thus, one of the first goals of the VMS designers was to make sure that VMS would not overwhelm memory with page tables.

The system reduced the pressure page tables place on memory in two ways. First, by segmenting the user address space into two, the VAX-11

provides a page table for each of these regions (P0andP1) per process;

thus, no page-table space is needed for the unused portion of the address space between the stack and the heap. The base and bounds registers are used as you would expect; a base register holds the address of the page table for that segment, and the bounds holds its size (i.e., number of page-table entries).

Second, the OS reduces memory pressure even further by placing user page tables (forP0andP1, thus two per process) in kernel virtual memory. Thus, when allocating or growing a page table, the kernel allocates space out of its own virtual memory, in segmentS. If memory comes under severe pressure, the kernel can swap pages of these page tables out to disk, thus making physical memory available for other uses.

Putting page tables in kernel virtual memory means that address translation is even further complicated. For example, to translate a virtual address inP0orP1, the hardware has to first try to look up the page-table entry for that page in its page table (theP0orP1page table for that pro-

0 Page 0: Invalid

User Code

User Heap User (P0) 230

User (P1)

User Stack 231

Trap Tables

Kernel Data

Kernel Code

System (S)

Kernel Heap

Unused 232

Figure 23.1:The VAX/VMS Address Space cess); in doing so, however, the hardware may first have to consult the system page table (which lives in physical memory); with that translation complete, the hardware can learn the address of the page of the page table, and then finally learn the address of the desired memory access.

All of this, fortunately, is made faster by the VAX's hardware-managed

TLBs, which usually (hopefully) circumvent this laborious lookup.

23.3 A Real Address Space

One neat aspect of studying VMS is that we can see how a real address space is constructed (Figure 23.1. Thus far, we have assumed a simple address space of just user code, user data, and user heap, but as we can see above, a real address space is notably more complex.

---

Page Replacement

23.4 Page Replacement

The page table entry (PTE) in VAX contains the following bits: a valid bit, a protection field (4 bits), a modify (or dirty) bit, a field reserved for

OS use (5 bits), and finally a physical frame number (PFN) to store the location of the page in physical memory. The astute reader might note:

noreference bit! Thus, the VMS replacement algorithm must make do without hardware support for determining which pages are active.

The developers were also concerned aboutmemory hogs, programs that use a lot of memory and make it hard for other programs to run.

Most of the policies we have looked at thus far are susceptible to such hogging; for example, LRU is aglobalpolicy that doesn't share memory fairly among processes.

Segmented FIFO

To address these two problems, the developers came up with thesegmented FIFOreplacement policy [RL81]. The idea is simple: each process has a maximum number of pages it can keep in memory, known as itsresident set size(RSS). Each of these pages is kept on a FIFO list; when a process exceeds its RSS, the "first-in" page is evicted. FIFO clearly does not need any support from the hardware, and is thus easy to implement.

Of course, pure FIFO does not perform particularly well, as we saw earlier. To improve FIFO's performance, VMS introduced twosecondchance listswhere pages are placed before getting evicted from memory, specifically a globalclean-page free listanddirty-page list. When a process

Pexceeds its RSS, a page is removed from its per-process FIFO; if clean (not modified), it is placed on the end of the clean-page list; if dirty (modified), it is placed on the end of the dirty-page list.

If another processQneeds a free page, it takes the first free page off of the global clean list. However, if the original processPfaults on that

pagebeforeit is reclaimed,Preclaims it from the free (or dirty) list, thus

avoiding a costly disk access. The bigger these global second-chance lists are, the closer the segmented FIFO algorithm performs to LRU [RL81].

Page Clustering

Another optimization used in VMS also helps overcome the small page size in VMS. Specifically, with such small pages, disk I/O during swapping could be highly inefficient, as disks do better with large transfers.

To make swapping I/O more efficient, VMS adds a number of optimizations, but most important is clustering. With clustering, VMS groups large batches of pages together from the global dirty list, and writes them to disk in one fell swoop (thus making them clean). Clustering is used in most modern systems, as the freedom to place pages anywhere within swap space lets the OS group pages, perform fewer and bigger writes, and thus improve performance.

---

Other Neat Vm Tricks

23.5 Other Neat VM Tricks

ASIDE: EMULATINGREFERENCEBITS

As it turns out, you don't need a hardware reference bit in order to get some notion of which pages are in use in a system. In fact, in the early 1980's, Babaoglu and Joy showed that protection bits on the VAX can be used to emulate reference bits [BJ81]. The basic idea: if you want to gain some understanding of which pages are actively being used in a system, mark all of the pages in the page table as inaccessible (but keep around the information as to which pages are really accessible by the process, perhaps in the "reserved OS field" portion of the page table entry). When a process accesses a page, it will generate a trap into the OS; the OS will then check if the page really should be accessible, and if so, revert the page to its normal protections (e.g., read-only, or read-write). At the time of a replacement, the OS can check which pages remain marked inaccessible, and thus get an idea of which pages have not been recently used.

The key to this "emulation" of reference bits is reducing overhead while still obtaining a good idea of page usage. The OS must not be too aggressive in marking pages inaccessible, or overhead would be too high. The

OS also must not be too passive in such marking, or all pages will end up referenced; the OS will again have no good idea which page to evict.

VMS had two other now-standard tricks: demand zeroing and copyon-write. We now describe theselazyoptimizations.

One form of laziness in VMS (and most modern systems) isdemand zeroingof pages. To understand this better, let's consider the example of adding a page to your address space, say in your heap. In a naive implementation, the OS responds to a request to add a page to your heap

by finding a page in physical memory, zeroing it (required for security;

otherwise you'd be able to see what was on the page from when some other process used it!), and then mapping it into your address space (i.e., setting up the page table to refer to that physical page as desired). But the naive implementation can be costly, particularly if the page does not get used by the process.

With demand zeroing, the OS instead does very little work when the page is added to your address space; it puts an entry in the page table that marks the page inaccessible. If the process then reads or writes the page, a trap into the OS takes place. When handling the trap, the OS notices (usually through some bits marked in the "reserved for OS" portion of the page table entry) that this is actually a demand-zero page; at this point, the OS then does the needed work of finding a physical page, zeroing it, and mapping it into the process's address space. If the process never accesses the page, all of this work is avoided, and thus the virtue of demand zeroing.

TIP: BELAZY

Being lazy can be a virtue in both life as well as in operating systems.

Laziness can put off work until later, which is beneficial within an OS for a number of reasons. First, putting off work might reduce the latency of the current operation, thus improving responsiveness; for example, operating systems often report that writes to a file succeeded immediately, and only write them to disk later in the background. Second, and more importantly, laziness sometimes obviates the need to do the work at all; for example, delaying a write until the file is deleted removes the need to do the write at all. Laziness is also good in life: for example, by putting off your OS project, you may find that the project specification bugs are worked out by your fellow classmates; however, the class project is unlikely to get canceled, so being too lazy may be problematic, leading to a late project, bad grade, and a sad professor. Don't make professors sad!

Another cool optimization found in VMS (and again, in virtually every

modern OS) iscopy-on-write(COWfor short). The idea, which goes at

least back to the TENEX operating system [BB+72], is simple: when the

OS needs to copy a page from one address space to another, instead of copying it, it can map it into the target address space and mark it readonly in both address spaces. If both address spaces only read the page, no further action is taken, and thus the OS has realized a fast copy without actually moving any data.

If, however, one of the address spaces does indeed try to write to the page, it will trap into the OS. The OS will then notice that the page is a

COW page, and thus (lazily) allocate a new page, fill it with the data, and map this new page into the address space of the faulting process. The process then continues and now has its own private copy of the page.

COW is useful for a number of reasons. Certainly any sort of shared library can be mapped copy-on-write into the address spaces of many processes, saving valuable memory space. In UNIX systems, COW is even more critical, due to the semantics of fork()andexec(). As you might recall,fork()creates an exact copy of the address space of the caller; with a large address space, making such a copy is slow and data intensive. Even worse, most of the address space is immediately over-written by a subsequent call toexec(), which overlays the calling process's address space with that of the soon-to-be-exec'd program. By instead performing a copy-on-writefork(), the OS avoids much of the needless copying and thus retains the correct semantics while improving performance.

You have now seen a top-to-bottom review of an entire virtual memory system. Hopefully, most of the details were easy to follow, as you should have already had a good understanding of most of the basic mechanisms and policies. More detail is available in the excellent (and short) paper by Levy and Lipman [LL82]; we encourage you to read it, a great way to see what the source material behind these chapters is like.

You should also learn more about the state of the art by reading about

Linux and other modern systems when possible. There is a lot of source material out there, including some reasonable books [BC05]. One thing that will amaze you: how classic ideas, found in old papers such as this one on VAX/VMS, still influence how modern operating systems are built.

[BB+72] "TENEX, A Paged Time Sharing System for the PDP-10"

Daniel G. Bobrow, Jerry D. Burchfiel, Daniel L. Murphy, Raymond S. Tomlinson

Communications of the ACM, Volume 15, March 1972

An early time-sharing OS where a number of good ideas came from. Copy-on-write was just one of those; inspiration for many other aspects of modern systems, including process management, virtual memory, and file systems are found herein.

[BJ81] "Converting a Swap-Based System to do Paging in an Architecture Lacking Page-Reference Bits"

Ozalp Babaoglu and William N. Joy

SOSP '81, Pacific Grove, California, December 1981

A clever idea paper on how to exploit existing protection machinery within a machine in order to emulate reference bits. The idea came from the group at Berkeley working on their own version of UNIX, known as the Berkeley Systems Distribution, or BSD. The group was heavily influential in the development of

UNIX, in virtual memory, file systems, and networking.

[BC05] "Understanding the Linux Kernel (Third Edition)"

Daniel P. Bovet and Marco Cesati

O'Reilly Media, November 2005

One of the many books you can find on Linux. They go out of date quickly, but many of the basics remain and are worth reading about.

[C03] "The Innovator's Dilemma"

Clayton M. Christenson

Harper Paperbacks, January 2003

A fantastic book about the disk-drive industry and how new innovations disrupt existing ones. A good read for business majors and computer scientists alike. Provides insight on how large and successful companies completely fail.

[C93] "Inside Windows NT"

Helen Custer and David Solomon

Microsoft Press, 1993

The book about Windows NT that explains the system top to bottom, in more detail than you might like.

But seriously, a pretty good book.

[LL82] "Virtual Memory Management in the VAX/VMS Operating System"

Henry M. Levy, Peter H. Lipman

IEEE Computer, Volume 15, Number 3 (March 1982)Read the original source of most of this material; it is a concise and easy read. Particularly important if you wish to go to graduate school, where all you do is read papers, work, read some more papers, work more, eventually write a paper, and then work some more. But it is fun!

[RL81] "Segmented FIFO Page Replacement"

Rollins Turner and Henry Levy

SIGMETRICS '81, Las Vegas, Nevada, September 1981

A short paper that shows for some workloads, segmented FIFO can approach the performance of LRU.