SHORTEST JOB SCHEDULING FIRST ALGORITHM

Shortest Job First (SJF)

• Best approach to minimize waiting time.
• Impossible to implement
• Processer should know in advance how much time process will take.

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.

Example:(non pre-emptive)

PROCESS           BURST TIME
P1 21
P2 3
P3 6
P4 2

In SJF shortest process  is first executed
Hence the GANTT chart will be

|------|--    |----------|----------------|
P4    P2 P3          P1
|-----|------|----------|---------------|
0 2        5 11                   32

Now the average time will be(0+2+5+11)/4=4.5ms

Example:(preemptive)
In Preemptive Shortest Job First Scheduling, jobs are put into ready queue as they arrive, but as a process with short burst time arrives, the existing process is preemptied.

process burst time arrival time
P1 21 0
P2 3 1
P3 6 2
P4 2 3

Hence the GANTT chart will be

|------------|------------|---------------|--------------|---------|---------|
P1            P2              P4             P2                  P3                 P1
|------------|-------------|----------|----------|------------|-------------|
0               1                   3              5               6              12                 32

The average waiting time will be=((5-3)+(6-2)+(21-1))/4=4.25ms

The average waiting time for Preemptive process is less than the both Non-preemptive and FCFS job scheduling.