Part 7 of 7 · 3 min read
Exercises
Easy
Easy 1: Split an address (20 minutes)
With 4 KiB pages, split the virtual addresses 0x3A7F and 0x12345678 into page number and offset (in hexadecimal).
Done when: page 0x3, offset 0xA7F, and page 0x12345, offset 0x678.
Hint
Mask with 0xFFF for the offset, and shift right by 12 for the page.
Easy 2: Translate (20 minutes)
With a 1,024-byte page and the table of section 2, translate logical addresses 2,100 and 3,500.
Done when: 2,100 gives page 2, offset 52, physical 7,220; and 3,500 gives page 3, offset 428, physical 2,476.
Hint
2,100 = 2 × 1,024 + 52; 3,500 = 3 × 1,024 + 428.
Easy 3: Table size (20 minutes)
A 32-bit address space uses 8 KiB pages and 4-byte entries. How many pages are there, and how big is a flat table?
Done when: 524,288 pages and a 2 MiB table.
Hint
2^32 / 2^13 = 2^19.
Medium
Medium 1: Write the translator (45 minutes)
Write the translate function and run it on the five addresses of section 2. Add a read-only bit and a write flag, and report a different trap for a write to a read-only page.
Done when: the five outputs match the text, and a sixth test writes to a read-only page and reports the trap.
Hint
Check the page number first, then the valid bit, then the write permission.
Medium 2: Internal waste (45 minutes)
Write a program that finds the number of pages and the waste for process sizes 1, 4,096, 4,097, 10,000 and 100,000 bytes with 4 KiB pages.
Done when: a five-row table with the waste in bytes.
Hint
Pages needed = (size + 4,095) / 4,096.
Medium 3: Read pagemap (60 minutes)
Run the pagemap program as root. Print the entries before and after touching eight pages, and compare consecutive frame numbers.
Done when: a list of eight frame numbers and a note on whether any two consecutive pages were in consecutive frames.
Hint
Open /proc/self/pagemap, and read 8 bytes at offset (address / 4096) * 8.
Hard
Hard 1: Choose a page size (60 minutes)
A system must run 200 processes with 24-bit address spaces, 4-byte entries, and an average region size of 100,000 bytes. For page sizes of 512 bytes, 4 KiB and 32 KiB, compute the table memory per process (flat) and the average internal waste per process, and the total of the two for all 200 processes.
Done when: a table of three page sizes with totals, and a recommendation with a reason.
Hint
For 24-bit spaces the number of pages is 2^24 divided by the page size.
Hard 2: Move a page (60 minutes)
Extend the translator with a function move(page, new_frame) that changes one entry. Show that a logical address gives a different physical address afterwards, with the same offset.
Done when: a before and after run for one address, with the offset unchanged.
Hint
Only the frame field changes.
Hard 3: Build a two-process system (90 minutes)
Write a simulation with two processes, each with its own table, and a switch_to(pid) function that selects the table. Show that the same logical address gives two different physical addresses, and that a frame mapped by both is shared.
Done when: a trace with the same logical address in two processes giving two physical addresses, and one shared frame visible in both tables.
Hint
Keep a pointer to the current table, and let translate use it.