CSE Roadmap

Core tier · about 5 hours · 7 parts

Part 7 of 7 · 3 min read

Exercises

Easy

Easy 1: Shares (20 minutes)

Three processes with 20, 30 and 50 tickets. Give the expected share of each.

Done when: 20, 30 and 50 per cent.

Hint

The total is 100, so the shares equal the ticket counts.

Easy 2: Stride (20 minutes)

With a constant of 1,200, give the stride of a process with 300 tickets and of one with 100 tickets.

Done when: 4 and 12.

Hint

Stride = constant ÷ tickets.

Easy 3: Weights (20 minutes)

Using the table, compute the share of a nice 5 task competing with a nice 0 task.

Done when: 335 ÷ 1,359 = 24.7 per cent.

Hint

Share = weight ÷ (sum of weights).

Medium

Medium 1: Trace stride (30 minutes)

Processes P (stride 5) and Q (stride 10) start with pass 0, ties to P. Give the first 9 picks.

Done when: P, Q, P, P, Q, P, P, Q, P with P six times and Q three times, the ratio 2 to 1.

Hint

Pick the lowest pass, add the stride, and repeat.

Medium 2: Virtual runtime by hand (30 minutes)

A nice 0 task and a nice 10 task both start at vruntime 0. Each runs once for 10 ms. Give both vruntime values, and say which runs next.

Done when: 10 and about 93.1 (10 × 1,024 ÷ 110); the nice 0 task runs next.

Hint

Growth = 10 × 1,024 ÷ weight.

Medium 3: Check nice on your machine (30 minutes)

Write the program of section 4, or use two shell loops with taskset -c 0, one under nice -n 10. Measure the CPU time of both over 10 seconds.

Done when: a share near 90 per cent for the nice 0 loop, and a sentence comparing it with the expected 90.3 per cent.

Hint

Read the CPU time with ps -o cputime or /proc/<pid>/stat.

Hard

Hard 1: Lottery simulator (60 minutes)

Write a lottery scheduler simulator for tickets 100, 50 and 250. Run 100, 1,000 and 100,000 draws with 20 different seeds each, and report the largest error from the expected share.

Done when: a table in which the largest error falls as the number of draws grows.

Hint

Use a different seed for each repeat and compare to the expected share.

Hard 2: Stride simulator (60 minutes)

Write a stride simulator for the same tickets. Run 400 picks and report the counts. Then let a new process with 100 tickets join after 200 picks, with its pass set to the smallest current pass, and report the counts of the next 400 picks.

Done when: counts A 100, B 50, C 250 for the first run, and shares that follow 100, 50, 250 and 100 tickets afterwards.

Hint

A new process with pass 0 would run alone for a long time.

Hard 3: Read the kernel's counters (60 minutes)

Start two spinning loops with nice 0 and nice 10 on one processor. After 10 seconds, read se.vruntime, se.sum_exec_runtime and se.load.weight from /proc/<pid>/sched for both. Show that the virtual runtimes are close and the real runtimes differ by the weight ratio.

Done when: a table with the two vruntime values within a few per cent of each other, and a real-time ratio near 9.3 (1,024 ÷ 110).

Hint

The file shows vruntime and run time in milliseconds.