Skip to main content

Module Quiz

Complete this quiz after finishing all concept and practice pages. Treat it as closed-book on the first pass; open notes on the second.

Current Module Questions​

Question 1: What is a process, exactly?​

Name the five runtime components that together define a process (as opposed to a program on disk). For each, say whether it lives in user space or kernel space.

Answer:

ComponentUser/Kernel
Address space (code, data, heap, stack, mmap regions)User space, mapped through kernel page tables
CPU register state (RAX..R15, RIP, RSP, RFLAGS, FPU/SIMD)Saved in the kernel's PCB while not running
Open file / socket tableKernel, indexed by user-level FDs
Signal handler table, signal mask, pending signalsKernel (handlers run in user space)
Scheduling state, credentials, parent/children pointers, resource accountingKernel (PCB)

Question 2: PCB transitions​

List the PCB fields that must change when a process moves from RUNNING to BLOCKED because of a blocking read().

Answer: task_state (RUNNING -> INTERRUPTIBLE/UNINTERRUPTIBLE), the saved register set (stored), wait_queue pointer (inserted into the device/file wait queue), last-scheduled timestamp for accounting. The scheduler removes it from the runqueue.

Question 3: fork and exec semantics​

What state is preserved and what is replaced when a child process calls execve after fork?

Answer: Preserved: PID, PPID, open file descriptors not marked FD_CLOEXEC, signal mask, working directory, uids/gids, controlling terminal. Replaced: entire address space (all mappings discarded and new ones installed from the ELF), register state (PC/SP set to the new program's entry), signal handlers reset to default (except those explicitly inherited by convention), some resource limits.

Question 4: Gantt chart -- SJF vs FCFS​

Workload: four jobs arriving at t=0 with lengths A=8, B=4, C=2, D=6. Draw the FCFS and SJF Gantt charts, then compute average turnaround time for each.

Answer:

FCFS order A, B, C, D:

| A (0-8) | B (8-12) | C (12-14) | D (14-20) |

Turnaround: A=8, B=12, C=14, D=20. Average = (8+12+14+20)/4 = 13.5.

SJF order C, B, D, A:

| C (0-2) | B (2-6) | D (6-12) | A (12-20) |

Turnaround: C=2, B=6, D=12, A=20. Average = (2+6+12+20)/4 = 10.0.

SJF reduces average turnaround by 3.5.

Question 5: Gantt chart -- Round-Robin​

Same four jobs with Round-Robin quantum q=2, cyclic order A, B, C, D. Draw the first 20 time units of the Gantt chart and give the completion time of each job.

Answer:

| A | B | C | D | A | B | D | A | B | D | A | A | A |
0   2   4   6   8  10  12  14  16  18  20

Completions: C=6, B=16, D=18, A=20 (A still has 2 units left at t=18; finishes at 20). Average turnaround (20+16+6+18)/4 = 15.0, strictly worse than SJF, comparable to FCFS, but better response time for C and B.

Question 6: Round-Robin quantum tradeoff​

Round-Robin quantum q = 100 ms versus q = 1 ms on an 8-job workload. Which is fairer on response time? Which has better throughput? Justify in one sentence each.

Answer: q = 1 ms is fairer on response time because every job gets a turn within ~8 ms; q = 100 ms is better on throughput because the context-switch overhead is amortized over a longer run and more useful work is done per second. The right q is somewhere in between -- typically an order of magnitude larger than the context-switch cost.

Question 7: Why SJF is optimal for average turnaround​

Sketch the exchange argument for why SJF minimizes average turnaround for a set of jobs all arriving at t=0.

Answer: Take any non-SJF schedule; find two adjacent jobs i, j with i run first where length(i) > length(j). Swapping them: job i's completion goes up by length(j), job j's completion goes down by length(i), and no other job moves. Sum of completions changes by length(j) - length(i) < 0. Swapping strictly decreases total (and therefore average) turnaround. Repeat until sorted by length -- that is SJF.

Question 8: Metric conflict​

Give a workload where Round-Robin has better average response time than FCFS but worse average turnaround time. Explain in one sentence why this is a general pattern.

Answer: Ten jobs of length 10 arriving at t=0, quantum q=1. FCFS turnaround average = 55, RR turnaround ≈ 95 (everyone ends near t=100). FCFS response average = 45, RR response average ≈ 1. In general, RR spreads "start time" evenly (good response) but stretches "finish time" (bad turnaround).

Question 9: MLFQ rules​

State MLFQ's two priority-adjustment rules and the reason each is needed.

Answer:

  1. Priority demotion on quantum expiry: If a job uses its entire allotment at its current priority, demote it one queue. Reason: differentiates CPU-bound from I/O-bound jobs without foreknowledge of job length.
  2. Priority boost: Periodically promote every job to the top queue. Reason: prevents starvation of demoted jobs when a new stream of short interactive jobs arrives, and handles jobs that change behavior (go from CPU-bound to interactive) mid-run.

Question 10: Priority inversion​

Explain the Mars Pathfinder priority inversion in three sentences. Include what went wrong and what fixed it.

Answer: A low-priority meteorological-data thread took a mutex, then a medium-priority communications thread preempted it; when the high-priority "bus management" thread came up and tried to take the same mutex, it was blocked indefinitely because the low-priority holder was itself never scheduled due to the medium-priority CPU hog. The watchdog saw the bus thread miss its deadline and rebooted the probe. It was fixed by enabling priority inheritance on the mutex, so the low-priority holder temporarily inherits the high priority of its blocked waiter and runs, releases the lock, and unblocks the high-priority thread.

Question 11: Real-time schedulability​

A uniprocessor has three periodic tasks with (C=1, T=4), (C=2, T=5), (C=1, T=8) (compute time C, period T). Is this schedulable under EDF? Under RMS? Explain.

Answer: U = 1/4 + 2/5 + 1/8 = 0.25 + 0.40 + 0.125 = 0.775. EDF is schedulable iff U <= 1, so yes -- EDF will meet all deadlines. RMS: the Liu-Layland bound for n=3 is 3(2^{1/3} - 1) ≈ 0.779. U = 0.775 < 0.779, so the sufficient bound holds and RMS also meets deadlines.

Question 12: Context-switch anatomy​

Rank the following by typical wall-clock cost on a modern x86-64 machine with Spectre mitigations enabled: (a) save/restore GP registers, (b) TLB flush on address-space change without PCID, (c) kernel trap entry+exit, (d) L1 cache cold start after being switched out.

Answer: Roughly: (d) L1 cold start > (b) TLB flush without PCID > (c) trap entry+exit > (a) register save/restore. (a) is a few hundred nanoseconds; (c) is a few hundred nanoseconds plus mitigations overhead; (b) is hundreds to thousands of nanoseconds amortized over subsequent page faults; (d) is often several microseconds of indirect cost and dominates.

Question 13: Threads vs processes​

List five items of state that threads of the same process share, and five items that they do not.

Answer:

SharedNot shared
Address space (all memory mappings)CPU register state, including RIP/RSP
Open file descriptor tableStack
Signal handler tableSignal mask
Process credentials (uid/gid)Thread-local storage (%fs / %gs)
PIDTID

Question 14: Multi-core load balancing​

Why is a single global run queue impractical on a 64-core machine? Name two specific mechanisms modern kernels use instead.

Answer: A global run queue requires a lock on every scheduling event; at 64 cores that lock is catastrophically contended and destroys scalability. Modern kernels use (1) per-CPU run queues so each core picks locally, and (2) a load balancer -- often work-stealing driven from the idle path plus periodic ticks -- that migrates tasks across queues with awareness of scheduling domains (SMT siblings, sockets, NUMA nodes).

Question 15: cgroups cpu.max vs cpu.weight​

A container has cpu.weight = 100 and cpu.max = "50000 100000" on a 4-core, otherwise-idle host. It runs four CPU-bound workers. How much CPU does the container receive? Which knob bound it?

Answer: It receives 50% of one CPU (the quota is 50000 µs per 100000 µs window). cpu.weight is a proportional knob and only matters under contention; cpu.max is a hard cap that applies even on an idle host. Here cpu.max is the binding constraint.

Interleaved Review Questions​

Prior Module 1 (S1 Math: Combinatorics)​

Two jobs are scheduled randomly in order onto a single CPU. How many distinct Gantt charts are possible, and how does this relate to the exchange argument for SJF?

Answer: 2! = 2 possible orders. The exchange argument says exactly one of these minimizes sum-of-completions, and you can reach it from the other by a single swap, which strictly decreases the sum when jobs are of different lengths.

Prior Module 2 (S1 Math: Probability)​

If context-switch cost is ~2 µs and each job's quantum is 2 ms, what fraction of CPU is lost to context-switch overhead? If the quantum shrinks to 200 µs, what is the new fraction?

Answer: At 2 ms quantum, overhead fraction = 2 / (2000 + 2) ≈ 0.1%. At 200 µs quantum, overhead = 2 / 202 ≈ 1%. Shrinking the quantum by 10× raises overhead by 10×.

Prior Module 3 (S2 Algorithms: Asymptotic Analysis)​

The Linux CFS scheduler uses a red-black tree keyed on vruntime. What are the asymptotic costs of (a) picking the next task to run, (b) inserting a waking task, (c) removing a task that went to sleep? Express in terms of the number of runnable tasks n.

Answer: (a) O(1) with a cached leftmost pointer, (b) O(log n) balanced-tree insert, (c) O(log n) balanced-tree delete. Amortized cost per scheduling event is O(log n).

Prior Module 4 (S2 Algorithms: Greedy)​

Is SJF a greedy algorithm? If so, what is its exchange argument? If not, why not?

Answer: Yes. SJF greedily picks the shortest remaining job at every decision point. The exchange argument (Q7) proves that any deviation from SJF can be improved by swapping a longer job ahead of a shorter one, strictly lowering average turnaround. This is the standard "exchange" template for greedy correctness.

Prior Module 5 (S4 Computer Architecture: Memory Hierarchy)​

Why does the L1 data cache get "cold" on a context switch, and how does that affect effective instruction throughput for the first few microseconds of the new task's execution?

Answer: After a switch, the L1 (and often L2) is full of the previous task's working set. The new task's first memory accesses miss in L1, hit in L2/L3 or go to DRAM, and cause hundreds-of-cycles stalls. Effective IPC drops by an order of magnitude for several microseconds until the cache refills, even though the CPU front end is otherwise healthy.

Self-Assessment and Remediation​

Mastery Level (90-100% correct):

  • Ready to advance to Module 2 (Memory Management) with confidence.

Proficient Level (75-89% correct):

  • Review only the missed concept pages and redo the matching Gantt exercises in Practice 1. One kata re-run (usually Kata 2 or 4) covers most remaining gaps.

Developing Level (60-74% correct):

  • Rework Practice 1 (scheduling policy lab) and Practice 3 (context-switch clinic). Expect the gap to be: (a) you can define metrics but not compute them on a Gantt chart, or (b) you conflate response time with turnaround time. Also redo Kata 1 (mini scheduler) and Kata 2 (measure context-switch cost) -- these make the metrics visceral.

Insufficient Level (<60% correct):

  • Go back to the concept sequence. Most likely issue: you are treating scheduling as "there is a best policy" rather than "every policy trades three metrics against each other." Restart from Cluster 2 and treat every policy page as an answer to "for what metric is this optimal, and what does it sacrifice?" Then return to Cluster 3 with that lens. Also redo Practice 2 (process model workshop) -- understanding state transitions is prerequisite for Cluster 4.