Paging with Linear Page Tables

In this homework, you will use a simple program, paging-linear-translate.py, to see if you understand how simple virtual-to-physical address translation works with linear page tables.

The program provides for you a page table for a particular process (remember, in a real system with linear page tables, there is one page table per process; here we just focus on one process, its address space, and thus a single page table). The page table tells you, for each virtual page number (VPN) of the address space, that the virtual page is mapped to a particular physical frame number (PFN) and thus valid, or not valid.

The format of the page table is simple:
The high-order (left-most) bit is the VALID bit.
If the bit is 1, the rest of the entry is the PFN.
If the bit is 0, the page is not valid.

Sample Page Table (from entry 0 down to the max size)
0x8000000c
0x00000000
0x00000000
0x80000006

In the example above, the page table maps VPN 0 to PFN 0xc, VPN 3 to PFN 0x6 , and leaves the other two virtual pages, 1 and 2, as not valid.

Your job, then, is to use this page table to translate the virtual addresses given to you in the trace to physical addresses.

Let's look at VA 0x3229.

To translate this virtual address into a physical address, we first have to break it up into its constituent components: a virtual page number and an offset. We do this by noting down the size of the address space and the page size.

In this example, the address space is set to 16KB (a very small address space) and the page size is 4KB. Thus, we know that there are 14 bits in the virtual address, and that the offset is 12 bits, leaving 2 bits for the VPN. Thus, with our address 0x3229, which is binary 11 0010 0010 1001, we know the top two bits specify the VPN. Thus, 0x3229 is on virtual page 3 with an offset of 0x229.

We next look in the page table to see if VPN 3 is valid and mapped to some physical frame or invalid, and we see that it is indeed valid (the high bit is 1) and mapped to physical page 6. Thus, we can form our final physical address by taking the physical page 6 and concatenating it with  the offset, as follows:
0x6000 (the physical page, shifted into the proper spot) OR 0x0229 (the offset), yielding the final physical address: 0x6229.

Thus, we can see that virtual address 0x3229 translates to physical address 0x6229 in this example.