Three Possible Page Lookup Methods
When a 32-bit linear memory address is submitted to the Paging Unit, the Paging Unit must somehow scan the directory in memory to determine where the page of information currently resides either in physical memory or on a mass storage device. The sections that follow describe three possible methods that the processor's Paging Unit could use to perform the directory scan.
First Method: Sequential Scan through a Large Table
Using this method, the Paging Unit starts at the first directory entry and compares the target linear address to every entry looking for a match. If the last entry is reached without a match, the page isn't currently in memory. This method has the following characteristics:
Each entry would contain a complete 20-bit linear page address and the corresponding 20-bit physical page address that it is mapped to. In addition, there would be a Page Present bit to indicate whether or not the page is currently in physical memory. In all, each entry is 41 bits in length (5 bytes plus one bit of another byte).
The entire table (containing 220 entries) is resident in memory all the time. The table alone consumes approximately 5MB of memory (just to keep track of the pages of information currently in memory).
The amount of time necessary to determine that a page of information isn't currently in memory (i.e., the amount of time it takes to compare the linear address to every directory entry) would be colossal.
Second Method: Index into a Large Table
In this method, the processor would use the 20-bit linear page address as a 20-bit table index to select a directory entry to compare against. Since only this specific linear page address would select this table entry, it wouldn't be necessary to store the 20-bit linear address in the entry. It's only necessary to store the physical page address it's mapped to, and to have a Page Present bit indicating whether the page currently resides in physical memory. This method has the following characteristics:
In the plus column, it's fast. The Paging Unit only has to read one entry to determine if the page is in physical memory and, if so, where.
As another plus, each table entry could only contain 21 bits: 20 to hold the physical page address and a Page Present bit. It should be noted that there could be additional page attribute bits indicating such things as whether or not the page is read/write or read-only, etc.
As a negative (and a large one), the entire table (consisting of 220 entries) has to be memory resident (consuming 1M x 21 bits/entry = approximately 3MB).
Third Method: Index into a Selected Small Table
The fast lookup provided by the previous method would be ideal if the table consumed considerably less memory. Consider a variation that has the following characteristics (see Figure 12-2 on page 218):
From the perspective of the Paging Unit, a 32-bit linear address is viewed as illustrated in Figure 12-2 on page 218.
The 4GB linear memory space is divided into 220 4KB pages grouped into 1024d page groups.
Each page group contains 1024d linear pages.
Each page group has its own lookup table (referred to as a Page Table) consisting of 1024d entries. There can be 1024d Page Tables.
Each entry in a Page Table contains the location of the respective page (in physical memory or on disk) that the associated linear page is mapped to.
At a given moment in time, only some of the Page Tables are resident in memory, while the remainder reside on disk. The disk-resident Page Tables are only loaded into memory on an as-needed basis.
The Paging Unit's master directory (referred to as the Page Directory) in memory keeps track of the Page Tables that are currently in memory, as well as those that are still on disk.
Each entry in the Page Directory contains a Page Table Present bit indicating whether the respective Page Table is present in physical memory and, if so, where (i.e., the start physical memory address of the Page Table).
Each entry in a Page Table contains a page Present bit indicating whether the respective page is present in physical memory and, if so, where (i.e., the start physical memory address of the associated page).
Whenever the currently executing program must perform a memory access, the 32-bit linear address is submitted to the Paging Unit and the following actions are taken to remap the access to the correct physical memory page:
Assuming that the selected PDE's Present bit = 1, the selected Page Table is present in memory and its start physical address is obtained from the selected PDE.
The middle 10 bits of the address identifies one of the 1024d pages within the selected page group. It selects the entry within the Page Table (Page Table Entry, or PTE) that identifies the location of the target 4KB page.
The Paging Unit forms the resultant 32-bit physical memory address in the following manner:
- The upper 20 bits (the 20-bit physical page address) is obtained from the selected entry in the Page Table.
- The lower 12 bits of the linear address become the lower 12 bits of the physical memory address. This part of the linear address is never translated. It identifies the target location within the 4096d locations that comprise the targeted 4KB page.