Program for Shortest Job First (or SJF) CPU Scheduling

The problem, simply

A computer has one worker, the CPU. Jobs arrive at different times, and each job needs a known amount of CPU time, called its burst. Once a job starts, it runs to the end.

Shortest Job First says: whenever the CPU is free, start the shortest job that has already arrived. For each job, work out its waiting time (start minus arrival) and its turnaround time (finish minus arrival). Give back the averages.

A story to remember it

Picture it

Examples

Way 1: the simple way

Act it out. Keep a clock. Each time the CPU is free, look at every job that has not run yet, and among those that have arrived, pick the one with the smallest burst. If none has arrived, move the clock to the next arrival.

class Solution {
    // jobs[i] = {arrival, burst}; returns {average wait, average turnaround}
    public double[] sjf(int[][] jobs) {
        int n = jobs.length;
        boolean[] done = new boolean[n];
        long time = 0, totalWait = 0, totalTurn = 0;
        for (int finished = 0; finished < n; ) {
            int pick = -1, nextArrival = Integer.MAX_VALUE;
            for (int i = 0; i < n; i++) {
                if (done[i]) continue;
                if (jobs[i][0] <= time) {
                    if (pick == -1 || jobs[i][1] < jobs[pick][1]
                            || (jobs[i][1] == jobs[pick][1] && jobs[i][0] < jobs[pick][0])) pick = i;
                } else {
                    nextArrival = Math.min(nextArrival, jobs[i][0]);
                }
            }
            if (pick == -1) { time = nextArrival; continue; }   // nobody here yet
            totalWait += time - jobs[pick][0];
            time += jobs[pick][1];
            totalTurn += time - jobs[pick][0];
            done[pick] = true;
            finished++;
        }
        return new double[]{(double) totalWait / n, (double) totalTurn / n};
    }
}

How long it takes: each of the n picks scans all n jobs, O(n^2). Extra room: the done flags, O(n).

Way 2: the clever way

Two things make it faster. Sort the jobs by arrival once, so you can add new arrivals with one pointer. Keep the jobs that are waiting in a min-heap ordered by burst, so the shortest waiting job is always on top.

1. Sort job numbers by arrival time. next points at the first job that has not arrived.
2. Loop: push every job with arrival <= time into the heap.
3. If the heap is empty, the CPU is idle. Jump the clock to the next arrival.
4. Otherwise pop the shortest job, add time - arrival to the waiting total, move the clock by its burst, and add time - arrival to the turnaround total.

The line on the ruler is the clock.

import java.util.*;

class Solution {
    // jobs[i] = {arrival, burst}; returns {average wait, average turnaround}
    public double[] sjf(int[][] jobs) {
        int n = jobs.length;
        Integer[] order = new Integer[n];
        for (int i = 0; i < n; i++) order[i] = i;
        Arrays.sort(order, (a, b) -> Integer.compare(jobs[a][0], jobs[b][0]));   // by arrival
        PriorityQueue<Integer> waiting = new PriorityQueue<>((a, b) ->
            jobs[a][1] != jobs[b][1] ? Integer.compare(jobs[a][1], jobs[b][1])    // shortest burst first
                                     : Integer.compare(jobs[a][0], jobs[b][0]));  // then earliest arrival
        long time = 0, totalWait = 0, totalTurn = 0;
        int next = 0, finished = 0;
        while (finished < n) {
            while (next < n && jobs[order[next]][0] <= time) waiting.add(order[next++]);
            if (waiting.isEmpty()) {                 // CPU idle: jump to the next arrival
                time = jobs[order[next]][0];
                continue;
            }
            int j = waiting.poll();
            totalWait += time - jobs[j][0];
            time += jobs[j][1];
            totalTurn += time - jobs[j][0];
            finished++;
        }
        return new double[]{(double) totalWait / n, (double) totalTurn / n};
    }
}

How long it takes: sorting is O(n log n), and every job enters and leaves the heap once at O(log n) each. Total O(n log n). Extra room: the order array and the heap, O(n).

Watch out for

• When nobody is waiting, jump the clock to the next arrival. Moving it by 1 each time is slow when the gaps are big.
• Decide the tie rule. Equal bursts usually go by earlier arrival, which is first come, first served.
• Waiting time is start minus arrival, and turnaround is finish minus arrival. Turnaround equals waiting plus burst.
• Return averages as double, and add the totals in long.

What interviewers ask next

• Why does shortest first give the smallest average wait when everyone arrives together? Each job's burst is added to the wait of every job after it. Putting short jobs first means short numbers get added many times. Swapping any long job in front of a shorter one makes the total worse.
• What is the preemptive version? Shortest Remaining Time First: when a new job arrives with less work left than the running job, it takes over the CPU. Use the same heap, keyed by remaining time, and stop at every arrival.
• What is the weakness of SJF? A long job can starve if short jobs keep arriving. Aging, which slowly raises the priority of jobs that wait a long time, fixes it. Also, real systems do not know bursts in advance and have to guess them.
• LeetCode "Single-Threaded CPU" is this problem, returning the order of jobs instead of the averages.

Remember this

Grown-up words: the worker is the CPU, the length of a job is its burst time, the waiting pile is the ready queue built as a min-heap, picking without interrupting is non-preemptive scheduling, and the timeline is a Gantt chart.