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.
2. (10 pts) What is the difference between inverted and hashed page tables?
3. (10 pts) Consider a paging system with the page table stored in memory.
   • (4pts) If a memory access takes 200 nanoseconds, how long does a paged memory reference take?
   • (4 pts.) If we add associative registers (a TLB), and 75 percent of all page table references are found in associative registers, what is the effective memory reference time? Assume that finding a page-table entry in the TLB takes zero time.
   • (2 pts.) A typical program has 20% memory instructions. Assume there are 5% data TLB misses, each requiring 100 cycles to handle.
     Assume each instruction requires 1 cycle to execute, each memory operation in the cache 1 cycle, 10% of data accesses are cache misses, each cache miss is 15 cycle. How long would take to execute 1000 instructions?
4. 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:
   • Page table type, show if you can an entry from the page table (i.e., the PTE)
   • How is the TLB content updated?
   • Size of pages and address space supported
   • How is protection provided?
   • Can you have a cache miss and a TLB miss at the same time? Why?
   • Can you have a cache hit and a TLB miss? Why?
   • Is there a combination of TLB (hit/miss) and cache access (hit/miss) that cannot happen?
   • What happens during a TLB miss?