Mapping a virtual address to a physical address is relatively easy once the correct formulas are known. There are also some pieces of information that you will need, such as the page size and a page table.

There are four steps to converting a virtual address to a physical address:

1. Calculate the page (Note: integer division is used for this):
   $$page = \frac{virtual\ address}{page\ size}$$
2. Calculate the page offset (Note: $\%$ is the modulus operator):
   $$offset = virtual\ address\ \%\ page\ size$$
3. Find the frame by mapping the page to a frame via the page table
4. Calculate the physical address:
   $$physical\ address = frame * page\ size + offset$$

It is not always possible to get a physical address from a virtual address. If the page table has a page listed as invalid, then a segmentation fault would occur, instead of accessing the physical address.

---

Q: Given the following page table, map the (base 10) virtual addresses to physical addresses.
Virtual Addresses: 500, 8200, 102400
(2011 Mid semester exam, Q15)

Relevant information: Page size is 4KB (4096B)

Page	Frame
0	200
1	201
2	22
3	invalid
...	invalid
25	24
...	invalid

For each of these virtual addresses, we need to calculate the physical address using the process outlined above.

Virtual address 500:

$$page = 500 / 4096 = 0$$

$$offset = 500\ \%\ 4096 = 500$$

From our page table, we can see that page 0 maps to frame 200.

$$physical\ address = 200 * 4096 + 500 = 819700$$

Virtual address 8200:

$$page = 8200 / 4096 = 2$$

$$offset = 8200\ \%\ 4096 = 8$$

From our page table, we can see that page 2 maps to frame 22.

$$physical\ address = 22 * 4096 + 8 = 90120$$

Virtual address 102400:

$$page = 102400 / 4096 = 25$$

$$offset = 102400\ \%\ 4096 = 0$$

From our page table, we can see that page 25 maps to frame 24.

$$physical\ address = 24 * 4096 + 0 = 98304$$

From this, we can see that it is possible to get a physical address for every virtual address we were asked to convert. This means that there were no segmentation faults.

It is possible for a page fault to occur, but we have not been given enough information to determine whether this is the case.

There are a few things to consider when calculating how many memory accesses are required for the CPU to access virtual addresses. First, what type of caching is happening during this memory access? How is the TLB being used? You should assume that the TLB is in use, but if other caching is not specified, then assume that there is none.

---

Q: The CPU accesses the following (base 10) virtual addresses in sequence: 45055, 45056, 8392710, 45090, 8392714, 45091. How many accesses to memory are required?
(2011 Mid semester exam, Q13)

Relevant information: Page size is 4KB (4096B). Use a 2 level page table. L1 and L2 cache are considered part of memory.

We are going to assume that the TLB is in use, and is currently empty. Also assume that there is no caching apart from the TLB.

The first step is to work out which pages the addresses fall in. From the exam, we are told that a page is 4KB (4096B). Therefore, to get the page that contains a virtual address, we should do:

$$page = \frac{virtual\ address}{page\ size}$$

Note: This must use integer division, as we want the page. The fraction would correspond to the offset from the start of the page.

Pages of Virtual Memory addresses

Virtual Memory Address	Page
45055	10
45056	11
8392710	2049
45090	11
8392714	2049
45091	11

Following this, we need to find the physical address of each virtual address. While we are doing this, we will calculate how many memory accesses are required.

1. Virtual address 45055 (page 10)
   1. There are two levels to the page table, so we need to go to the L1 page first. This tells us which L2 page contains the address for page 10. Memory accesses: 1
   2. We go to the L2 page to find the physical address of our virtual address. Memory accesses: 2
   3. Now that we have the physical address, we access it. This map of page to frame is now stored in the TLB. Memory accesses: 3
2. Virtual address 45056 (page 11)
   1. Go to L1 page to find which L2 page contains the address for page 11. Memory accesses: 4
   2. Go to the L2 page to find the physical address of our virtual address. Memory accesses: 5
   3. Access the frame containing our physical address. This map of page to frame is now stored in the TLB. Memory accesses: 6
