Sample Homework Assignment #7

Overview

This is a sample assignment with questions that are more involved than the provided sample problems.

Solutions

Solutions are available as a plain ASCII file.

Exercise #1: Address Translation

Consider the following page table, in which “x” means an invalid entry:

------------------
logical | physical 
------------------
|  15   |   9    |
|  14   |   x    |
|  13   |   40   |
|  12   |   x    |
|  11   |   25   |
|  10   |   x    |
|  9    |   x    |
|  8    |   7    |
|  7    |   x    |
|  6    |   5    |
|  5    |   x    |
|  4    |   8    |
|  3    |   x    |
|  2    |   1    |
|  1    |   0    |
|  0    |   11   |
------------------

Assume a 1KiB (i.e., 1,024 bytes) page size. Give the physical address corresponding to the following three logical addresses, or state that an error occurs. For convenience, in this exercise all physical and logical addresses are base-10 values.

Your answer should thus be base-10 values. Show your work for all questions.

• [q1] 2020

• [q2] 8205

• [q3] 6150

• [q4] 13963

Exercise #2: Logical and physical address

Consider a logical address space of 64 pages with 2,048 bytes per page, mapped onto a physical memory of 16 frames.

• [q1] How many bits are required in the logical address? (show your work)

• [q2] How many bits are required in the physical address? (show your work)

Exercise #3: Page table size

Consider a computer system with a 40-bit logical addresses and a 8-KiB page size. The system supports up to 2GiB of physical memory. (Give all answers as powers of 2.)

• [q1] How many entries are there in a conventional single-level page table? (show your work)

• [q2] How many entries are there in an inverted page table? (show your work)

Exercise #4: Page table structure

Suppose we have a computer system with a 38-bit logical address, page size of 32KiB, and 8 bytes per page table entry.

• [q1] Suppose we use two-level paging and arrange for all page tables to fit into a single page frame. How will the bits of the address be divided up? (show your work)

• [q2] Is the outer page table page fully utilized? (show your work)

• [q3] In the scheme above, assume that only 7 of the entries in the outer-level page table page are valid, and only 1/4 of the entries in all the inner-level page table pages are valid. What is the current total RAM footprint of the address space in MiB (counting the page table pages)? (show your work)