Most virtual memory systems use a technique called paging, which we will
now describe. On any computer, programs reference a set of memory addresses.
When a program executes an instruction like
MOV REG,1000
it does so to copy the contents of memory address 1000 to REG (or vice versa, depending on the computer). Addresses can be generated using indexing, base registers, segment registers, and other ways.
CPU
package
CPU
The CPU sends virtual
addresses to the MMU
The MMU sends physical
addresses to the memory
Memory
management
unit
Memory Disk
controller
Bus
Figure 3-8. The position and function of the MMU. Here the MMU is shown as
being a part of the CPU chip because it commonly is nowadays. However, logically it could be a separate chip and was years ago.
These program-generated addresses are called virtual addresses and form the
virtual address space. On computers without virtual memory, the virtual address
196 MEMORY MANAGEMENT CHAP. 3
is put directly onto the memory bus and causes the physical memory word with the
same address to be read or written. When virtual memory is used, the virtual addresses do not go directly to the memory bus. Instead, they go to an MMU (Memory Management Unit) that maps the virtual addresses onto the physical memory
addresses, as illustrated in Fig. 3-8.
A very simple example of how this mapping works is shown in Fig. 3-9. In
this example, we have a computer that generates 16-bit addresses, from 0 up to
64K − 1. These are the virtual addresses. This computer, howev er, has only 32 KB
of physical memory. So although 64-KB programs can be written, they cannot be
loaded into memory in their entirety and run. A complete copy of a program’s core
image, up to 64 KB, must be present on the disk, however, so that pieces can be
brought in as needed.
The virtual address space consists of fixed-size units called pages. The corresponding units in the physical memory are called page frames. The pages and page
frames are generally the same size. In this example they are 4 KB, but page sizes
from 512 bytes to a gigabyte have been used in real systems. With 64 KB of virtual
address space and 32 KB of physical memory, we get 16 virtual pages and 8 page
frames. Transfers between RAM and disk are always in whole pages. Many processors support multiple page sizes that can be mixed and matched as the operating
system sees fit. For instance, the x86-64 architecture supports 4-KB, 2-MB, and
1-GB pages, so we could use 4-KB pages for user applications and a single 1-GB
page for the kernel. We will see later why it is sometimes better to use a single
large page, rather than a large number of small ones.
The notation in Fig. 3-9 is as follows. The range marked 0K–4K means that
the virtual or physical addresses in that page are 0 to 4095. The range 4K–8K
refers to addresses 4096 to 8191, and so on. Each page contains exactly 4096 addresses starting at a multiple of 4096 and ending one shy of a multiple of 4096.
When the program tries to access address 0, for example, using the instruction
MOV REG,0
virtual address 0 is sent to the MMU. The MMU sees that this virtual address falls
in page 0 (0 to 4095), which according to its mapping is page frame 2 (8192 to
12287). It thus transforms the address to 8192 and outputs address 8192 onto the
bus. The memory knows nothing at all about the MMU and just sees a request for
reading or writing address 8192, which it honors. Thus, the MMU has effectively
mapped all virtual addresses between 0 and 4095 onto physical addresses 8192 to
12287.
Similarly, the instruction
MOV REG,8192
is effectively transformed into
MOV REG,24576
SEC. 3.3 VIRTUAL MEMORY 197
Virtual
address
space
Physical
memory
address
60K–64K
56K–60K
52K–56K
48K–52K
44K–48K
40K–44K
36K–40K
32K–36K
28K–32K
24K–28K
20K–24K
16K–20K
12K–16K
8K–12K
4K–8K
0K–4K
28K–32K
24K–28K
20K–24K
16K–20K
12K–16K
8K–12K
4K–8K
 0K–4K
