A Simple Example And Overview
Understand paging further by studying the brief overview and the demonstration of paging provided in this lesson.
We'll cover the following
To help make this approach more clear, let’s illustrate it with a simple example.
Example
The figure below 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 bits; in the course, we’ll often use tiny examples to make them easier to digest.
Physical memory, as shown in the figure below, 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 the physical memory for itself.
Advantages of paging
Paging, as we will see, has a number of advantages over our previous approaches.
Flexibility
Probably the most important improvement will be flexibility: 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.
Simplicity
Another advantage is the simplicity of 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 a free list of all free pages for this, and just grabs the first four free pages off of this list. In the example, the OS 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.
Page table
To record where each virtual page of the address space is placed in physical memory, the operating system usually keeps a per-process data structure known as a page 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 (see figure above), 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 a per-process data structure (most page table structures we discuss are per-process structures; an exception we’ll touch on is the inverted 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 to different physical pages (modulo any sharing going on).
Address translation example
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 address <virtual address>
into the register eax
(and thus ignore the instruction fetch that must have happened prior).
To translate this virtual address that the process generated, we have to first split it into two components: the virtual page number (VPN), and the offset within 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 (). Thus, our virtual address can be conceptualized as follows:
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:
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:
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 the physical frame number (PFN) (also sometimes called the physical page number or PPN) 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 (see figure below).
Note the offset stays the same (i.e., it is not translated) because the offset just tells us which byte within the page we want. Our final physical address is 1110101 (117 in decimal) and is exactly where we want our load to fetch data from (see figure labeled “A 64-Byte Address Space In A 128-Byte Physical Memory”).
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!
Get hands-on with 1400+ tech skills courses.