Operating System Scenarios: Solve Scheduling, Concurrency, and Page Replacement

A changed workload can invalidate an otherwise familiar Round Robin, semaphore, or LRU answer. Freeze the inputs, write the mutable state, apply one transition at a time, and check an invariant before answering.

1. Use one state-trace method for every OS scenario

Set up four columns before calculating:

Declare conventions too. A context switch occurs only when the CPU changes processes, so initial dispatch is excluded. An arrival at a quantum boundary enters before the preempted process. Fixed frame-slot order is only a display aid, not FIFO order or LRU recency.

2. Scenario 1: Trace Round Robin before counting context switches

The CPU Scheduling Algorithms Explained guide owns the algorithm comparison. Here, one workload isolates the boundary-arrival rule and then changes only the quantum. Take P1(arrival 0, burst 5), P2(arrival 1, burst 3), and P3(arrival 2, burst 1), with quantum q = 2 and zero dispatch overhead.

The ready queue at each decision is:

• t=0 [P1]: run P1 for two units.

• t=2 [P2,P3,P1]: P2 and P3 have arrived, and the boundary rule places them before preempted P1.

• t=4 [P3,P1,P2]: run P3 next.

• t=5 [P1,P2]: P3 completes.

• t=7 [P2,P1]: P1 has one unit left.

• t=8 [P1]: P2 completes, then P1 finishes.

The Gantt chart is 0-2 P1 | 2-4 P2 | 4-5 P3 | 5-7 P1 | 7-8 P2 | 8-9 P1.

Completion times are P1 = 9, P2 = 8, P3 = 5. Turnaround times, completion - arrival, are 9, 7, 3. Waiting times, turnaround - burst, are P1 = 4, P2 = 4, P3 = 2. The average is (4 + 4 + 2) / 3 = 10/3 = 3.33 time units.

Six segments create five process-to-process context switches, at times 2, 4, 5, 7, and 8. Counting initial dispatch uses a different convention, so state yours. Executed time is 2 + 2 + 1 + 2 + 1 + 1 = 9, equal to total burst time 5 + 3 + 1 = 9.

3. Scenario 2: Prove a race condition with the actual interleaving

Set shared seats = 1. T1 and T2 each run the same check-then-act sequence: local = seats; if local > 0, write seats = local - 1 and return success. The read, decision, and update are not one indivisible action.

Trace one legal interleaving. T1 reads seats = 1 and passes the check. Before it writes, T2 also reads 1 and passes. Both compute 0, both write 0, and both report success. The stored value looks plausible, but one available seat has produced two reservations. In serial execution, the first thread reserves it and the second reads 0, so exactly one succeeds. That diagnoses the race.

Protect the full read-check-write sequence with wait and signal as defined in Process Synchronization and Semaphores. The linked primer owns semaphore definitions and standard patterns; this trace isolates a check-then-act failure. With binary semaphore S = 1, the first thread writes 0, releases the lock, and returns success. The second then reads 0 and cannot reserve, so overbooking is impossible.

Changing the semaphore value changes the diagnosis. With S = 0, both threads block unless another actor signals. With counting semaphore S = 2, both may pass the one-seat check together, so the overbooking interleaving can return. A resource counter and a semaphore count answer different questions.

4. Scenario 3: Keep policy metadata separate from frame contents

Use three empty frames and references 6, 2, 6, 1, 3, 2, 4, 1, 5, 2, 3, 4. In each trace, F means fault and H means hit.

FIFO gives [6,-,-] F -> [6,2,-] F -> [6,2,-] H -> [6,2,1] F -> [3,2,1] F -> [3,2,1] H -> [3,4,1] F -> [3,4,1] H -> [3,4,5] F -> [2,4,5] F -> [2,3,5] F -> [2,3,4] F: 9 faults and 3 hits. FIFO order changes on a fault, never on a hit.

LRU gives [6,-,-] F -> [6,2,-] F -> [6,2,-] H -> [6,2,1] F -> [6,3,1] F -> [2,3,1] F -> [2,3,4] F -> [2,1,4] F -> [5,1,4] F -> [5,1,2] F -> [5,3,2] F -> [4,3,2] F: 11 faults and 1 hit.

The decisive event is the fifth reference, page 3. FIFO evicts 6 because insertion age ignores the hit at the third reference. LRU evicts 2 because that hit refreshed 6's recency. The FIFO, LRU, and Optimal page replacement comparison owns the broader algorithm survey; this scenario isolates one policy divergence and requires every slot change to follow the selected metadata.

5. When one input changes, recompute from the first affected event

Change only the Round Robin quantum to q = 4. The new chart is 0-4 P1 | 4-7 P2 | 7-8 P3 | 8-9 P1, so context switches fall from 5 to 3.

Completion times are 9, 7, 8. Turnaround times are 9, 6, 6, so waiting times are P1 = 9 - 5 = 4, P2 = 6 - 3 = 3, and P3 = 6 - 1 = 5. Average waiting is (4 + 3 + 5) / 3 = 12/3 = 4.0. Fewer switches did not produce a lower average wait.

Use the delta method: copy state before the changed event, invalidate everything after it, and continue. Never retain a completion time, queue order, local value, or recency list from the old branch.

6. Plausible-looking answers that should fail the invariant check

For scheduling, do not enqueue P1 before an arrival at the time-2 boundary under the declared rule. Do not count initial dispatch as a switch without saying so. Derive waiting as turnaround - burst, not by visual guesswork.

For concurrency, do not treat a check-then-decrement as indivisible, lock only the final write, or assume S = 2 gives mutual exclusion to two threads. For replacement, never replace on a hit, refresh FIFO order on a hit, or read visual slot order as LRU recency.

Say: “My convention is X, the next event is Y, this row changes only Z, and the invariant still holds.” This keeps the reasoning auditable.

7. The short version and the next practice step

Write the fixed inputs, expose mutable state, advance one event, and check the invariant. A correct number without a visible trace is fragile. A trace lets you defend it and adapt it.

For structured revision, continue with the Operating System learn module. Then use Interview and Resume Preparation to practise explaining a trace aloud and responding when a value changes.