Skip to main content

Chapter 15: Assumptions

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 Assumptions.
  • Work through the source examples for Assumptions without depending on raw chunk order.
  • Use Assumptions as selective reference when learner modules point back to Ostep.

Prerequisites​

  • Earlier prerequisite concepts leading into Chapter 15: Assumptions.

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 15: Assumptions". 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 15: Chapter 15: Assumptions
  • Raw source file: 065-15-1-assumptions.md
  • Raw source file: 066-15-2-an-example.md

Merged source​

Assumptions​

15.1 Assumptions

15 Mechanism: Address Translation​

In developing the virtualization of the CPU, we focused on a general mechanism known aslimited direct execution (or LDE). The idea behind LDE is simple: for the most part, let the program run directly on the hardware; however, at certain key points in time (such as when a process issues a system call, or a timer interrupt occurs), arrange so that the OS gets involved and makes sure the "right" thing happens. Thus, the OS, with a little hardware support, tries its best to get out of the way of the running program, to deliver anefficientvirtualization; however, byinterposingat those critical points in time, the OS ensures that it maintains controlover the hardware. Efficiency and control together are two of the main goals of any modern operating system.

In virtualizing memory, we will pursue a similar strategy, attaining both efficiency and control while providing the desired virtualization. Efficiency dictates that we make use of hardware support, which at first will be quite rudimentary (e.g., just a few registers) but will grow to be fairly complex (e.g., TLBs, page-table support, and so forth, as you will see). Control implies that the OS ensures that no application is allowed to access any memory but its own; thus, to protect applications from one another, and the OS from applications, we will need help from the hardware here too. Finally, we will need a little more from the VM system, in terms offlexibility; specifically, we'd like for programs to be able to use their address spaces in whatever way they would like, thus making the system easier to program. And thus we arrive at the refined crux:

THECRUX:

HOWTOEFFICIENTLYANDFLEXIBLYVIRTUALIZEMEMORY

How can we build an efficient virtualization of memory? How do we provide the flexibility needed by applications? How do we maintain control over which memory locations an application can access, and thus ensure that application memory accesses are properly restricted? How do we do all of this efficiently?

1

The generic technique we will use, which you can consider an addition to our general approach of limited direct execution, is something that is referred to ashardware-based address translation, or justaddress translationfor short. With address translation, the hardware transforms each memory access (e.g., an instruction fetch, load, or store), changing thevirtualaddress provided by the instruction to aphysicaladdress where the desired information is actually located. Thus, on each and every memory reference, an address translation is performed by the hardware to redirect application memory references to their actual locations in memory.

Of course, the hardware alone cannot virtualize memory, as it just provides the low-level mechanism for doing so efficiently. The OS must get involved at key points to set up the hardware so that the correct translations take place; it must thusmanage memory, keeping track of which locations are free and which are in use, and judiciously intervening to maintain control over how memory is used.

Once again the goal of all of this work is to create a beautiful illusion: that the program has its own private memory, where its own code and data reside. Behind that virtual reality lies the ugly physical truth:

that many programs are actually sharing memory at the same time, as the CPU (or CPUs) switches between running one program and the next.

