CSE Roadmap

Core tier · about 3 hours · 6 parts

Part 6 of 6 · 3 min read

Exercises

Easy

Easy 1: Order the steps (20 minutes)

Put in order: load B's registers, pick B, save A's registers, enter kernel mode, return to user mode.

Done when: enter kernel mode, save A, pick B, load B, return to user mode.

Hint

The kernel must be running before it can save anything.

Easy 2: Mode or context (20 minutes)

For each event, say whether it is a mode switch, a context switch, or both: a call to getpid; a read that blocks on an empty pipe; a timer interrupt that ends a slice and starts another process.

Done when: mode only; both; both.

Hint

Only a change of process is a context switch.

Easy 3: Overhead share (20 minutes)

A switch takes 2 microseconds and a time slice is 10 ms. What fraction of the time is lost to switching?

Done when: you write 0.02 per cent (2 / 10,000).

Hint

2 microseconds is 0.002 ms.

Medium

Medium 1: Subtract the calls (30 minutes)

A ping-pong has 2,400 ns per round trip, and each of the four system calls costs 100 ns. Compute the cost per switch.

Done when: you write (2,400 − 400) / 2 = 1,000 ns.

Hint

Subtract the system calls before dividing by two.

Medium 2: Run the benchmark (30 minutes)

Compile and run the ping-pong program three times. Report the three per-switch figures and their average.

Done when: three numbers, an average, and a sentence saying they differ a little from run to run.

Hint

Run each time from a fresh shell prompt.

Medium 3: Remove the pinning (30 minutes)

Remove the sched_setaffinity call, run again, and compare. Explain the change.

Done when: a second set of figures and an explanation, for example that two processors let the processes wake each other across processors, which changes the cost.

Hint

With two processors, the processes may run at the same time on different ones.

Hard

Hard 1: Slice or switch (60 minutes)

A switch costs 3 microseconds in direct work and the next process loses another 12 microseconds to cold caches. Find the smallest slice for which the total loss stays under 5 per cent. Then give the loss for a slice of 100 microseconds.

Done when: a slice of at least 300 microseconds, since 15 / 300 = 5 per cent, and 15 per cent for 100 microseconds.

Hint

Loss = (3 + 12) / slice.

Hard 2: Count the switches (60 minutes)

Extend the ping-pong program so that it prints the voluntary and non-voluntary counters of both processes at the end. Explain why the voluntary counts are close to the number of round trips and why the non-voluntary ones are small.

Done when: four counters printed, and an explanation tying waits to voluntary switches.

Hint

Read /proc/self/status just before each process exits.

Hard 3: CPU hog against a sleeper (60 minutes)

Run on one processor a program that loops without waiting and a program that sleeps for 1 ms in a loop. After 5 seconds, read both programs' counters. Say which one has more voluntary and which more non-voluntary switches, and why.

Done when: a table of four counters and an explanation using page 2.

Hint

Use taskset -c 0 to run both programs on one processor.