The question this layer answers
How does one computer safely host many programs?
Sharing and virtualizing the machine. This layer connects Processes, Memory, Files, Scheduling to the rest of the computing stack.
The operating system manages competing claims
A process combines an address space with resources and execution state. Threads within a process generally share that address space while having their own execution state, including registers and stacks. The scheduler decides which runnable thread gets CPU time. A context switch changes the active execution state; a switch between address spaces may also require changing memory-management state.
Virtual memory introduces a mapping between addresses used by a program and physical storage. With 4 KiB pages, virtual address 13,000 has page number 3 and offset 712 because 13,000 = 3 × 4096 + 712. If virtual page 3 maps to physical frame 9, the corresponding physical address is 9 × 4096 + 712 = 37,576, assuming access permissions allow it. The offset stays the same; the page/frame part changes.
A missing or disallowed mapping can cause a page fault. A fault does not necessarily mean “fetch from disk”: it may require allocating a page, handling copy-on-write, or rejecting the access. A TLB caches translations; it does not store the application's ordinary data in place of the data cache.
Shared memory makes interleavings observable
The expression counter = counter + 1 can involve a read, a computation, and a write. Begin with counter = 0 and two threads:
| Step | Thread A | Thread B | Shared counter |
|---|
| 1 | Read 0 | · | 0 |
| 2 | · | Read 0 | 0 |
| 3 | Compute 1 | · | 0 |
| 4 | · | Compute 1 | 0 |
| 5 | Write 1 | · | 1 |
| 6 | · | Write 1 | 1 |
Both threads ran, but only one increment survives. In languages where unsynchronized data races are undefined, even this interleaving model is too generous; consult the language's memory model. The educational trace explains the lost-update mechanism without promising that all runtimes behave this way.
Protect the operation, not just the final write
A mutex around the entire read-modify-write operation prevents these critical sections from overlapping when every participating thread follows the protocol. Locking only the write leaves both reads free to observe the old value. A lock also has costs: contention, scheduling interactions, and possible deadlock if multiple locks are acquired inconsistently.
The library reservation has the same shape. “Check availability, then claim” must be protected as a unit. A process-local mutex will not coordinate independent server processes; the shared authority must enforce the invariant. Later, a database can supply that boundary.
Before moving on: produce a different legal schedule with final counter = 2, then explain why seeing that successful schedule in a test does not prove the concurrent program correct.
Free Operating systems & runtimes lessons
Many streams of work share finite processors
Threads in one process commonly share code, heap, and open resources while keeping registers and stacks of their own. The scheduler chooses runnable threads for available cores, preempts them to share time, and leaves blocked threads asleep until an event makes progress possible.
The kernel preserves the outgoing thread’s architectural state, updates accounting and address-space context if needed, selects a runnable successor, and restores its state. Cache and translation state may no longer match the new workload, so a switch has indirect costs beyond saving registers.
Isolation, translation, paging, and faults
Page tables map virtual pages to physical frames with permissions and status. A translation lookaside buffer caches recent mappings. A missing or disallowed mapping triggers a page fault so the kernel can reject access, create a page, load data, or update a copy-on-write mapping.
After a process fork, parent and child can initially share read-only mappings to the same frames. When either writes, a protection fault lets the kernel allocate and copy only that page, then grant the writer a private mapping. Unmodified pages never pay the copy cost.
Files, descriptors, buffering, and persistence
User code places arguments according to an ABI and traps into the kernel. The kernel validates permissions and addresses, performs or starts the operation, then returns a result. File descriptors are process-local handles to kernel-managed open objects; paths are names resolved through a filesystem namespace.
A library may buffer in user space; the kernel may buffer in memory; the device may have its own cache. A successful write can mean bytes were accepted at one boundary, not that stable media now contains them. Flush and synchronization operations strengthen the promise, subject to filesystem and hardware contracts.
Atomicity, waiting, deadlock, and isolation
An operation that looks single in source may compile into several loads and stores that interleave. Locks establish mutual exclusion; condition variables coordinate state changes; atomics provide specified indivisible operations and ordering. Deadlock can arise when tasks wait in a cycle for resources held by one another.
For a bounded queue, the useful invariant connects buffer contents, head, tail, and count. A lock protects the transition that changes those fields together. Producers wait while full; consumers wait while empty; state changes signal waiters. Locking one field but not the invariant still permits impossible combined states.
Calculate response and turnaround while tracking process states.
Compute offsets, distinguish misses from faults, and account for translation cost.
Build a bounded-buffer protocol with a mutex and condition variable.
Model ownership and waiting before choosing a prevention policy.
Order data, metadata, and commit records under an explicit crash model.
Trace submission, ownership, completion, and backpressure.
Practice lab: Catch a lost update
About 25 minutes. Trace loads and stores from Execution. A thread has its own registers but can share memory with other threads.
Shared counter x starts at 0. Two threads each execute LOAD x into a private register, ADD 1 to that register, then STORE the register into x. For this exercise, individual loads and stores are atomic and all steps appear in one sequentially consistent order.
- Give one schedule ending with x = 1 and one ending with x = 2.
- Place a shared mutex around the smallest complete operation that prevents the lost update. Show why protecting only STORE is insufficient.
- Translate virtual address 13 with page size 4 when virtual page 3 maps to physical frame 7. State what extra checks a real translation requires.
Hint
Let both threads load before either stores. For the address, separate page number from offset; only the page number is translated.
Worked solution
A.load(0), B.load(0), A.add(1), B.add(1), A.store(1), B.store(1) ends at 1. Running all of A before all of B ends at 2. The same mutex must protect LOAD–ADD–STORE for every writer; a lock only around stores still permits both threads to compute 1. An atomic increment is another solution under its memory-model contract. Address 13 gives page 3 and offset 1; frame 7 yields 7 × 4 + 1 = 29. Real translation also checks presence and permissions; an absent page can fault rather than translate. Language data races may have stronger consequences than this deliberately simplified schedule.
- Show both valid schedules, keeping each thread’s own order.
- Protect the read–modify–write operation, not just the final write.
- Keep virtual addresses separate from physical addresses and permission checks.
Change one assumption
If thread A locks X then Y while B locks Y then X, show a deadlock schedule and repair it with a shared lock order.
Make resource sharing and recovery observable
Work with explicit schedules, address translations, and crash points. A correct answer identifies the invariant and the event that changes it.
1. Schedule and compare · allow 40 minutes
Optimize a named scheduling objective
Three CPU-only jobs arrive at time 0: A needs 6 ms, B needs 2 ms, C needs 1 ms. Ignore switching cost. Compare nonpreemptive FCFS in order A, B, C; shortest-job-first; and round robin with 2 ms quantum and initial queue A, B, C. Draw timelines and calculate each job's completion time, mean turnaround, and mean first-response time.
Explain why shortest-job-first's result here does not establish fairness under an endless stream of short jobs. State how unknown burst lengths and nonzero switching costs change the decision.
Get a starting hint
All arrivals are 0, so turnaround equals completion time. Response time stops at the first CPU service, not at completion.
Compare your reasoning with the worked solution
FCFS runs A: 0–6, B: 6–8, C: 8–9. Completion times(A,B,C)=(6,8,9), mean turnaround 23/3≈7.667 ms, and mean response(0+6+8)/3≈4.667 ms. SJF runs C: 0–1, B: 1–3, A: 3–9. Completions are(9,3,1), mean 13/3≈4.333 ms; first responses(A,B,C)=(3,1,0), mean 4/3≈1.333 ms.
Round robin runs A: 0–2, B: 2–4, C: 4–5, A: 5–7, A: 7–9. Completions are(9,4,5), mean 6 ms; first responses are(0,2,4), mean 2 ms. The final two A quanta are adjacent because no other job remains.
The finite all-at-once workload has known bursts and no future arrivals. Repeatedly favoring newly arrived short jobs can starve a long job under different assumptions. Real schedulers estimate rather than know future CPU demand, and a small quantum can increase switching overhead. Choose a metric and workload model before declaring one schedule best.
Check your reasoning
- Keep response and turnaround distinct.
- Account for the short job ending before its quantum expires.
- State which assumptions support the comparison.
2. Address and timing calculation · allow 35 minutes
A TLB miss is not a page fault
A machine uses 16-bit virtual byte addresses and 1 KiB pages. Translate virtual address 0x2C34 given that its virtual page maps to physical frame 7. State virtual-page number, offset, and physical address.
A TLB lookup costs 5 ns. A hit then requires one 100 ns memory access. A miss walks two page-table levels, each costing 100 ns, then accesses data. With 90% TLB hits and no cache effects or page faults, calculate average access time. Explain what changes if the valid mapping forbids writes or if the page is not resident.
Get a starting hint
A 1 KiB page uses ten offset bits. Page-table lookup cost and residency are different questions.
Compare your reasoning with the worked solution
0x2C34=11316. Dividing by 1024 gives virtual page 11 and offset 52=0x34. Frame 7 begins at 7×1024=7168=0x1C00, so physical address is 0x1C34. The offset is preserved by translation.
Hit time is 5+100=105 ns. Miss time is 5+2×100+100=305 ns. The average is 0.9×105+0.1×305=125 ns. A TLB miss in this example merely requires a page-table walk; the mapped data is resident.
A write to a read-only mapping must fail the permission check even if the translation is cached. A nonresident page can require a fault handler, storage access, replacement, and a retry, so its cost is not included in the 305 ns walk. A valid address can fault for residency reasons; an invalid or forbidden address may instead produce an error. Hardware and operating-system policies determine the exact distinction.
Check your reasoning
- Split page and offset correctly.
- Count both page-table accesses plus the data access.
- Preserve permission checks on cached translations.
3. Interleaving proof · allow 45 minutes
Repair a lost wakeup and a stolen predicate
A consumer checks whether a shared queue is empty, releases its mutex, then waits for a notification. A producer appends an item and signals. Construct an interleaving where the consumer sleeps despite available work.
Write correct consumer pseudocode using a condition variable whose wait atomically releases the mutex and begins waiting, then reacquires it before returning. Explain why the queue predicate belongs in a while loop. Give a two-consumer schedule showing a wakeup that does not imply an item is still available. State the producer's locking and notification obligations.
Get a starting hint
A notification is not stored work. The mutex protects the predicate, and the wait operation bridges checking with sleeping.
Compare your reasoning with the worked solution
The consumer observes empty and unlocks. Before it begins waiting, the producer locks, appends, signals when nobody is waiting, and unlocks. The consumer then sleeps even though the queue is nonempty. The gap between predicate check and wait registration caused the lost wakeup.
Correct pseudocode is: lock(m); while queue.empty(): cv.wait(m); item=queue.pop(); unlock(m). The producer changes the queue while holding the same mutex and notifies according to the condition-variable protocol. The wait's atomic release-and-registration prevents the gap; reacquisition makes the next predicate check synchronized.
With two waiting consumers, a broadcast may wake both after one item is inserted. Consumer 1 reacquires the mutex and removes the item. Consumer 2 later reacquires it with the queue empty again. An if guard would allow an invalid pop; a while guard returns to waiting. Spurious wakeups are another reason to recheck. Notification means the predicate may have changed, not that a particular consumer owns a resource. Keep the state predicate as the source of truth.
Check your reasoning
- Show the exact check-to-wait gap.
- Use the same mutex for every predicate mutation and check.
- Explain a nonspurious schedule that still requires a loop.
4. Wait graph and invariant · allow 40 minutes
Prove a lock-order repair
Thread T1 locks A then B. Thread T2 locks B then A. Locks are exclusive and neither thread releases its first lock while waiting for the second. Construct the deadlock schedule and its wait-for graph.
Change the policy so every thread acquires locks in ascending order A<B<C. Prove a wait cycle is impossible under that policy. Explain why a timeout alone does not make a partially executed operation correct, and specify what rollback or idempotency obligations arise when a timed-out operation is retried.
Get a starting hint
A cycle of waiting under a strict global lock order would require lock ranks to increase and return to the starting rank.
Compare your reasoning with the worked solution
T1 acquires A; T2 acquires B; T1 requests B and waits; T2 requests A and waits. The wait-for graph has T1→T2 and T2→T1. Neither can reach its release operation.
Under a strict global order, a thread holding a lock can wait only for a higher-ranked lock. Following a hypothetical cycle produces a strictly increasing sequence of ranks that returns to its starting point, a contradiction. The proof assumes every relevant acquisition follows the same order and that other resources do not introduce an unmodeled dependency. Reentrant behavior and upgrades need their own rules.
A timeout breaks a wait only if the system actually aborts or changes the operation. If an operation already changed shared state, releasing locks without restoring its invariant can expose partial work. A retry can duplicate effects unless the operation is rolled back or keyed for idempotent completion. Deadlock prevention, starvation freedom, and transaction correctness are distinct guarantees.
Check your reasoning
- Draw the two-edge wait cycle.
- Use a strict ordering argument for the repair.
- State how partial effects are handled after timeout.
5. Crash-state analysis · allow 50 minutes
Recover an update at every crash boundary
A toy store updates two home pages, P and Q, from values (4,7) to (5,8). It uses a redo journal containing full new page images and a commit record. Individual journal records are atomic, but a crash during a flush may leave any subset of the submitted records durable. A completed flush acknowledges durability of all preceding journal writes. Home-page writes can become durable in either order.
Specify a safe sequence. Determine recovery after crashes: during the page-image flush; after the images are durable but before the commit record; during the commit-record flush; after durable commit but before either home page; after only P reaches home; after both pages but before log reclamation. Explain why redo must be idempotent and why changing page images to “increment by 1” requires additional machinery.
Get a starting hint
Make the complete redo information durable before writing commit evidence. Then make commit evidence durable before exposing any home-page update. A flush of several records is not an atomic transaction.
Compare your reasoning with the worked solution
Write journal images P=5 and Q=8. Flush the images and wait for durable completion. Only then write the commit record, flush it, and wait again before issuing any home-page write. Apply both home images, ensure they are durably complete, then reclaim the journal under its own safe reclamation protocol. The first durability barrier prevents a commit record from surviving without its required images; the second prevents uncommitted home effects.
During the image flush, only some images may survive, but no commit record has been issued, so recovery ignores the incomplete transaction. The same applies after durable images but before the commit record. During the commit flush, either the atomic commit record survives or it does not: if present, all images are already durable and recovery replays them; otherwise the transaction is ignored. After durable commit and before home writes, recovery installs both images. After only P is durable, redo reinstalls P=5 and installs Q=8. After both are durable but the journal remains, replaying both assignments leaves (5,8) unchanged.
Assignments are idempotent: applying the same image twice has the same result as once. Blindly replaying increments would produce (6,9) after a previously applied update. Operation logs therefore need sequence/version checks or another method preventing duplicate application. The toy assumptions omit torn records, checksums, concurrent transactions, and real storage ordering; removing atomic-record assumptions requires explicit detection and recovery rules.
Check your reasoning
- Order durable images, durable commit evidence, and home-page writes with two acknowledged journal barriers.
- Analyze every listed crash point.
- Show why replay semantics determine idempotence.
6. Queue growth and admission control · allow 35 minutes
Asynchronous code cannot create service capacity
A single worker takes 10 ms per request and receives 120 requests per second for a sustained interval. Assume constant service time and no parallel execution. Calculate capacity and the long-run queue growth rate if every request is admitted. Estimate backlog growth after 30 seconds from an empty system, ignoring startup rounding.
Design a bounded queue of 50 waiting requests with an explicit overload response. Explain how cancellation and retries can undermine the bound. Compare blocking a caller, rejecting work, and adding workers; identify one correctness issue that must be addressed before parallelizing.
Get a starting hint
Changing the waiting API does not change the service rate. Count admitted work and running work separately.
Compare your reasoning with the worked solution
Service capacity is 1/0.01=100 requests per second. Arrival exceeds it by 20 per second, so backlog grows by about 600 requests over 30 seconds under the fluid approximation. An async handler can keep threads free while waiting, but cannot eliminate the excess work.
A bounded design permits at most 50 waiting requests plus the one running request. Admission atomically checks/reserves queue space and returns a documented overload result when full. A caller can retry with backoff and an idempotency key where effects may already occur. Immediate unbounded retries can increase arrivals precisely when the system is least able to handle them. Cancellation must define whether queued work is removed and whether an already running effect can still finish.
Blocking propagates pressure but consumes caller resources and needs deadlines. Rejection makes overload explicit. Extra workers may increase capacity only if another bottleneck does not dominate. Before parallelizing, protect shared invariants such as one reservation per item; throughput is not useful if concurrent execution corrupts state.
Check your reasoning
- Derive capacity from service time.
- Bound waiting and running work explicitly.
- Connect overload policy with retry and shared-state semantics.
Study the underlying methods
Section project: Simulate scheduling and a blocking bounded mailbox
6 to 8 hours. Create a deterministic operating-system simulator for small process scripts. Instructions are COMPUTE, SEND(value), RECEIVE, SLEEP(ticks), and EXIT. Each successful nonblocking instruction consumes one simulated tick; a blocked operation remains pending without consuming a tick. Use a FIFO ready queue with one successful instruction per quantum and a shared FIFO mailbox of capacity two. SEND blocks when full, RECEIVE blocks when empty, and completing an opposite operation wakes one waiter in FIFO order. Sleep deadlines use absolute ticks; when no process is ready, advance time to the next deadline, if one exists. Inputs are process instruction lists and initial mailbox state. Outputs are the per-tick scheduler trace, process-state changes, delivered values, and completion or deadlock status. Write down the order of wakeups, requeueing, and timer processing so identical inputs produce identical traces. This is a single-threaded simulation of concurrency, allowing failures to be reproduced without relying on host thread timing. Explain separately why a full mailbox is temporary blocking while a closed wait cycle with no future wakeup is deadlock. Record why each blocked process is waiting and which event can release it. An invariant should prevent the same process from appearing simultaneously in the ready queue and a wait queue.
Milestones
- Define ready, running, blocked, sleeping, and exited states and their legal transitions.
- Implement round-robin dispatch, sleep deadlines, and deterministic trace logging.
- Implement bounded-mailbox blocking and FIFO wakeup queues.
- Run producer-consumer, sleeping-worker, and deadlocked-script scenarios.
- State and check mailbox capacity, delivery, and scheduler-state invariants.
Acceptance criteria
- A producer sending 0 through 5 and a consumer receiving six times deliver exactly [0,1,2,3,4,5], without duplication or loss.
- Mailbox occupancy remains between zero and two at every recorded transition.
- Blocked processes do not consume CPU ticks until a matching wakeup makes their pending operation eligible.
- Two always-ready compute-only processes alternate successful instructions until one exits.
- With no ready process but a future sleep deadline, time advances and execution resumes rather than reporting deadlock.
- With only blocked receivers, an empty mailbox, and no possible future wakeup, the simulator reports deadlock with the waiting process identifiers.
Add cancellation of a blocked process and prove that removing it from wait queues cannot lose a mailbox value or wake the wrong successor.
Practise Operating systems & runtimes free →