Operating Systems | Scheduling Algorithms : SJF


Shortest Job First(SJF)

SJF algorithm schedules the shortest job(low burst time) available on main memory at the time of context switching in ready state . It can be either preemptive or non-preemptive depending on the nature of scheduler.

Since the SJF select the job which is shorted among available jobs on main memory, Non-preemptive SJF algorithm will have larger waiting time if a job with longer burst time get scheduled first. In short SJF is also vulnerable to Convoy Effect

To find shortest process among min-heap would be the best data structure to be used

Example : Consider the following table of processes and calculate completion time, turn around time and waiting time using SJF algorithm with the following assumptions.

  • No preemption.
  • No I/O request will be there from any process.
  • Arrival time is relative to CPU on time.

Process Number AT BT
1 0 3
2 2 2
3 2 4
4 4 2

Advantages:

  • Throughput is the degree of processes completed per unit interval of time. SJF has maximum throughput.
  • SJF algorithm provides minimum turnaround time and waiting time.

Disadvantages:

  • Starvation for longer jobs.
  • It is not implementable since burst time of a process is not predefined.

There are various methods to prediction of unknown burst time for the implementation of an algorithm which is very close in functionalities with SJF

  1. Static Prediction Methods
    • Prediction based on process size similarity

      The method assumes, that the process with nearly equal memory sizes can have almost equal processing time.

    • Prediction based on type of process

      Scheduler, dispatcher... are a process of Operating system doing core functionalities of the system and which will have a fast processing time.

      Custom processes where user's need plays a major role can be of type interactive where real time interaction with user is mandatory (example: Gaming), background process which need less interaction from user or foreground process.

      Normally Operating system's process are the fastest among all. Interactive process are faster than normal foreground processes and background processes are slower than that of foreground process. So it is possible to predict the burst time on a relative basis with reference to type of process.

  2. Dynamic Prediction Methods
    • Simple Averaging

      The time taken for the n+1th process is assumed as the average processing time of n process which are already completed the execution.

    • Exponential Averaging

      Prediction of time taken for current process is taken as weighted average of actual time and predicted time of previous process.

      Softening factor is the fractional weightage given to the processing time of the previous process.

Comments