Home › GATE CSE › computerscience › Operating Systems › Among non-preemptive CPU scheduling algorithms, …
Among non-preemptive CPU scheduling algorithms, which is provably optimal for average waiting time?
AFCFS, because it minimises overhead
BRound Robin with quantum equal to the maximum burst
CSJF (shortest job first); fewer total wait units
DPriority scheduling with all priorities equal
Answer & Solution
Correct answer: C. SJF (shortest job first); fewer total wait units
SJF picks the shortest available burst next. Intuition: completing a 2-unit job in 2 units adds 2 to one process's waiting time vs forcing a 10-unit job ahead, which would make the 2-unit job wait 10 units. Across all permutations, putting shortest first minimises the total wait. It is provably optimal among non-preemptive policies. FCFS, RR, and equal-priority schemes do not minimise waiting time.
Related questions
On a MULTI-CORE system, a SPIN LOCK is generallyDisabling INTERRUPTS as a way to implement mutual exclusion on a single-CPU system isA LIVELOCK differs from a DEADLOCK in thatSuppose thread A acquires lock L1, then thread B acquires lock L2. Now A tries to acquire Without atomic hardware support, building a correct mutual-exclusion lock for $N \geq 2$ tA CRITICAL SECTION isLinux's `pthread_mutex_lock()` is typically implemented as a HYBRID:What is the PRIMARY problem with using a SPIN LOCK on a SINGLE-CPU uniprocessor system (wi