Memory Accesses

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.