Virtual page
Page frame
X
X
X
X
7
X
5
X
X
X
3
4
0
6
1
2
Figure 3-9. The relation between virtual addresses and physical memory addresses is given by the page table. Every page begins on a multiple of 4096 and
ends 4095 addresses higher, so 4K–8K really means 4096–8191 and 8K to 12K
means 8192–12287.
because virtual address 8192 (in virtual page 2) is mapped onto 24576 (in physical
page frame 6). As a third example, virtual address 20500 is 20 bytes from the start
of virtual page 5 (virtual addresses 20480 to 24575) and maps onto physical address 12288 + 20 = 12308.
By itself, this ability to map the 16 virtual pages onto any of the eight page
frames by setting the MMU’s map appropriately does not solve the problem that
the virtual address space is larger than the physical memory. Since we have only
eight physical page frames, only eight of the virtual pages in Fig. 3-9 are mapped
onto physical memory. The others, shown as a cross in the figure, are not mapped.
In the actual hardware, a Present/absent bit keeps track of which pages are physically present in memory.
What happens if the program references an unmapped address, for example, by
using the instruction
MOV REG,32780
which is byte 12 within virtual page 8 (starting at 32768)? The MMU notices that
the page is unmapped (indicated by a cross in the figure) and causes the CPU to
198 MEMORY MANAGEMENT CHAP. 3
trap to the operating system. This trap is called a page fault. The operating system
picks a little-used page frame and writes its contents back to the disk (if it is not already there). It then fetches (also from the disk) the page that was just referenced
into the page frame just freed, changes the map, and restarts the trapped instruction.
For example, if the operating system decided to evict page frame 1, it would
load virtual page 8 at physical address 4096 and make two changes to the MMU
map. First, it would mark virtual page 1’s entry as unmapped, to trap any future accesses to virtual addresses between 4096 and 8191. Then it would replace the
cross in virtual page 8’s entry with a 1, so that when the trapped instruction is reexecuted, it will map virtual address 32780 to physical address 4108 (4096 + 12).
Now let us look inside the MMU to see how it works and why we hav e chosen
to use a page size that is a power of 2. In Fig. 3-10 we see an example of a virtual
address, 8196 (0010000000000100 in binary), being mapped using the MMU map
of Fig. 3-9. The incoming 16-bit virtual address is split into a 4-bit page number
and a 12-bit offset. With 4 bits for the page number, we can have 16 pages, and
with 12 bits for the offset, we can address all 4096 bytes within a page.
The page number is used as an index into the page table, yielding the number
of the page frame corresponding to that virtual page. If the Present/absent bit is 0,
a trap to the operating system is caused. If the bit is 1, the page frame number
found in the page table is copied to the high-order 3 bits of the output register,
along with the 12-bit offset, which is copied unmodified from the incoming virtual
address. Together they form a 15-bit physical address. The output register is then
put onto the memory bus as the physical memory address.
3.3.2 Page Tables
In a simple implementation, the mapping of virtual addresses onto physical addresses can be summarized as follows: the virtual address is split into a virtual
page number (high-order bits) and an offset (low-order bits). For example, with a
16-bit address and a 4-KB page size, the upper 4 bits could specify one of the 16
virtual pages and the lower 12 bits would then specify the byte offset (0 to 4095)
within the selected page. However a split with 3 or 5 or some other number of bits
for the page is also possible. Different splits imply different page sizes.
The virtual page number is used as an index into the page table to find the
entry for that virtual page. From the page table entry, the page frame number (if
any) is found. The page frame number is attached to the high-order end of the offset, replacing the virtual page number, to form a physical address that can be sent
to the memory.
Thus, the purpose of the page table is to map virtual pages onto page frames.
Mathematically speaking, the page table is a function, with the virtual page number as argument and the physical frame number as result. Using the result of this
SEC. 3.3 VIRTUAL MEMORY 199
15
14
13
12
11
10
9
8
7
6
5
4
3
2
1
0
000
000
000
000
111
000
101
000
000
000
011
100
000
110
001
010
0
0
0
0
1
0
1
0
0
0
1
1
1
1
1
1 Present/
absent bit
Page
table
12-bit offset
copied directly
from input
to output
Virtual page = 2 is used
as an index into the
page table Incoming
virtual
address
(8196)
Outgoing
physical
address
(24580)
110
1 1 0 0 0 0 0 0 0 0 0 0 1 0 0
0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0
Figure 3-10. The internal operation of the MMU with 16 4-KB pages.
function, the virtual page field in a virtual address can be replaced by a page frame
field, thus forming a physical memory address.
In this chapter, we worry only about virtual memory and not full virtualization.
In other words: no virtual machines yet. We will see in Chap. 7 that each virtual
machine requires its own virtual memory and as a result the page table organization becomes much more complicated—involving shadow or nested page tables
and more. Even without such arcane configurations, paging and virtual memory
are fairly sophisticated, as we shall see.
Structure of a Page Table Entry
Let us now turn from the structure of the page tables in the large, to the details
of a single page table entry. The exact layout of an entry in the page table is highly
machine dependent, but the kind of information present is roughly the same from
machine to machine. In Fig. 3-11 we present a sample page table entry. The size
200 MEMORY MANAGEMENT CHAP. 3
varies from computer to computer, but 32 bits is a common size. The most important field is the Pa g e frame number. After all, the goal of the page mapping is to
output this value. Next to it we have the Present/absent bit. If this bit is 1, the
entry is valid and can be used. If it is 0, the virtual page to which the entry belongs
is not currently in memory. Accessing a page table entry with this bit set to 0
causes a page fault.
Caching
disabled Modified Present/absent
Page frame number
Referenced Protection

Figure 3-11. A typical page table entry.
The Protection bits tell what kinds of access are permitted. In the simplest
form, this field contains 1 bit, with 0 for read/write and 1 for read only. A more
sophisticated arrangement is having 3 bits, one bit each for enabling reading, writing, and executing the page.
The Modified and Referenced bits keep track of page usage. When a page is
written to, the hardware automatically sets the Modified bit. This bit is of value
when the operating system decides to reclaim a page frame. If the page in it has
been modified (i.e., is ‘‘dirty’’), it must be written back to the disk. If it has not
been modified (i.e., is ‘‘clean’’), it can just be abandoned, since the disk copy is
still valid. The bit is sometimes called the dirty bit, since it reflects the page’s
state.
The Referenced bit is set whenever a page is referenced, either for reading or
for writing. Its value is used to help the operating system choose a page to evict
when a page fault occurs. Pages that are not being used are far better candidates
than pages that are, and this bit plays an important role in several of the page replacement algorithms that we will study later in this chapter.
Finally, the last bit allows caching to be disabled for the page. This feature is
important for pages that map onto device registers rather than memory. If the operating system is sitting in a tight loop waiting for some I/O device to respond to a
command it was just given, it is essential that the hardware keep fetching the word
from the device, and not use an old cached copy. With this bit, caching can be
turned off. Machines that have a separate I/O space and do not use memory-mapped I/O do not need this bit.
Note that the disk address used to hold the page when it is not in memory is
not part of the page table. The reason is simple. The page table holds only that
information the hardware needs to translate a virtual address to a physical addres
SEC. 3.3 VIRTUAL MEMORY 201
Information the operating system needs to handle page faults is kept in software
tables inside the operating system. The hardware does not need it.
Before getting into more implementation issues, it is worth pointing out again
that what virtual memory fundamentally does is create a new abstraction—the address space—which is an abstraction of physical memory, just as a process is an
abstraction of the physical processor (CPU). Virtual memory can be implemented
by breaking the virtual address space up into pages, and mapping each one onto
some page frame of physical memory or having it (temporarily) unmapped. Thus
this section is bassically about an abstraction created by the operating system and
how that abstraction is managed.