Page 87 - DCAP103_Principle of operating system

Principles of Operating Systems

Notes • Much better than previous case.
• Convoy effect short process behind long process

3 Shortest-Job-First (SJR) Scheduling
Associate with each process the length of its next CPU burst. Use these
lengths to schedule the process with the shortest time.
Two schemes:

1. non pre- emptive - once CPU given to the process it cannot be
preempted until completes its CPU burst.

2. preemptive - if a new process arrives with CPU burst length less
than remaining time of current executing process, preempt. This
scheme is know as the Shortest-Remaining-Time-First (SRTF).
SJF is optimal - gives minimum average waiting time for a given
set of processes.

Process Arrival Time Burst Time
P1 0.0 7
P2 2.0 4
P3 4.0 1
P4 5.0 4
SJF (non-preemptive)

P1 P3 P2 P4

0 7 8 12 16

Average waiting time = [0 +(8-2)+(7-4) +(12-5)] /4 =4
Example of Preemptive SJF

Process Arrival Time Burst Time
P1 0.0 7
P2 2.0 4
P3 4.0 1
P4 5.0 4

SJF (preemptive)

P1 P2 P3 P2 P4 P1

0 2 4 5 7 11 16

Average waiting time = (9 + 1 + 0 +2)/4 =3
Determining Length of Next CPU Burst

80 LOVELY PROFESSIONAL UNIVERSITY