CSE Roadmap

Core tier · about 6 hours · 7 parts

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.