3. Virtual address 8392710 (page 2049)
   1. Go to L1 page to find which L2 page contains the address for page 11. Memory accesses: 7
   2. Go to L2 page to find the physical address of our virtual address. Memory accesses: 8
   3. Access the frame containing our physical address. This map of page to frame is now stored in the TLB. Memory accesses: 9
4. Virtual address 45090 (page 11)
   1. We have already found where page 11 is stored, so the map of page 11 to physical frame is stored in the TLB. We can go straight to this frame to access the physical address, skipping the L1 and L2 page table memory accesses. Memory accesses: 10
5. Virtual address 8392714 (page 2049)
   1. We have already found where page 2049 is stored, so the map of page 2049 to physical frame is stored in the TLB. We can go straight to this frame to access the physical address, skipping the L1 and L2 page table memory accesses. Memory accesses: 11
6. Virtual address 45091 (page 11)
   1. We have already found where page 11 is stored, so the map of page 11 to physical frame is stored in the TLB. We can go straight to this frame to access the physical address, skipping the L1 and L2 page table memory accesses. Memory accesses: 12

From this working, we can see that we would need a total of 12 memory accesses to access the given virtual memory addresses in sequence.

Find memory required for page table

To find the memory required for a page table, follow the following steps.

1. work out what pages (or ranges of pages) you need to map.
2. a page is mapped by a page table entry in some page table, so for each page work out which page table it is mapped in.
3. make note of each unique page table. For a multilevel page table with two levels, the root page table is always required (1 page) plus all the page tables from the previous step.

 

$$ \textrm{memory} = \textrm{number of page tables} \cdot \textrm{page size} $$

 

Example

Given a system with

• $32$-bit virtual addresses,
• $4$kB pages,
• page table entries are $4$ bytes, and
• it uses two level page table.

How much memory is required for the page table of a process which uses the following memory: $122880$ bytes starting at $1024$ and $30719$ starting at $125825024$

So we have a multilevel page table with two levels. That means we have a single root level-1 page table, each of whose entries point to a level-2 page table. The entries of each level-2 page table are the actual page table entries that map the virtual pages to physical page frames.

First we want to know how many entries each page has

$$ \frac{\textrm{page size}}{\textrm{entry size}} = \frac{4kB}{4B} = 1024 \text{ entries per page table.} $$

 

We have the first region starting at address 1024, but what page is that on? Each page has 4096 bytes (0-4095), so it must be on the first page (page 0). Here's the formula, note that we use integer division (round down).

$$ \textrm{page} = \frac{\textrm{address}}{\textrm{page size}} = \frac{1024}{4096} = 0$$

What page does this memory region end on? It starts at address 1024 and is 122880 bytes long, so it ends at address $1024 + 122880 = 123904$. Plug that into the page formula, and we get page $123904 / 4096 = 30$.

Address	Page	L2 Page Table
1024	0	0
123904	30	0

The region starts on page 0 and ends at page 30. Where are the page table entries for these pages? The first pointer in the root of the multilevel page table points to a level-2 page table that maps the first 1024 pages (0 - 1023). So entries for pages 0-30 are in that first level-2 page table.

 

What about the second memory region? It starts at 125825024 and is 30719 bytes long.

125825024 is on page 30719 and the region ends at address $125825024 + 30719 = 125855743$, which is on page 30726.

 

Address	Page	L2 Page Table
125825024	30719	29
125855743	30726	30

 

 

Where are the page table entries for this region? The first level-2 page table maps pages 0-1023, the second maps 1024-2047 etc. We have the formula

$$ \textrm{L2 page table} = \frac{\textrm{page}}{\textrm{entries per page table}}$$

So the #29 level-2 page table contains the entry for the start page (30719) and the #30 level-2 page table contains the entry for the end page (30726).

For the first memory region, we needed a single level-2 page table and for the second region we needed two level-2 page tables.

 

Root page table

Entry	Maps to
0	address of 1st level-2 page table
...	...
29	address of #29 level-2 page table
30	address of #30 level-2 page table
...	...

 

So, we need the root table (4kB) plus the three level-2 page tables (4kB each). In total, we need $4 \cdot 4kB = 16kB$ for our multilevel page table.