Three processes arrive simultaneously: P1 (burst 30ms), P2 (burst 2ms), P3 (burst 4ms). Under FCFS in arrival order P1, P2, P3, what is P2's waiting time?
A0ms — P2 runs immediately after P1 without waiting
B30ms — P2 waits for P1 to complete
C2ms — P2 waits for its own burst time
D34ms — P2 waits for both P1 and P3 to complete
FCFS runs processes in arrival order to completion. P1 runs first for 30ms; P2 waits the entire time. This is the convoy effect: a long CPU-bound process (P1) blocks all the short processes behind it. Under SJF, P2 would run first (burst 2ms), P3 second (4ms), P1 last — P2's waiting time would be 0ms and the average waiting time drops dramatically. The convoy effect is FCFS's critical flaw.
Question 2 Multiple Choice
In a Multilevel Feedback Queue, a process that consistently uses its entire time quantum at the highest priority level will be:
APromoted to an even higher priority level as a reward for intensive CPU use
BDemoted to a lower priority queue, because full quantum usage signals CPU-bound behavior
CKept at the same level with a longer quantum to reduce context-switching overhead
DTerminated, since MLFQ assumes interactive processes should dominate
MLFQ interprets full quantum usage as evidence of CPU-bound behavior — the process is doing heavy computation and doesn't frequently yield for I/O. CPU-bound processes get lower priority because interactive responsiveness matters more for user-facing tasks. The process is demoted to a lower queue with a larger quantum. Conversely, a process that blocks early (suggesting interactive I/O-bound behavior) stays at high priority. MLFQ learns process behavior through observation rather than requiring advance knowledge of burst times.
Question 3 True / False
Shortest Job First is the best scheduling algorithm for real operating systems because it provably minimizes average waiting time.
TTrue
FFalse
Answer: False
SJF minimizes average waiting time theoretically, but it is impractical for real operating systems because burst times are unknown in advance. You cannot implement pure SJF without knowing how long each process will run — and processes don't declare their burst times. Real implementations use exponential averaging of past bursts to estimate future ones, making it an approximation. MLFQ is used by most real operating systems instead, because it adapts to observed behavior without any prediction. SJF is best understood as a theoretical benchmark, not a deployable algorithm.
Question 4 True / False
Making the Round Robin time quantum very small (e.g., 1ms) typically improves responsiveness because nearly every process gets the CPU more frequently.
TTrue
FFalse
Answer: False
A very small quantum does increase how frequently each process gets CPU turns, but it also dramatically increases context-switching overhead. Each context switch requires saving and restoring register state, flushing CPU caches, and updating OS data structures — all of which consume CPU time. If the quantum is smaller than context-switch overhead, the system spends more time switching than executing actual process code. The guideline is that the quantum should be large enough that roughly 80% of CPU bursts complete within a single quantum, balancing responsiveness against overhead.
Question 5 Short Answer
Explain why MLFQ does not need to know CPU burst times in advance, and how it nonetheless approximates the goal that SJF is trying to achieve.
Think about your answer, then reveal below.
Model answer: MLFQ infers burst behavior by observing how processes use their time quanta. A process that uses its full quantum is inferred to be CPU-bound (long bursts) and is demoted to a lower-priority queue with a larger quantum. A process that blocks before using its quantum is inferred to be I/O-bound or interactive (short bursts) and stays at high priority. This approximates SJF's goal — running short jobs first — without any advance knowledge. Interactive processes naturally self-select into high-priority queues by blocking frequently, while batch processes settle into lower queues, achieving similar scheduling order to what SJF would produce.
SJF requires omniscience about future burst times. MLFQ substitutes learning: past behavior predicts future behavior well enough for scheduling purposes. The key insight is that CPU-bound vs. I/O-bound behavior is observable at runtime, making SJF's impractical requirement achievable through adaptive classification.