Scribd
Upload
6 views7 pages

SJF

Shortest Job First (SJF) scheduling selects the process with the smallest execution time to execute next, reducing average waiting time. The document provides scenarios with processes having the same and different arrival times, demonstrating average turnaround and waiting times. It also discusses the advantages and disadvantages of SJF scheduling, including its optimality in average turnaround time and potential for job starvation.

Uploaded by

Mathura Subhash
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
6 views7 pages

SJF

Shortest Job First (SJF) scheduling selects the process with the smallest execution time to execute next, reducing average waiting time. The document provides scenarios with processes having the same and different arrival times, demonstrating average turnaround and waiting times. It also discusses the advantages and disadvantages of SJF scheduling, including its optimality in average turnaround time and potential for job starvation.

Uploaded by

Mathura Subhash
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Shortest Job First (SJF) or Shortest Job Next (SJN) is a scheduling

process that selects the waiting process with the smallest


execution time to execute next. This scheduling method may or
may not be preemptive. Significantly reduces the average waiting
time for other processes waiting to be executed.

Scenario 1: Processes with Same Arrival Time


Example: Consider the following table of arrival time and burst
time for three processes P1, P2 and P3.

Process Burst Time Arrival Time

P1 6 ms 0 ms

P2 8 ms 0 ms

P3 5 ms 0 ms
Arrival Burst Turn
Time Time Completion Around Waiting
Process (AT) (BT) Time (CT) Time (TAT) Time (WT)

P1 0 6 11 11-0 = 11 11-6 = 5

P2 0 8 19 19-0 = 19 19-8 = 11

P3 0 5 5 5-0 = 5 5-5 = 0

• Average Turn around time = (11 + 19 + 5)/3 = 11.6 ms


• Average waiting time = (5 + 0 + 11 )/3 = 16/3 = 5.33 ms
Scenario 2: Processes with Different Arrival Times
Consider the following table of arrival time and burst time for
three processes P1, P2 and P3.

Process Burst Time Arrival Time

P1 6 ms 0 ms

P2 3 ms 1 ms

P3 7 ms 2 ms

Arrival Burst Turn Waiting


Time Time Completion Around Time
Process (AT) (BT) Time (CT) Time (TAT) (WT)

P1 0 6 9 9-0 = 9 9-6 = 3

P2 1 3 4 4-1 = 3 3-3 = 0

P3 2 7 16 16-2 = 14 14-7 = 7
• Average Turn around time = (9 + 14 + 3)/3 = 8.6 ms
• Average waiting time = (3 + 0 + 7 )/3 = 10/3 = 3.33 ms
Advantages of SJF Scheduling
• SJF is better than the First come first serve(FCFS) algorithm
as it reduces the average waiting time.
• SJF is generally used for long term scheduling.
• It is suitable for the jobs running in batches, where run
times are already known.
• SJF is probably optimal in terms of average Turn Around
Time (TAT).
Disadvantages of SJF Scheduling
• SJF may cause very long turn-around times or starvation.
• In SJF job completion time must be known earlier.
• Many times it becomes complicated to predict the length
of the upcoming CPU request.
Scenario 3: Consider the following table of arrival time and burst
time for three processes P1, P2 and P3.

Process Burst Time Arrival Time

P1 6 ms 0 ms

P2 8 ms 2 ms

P3 3 ms 4 ms
Arrival Burst Turn Waiting
Time Time Completion Around Time
Process (AT) (BT) Time (CT) Time (TAT) (WT)

P1 0 6 6 6-0 = 6 6-6 = 0

P2 2 8 17 17-2 = 15 15-8 = 7

P3 4 3 9 9-4 = 5 5-3 = 2

• Average Turn around time = (6 + 15 + 5)/3 = 8.6 ms


• Average waiting time = ( 2 + 0 + 7 )/3 = 9/3 = 3 ms
Example of Non-Preemptive Priority Scheduling:
Consider the following table of arrival time and burst time
for three processes P1, P2 and P3:
• Note: Lower number represents higher priority.

Arrival
Process Time Burst Time Priority

P1 0 4 2

P2 1 2 1

P3 2 6 3

Turnarou Waiting
Arrival Burst Completi nd Time Time (TAT -
Process Time Time on Time (CT - AT) BT)

P1 0 4 4 4 0

P2 1 2 6 5 3

P3 2 6 12 10 4

• Average Turnaround Time = 6.33


• Average Waiting Time = 2.33

You might also like