Chapter 18: A Simple Example And Overview

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

Prerequisites

Earlier prerequisite concepts leading into Chapter 18: A Simple Example And Overview.

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 18: A Simple Example And Overview". 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 18: Chapter 18: A Simple Example And Overview
Raw source file: 082-18-1-a-simple-example-and-overview.md
Raw source file: 083-18-4-paging-also-too-slow.md

Merged source

A Simple Example And Overview

18.1 A Simple Example And Overview

To help make this approach more clear, let's illustrate it with a simple

example. Figure 18.1 (page 2) presents an example of a tiny address space, only 64 bytes total in size, with four 16-byte pages (virtual pages 0, 1, 2, and 3). Real address spaces are much bigger, of course, commonly 32 bits and thus 4-GB of address space, or even 64 bits1; in the book, we'll often use tiny examples to make them easier to digest.

1A 64-bit address space is hard to imagine, it is so amazingly large. An analogy might help: if you think of a 32-bit address space as the size of a tennis court, a 64-bit address space is about the size of Europe(!).

1 0

(page
of the address space)
(page 1)
(page 2)
(page 3)

Figure 18.1:A Simple 64-byte Address Space

Physical memory, as shown in Figure 18.2, also consists of a number of fixed-sized slots, in this case eight page frames (making for a 128-byte physical memory, also ridiculously small). As you can see in the diagram, the pages of the virtual address space have been placed at different locations throughout physical memory; the diagram also shows the OS using some of physical memory for itself.

Paging, as we will see, has a number of advantages over our previous approaches. Probably the most important improvement will beflexibility: with a fully-developed paging approach, the system will be able to support the abstraction of an address space effectively, regardless of how a process uses the address space; we won't, for example, make assumptions about the direction the heap and stack grow and how they are used.

Another advantage is thesimplicityof free-space management that paging affords. For example, when the OS wishes to place our tiny 64-byte address space into our eight-page physical memory, it simply finds four free pages; perhaps the OS keeps afree listof all free pages for this, and just grabs the first four free pages off of this list. In the example, the OS 0 reserved for OS page frame 0 of physical memory 16 (unused) page frame 1 32 page 3 of AS page frame 2 48 page 0 of AS page frame 3 64 (unused) page frame 4 80 page 2 of AS page frame 5 96 (unused) page frame 6 112 page 1 of AS page frame 7 128

Figure 18.2:A 64-Byte Address Space In A 128-Byte Physical Memory has placed virtual page 0 of the address space (AS) in physical frame 3, virtual page 1 of the AS in physical frame 7, page 2 in frame 5, and page 3 in frame 2. Page frames 1, 4, and 6 are currently free.

To record where each virtual page of the address space is placed in physical memory, the operating system usually keeps aper-process data structure known as apage table. The major role of the page table is to store address translations for each of the virtual pages of the address space, thus letting us know where in physical memory each page resides.

For our simple example (Figure 18.2, page 2), the page table would thus have the following four entries: (Virtual Page 0 →Physical Frame 3), (VP 1→PF 7), (VP 2→PF 5), and (VP 3→PF 2).

