CSE Roadmap

Core tier · about 3 hours · 6 parts

Part 6 of 6 · 3 min read

Exercises

Easy

Easy 1: Name the arrow (20 minutes)

For each event, name the state change: a timer interrupt, a disk read finishing, scanf waiting for the keyboard, and the scheduler picking a process.

Done when: four answers: running to ready, waiting to ready, running to waiting, ready to running.

Hint

Interrupts from the timer remove the processor; interrupts from devices end a wait.

Easy 2: Which is impossible (20 minutes)

Which of these arrows does the standard diagram not have: ready to running, waiting to running, running to waiting, ready to waiting? Explain in one line each for the two impossible ones.

Done when: you name waiting to running and ready to waiting, with reasons.

Hint

A process cannot wait on something it has not asked for.

Easy 3: Match the letter (20 minutes)

Give the Linux letter for a process waiting for a timer, one computing, one stopped with Ctrl+Z, and one finished but not collected.

Done when: S, R, T and Z.

Hint

ps shows these letters in the STAT column.

Medium

Medium 1: Trace three processes (30 minutes)

One processor, three processes. A computes for two slots then waits for I/O for three slots, then computes one more. B and C only compute. Draw a table of slots 1 to 7 with the state of each.

Done when: a table where the processor is busy in each slot and A is ready, not running, when its I/O ends if B or C holds the processor.

Hint

When I/O ends the process becomes ready, not running.

Medium 2: Observe a state change (30 minutes)

Start sleep 300 &, then use ps -o pid,stat,wchan:20,comm -p PID and kill -STOP, kill -CONT to see the state turn S, T and S again. Record each output.

Done when: three outputs and a line on what each letter means.

Hint

The kill -STOP signal can be undone with kill -CONT.

Medium 3: Count switches (30 minutes)

Write one program that sleeps ten times and one that loops for two seconds. Print the voluntary and non-voluntary counters of each at the end.

Done when: a table of four counters, with the sleeping program voluntary-heavy and the loop non-voluntary-heavy.

Hint

Read the counters just before returning from main.

Hard

Hard 1: Reconstruct the PCB (60 minutes)

From /proc/self/status and /proc/self/stat of a small program, find at least six pieces of information that match PCB fields in the table above. Map each to its PCB field.

Done when: a table of six rows with the proc line, its value and the matching field.

Hint

Look at State, Pid, PPid, VmRSS, Threads and the context-switch lines.

Hard 2: Find a D state (60 minutes)

Run a large disk copy (such as dd if=/dev/zero of=big bs=1M count=2000) and, in a second terminal, sample the STAT column of ps once per half second. Report how often D appeared and explain why.

Done when: a list of samples, a count of D, and an explanation tying D to uninterruptible I/O.

Hint

Files can be larger than memory, so the copy is slowed by the disk.

Hard 3: Draw the diagram from data (60 minutes)

Write a small C program that does a computation, then sleep(1), then another computation. Record State at several points using a second process that reads /proc/PID/status every 100 ms. Plot the sequence R, S, R and relate it to the state diagram.

Done when: a sampled sequence of states, a drawn diagram with your run traced on it.

Hint

Use usleep(100000) in the sampler.