(i). Shortest-Job-First (SJF)

The SJF scheduler is exactly like FCFS except that instead of choosing the job at the front of the queue, it will always choose the shortest job (i.e. the job that takes the least time) available. Use a sorted list to order the processes from longest to shortest. When adding a new process/task, need to figure out where in the list to insert it. Our API will need:

sorted_list  sl                                         // sorted list data structure
add_task(proc, expected_runtime) {         // method to add a process to the list.
    sl.insert(proc, proc.runtime);               // input the process’s expected runtime
}                                                        // to indicate where it should be inserted.

reschedule()  {                                     // method to remove the shortest job from
    return sl.remove_head();                    // the list and run it.
}

For the jobs A, B, C and D ,The SJF Gantt Chart would be:

The SJF achieves better performance than FCFS. However, unlike FCFS, there is the potential for starvation in SJF. Starvation occurs when a large process never gets to run because shorter jobs keep entering the queue.

In addition, SJF needs to know how long a process is going to run (i.e. it needs to predict the future). This runtime estimation feature may be hard to implement, and thus SJF is not a widely used scheduling scheme.