Difference between revisions of "GATE2003 q78 79"

Latest revision as of 20:00, 30 January 2015

A processor uses 2-level page tables for virtual to physical address translation. Page tables for both levels are stored in the main memory. Virtual and physical addresses are both 32 bits wide. The memory is byte addressable. For virtual to physical address translation, the 10 most significant bits of the virtual address are used as index into the first level page table while the next 10 bits are used as index into the second level page table. The 12 least significant bits of the virtual address are used as offset within the page. Assume that the page table entries in both levels of page tables are 4 bytes wide. Further, the processor has a translation look-aside buffer (TLB), with a hit rate of 96%. The TLB caches recently used virtual page numbers and the corresponding physical page numbers. The processor also has a physically addressed cache with a hit rate of 90%. Main memory access time is 10 ns, cache access time is 1 ns, and TLB access time is also 1 ns.

78. Assuming that no page faults occur, the average time taken to access a virtual address is approximately (to the nearest 0.5 ns)

(A) 1.5 ns (B) 2 ns (C) 3 ns (D) 4 ns

79. Suppose a process has only the following pages in its virtual address space: two contiguous code pages starting at virtual address 0x00000000, two contiguous data pages starting at virtual address 0x00400000, and a stack page starting at virtual address 0xFFFFF000. The amount of memory required for storing the page tables of this process is

(A) 8 KB (B) 12 KB (C) 16 KB (D) 20 KB

Solution by Arjun Suresh

78. It is given cache is physically addressed. So, address translation is needed for all memory accesses.

Average access time = Average address translation time + Average memory access time
= 1ns (TLB is accessed for all accesses) + 2*10*0.04 (2 page tables accessed from main memory in case of TLB miss) + Average memory access time
= 1.8ns + Cache access time + Average main memory access time
= 1.8ns + 1 (cache is accessed for all memory accesses) + 0.1 * 10 (main memory is accessed for cache misses only)
= 1.8ns + 1 + 1
= 3.8ns

79. First level page table is addressed using 10 bits and hence contains <math>2^{10}</math> entries. Each entry is 4 bytes and hence this table requires 4 KB. Now, the process uses only 3 unique entries from this 1024 possible entries (two code pages starting from 0x00000000 and two data pages starting from 0x00400000 have same first 10 bits). Hence, there are only 3 second level page tables. Each of these second level page tables are also addressed using 10 bits and hence of size 4 KB. So,

total page table size of the process 
= 4 KB + 3 * 4 KB
= 16 KB