Shortest-Job-First Scheduling, SJF
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
Proces
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
Can
only estimate the length.
Can
be done by using the length of previous CPU bursts,
using
exponential averaging.
Prediction of the Length of the Next CPU Burst
Pn+1 = a
tn +(1-a)Pn
This
formula defines an exponential average
Pn
stores the past history
tn
contents are most recent information
the
parameter “a “controls the relative weight of recent and past history of in
our prediction
If a =0
then Pn +1 =Pn
That is
prediction is constant
If a = 1
then Pn +1 = tn
Prediction is last cpu burst
Comments
Post a Comment