CS 105

Paging

Address Spaces and Virtual Memory

Often in discussing virtual memory, we use the term “address space”. But what is an address space, really? What does it mean for a process to have its own address space?

Multi-Level Page Tables

In the lectures, we imagined page tables as a single array of entries, like the page table shown below:

Page Frames Page Table
A Larger Page Table

We can make two (other) observations about this page table:

  • It's sparse. Many of the entries are empty.
  • Pages are allocated in contiguous regions, so the page table tends to have long runs of unused entries.

Which suggests a way we could shorten our page table—and use less memory!

Notice that the page table has a blue line every eight entries, dividing the table into blocks of eight pages.

If we look at each block of pages, we can see that some blocks have pages in use (darker colors), and some do not. Since we only care about the memory that's in use, we can drop the empty blocks, which leaves us with three separate eight-slot page tables with pointers to physical memory frames.

Now we add a new eight-slot upper-level page table whose in-use slots point to the appropriate subtable, giving us a hierarchical or multi-level page table.

Lower Tables Page Frames Upper Table
A Multi-Level Page Table

(Notice that when there is no memory allocated in a block, we can simply have the upper-level page table entry point not point anywhere instead of a to subtable. This is how we can save memory by not allocating subtables for blocks of pages that are not in use.)

In the first diagram, how many bits of the virtual address are used to index into the page table?

In the second diagram, how many bits of the virtual address are used to index into the upper page table?

And how many bits are used to index into the relevant lower page table?

When we specified the upper and lower page tables (for our simple example with eight entries per table), we used first three bits for the upper page table and then three bits for the lower page table. Could we have done it the other way around, using the first three bits for the lower page table and then three bits for the upper page table? Why or why not?

A 32-bit system with 4 KB pages would typically use a two-level page table with the same number of bits for the upper and lower page tables. How many bits would be used for the upper and lower page tables in this case? Explain your answer.

What has become more expensive with this design and how can we mitigate that cost?

(When logged in, completion status appears here.)