Quiz · Hard
Multi-step problems on SRTF, effective access time, page tables, disk scheduling, the Banker's algorithm and synchronization.
SRTF (preemptive SJF): P1 arrives at 0 with burst 8, P2 at 1 with 4, P3 at 2 with 9, P4 at 3 with 5. What is the average waiting time?
5.5 ms
7.75 ms
6.5 ms
8.5 ms
Schedule: P1 0–1, P2 1–5, P4 5–10, P1 10–17, P3 17–26. Waits: P1 = 9, P2 = 0, P3 = 15, P4 = 2, average 26/4 = 6.5. The non-preemptive SJF average is 7.75.
A process predicts its next CPU burst with exponential averaging, α = 0.5, previous prediction τ = 10 ms and the last actual burst t = 6 ms. What is the next prediction?
8 ms
6 ms
10 ms
16 ms
τ_next = α·t + (1 − α)·τ = 0.5 × 6 + 0.5 × 10 = 8 ms.
A system has a TLB hit ratio of 80%, a TLB lookup of 20 ns and a memory access of 100 ns (single-level page table). What is the effective access time?
120 ns
150 ns
220 ns
140 ns
EAT = 0.8 × (20 + 100) + 0.2 × (20 + 100 + 100) = 96 + 44 = 140 ns.
Memory access takes 200 ns and a page fault takes 8 ms to service. To keep slowdown below 10% (EAT ≤ 220 ns), what is the maximum page-fault rate p, approximately?
p ≈ 2.5 × 10⁻³
p ≈ 2.5 × 10⁻⁶
p ≈ 0.1
p ≈ 0.025
EAT ≈ 200 + p × 8,000,000 ≤ 220 gives p ≤ 20 / 8,000,000 = 2.5 × 10⁻⁶: about one fault per 400,000 accesses.
A system has 32-bit virtual addresses, 4 KiB pages and 4-byte page-table entries. How large is a single-level page table for one process?
4 KiB
1 MiB
4 MiB
16 MiB
2²⁰ entries × 4 bytes = 4 MiB per process, which motivates multi-level page tables.
Using the common reference string 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 with 3 frames, which page-replacement ranking (fewest faults first) is correct?
OPT, LRU, FIFO
FIFO, LRU, OPT
LRU, OPT, FIFO
OPT, FIFO, LRU
OPT gives 9 faults, LRU 12 and FIFO 15. OPT is the unattainable lower bound that needs knowledge of the future.
Ext2-style inode: 12 direct pointers, one single, one double and one triple indirect pointer, 4 KiB blocks, 4-byte block pointers. Roughly what is the largest file addressable?
About 4 GiB
About 16 GiB
About 1 PiB
About 4 TiB
Direct 48 KiB + single 4 MiB + double 4 GiB + triple 4 TiB: about 4 TiB (the triple indirect term dominates).
Disk head at cylinder 53, requests 98, 183, 37, 122, 14, 124, 65, 67. What is the total head movement for FCFS?
236
640
412
699
45 + 85 + 146 + 85 + 108 + 110 + 59 + 2 = 640 cylinders. SSTF would need only 236.
Banker's algorithm: Available = (3,3,2). P1 has Max (3,2,2) and Allocation (2,0,0). Can P1's remaining need be granted immediately, and what does available become after P1 finishes?
No, need (1,2,2) exceeds available
Yes, then Available = (3,3,2)
Yes, then Available = (5,3,2)
Yes, then Available = (1,2,2)
Need = Max − Allocation = (1,2,2) ≤ (3,3,2). After P1 completes it releases its allocation: (3,3,2) + (2,0,0) = (5,3,2).
Which change breaks the circular-wait condition in a system with several locks?
Requiring all threads to acquire locks in one global order
Using larger locks
Adding more CPUs
Using spinlocks instead of mutexes
If every thread acquires locks in the same global order, a cycle in the wait-for graph cannot form.
In the dining philosophers diagram, which solution removes the possibility of deadlock?

Everyone picks up the left fork first
Add a second plate per philosopher
Let philosophers wait without a time limit
Allow at most four philosophers to sit at the table at once
With at most four philosophers competing for five forks, at least one can always get two forks. The classic left-fork-first rule is exactly what causes the deadlock. Image: bdesham and Belbury, CC BY 3.0, via Wikimedia Commons.
What problem does priority inheritance solve?
Starvation of low-priority processes in a scheduler
Unbounded priority inversion while a low-priority task holds a lock
Page thrashing
Race conditions on a counter
The lock holder temporarily runs at the priority of the highest-priority task waiting for the lock, so medium-priority tasks cannot preempt it indefinitely.
A counting semaphore is initialized to 2. Three threads call wait() and none has called signal() yet. How many threads are blocked?
0
2
1
3
The first two calls decrement the value to 0 and proceed. The third finds no free unit and blocks (in the classic definition the value goes to −1, whose magnitude is the number of waiters).
Which statement best describes copy-on-write after fork()?
Parent and child share pages marked read-only and a page is copied only when one writes to it
The child receives a full copy of memory immediately
The child cannot write to memory
The parent is suspended until the child ends
Copy-on-write makes fork() cheap, especially when the child calls exec() right away.
Which statement about a hard link and a symbolic link in Unix is correct?
A hard link can cross file systems; a symbolic link cannot
Both always point to a path string
Deleting the target removes a hard link
A hard link adds another directory entry for the same inode; a symbolic link stores a path
A hard link is another name for the same inode (link count increases). A symbolic link holds a path, so it can cross file systems and can dangle.
The microkernel diagram's dotted line separates kernel mode from user mode. Which components run in user mode?

The microkernel
The servers (such as file systems and drivers) and applications
Only the applications
Nothing; everything is in kernel mode
Servers run as ordinary user-space processes, which is the main difference from a monolithic kernel. Image: Golftheman, public domain, via Wikimedia Commons.