Consider a system with a byte-addressable virtual address space of 65536 bytes,

Question

Consider a system with a byte-addressable virtual address space of 65536 bytes, and a physical address space of 64 32-bit words. a. Assume that said system has an 8 entry cache with a block size of 8 bytes and an associativity of 1. Further assume that the cache is both virtually indexed and virtually tagged. If the cache entries are all initially invalid, what is the state of the cache (given as a table indicating the tuple for each cache set) after reads have been issued for word addresses 8, 6, 7, 5, 3, 0, 9? b. What is the state of the cache if block size and capacity are held constant, but associativity increases to 2 with LRU replacement? c. What is the state of the cache if block size and capacity are held constant, associativity increases to 2 with LRU replacement, and the cache is virtually indexed and physically tagged, assuming that there are 1KB pages and that the first 2 virtual pages (0 and 1) are mapped into the first two physical pages?

Explanation / Answer

Since physical addresses are 44 bits and page size is 4K, the page frame number occupies 32 bits. Taking the 4 protection bits into account, each entry of the level-3 page table takes (32+4) = 36 bits. Rounding up to make entries byte (word) aligned would make each entry consume 40 (64) bits or 5 (8) bytes. For a 256 entry table, we need 1280 (2048) bytes.

The top-level page table should not assume that 2nd level page tables are page-aligned. So, we store full physical addresses there. Fortunately, we do not need control bits. So, each entry is at least 44 bits (6 bytes for byte-aligned, 8 bytes for word-aligned). Each top-level page table is therefore 256*6 = 1536 bytes (256 * 8 = 2048 bytes).

Trying to take advantage of the 256-entry alignment to reduce entry size is probably not worth the trouble. Doing so would be complex; you would need to write a new memory allocator that guarantees such alignment. Further, we cannot quite fit a table into a 1024-byte aligned region (44-10 = 34 bits per address, which would require more than 4 bytes per entry), and rounding the size up to the next power of 2 would not save us any size over just storing pointers and using the regular allocator.

Similarly, each entry in the 2nd level page table is a 44-bit physical pointer, 6 bytes (8 bytes) when aligned to byte (word) alignment. A 16 entry table is therefore 96 (128) bytes. So the space required is 1536 (2048) bytes for the top-level page table + 96 (128) bytes for one second-level page table + 1280 (2048) bytes for one third-level page table = 2912 (4224) bytes. Since the process can fit exactly into 16 pages, there is no memory wasted by internal fragmentation.

So the space required is 1536 (2048) bytes for the top level page table + 3 * 96 (3 * 128) bytes for 3 second-level page tables + 3 * 1280 (3 * 2048) for 3 third-level page table = 5664 (8576) bytes.

As the code, data, stack segment of the process fits exactly into 12, 150, 16 pages respectively, there is no memory wasted by internal fragmentation.

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.