GATE CS 1995 Q2.6 — CPU Scheduling

An optimal scheduling sequence is one that minimizes the average turnaround time (TAT). Let's compare the two main non-preemptive scheduling strategies:

Strategy 1: Schedule immediately at $t = 0$ (No Idle Time)
Since Job 1 is the only job available at $t = 0$, it must run first. After Job 1 finishes at $t = 9$, we schedule the remaining jobs using Shortest Job First (SJF): Job 3, then Job 2.

• Execution sequence: $1 \rightarrow 3 \rightarrow 2$
• Completion times: $C_1 = 9$, $C_3 = 10$, $C_2 = 15$
• Turnaround times ($TAT = C - AT$): $TAT_1 = 9$, $TAT_3 = 9$, $TAT_2 = 14.4$
• Average TAT = $\frac{9 + 9 + 14.4}{3} = 10.8$ units
• CPU Idle Time = $0$ units

Strategy 2: Keep the CPU idle to run shorter jobs first (SJF with Idle Time)
If we keep the CPU idle from $t = 0$ to $t = 1.0$ to wait for all jobs to arrive, we can execute them in the optimal SJF order: Job 3, then Job 2, then Job 1.

• Execution sequence: $3 \rightarrow 2 \rightarrow 1$
• Completion times: $C_3 = 2$, $C_2 = 7$, $C_1 = 16$
• Turnaround times ($TAT = C - AT$): $TAT_3 = 2 - 1.0 = 1.0$, $TAT_2 = 7 - 0.6 = 6.4$, $TAT_1 = 16 - 0 = 16.0$
• Average TAT = $\frac{1.0 + 6.4 + 16.0}{3} = 7.8$ units
• CPU Idle Time = $1.0$ unit (from $t = 0$ to $t = 1.0$)

Since Strategy 2 yields a significantly lower average turnaround time ($7.8 < 10.8$), the optimal sequence is $\{3, 2, 1\}$ with $1$ unit of CPU idle time.