Practice: OS rapid-fire and numericals
60 min · Advanced
Need help? Ask a tutor on WhatsApp (opens in a new tab)A placement test often ends with one mixed OS round: a scheduling numerical, a page-fault table, a deadlock scenario and a few spoken questions. The interviewer is checking speed, exact answers and clear spoken reasoning together.
Rapid-fire round and the self-scoring sheet
Rapid-fire round is a run of short questions answered in one or two sentences, used to check breadth quickly; aim for about 20 seconds each.
Say each answer aloud, then mark it. Score every part of this set separately, so you know what to revise and not just your total.
- Interview tab: 1 point per question answered correctly and clearly (26).
- Practice tab numericals: 2 points each when the final answer and the working are right (20).
- MCQ tab: 1 point per correct answer (12).
- Below 70% in any part: go back to that lesson's Summary tab before retrying.
Order of execution
A 20-second answer
Put the parts of a strong spoken answer in order.
Scheduling numericals drill
TAT / WT are the two numbers every scheduling numerical needs: turnaround time = completion − arrival, and waiting time = turnaround − burst.
The program below prints the Gantt chart and average waiting time for FCFS, SJF, SRTF and Round Robin (q = 3) on the drill data, so you can find where your own chart differs.
Example 1 · Checker: four scheduling algorithms on the drill data
from collections import deque
name = ["P1", "P2", "P3", "P4", "P5"]arr = [0, 2, 3, 5, 6]burst = [6, 2, 8, 3, 4]n = 5
def report(title, gantt, finish): w = sum(finish[i] - arr[i] - burst[i] for i in range(n)) print(f"{title:<5} {gantt} | avg WT {w / n:.2f}")
# FCFSfin, time, g = [0] * n, 0, "0"for i in range(n): time = max(time, arr[i]) + burst[i] fin[i] = time g += f" [{name[i]}] {time}"report("FCFS", g, fin)
# SJF (non-preemptive)fin, done, time, g = [0] * n, set(), 0, "0"while len(done) < n: ready = [i for i in range(n) if i not in done and arr[i] <= time] if not ready: time += 1 continue pick = min(ready, key=lambda i: burst[i]) time += burst[pick] fin[pick] = time done.add(pick) g += f" [{name[pick]}] {time}"report("SJF", g, fin)
# SRTF (preemptive)fin, left, time, g, last, finished = [0] * n, burst[:], 0, "", "", 0while finished < n: ready = [i for i in range(n) if left[i] > 0 and arr[i] <= time] pick = min(ready, key=lambda i: left[i]) if ready else None now = name[pick] if ready else "idle" if now != last: g += f"{time} [{now}] " last = now time += 1 if pick is not None: left[pick] -= 1 if left[pick] == 0: fin[pick] = time finished += 1report("SRTF", g + str(time), fin)
# Round Robin, q = 3fin, left, q, nxt, time, g = [0] * n, burst[:], deque(), 0, 0, "0"while nxt < n and arr[nxt] <= time: q.append(nxt) nxt += 1while q or nxt < n: if not q: time = arr[nxt] while nxt < n and arr[nxt] <= time: q.append(nxt) nxt += 1 p = q.popleft() run = min(3, left[p]) time += run left[p] -= run g += f" [{name[p]}] {time}" while nxt < n and arr[nxt] <= time: q.append(nxt) nxt += 1 if left[p] > 0: q.append(p) else: fin[p] = timereport("RR q3", g, fin)FCFS 0 [P1] 6 [P2] 8 [P3] 16 [P4] 19 [P5] 23 | avg WT 6.60 SJF 0 [P1] 6 [P2] 8 [P4] 11 [P5] 15 [P3] 23 | avg WT 4.80 SRTF 0 [P1] 2 [P2] 4 [P1] 8 [P4] 11 [P5] 15 [P3] 23 | avg WT 4.40 RR q3 0 [P1] 3 [P2] 5 [P3] 8 [P1] 11 [P4] 14 [P5] 17 [P3] 20 [P5] 21 [P3] 23 | avg WT 7.00
What this code does
- Each block is one algorithm from the module, written as briefly as possible so you can compare it with your hand working.
- SRTF preempts P1 at time 2 for P2 (2 ms vs 4 ms left), then resumes P1. In RR, at time 3 the queue is P2, P3, P1 because new arrivals join before the preempted P1.
The drill data is P1 (arrival 0, burst 6), P2 (2, 2), P3 (3, 8), P4 (5, 3) and P5 (6, 4). Solve all four algorithms by hand first. Expected average waiting times: FCFS 6.60, SJF 4.80, SRTF 4.40 and RR 7.00.
Round Robin rule used here: a process arriving at the moment a quantum ends joins the queue before the preempted process. Revise: FCFS and SJF (opens in a new tab) | Round Robin and priority (opens in a new tab)
Predict the output
Check one number
Use the drill data for a quick check of the FCFS answer.
What total waiting time does FCFS give? (The average is the total divided by 5.)
Page-replacement numericals drill
Compulsory miss is a page fault on the first touch of a page; the first n distinct pages always fault, whatever the replacement algorithm.
The program below prints the frames after every reference for FIFO, LRU and Optimal on the string 2, 3, 2, 1, 5, 2, 4, 5, 3, 2, 5, 2 with 3 frames, and marks every fault with F.
Example 2 · Checker: frames after every reference
refs = [2, 3, 2, 1, 5, 2, 4, 5, 3, 2, 5, 2]
def run(algo, frames, show=False): mem = [] # FIFO: load order; LRU: use order faults, line = 0, algo + ":" for i, page in enumerate(refs): hit = page in mem if hit and algo == "LRU": mem.remove(page) mem.append(page) elif not hit: faults += 1 if len(mem) == frames: victim = 0 if algo == "OPT": rest = refs[i + 1:] next_use = lambda p: rest.index(p) if p in rest else len(refs) victim = max(range(len(mem)), key=lambda k: next_use(mem[k])) del mem[victim] mem.append(page) line += " " + ("." if hit else "F") if show: print(f"{line} -> {faults} faults") return faults
print("refs: 2 3 2 1 5 2 4 5 3 2 5 2 (F = fault, . = hit), 3 frames")for algo in ("FIFO", "LRU", "OPT"): run(algo, 3, show=True)print(f"4 frames: FIFO {run('FIFO', 4)}, LRU {run('LRU', 4)}, OPT {run('OPT', 4)}")refs: 2 3 2 1 5 2 4 5 3 2 5 2 (F = fault, . = hit), 3 frames FIFO: F F . F F F F . F . F F -> 9 faults LRU: F F . F F . F . F F . . -> 7 faults OPT: F F . F F . F . . F . . -> 6 faults 4 frames: FIFO 6, LRU 6, OPT 5
What this code does
- Each line marks every reference as a fault (F) or hit (.), so you can find the exact reference where your table went wrong.
- One list serves all three: FIFO keeps load order, LRU moves a page to the end on a hit, and OPT chooses the victim by next use. The OPT code puts the new page at the end, which does not change the count.
Expected faults with 3 frames: FIFO 9, LRU 7 and Optimal 6. With 4 frames: FIFO 6, LRU 6 and Optimal 5. Check each table with faults + hits = 12.
Optimal can never have more faults than the others on the same string. LRU can occasionally be worse than FIFO on an odd string, so do not assume an order between those two. Revise: Virtual memory and page replacement (opens in a new tab)
Find the bug
Find the slip in the working
Each hand working has one wrong line. Click it.
LRU with 3 frames on the string 2, 3, 2, 1, 5.
Round 1 of 2Deadlock scenario analysis
Need is the number of units of each resource that a process may still request: Max minus Allocation.
The program below runs Banker's algorithm on a college print-server scenario with scanners, printers and plotters, finds a safe sequence and tests two new requests.
Example 3 · Banker's check for the print-server scenario
alloc = [[1, 0, 1], [2, 1, 0], [0, 1, 1], [1, 0, 0]]maximum = [[3, 2, 2], [2, 2, 1], [1, 3, 2], [2, 1, 1]]available = [1, 1, 1]
def safe(avail, al): work, done, seq = avail[:], set(), [] moved = True while moved: moved = False for i in range(4): need = [m - a for m, a in zip(maximum[i], al[i])] if i not in done and all(x <= w for x, w in zip(need, work)): work = [w + a for w, a in zip(work, al[i])] done.add(i) seq.append(f"P{i}") moved = True return seq if len(seq) == 4 else None
def request(p, req): av = available[:] al = [row[:] for row in alloc] for j in range(3): if req[j] > maximum[p][j] - alloc[p][j] or req[j] > av[j]: print(f"P{p} {req}: must wait") return av[j] -= req[j] al[p][j] += req[j] seq = safe(av, al) if seq is None: print(f"P{p} {req}: deny (unsafe), Available would be {av}") else: print(f"P{p} {req}: grant, sequence {', '.join(seq)}")
print("Safe sequence now:", ", ".join(safe(available, alloc)))request(3, [1, 0, 1])request(0, [1, 1, 0])request(0, [2, 0, 0])Safe sequence now: P1, P2, P3, P0 P3 [1, 0, 1]: grant, sequence P3, P1, P2, P0 P0 [1, 1, 0]: deny (unsafe), Available would be [0, 0, 1] P0 [2, 0, 0]: must wait
What this code does
safestores no Need array; it computes Max − Allocation on the fly, which is the same thing.- P0's request (1, 1, 0) fits in Available, but afterwards no process's Need fits in what is left, (0, 0, 1), so it is denied. P0's request (2, 0, 0) is within its Need but asks for 2 scanners when only 1 is free, so it must wait. Each request is tested on the starting state.
The scenario: resource types A (scanner), B (printer), C (plotter). Allocation: P0 (1, 0, 1), P1 (2, 1, 0), P2 (0, 1, 1), P3 (1, 0, 0). Max: P0 (3, 2, 2), P1 (2, 2, 1), P2 (1, 3, 2), P3 (2, 1, 1). Available: (1, 1, 1). Decide on the requests P3 (1, 0, 1) and P0 (1, 1, 0).
- Need = Max − Allocation: P0 (2, 2, 1), P1 (0, 1, 1), P2 (1, 2, 1), P3 (1, 1, 1).
- Scan for Need ≤ Available and add back the Allocation of each finisher.
- Scanning P0 to P3 each round gives the safe sequence P1, P2, P3, P0.
- For each request: check ≤ Need and ≤ Available, pretend to grant it, run the safety check.
Revise: Deadlock (opens in a new tab)
Predict the output
Need and the first test
Work with the print-server data.
Round 1 of 2
What is the Need of P0 (Max 3, 2, 2 and Allocation 1, 0, 1)?
Fixing wrong model answers
The text below shows five confident but wrong model answers, each followed by its correction.
Example 4 · Five wrong model answers, corrected
1. "Internal fragmentation is free memory split into small holes."2. "When I/O finishes, the process goes back to running."3. "An unsafe state means the system is deadlocked."4. "LRU can suffer from Belady's anomaly."5. "A semaphore and a mutex are the same; both have an owner."1. That is EXTERNAL fragmentation. Internal = unused space inside an allocated block (for example the end of the last page). 2. It goes to READY and waits for the scheduler. 3. Unsafe means deadlock MAY happen; the OS cannot guarantee completion. 4. Only FIFO (non-stack algorithms). LRU and OPT never get more faults with more frames. 5. A mutex has an owner (only the locker unlocks); a semaphore is a counter with no owner and can be used for signalling.
What this code does
- Each wrong answer has one word or idea out of place: external vs internal, running vs ready, may vs is, FIFO vs LRU, owner vs no owner.
- In an interview, say the corrected sentence fully instead of only "that is wrong".
Each wrong answer has one word or idea out of place: external vs internal, running vs ready, may vs is, FIFO vs LRU, owner vs no owner. In an interview, say the corrected sentence in full instead of only "that is wrong".
Read each statement slowly and find the one word that makes it wrong.
Find the bug
Weak spoken answers
Each spoken answer has one wrong sentence. Click it.
Answer to "Internal vs external fragmentation?"
Round 1 of 2What's next
You finished the preview of Operating Systems
Python Programming has 21 sections, 110 modules and 609 lessons. An account opens every lesson and saves your progress.
Next step
Check your understanding
12 quick questions