SJF Scheduling | SRTF | CPU Scheduling

 In SJF Scheduling,

• Out of all the available processes, CPU is assigned to the process having smallest burst time.
• In case of a tie, it is broken by FCFS Scheduling. 

 

• SJF Scheduling can be used in both preemptive and non-preemptive mode.
• Preemptive mode of Shortest Job First is called as Shortest Remaining Time First (SRTF).

 

Advantages-

 

• SRTF is optimal and guarantees the minimum average waiting time.
• It provides a standard for other algorithms since no other algorithm performs better than it.

 

Disadvantages-

 

• It can not be implemented practically since burst time of the processes can not be known in advance.
• It leads to starvation for processes with larger burst time.
• Priorities can not be set for the processes.
• Processes with larger burst time have poor response time.

 

PRACTICE PROBLEMS BASED ON SJF SCHEDULING-

 

Problem-01:

 

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

 

Process Id	Arrival time	Burst time
P1	3	1
P2	1	4
P3	4	2
P4	0	6
P5	2	3

 

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

Solution-

 

Gantt Chart-

 

 Now, we know-

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

Process Id	Exit time	Turn Around time	Waiting time
P1	7	7 – 3 = 4	4 – 1 = 3
P2	16	16 – 1 = 15	15 – 4 = 11
P3	9	9 – 4 = 5	5 – 2 = 3
P4	6	6 – 0 = 6	6 – 6 = 0
P5	12	12 – 2 = 10	10 – 3 = 7

 

Now,

• 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-

 

Process Id	Arrival time	Burst time
P1	3	1
P2	1	4
P3	4	2
P4	0	6
P5	2	3

 

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

 

Solution-

 

Gantt Chart-

 

 

Now, we know-

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

 

Process Id	Exit time	Turn Around time	Waiting time
P1	4	4 – 3 = 1	1 – 1 = 0
P2	6	6 – 1 = 5	5 – 4 = 1
P3	8	8 – 4 = 4	4 – 2 = 2
P4	16	16 – 0 = 16	16 – 6 = 10
P5	11	11 – 2 = 9	9 – 3 = 6

 

Now,

• 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-

 

Process Id	Arrival time	Burst time
P1	0	7
P2	1	5
P3	2	3
P4	3	1
P5	4	2
P6	5	1

 

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

 

Solution-

 

Gantt Chart-

 

 

Now, we know-

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

 

Process Id	Exit time	Turn Around time	Waiting time
P1	19	19 – 0 = 19	19 – 7 = 12
P2	13	13 – 1 = 12	12 – 5 = 7
P3	6	6 – 2 = 4	4 – 3 = 1
P4	4	4 – 3 = 1	1 – 1 = 0
P5	9	9 – 4 = 5	5 – 2 = 3
P6	7	7 – 5 = 2	2 – 1 = 1

 

Now,

• 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-

 

Process Id	Arrival time	Burst time
P1	0	9
P2	1	4
P3	2	9

 

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

 

Solution-

 

Gantt Chart-

 

 

Now, we know-

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

 

Process Id	Exit time	Turn Around time	Waiting time
P1	13	13 – 0 = 13	13 – 9 = 4
P2	5	5 – 1 = 4	4 – 4 = 0
P3	22	22- 2 = 20	20 – 9 = 11

 

Now,

• 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-

 

Process Id	Arrival time	Burst time
P1	0	20
P2	15	25
P3	30	10
P4	45	15

 

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

 

Solution-

 

Gantt Chart-

 

 

Now, we know-

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

Thus,

• 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,