Search⌘ K
Home
Courses
Operating Systems: Virtualization, Concurrency & Persistence

Example: Accessing An Array

Explore how Translation Lookaside Buffers improve virtual memory access by caching address translations. Understand TLB performance through examples showing the impact of spatial and temporal locality on CPU efficiency during array access loops.

We'll cover the following...

To make clear the operation of a TLB, let’s examine a simple virtual address trace and see how a TLB can improve its performance. In this example, let’s assume we have an array of 10 4-byte integers in memory, starting at virtual address 100. Assume further that we have a small 8-bit virtual address space, with 16-byte pages; thus, a virtual address breaks down into a 4-bit VPN (there are 16 virtual pages) and a 4-bit offset (there are 16 bytes on each of those pages).

The figure below shows the array laid out on the 16 16-byte pages of the system. As you can see, the array’s first entry (a[0]) begins on (VPN=06, offset=04); only three 4-byte integers fit onto that page. The array continues onto the next page (VPN=07), where the next four entries (a[3] ... a[6]) are found. Finally, the last three entries of the 10-entry array (a[7] ... a[9]) are located on the next page of the address space (VPN=08).

Example

Now let’s consider a simple loop that accesses each array element, something that would look like this in C:

C
int sum = 0;
for (i = 0; i < 10; i++) {
    sum += a[i];
}

For the sake of simplicity, we will pretend that the only memory accesses the loop generates are to the array (ignoring the variables i and sum, as well as the instructions themselves). When the first array element (a[0]) is accessed, the CPU will see a load ...