Through virtualization, the OS (with the hardware's help) turns the ugly machine reality into something that is a useful, powerful, and easy to use abstraction.

Our first attempts at virtualizing memory will be very simple, almost laughably so. Go ahead, laugh all you want; pretty soon it will be the OS laughing at you, when you try to understand the ins and outs of TLBs, multi-level page tables, and other technical wonders. Don't like the idea of the OS laughing at you? Well, you may be out of luck then; that's just how the OS rolls.

Specifically, we will assume for now that the user's address space must be placedcontiguouslyin physical memory. We will also assume, for simplicity, that the size of the address space is not too big; specifically, that it is less than the size of physical memory. Finally, we will also assume that each address space is exactly thesame size. Don't worry if these assumptions sound unrealistic; we will relax them as we go, thus achieving a realistic virtualization of memory.

An Example​

15.2 An Example

To understand better what we need to do to implement address translation, and why we need such a mechanism, let's look at a simple example. Imagine there is a process whose address space is as indicated in

Figure 15.1. What we are going to examine here is a short code sequence

TIP: INTERPOSITIONISPOWERFUL

Interposition is a generic and powerful technique that is often used to great effect in computer systems. In virtualizing memory, the hardware will interpose on each memory access, and translate each virtual address issued by the process to a physical address where the desired information is actually stored. However, the general technique of interposition is much more broadly applicable; indeed, almost any well-defined interface can be interposed upon, to add new functionality or improve some other aspect of the system. One of the usual benefits of such an approach is transparency; the interposition often is done without changing the client of the interface, thus requiring no changes to said client.

that loads a value from memory, increments it by three, and then stores the value back into memory. You can imagine the C-language representation of this code might look like this:

void func() {
int x; x = x + 3; // this is the line of code we are interested in
The compiler turns this line of code into assembly, which might look something like this (in x86 assembly). Useobjdumpon Linux orotool on Mac OS X to disassemble it:
128: movl 0x0(%ebx), %eax ;load 0+ebx into eax 132: addl $0x03, %eax ;add
to eax register 135: movl %eax, 0x0(%ebx) ;store eax back to mem

This code snippet is relatively straightforward; it presumes that the address ofxhas been placed in the registerebx, and then loads the value at that address into the general-purpose registereaxusing themovlinstruction (for "longword" move). The next instruction adds 3 to eax, and the final instruction stores the value ineaxback into memory at that same location.

In Figure 15.1 (page 4), you can see how both the code and data are laid out in the process's address space; the three-instruction code sequence is located at address 128 (in the code section near the top), and the value of the variablexat address 15 KB (in the stack near the bottom). In the figure, the initial value ofxis 3000, as shown in its location on the stack.

When these instructions run, from the perspective of the process, the following memory accesses take place.

  • Fetch instruction at address 128
  • Execute this instruction (load from address 15 KB)
  • Fetch instruction at address 132
  • Execute this instruction (no memory reference)
  • Fetch the instruction at address 135
  • Execute this instruction (store to address 15 KB) 128 movl 0x0(%ebx),%eax 132 addl 0x03, %eax 135 movl %eax,0x0(%ebx) 1KB

Program Code 2KB 3KB Heap 4KB

(free)

14KB 15KB 3000

Stack 16KB

Figure 15.1:A Process And Its Address Space

From the program's perspective, itsaddress spacestarts at address 0 and grows to a maximum of 16 KB; all memory references it generates should be within these bounds. However, to virtualize memory, the OS wants to place the process somewhere else in physical memory, not necessarily at address 0. Thus, we have the problem: how can werelocate this process in memory in a way that istransparentto the process? How can we provide the illusion of a virtual address space starting at 0, when in reality the address space is located at some other physical address?

Operating System 16KB

(not in use)

32KB Code

Heap

(allocated but not in use)

Stack 48KB

Relocated Process

(not in use)

64KB

Figure 15.2:Physical Memory with a Single Relocated Process

An example of what physical memory might look like once this process's address space has been placed in memory is found in Figure 15.2.

In the figure, you can see the OS using the first slot of physical memory for itself, and that it has relocated the process from the example above into the slot starting at physical memory address 32 KB. The other two

slots are free (16 KB-32 KB and 48 KB-64 KB).

15.3 Dynamic (Hardware-based) Relocation

To gain some understanding of hardware-based address translation, we'll first discuss its first incarnation. Introduced in the first time-sharing machines of the late 1950's is a simple idea referred to asbase and bounds; the technique is also referred to as dynamic relocation; we'll use both terms interchangeably [SS74].

Specifically, we'll need two hardware registers within each CPU: one is called thebaseregister, and the other thebounds(sometimes called a limitregister). This base-and-bounds pair is going to allow us to place the address space anywhere we'd like in physical memory, and do so while ensuring that the process can only access its own address space.

In this setup, each program is written and compiled as if it is loaded at address zero. However, when a program starts running, the OS decides where in physical memory it should be loaded and sets the base register to that value. In the example above, the OS decides to load the process at physical address 32 KB and thus sets the base register to this value.

Interesting things start to happen when the process is running. Now, when any memory reference is generated by the process, it istranslated by the processor in the following manner:

physical address = virtual address + base