Skip to main content

Quiz Calibration

Attempt the quiz before reading this page. Preserve the original answer, correction and help received. These explanations calibrate retrieval; successful recall alone does not complete the module or its practical evidence gates. For context such as shared schemas, use the question page.

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.

Calibration: | Component | User/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 table | Kernel, indexed by user-level FDs | | Signal handler table, signal mask, pending signals | Kernel (handlers run in user space) | | Scheduling state, credentials, parent/children pointers, resource accounting | Kernel (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().

Calibration: 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?

Calibration: 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.

Calibration: 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.

Calibration: ``` | 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.

**Calibration:** `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`.

**Calibration:** 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.

**Calibration:** 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.

**Calibration:** 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.

**Calibration:** 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.

**Calibration:** `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.

**Calibration:** 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.

**Calibration:** | Shared | Not shared |
| --- | --- |
| Address space (all memory mappings) | CPU register state, including `RIP/RSP` |
| Open file descriptor table | Stack |
| Signal handler table | Signal mask |
| Process credentials (uid/gid) | Thread-local storage (`%fs` / `%gs`) |
| PID | TID |

### 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.

**Calibration:** 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?

**Calibration:** 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.

### 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?

**Calibration:** `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?

**Calibration:** 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`.

**Calibration:** (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?

**Calibration:** 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?

**Calibration:** 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.