Shortest Job First Scheduling

<<Previous

Next >>





Shortest Job First Scheduling or SJF allocates the CPU to the process which has the smallest CPU-bursts time.

  • SJF is also called Shortest Job Next scheduling shortly referred to as SJN. Since Job can be called as a process, SJF is also referred to as Shortest Process Next or SPN scheduling

  • Suppose, if the CPU bursts of two processes are the same, then we use FCFS scheduling to break the tie.

  • SJF is used frequently in long term scheduling but it cannot be implemented in short-term scheduling.

  • SJF can either be a preemptive or nonpreemptive.

Advantages of SJF

Pros of using SJF:

  • Shortest jobs execute first and do not wait for time consuming jobs.
  • SJF helps achieve lesser average waiting time
  • More jobs complete faster since long running jobs are executed later
  • Helps achieve lesser turnaround time

  • SJF is simple and hence reduces overhead
  • SJF is most suitable for environments where estimated time for each job is available
  • SJF most sutiable for interactive processes which wait for a trigger and then execute

Limitations of SJF

Disadvantages/drawbacks/cons of using SJF:

  • Jobs or processes that need more time will wait and result in Job starvation or process starvation


Preemptive SJF scheduling

Preemptive SJF scheduling is sometime called Shortest remaining time first Scheduling.

How does it work?

Preemptive means a Job can be stopped midway to give CPU time to another Job. In Preemptive SJF, the job which has minimum remaining time will be executed next


For Processes That Arrive At The Same Time

For example, consider the set of processes that arrive at time 0 and CPU burst time given in millisecond:

ProcessCPU-Burst Time
P120
P24
P33

Following shows the Gantt Chart:

In the above diagram: 3,7 and 27 are finish times

Waiting Time and Turnaround time


Process
OrderArrival
Time
CPU
Burst
Waiting
Time
Turn
around
time
P1Job executed Third020727
P2Job executed Second0437
P3Job executed First because it takes less time0303
Average Waiting Time = (7+3+0)/3 = 3.333 ms
Average Turnaround Time = (27+7+3)/3 = 12.333 ms

For Processes That Arrive At Different Times

Let us say, the processes arrive in the different arrival time, and say, the process is served by using Preemptive SJF Scheduling.


ProcessArrival TimeCPU-Burst Time
P1020
P214
P333

Now, based on the processes which are in queue at the start:

  • Process which takes the least time will be executed first.
  • Once first process is progressing, other processes are checked.
  • Algorithm will calculate the remaining time for all the processes.
  • Either the current process or any other process that arrived, which has the least remaining time will execute next.
  • In a similar way, as more processes arrive, current process is paused and process with the least remaining time will be executed.
Gantt Chart:

Waiting Time and Turnaround time


Process
Arrival
Time
CPU
Burst
Start
Time
Waiting Time =
Start Time -
Arrival Time
Finish
Time
Turnaround
time=
Finish Time -
Arrival Time
P102088-1=72727-0=27
P21411-1=055-1=4
P33355-3=288-3=5
Average Waiting Time = (7+0+2)/3 = 3 ms
Average Turnaround Time = (27+4+5)/3 = 12 ms
Average Waiting Time
= (7+0+2)/3
= 3 ms
Average Turnaround Time
= (27+4+5)/3
= 12 ms

<<Previous

Next >>







Shortest Job First Scheduling

<<Previous

Next >>





Shortest Job First Scheduling or SJF allocates the CPU to the process which has the smallest CPU-bursts time.

  • SJF is also called Shortest Job Next scheduling shortly referred to as SJN. Since Job can be called as a process, SJF is also referred to as Shortest Process Next or SPN scheduling

  • Suppose, if the CPU bursts of two processes are the same, then we use FCFS scheduling to break the tie.

  • SJF is used frequently in long term scheduling but it cannot be implemented in short-term scheduling.

  • SJF can either be a preemptive or nonpreemptive.

Advantages of SJF

Pros of using SJF:

  • Shortest jobs execute first and do not wait for time consuming jobs.
  • SJF helps achieve lesser average waiting time
  • More jobs complete faster since long running jobs are executed later
  • Helps achieve lesser turnaround time

  • SJF is simple and hence reduces overhead
  • SJF is most suitable for environments where estimated time for each job is available
  • SJF most sutiable for interactive processes which wait for a trigger and then execute

Limitations of SJF

Disadvantages/drawbacks/cons of using SJF:

  • Jobs or processes that need more time will wait and result in Job starvation or process starvation


Preemptive SJF scheduling

Preemptive SJF scheduling is sometime called Shortest remaining time first Scheduling.

How does it work?

Preemptive means a Job can be stopped midway to give CPU time to another Job. In Preemptive SJF, the job which has minimum remaining time will be executed next


For Processes That Arrive At The Same Time

For example, consider the set of processes that arrive at time 0 and CPU burst time given in millisecond:

ProcessCPU-Burst Time
P120
P24
P33

Following shows the Gantt Chart:

In the above diagram: 3,7 and 27 are finish times

Waiting Time and Turnaround time


Process
OrderArrival
Time
CPU
Burst
Waiting
Time
Turn
around
time
P1Job executed Third020727
P2Job executed Second0437
P3Job executed First because it takes less time0303
Average Waiting Time = (7+3+0)/3 = 3.333 ms
Average Turnaround Time = (27+7+3)/3 = 12.333 ms

For Processes That Arrive At Different Times

Let us say, the processes arrive in the different arrival time, and say, the process is served by using Preemptive SJF Scheduling.


ProcessArrival TimeCPU-Burst Time
P1020
P214
P333

Now, based on the processes which are in queue at the start:

  • Process which takes the least time will be executed first.
  • Once first process is progressing, other processes are checked.
  • Algorithm will calculate the remaining time for all the processes.
  • Either the current process or any other process that arrived, which has the least remaining time will execute next.
  • In a similar way, as more processes arrive, current process is paused and process with the least remaining time will be executed.
Gantt Chart:

Waiting Time and Turnaround time


Process
Arrival
Time
CPU
Burst
Start
Time
Waiting Time =
Start Time -
Arrival Time
Finish
Time
Turnaround
time=
Finish Time -
Arrival Time
P102088-1=72727-0=27
P21411-1=055-1=4
P33355-3=288-3=5
Average Waiting Time = (7+0+2)/3 = 3 ms
Average Turnaround Time = (27+4+5)/3 = 12 ms
Average Waiting Time
= (7+0+2)/3
= 3 ms
Average Turnaround Time
= (27+4+5)/3
= 12 ms

<<Previous

Next >>







Learn about Stack Data Structure

Learn about Heap Data Structure

Learn about Operating System

Learn AVL Tree

Learn Djikstra's Algorithm