CSE Roadmap

Core tier · about 4 hours · 7 parts

Part 3 of 7 · 4 min read

SJF

In plain words: At a bank, the teller who serves the customer with a one-minute task first, before the one with a thirty-minute task, lowers the average wait of the whole line. The analogy stops in one place: a teller can ask each customer for the task length, and the scheduler cannot ask a process.

Shortest job first picks, among the ready processes, the one with the shortest next CPU burst. When it starts running, it runs to the end of that burst. This version is non-preemptive.

A short program traces both FCFS and SJF for the page 1 workload. Each pass picks one job and runs it to the end:

struct job { char name; int arrive, burst, start, finish, done; };

int main(int argc, char **argv) {
    int sjf = argc > 1 && strcmp(argv[1], "sjf") == 0;
    struct job j[4] = {{'A',0,5,0,0,0},{'B',1,3,0,0,0},{'C',2,8,0,0,0},{'D',3,2,0,0,0}};
    int t = 0, left = 4;
    while (left > 0) {
        int pick = -1;
        for (int i = 0; i < 4; i++) {
            if (j[i].done || j[i].arrive > t) continue;
            if (pick < 0) { pick = i; continue; }
            if (sjf ? j[i].burst < j[pick].burst : j[i].arrive < j[pick].arrive) pick = i;
        }
        if (pick < 0) { t++; continue; }          /* idle */
        t += j[pick].burst;  j[pick].done = 1;  left--;
        printf("%c runs to %d\n", j[pick].name, t);
    }
}

The full program also prints the start time and the two averages. Its output:

$ ./np                      $ ./np sjf
A runs  0 to  5             A runs  0 to  5
B runs  5 to  8             D runs  5 to  7
C runs  8 to 16             B runs  7 to 10
D runs 16 to 18             C runs 10 to 18
average turnaround 10.25    average turnaround 8.50
average waiting 5.75        average waiting 4.00

Trace SJF by hand. At time 0, only A has arrived, so A runs from 0 to 5. At time 5, B (3), C (8) and D (2) are ready, and D is the shortest. D runs from 5 to 7. Then B (3) beats C (8), and B runs from 7 to 10. C runs last, from 10 to 18.

Process Finish Turnaround Waiting Response
A 5 5 0 0
B 10 9 6 6
C 18 16 8 8
D 7 4 2 2

The averages are turnaround 8.50, waiting 4.00 and response 4.00, better than FCFS (10.25, 5.75, 5.75) on the same jobs.

This is not luck. Among non-preemptive policies, running the shortest ready job first gives the lowest average waiting time for a given set of jobs. The argument: if a long job runs just before a short one, swapping them lowers the short job's wait by the long job's length and raises the long job's wait by the short job's length, a net gain for the average. Repeated swaps lead to the shortest-first order.

Shortest job first

Shortest job first (SJF) is a scheduling policy that, whenever the processor is free, runs the ready process whose next CPU burst is shortest, without interrupting it, and that gives the least average waiting time of all non-preemptive policies.

Example: at time 5, with B (3), C (8) and D (2) ready, SJF runs D first, for an average waiting time of 4.00.

Check yourself: 1. At time 7 in the trace, which processes are ready, and which is chosen? 2. Why did C wait 8 units under SJF but only 6 under FCFS? 3. State the swap argument in one sentence.