Operating Systems

Homework 3: Memory Management

  1. (10 pts) If the virtual address space supported is 2**64 bits (note bits not bytes), the page size is 1Kbyte, the size of the physical memory is 64Kbyte, the size of a PTE is two bytes, and the addressing is at the byte level, calculate the size of the page table required for both standard and inverted page tables.

Standard page table:

address space is 61 bits in byte addressing
number of pages = 2^61 / 1K = 2^51;
Page Table Size = 2^51 * (PTE size) = 2^52 bytes

Inverted page table:

Total frames = 64k / 1K = 64;
Page Table Size = 64* (PTE size) = 128 bytes

  1. (10 pts) What is the difference between inverted and hashed page tables?

Inverted: contains one entry per physical frame as opposed to one for each virtual page as in the case of standard page tables. This makes it much smaller compared to standard page tables. However, the lookup time can be very high, because the whole table has to be linearly searched typically.

Hashed: maintains a hash-table of virtual-to-physical translations. Has the advantage of inverted tables (smaller size compared to standard tables) while the lookup is much faster compared to inverted tables: typically 1 or 2 accesses.


  1. (10 pts) Consider a paging system with the page table stored in memory.

2 memory accesses: page lookup followed by actual access => 2*200ns = 400ns

75% * TLB hit-time + 25% * TLB miss-time = 75% * 200ns + 25% * 400ns = 250ns

Overhead on Cache-misses = 14cycles

Overhead on TLB-miss = 99cycles

# cache misses = 1000 * 20% * 10% = 20

# TLB misses = 1000 * 20% * 5% = 10

Total cycles      = 1000cycles + (overhead due to cache misses) + (overhead due to TLB misses)

                              = 1000 + (20 * 14) + (10 * 99) = 1000 + 280 + 990 = 2270 cycles

  1. Extra Credit (20 pts) Compare the address translation mechanisms of the Alpha 21164 with the PowerPC 604. Read sections from the paper I distributed.
    Organize your answer by answering the following questions:

Alpha: a standard page table with software-managed TLB.

      PowerPC: uses inverted and hashed page tables with hardware-managed TLB.

Alpha: The TLB is managed by the OS directly through PALcode. PTEs are loaded from hardware registers into the TLB. The not-most-recently-used replacement policy is used.

PowerPC : A paged segmentation system is used. The hardware loads an entire PTE group into the TLB.

Alpha: The OS supports an 8Kbytes page size and 64-bit addressing.

PowerPC: A 52-bit segmented virtual address space for 32-bit implementations of the architecture or an 80-bit segmented virtual address space for 64-bit implementations of the architecture.

Alpha: ASID

PowerPC: segmentation

Yes: If an address can never be accessed or if the page is not in physical memory, it couldn’t be in either TLB or the cache.

Yes: If the size of cache is larger than the total size of pages that have translation entries in the TLB.

The case when a TLB miss and cache hit happens at the same time would be one, but it is typically avoided.

Alpha: The PAL loads the PTEs from a hardware register into the TLB.

PowerPC: The hardware loads an entire PTE group and performs a linear search for a matching virtual address. If the PTE is not found in the first PTE group, the hardware performs a second lookup to a different PTE group, based on a secondary hash.