SHORTEST JOB FIRST (SJF)

•         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-preemptive – 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).

Example of Non-Preemptive SJF

Process     Arrival Time  Burst Time

  P1                     0.0                      7

 P2                      2.0                      4

 P3                      4.0                      1

P4                      5.0                       4

•        SJF (non-preemptive)

•         Average waiting time = (0 + 6 + 3 + 7)/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)

Average waiting time = (9 + 1 + 0 +2)/4 - 3

More SJF Examples

• SJF non-preemptive     Proc   Arrives    Burst

                                                                P1         0               8

                                                               P2          1               4

                                                              P3           2               9

                                                             P4            3              5

And then preemptive

SJF non-preemptive  Proc   Arrives    Burst

                                         P1           1              2

                                        P2            0             7

                                       P3            2              7

                                      P4             5              3

                                     P5              6             1

And then preemptive

Determining Length of Next CPU Burst

SJF is optimal – gives minimum average waiting time for a given set of processes.

But we can only estimate the length of a CPU burst.

Can be done by using the length of previous CPU bursts, using exponential averaging.

Prediction of the Length of the Next CPU Burst

Examples of Exponential Averaging

a =0

tn+1 = tn

Recent history does not count.

a =1

 tn+1 = tn

Only the actual last CPU burst counts.

If we expand the formula, we get:

tn+1 = a tn+(1 - a) a tn -1 + …

            +(1 - a )j a tn -1 + …

            +(1 - a )n=1 tn t0

Since both a and (1 - a) are less than or equal to 1, each successive term has less weight than its predecessor.

Priority Scheduling

A priority number (integer) is associated with each process,

Internal, e.g., by resource needs

External, e.g., by user priority

The CPU is allocated to the process with the highest priority (smallest integer º highest priority).

Non-preemptive or Preemptive

Example     Proc       Arrival      Burst       Priority

                      P1               0              10                3

                      P2               1               1                 1

                      P3               2               2                 3

                      P4               4               1                 4

                      P5               8               5                 2

• SJF is a priority scheduling where priority is the predicted next CPU burst time.

• Problem º Starvation – low priority processes may never execute.

• Solution º Aging – as time progresses increase the priority of the process.

More Priority Examples

Proc  Arrival  Burst  Priority

P1  0  6  5

  P2  2  2  3

  P3  3  3  4

  P4  9  3  2

  P5  10  1  1

EDITED BY:
SITI NOORAINA MOHD JAMAL (F1075)