CPU scheduling with worked FCFS, SJF and Round Robin numbers

Why scheduling exists

You have more runnable processes than CPU cores. The scheduler decides who runs next and for how long. Every few milliseconds a timer interrupt fires and the kernel may switch to a different process. That switch is a context switch: save the current registers, load the next process's registers.

Four numbers matter, and mixing them up costs marks.

• Burst time — how long a process needs the CPU.
• Waiting time — total time spent in the ready queue, not running.
• Turnaround time — completion time minus arrival time. Equals waiting time plus burst time.
• Response time — arrival to the first moment it runs. Matters for anything interactive.

Our four processes

All arrive at time 0, in this order.

Total CPU work is 24 units in every algorithm. Only the ordering changes.

FCFS — first come, first served

Run them in arrival order. Non-preemptive: once a process starts, it finishes.

Timeline: P1 runs 0 to 6, P2 runs 6 to 14, P3 runs 14 to 21, P4 runs 21 to 24.

Average waiting = (0 + 6 + 14 + 21) / 4 = 41 / 4 = 10.25 Average turnaround = (6 + 14 + 21 + 24) / 4 = 65 / 4 = 16.25

P4 needed 3 units and waited 21. That is the convoy effect: short jobs stuck behind a long one, like a scooter behind a loaded truck on a single-lane road. Here is the same sum in C, so you can change the numbers and check your homework.

#include <stdio.h>

int main(void) {
    int burst[] = {6, 8, 7, 3};
    int n = 4;
    int clock = 0, total_wait = 0, total_tat = 0;

    for (int i = 0; i < n; i++) {
        int wait = clock;
        clock += burst[i];
        total_wait += wait;
        total_tat  += clock;
        printf("P%d  burst=%d  wait=%2d  turnaround=%2d\n",
               i + 1, burst[i], wait, clock);
    }

    printf("avg wait = %.2f, avg turnaround = %.2f\n",
           (double)total_wait / n, (double)total_tat / n);
    return 0;
}

It prints an average wait of 10.25 and average turnaround of 16.25, matching the table.

SJF — shortest job first

Pick the shortest burst available. Still non-preemptive.

Order becomes P4 (3), P1 (6), P3 (7), P2 (8).

Timeline: P4 0 to 3, P1 3 to 9, P3 9 to 16, P2 16 to 24.

Average waiting = 28 / 4 = 7.00 Average turnaround = 52 / 4 = 13.00

SJF is provably optimal for average waiting time. No algorithm can beat 7.00 on this set.

Round Robin, quantum = 4

Preemptive. Each process runs at most 4 units, then goes to the back of the ready queue.

Trace it carefully. Initial queue: P1, P2, P3, P4.

• 0 to 4: P1 runs, 2 left, goes to back. Queue: P2, P3, P4, P1
• 4 to 8: P2 runs, 4 left, goes to back. Queue: P3, P4, P1, P2
• 8 to 12: P3 runs, 3 left, goes to back. Queue: P4, P1, P2, P3
• 12 to 15: P4 needs only 3, finishes at 15. Queue: P1, P2, P3
• 15 to 17: P1 needs only 2, finishes at 17. Queue: P2, P3
• 17 to 21: P2 needs 4, finishes at 21. Queue: P3
• 21 to 24: P3 needs 3, finishes at 24

Average waiting = 53 / 4 = 13.25 Average turnaround = 77 / 4 = 19.25

Round Robin looks worst on both averages. So why is it the basis of every real interactive scheduler?

Look at response time — arrival to first run. FCFS: 0, 6, 14, 21, average 10.25. Round Robin: 0, 4, 8, 12, average 6.00. Every process gets a slice early. On a desktop that is the difference between a responsive machine and a frozen one.

Choosing the quantum

Too large and Round Robin degenerates into FCFS — with quantum 10, every process here finishes in one turn. Too small and you spend all your time context switching: if a switch costs 10 microseconds and the quantum is 100, you burn 10 percent of the CPU on overhead alone.

One table, three different winners depending on what you measure. That is the real lesson of scheduling.