CSE Roadmap

Common tier · about 5 hours · 6 parts

Part 6 of 6 · 2 min read

Exercises

Easy

Easy 1: Segment translation (20 minutes)

Segment 0 has base 10,000 and size 1,500, segment 1 has base 20,000 and size 600. Translate (0, 1,499), (1, 599), (1, 600) and (0, 1,500).

Done when: 11,499; 20,599; trap; trap.

Hint

The check is "offset less than size".

Easy 2: Which fault? (20 minutes)

A page is mapped with permissions r-x. Which of these accesses cause SIGSEGV: a read, a write, a jump into the page?

Done when: only the write causes SIGSEGV.

Hint

A jump into the page is an execute access, which x allows.

Easy 3: Pss by hand (20 minutes)

A shared page is mapped by 4 processes. How many kB does it add to the Pss of each process, if the page is 4 kB?

Done when: 1 kB.

Hint

Divide the page size by the number of sharers.

Medium

Medium 1: Cause a SIGSEGV (45 minutes)

Write the mprotect program of section 2 with a handler for SIGSEGV that prints a message and exits. Run it.

Done when: the handler message, and the exit status.

Hint

Install the handler with signal(SIGSEGV, handler), and use _exit in it.

Medium 2: Count the faults (60 minutes)

Write the fork test with getrusage. Report the faults of the child that only reads, and the child that writes.

Done when: a table with 0 and about 1,000 faults for 1,000 pages.

Hint

Use getrusage(RUSAGE_SELF) inside the child, and read ru_minflt.

Medium 3: See sharing (60 minutes)

Start five copies of a program that sleeps, read Rss and Pss from /proc/<pid>/smaps for the libc mapping, and report them.

Done when: a Pss far below the Rss, with a sentence on why.

Hint

Look at the lines that start with Rss and Pss after the line for libc.so.6.

Hard

Hard 1: Time fork (60 minutes)

Write a program that allocates and touches 64 MiB, 256 MiB and 1 GiB, and times fork for each, taking the best of five runs.

Done when: a table of three times, and a statement of how the time grows with size.

Hint

Use madvise(MADV_NOHUGEPAGE) so that all pages are 4 KiB.

Hard 2: Do the copies happen? (90 minutes)

Make a parent with 512 MiB of touched memory. Fork a child that writes to 10% of the pages and measure its faults, its run time, and the growth of the system's free memory use (from /proc/meminfo).

Done when: about 13,000 faults, and a memory increase of about 52 MiB.

Hint

10% of 131,072 pages is about 13,107 pages, or about 51 MiB.

Hard 3: A segment simulator (90 minutes)

Write a C simulation with a segment table of three segments with permissions. Test reads, writes and executes. Report a trap for each wrong access, with its reason.

Done when: twelve tests with results, covering out-of-range offsets and wrong permissions.

Hint

Keep a bit for each of read, write and execute in the table.