SJF Scheduling | SRTF | CPU Scheduling

PRACTICE PROBLEMS BASED ON SJF SCHEDULING-

Problem-01:

Consider the set of 5 processes whose arrival time and burst time are given below-

If the CPU scheduling policy is SJF non-preemptive, calculate the average waiting time and average turn around time.

Solution-

Gantt Chart-

• Turn Around time = Exit time – Arrival time
• Waiting time = Turn Around time – Burst time

• Average Turn Around time = (4 + 15 + 5 + 6 + 10) / 5 = 40 / 5 = 8 unit
• Average waiting time = (3 + 11 + 3 + 0 + 7) / 5 = 24 / 5 = 4.8 unit

Problem-02:

Consider the set of 5 processes whose arrival time and burst time are given below-

If the CPU scheduling policy is SJF preemptive, calculate the average waiting time and average turn around time.

Solution-

Gantt Chart-

• Turn Around time = Exit time – Arrival time
• Waiting time = Turn Around time – Burst time

• Average Turn Around time = (1 + 5 + 4 + 16 + 9) / 5 = 35 / 5 = 7 unit
• Average waiting time = (0 + 1 + 2 + 10 + 6) / 5 = 19 / 5 = 3.8 unit

Problem-03:

Consider the set of 6 processes whose arrival time and burst time are given below-

If the CPU scheduling policy is shortest remaining time first, calculate the average waiting time and average turn around time.

Solution-

Gantt Chart-

• Turn Around time = Exit time – Arrival time
• Waiting time = Turn Around time – Burst time

• Average Turn Around time = (19 + 12 + 4 + 1 + 5 + 2) / 6 = 43 / 6 = 7.17 unit
• Average waiting time = (12 + 7 + 1 + 0 + 3 + 1) / 6 = 24 / 6 = 4 unit

Problem-04:

Consider the set of 3 processes whose arrival time and burst time are given below-

If the CPU scheduling policy is SRTF, calculate the average waiting time and average turn around time.

Solution-

Gantt Chart-

• Turn Around time = Exit time – Arrival time
• Waiting time = Turn Around time – Burst time

• Average Turn Around time = (13 + 4 + 20) / 3 = 37 / 3 = 12.33 unit
• Average waiting time = (4 + 0 + 11) / 3 = 15 / 3 = 5 unit

Problem-05:

Consider the set of 4 processes whose arrival time and burst time are given below-

If the CPU scheduling policy is SRTF, calculate the waiting time of process P2.

Solution-

Gantt Chart-

• Turn Around time = Exit time – Arrival time
• Waiting time = Turn Around time – Burst time

• Turn Around Time of process P2 = 55 – 15 = 40 unit
• Waiting time of process P2 = 40 – 25 = 15 unit

Implementation of Algorithm-

• Practically, the algorithm can not be implemented but theoretically it can be implemented.
• Among all the available processes, the process with smallest burst time has to be selected.
• Min heap is a suitable data structure where root element contains the process with least burst time.
• In min heap, each process will be added and deleted exactly once.
• Adding an element takes log(n) time and deleting an element takes log(n) time.
• Thus, for n processes, time complexity = n x 2log(n) = nlog(n)

To gain better understanding about SJF Scheduling,

Get more notes and other study material of Operating System.

Watch video lectures by visiting our YouTube channel LearnVidFun.

Shortest Job First or SJF Scheduling is a CPU Scheduling Algorithm that assigns CPU to the process with smallest burst time. Shortest Remaining Time First (SRTF) guarantees the minimal average waiting time and is optimal.