It is important to remember that this page table is aper-process data structure (most page table structures we discuss are per-process structures; an exception we'll touch on is theinverted page table). If another process were to run in our example above, the OS would have to manage a different page table for it, as its virtual pages obviously map todifferent physical pages (modulo any sharing going on).

Now, we know enough to perform an address-translation example.

Let's imagine the process with that tiny address space (64 bytes) is performing a memory access:

movl <virtual address>, %eax

Specifically, let's pay attention to the explicit load of the data from

addressinto the registereax(and thus ignore the

instruction fetch that must have happened prior).

Totranslatethis virtual address that the process generated, we have to first split it into two components: thevirtual page number (VPN), and theoffsetwithin the page. For this example, because the virtual address space of the process is 64 bytes, we need 6 bits total for our virtual address (26 = 64). Thus, our virtual address can be conceptualized as follows:

Va5 Va4 Va3 Va2 Va1 Va0

In this diagram, Va5 is the highest-order bit of the virtual address, and

Va0 the lowest-order bit. Because we know the page size (16 bytes), we can further divide the virtual address as follows:

VPN offset

Va5 Va4 Va3 Va2 Va1 Va0

The page size is 16 bytes in a 64-byte address space; thus we need to be able to select 4 pages, and the top 2 bits of the address do just that.

Thus, we have a 2-bit virtual page number (VPN). The remaining bits tell us which byte of the page we are interested in, 4 bits in this case; we call this the offset.

When a process generates a virtual address, the OS and hardware must combine to translate it into a meaningful physical address. For example, let us assume the load above was to virtual address 21:

movl 21, %eax

Turning "21" into binary form, we get "010101", and thus we can examine this virtual address and see how it breaks down into a virtual page number (VPN) and offset:

VPN offset 0 1 0 1 0 1

Thus, the virtual address "21" is on the 5th ("0101"th) byte of virtual page "01" (or 1). With our virtual page number, we can now index our page table and find which physical frame virtual page 1 resides within. In the page table above thephysical frame number (PFN)(also sometimes called thephysical page numberorPPN) is 7 (binary 111). Thus, we can translate this virtual address by replacing the VPN with the PFN and then issue the load to physical memory (Figure 18.3).

Note the offset stays the same (i.e., it is not translated), because the offset just tells us which bytewithinthe page we want. Our final physical address is 1110101 (117 in decimal), and is exactly where we want our load to fetch data from (Figure 18.2, page 2).

With this basic overview in mind, we can now ask (and hopefully, answer) a few basic questions you may have about paging. For example, where are these page tables stored? What are the typical contents of the page table, and how big are the tables? Does paging make the system (too) slow? These and other beguiling questions are answered, at least in part, in the text below. Read on!

VPN offset

Virtual 0 1 0 1 0 1

Address

Translation

Physical 1 1 1 0 1 0 1

Address

PFN offset

Figure 18.3:The Address Translation Process 0 page table:

page frame 0 of physical memory 3 7 5 16 (unused) page frame 1 32 page 3 of AS page frame 2 48 page 0 of AS page frame 3 64 (unused) page frame 4 80 page 2 of AS page frame 5 96 (unused) page frame 6 112 page 1 of AS page frame 7 128

Figure 18.4:Example: Page Table in Kernel Physical Memory 18.2 Where Are Page Tables Stored?

Page tables can get terribly large, much bigger than the small segment table or base/bounds pair we have discussed previously. For example, imagine a typical 32-bit address space, with 4KB pages. This virtual address splits into a 20-bit VPN and 12-bit offset (recall that 10 bits would be needed for a 1KB page size, and just add two more to get to 4KB).

A 20-bit VPN implies that there are220translations that the OS would have to manage for each process (that's roughly a million); assuming we need 4 bytes perpage table entry (PTE)to hold the physical translation plus any other useful stuff, we get an immense 4MB of memory needed for each page table! That is pretty large. Now imagine there are 100 processes running: this means the OS would need 400MB of memory just for all those address translations! Even in the modern era, where machines have gigabytes of memory, it seems a little crazy to use a large chunk of it just for translations, no? And we won't even think about how big such a page table would be for a 64-bit address space; that would be too gruesome and perhaps scare you off entirely.

Because page tables are so big, we don't keep any special on-chip hardware in the MMU to store the page table of the currently-running process.

Instead, we store the page table for each process inmemorysomewhere.

Let's assume for now that the page tables live in physical memory that the OS manages; later we'll see that much of OS memory itself can be virtualized, and thus page tables can be stored in OS virtual memory (and even swapped to disk), but that is too confusing right now, so we'll ignore it. In Figure 18.4 is a picture of a page table in OS memory; see the tiny set of translations in there?

31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1

PFN G D A P

PAT PCDPWTU/SR/W

Figure 18.5:An x86 Page Table Entry (PTE)

Paging Also Too Slow

18.4 Paging: Also Too Slow

18.3 What's Actually In The Page Table?

Let's talk a little about page table organization. The page table is just a data structure that is used to map virtual addresses (or really, virtual page numbers) to physical addresses (physical frame numbers). Thus, any data structure could work. The simplest form is called alinear page table, which is just an array. The OSindexesthe array by the virtual page number (VPN), and looks up the page-table entry (PTE) at that index in order to find the desired physical frame number (PFN). For now, we will assume this simple linear structure; in later chapters, we will make use of more advanced data structures to help solve some problems with paging.

As for the contents of each PTE, we have a number of different bits in there worth understanding at some level. Avalid bitis common to indicate whether the particular translation is valid; for example, when a program starts running, it will have code and heap at one end of its address space, and the stack at the other. All the unused space in-between will be markedinvalid, and if the process tries to access such memory, it will generate a trap to the OS which will likely terminate the process.

Thus, the valid bit is crucial for supporting a sparse address space; by simply marking all the unused pages in the address space invalid, we remove the need to allocate physical frames for those pages and thus save a great deal of memory.

We also might haveprotection bits, indicating whether the page could be read from, written to, or executed from. Again, accessing a page in a way not allowed by these bits will generate a trap to the OS.

There are a couple of other bits that are important but we won't talk about much for now. Apresent bitindicates whether this page is in physical memory or on disk (i.e., it has beenswapped out). We will understand this machinery further when we study how toswapparts of the address space to disk to support address spaces that are larger than physical memory; swapping allows the OS to free up physical memory by moving rarely-used pages to disk. Adirty bitis also common, indicating whether the page has been modified since it was brought into memory.

Areference bit(a.k.a.accessed bit) is sometimes used to track whether a page has been accessed, and is useful in determining which pages are popular and thus should be kept in memory; such knowledge is critical duringpage replacement, a topic we will study in great detail in subsequent chapters.

Figure 18.5 shows an example page table entry from the x86 architecture [I09]. It contains a present bit (P); a read/write bit (R/W) which determines if writes are allowed to this page; a user/supervisor bit (U/S) which determines if user-mode processes can access the page; a few bits (PWT, PCD, PAT, and G) that determine how hardware caching works for these pages; an accessed bit (A) and a dirty bit (D); and finally, the page frame number (PFN) itself.

Read the Intel Architecture Manuals [I09] for more details on x86 paging support. Be forewarned, however; reading manuals such as these, while quite informative (and certainly necessary for those who write code to use such page tables in the OS), can be challenging at first. A little patience, and a lot of desire, is required.

With page tables in memory, we already know that they might be too big. As it turns out, they can slow things down too. For example, take our simple instruction:

movl 21, %eax

Again, let's just examine the explicit reference to address 21 and not worry about the instruction fetch. In this example, we'll assume the hardware performs the translation for us. To fetch the desired data, the system must firsttranslatethe virtual address (21) into the correct physical address (117). Thus, before fetching the data from address 117, the system must first fetch the proper page table entry from the process's page table, perform the translation, and then load the data from physical memory.

To do so, the hardware must know where the page table is for the currently-running process. Let's assume for now that a singlepage-table base registercontains the physical address of the starting location of the page table. To find the location of the desired PTE, the hardware will thus perform the following functions:

VPN = (VirtualAddress & VPN_MASK) >> SHIFT
PTEAddr = PageTableBaseRegister + (VPN * sizeof(PTE))
In our example, VPNMASKwould be set to 0x30 (hex 30, or binary
110000) which picks out the VPN bits from the full virtual address;SHIFT

is set to 4 (the number of bits in the offset), such that we move the VPN bits down to form the correct integer virtual page number. For example, with virtual address 21 (010101), and masking turns this value into 010000; the shift turns it into 01, or virtual page 1, as desired. We then use this value as an index into the array of PTEs pointed to by the page table base register.

Once this physical address is known, the hardware can fetch the PTE from memory, extract the PFN, and concatenate it with the offset from the virtual address to form the desired physical address. Specifically, you can think of the PFN being left-shifted bySHIFT, and then logically OR'd with the offset to form the final address as follows:

offset = VirtualAddress & OFFSET_MASK
PhysAddr = (PFN << SHIFT) | offset
/ Extract the VPN from the virtual address
// Form the address of the page-table entry (PTE)
PTEAddr = PTBR + (VPN * sizeof(PTE))

6 7 // Fetch the PTE

PTE = AccessMemory(PTEAddr)

9 10 // Check if process can access the page

if (PTE.Valid == False)
RaiseException(SEGMENTATION_FAULT)
else if (CanAccess(PTE.ProtectBits) == False)
RaiseException(PROTECTION_FAULT)
else
// Access is OK: form physical address and fetch it
offset = VirtualAddress & OFFSET_MASK
PhysAddr = (PTE.PFN << PFN_SHIFT) | offset
Register = AccessMemory(PhysAddr)

Figure 18.6:Accessing Memory With Paging

Finally, the hardware can fetch the desired data from memory and put it into registereax. The program has now succeeded at loading a value from memory!

To summarize, we now describe the initial protocol for what happens on each memory reference. Figure 18.6 shows the basic approach. For every memory reference (whether an instruction fetch or an explicit load or store), paging requires us to perform one extra memory reference in order to first fetch the translation from the page table. That is a lot of work! Extra memory references are costly, and in this case will likely slow down the process by a factor of two or more.

And now you can hopefully see that there aretworeal problems that we must solve. Without careful design of both hardware and software, page tables will cause the system to run too slowly, as well as take up too much memory. While seemingly a great solution for our memory virtualization needs, these two crucial problems must first be overcome.

18.5 A Memory Trace

Before closing, we now trace through a simple memory access example to demonstrate all of the resulting memory accesses that occur when using paging. The code snippet (in C, in a file calledarray.c) that we are interested in is as follows:

int array[1000];
...
for (i = 0; i < 1000; i++)
array[i] = 0;

We compilearray.cand run it with the following commands:

Learning objectives​

Prerequisites​

Module targets​

AI companion modes​

Source-of-truth note​

External enrichment​

Source provenance​

Merged source​

A Simple Example And Overview​