Operating System - Shortest Job First(SJF) Scheduling

<<Previous

Next >>





  • SJF (Shortest Job First) allocates the CPU to the process which has the smallest CPU-bursts time.

  • SJF is also called Shortest Job Next(SJN) scheduling.

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

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

  • It can either be a preemptive or nonpreemptive.


    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

    To put it differently, process execution will be as follows. In the diagram below: 3, 4, and 20 are duration of each process.


    P3
    3P2
    4P1
    20
    P3
    3P2
    4P1
    20

    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 time
    0303

    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, Let us say, other processes arrive.
    • Algorithm will calculate the remaining time for all the processes.
    • Current or other process that arrived, whichever has least remaining time will execute next.
    • In a similar way, as more processes arrive, current process is paused and process with least remaining time will be executed.

    Gantt Chart:

    Above Gantt chart can also be represented as shown below


    P1
    1P2
    2P2
    2P3
    3P1
    19
    P1
    1P2
    2P2
    2P3
    3P1
    19

    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

    Advantages

    It helps achieve lesser average waiting time and lesser turnaround time.


    <<Previous

    Next >>







Operating System - Shortest Job First(SJF) Scheduling

<<Previous

Next >>





  • SJF (Shortest Job First) allocates the CPU to the process which has the smallest CPU-bursts time.

  • SJF is also called Shortest Job Next(SJN) scheduling.

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

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

  • It can either be a preemptive or nonpreemptive.


    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

    To put it differently, process execution will be as follows. In the diagram below: 3, 4, and 20 are duration of each process.


    P3
    3P2
    4P1
    20
    P3
    3P2
    4P1
    20

    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 time
    0303

    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, Let us say, other processes arrive.
    • Algorithm will calculate the remaining time for all the processes.
    • Current or other process that arrived, whichever has least remaining time will execute next.
    • In a similar way, as more processes arrive, current process is paused and process with least remaining time will be executed.

    Gantt Chart:

    Above Gantt chart can also be represented as shown below


    P1
    1P2
    2P2
    2P3
    3P1
    19
    P1
    1P2
    2P2
    2P3
    3P1
    19

    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

    Advantages

    It helps achieve lesser average waiting time and lesser turnaround time.


    <<Previous

    Next >>







Learn about Stack Data Structure

Learn about Heap Data Structure

Learn about Operating System

Learn AVL Tree

Learn Djikstra's Algorithm