Page 83 - DCAP403_Operating System

Operating System

Notes Suppose that the processes arrive in the order: P , P , P . The Gantt chart for the schedule is:
1 2 3
P P P
1 2 3
0 24 27 30
Waiting time for P = 0; P = 24; P = 27
1 2 3
Average waiting time: (0 + 24 + 27)/3 = 17
Suppose that the processes arrive in the order P , P , P . The Gantt chart for the schedule is:
2 3 1
P P P
2 3 1
7
0 3 6 30
Waiting time for P = 6; P = 0; P = 3
1 2 3
Average waiting time: (6 + 0 + 3)/3 = 3

5.3.2 Shortest-Job-First (SJF)

The SJF algorithm takes processes that use the shortest CPU time first. Mathematically seen, and
corresponding to the experience, this is the ideal scheduling algorithm. I won’t give details in
here about the performance. It’s all to do about overhead and response time, actually: the system
will be fast when the scheduler doesn’t take much of the CPU time itself, and when interactive
processes react quickly (get a fast response). This system would be very good.
The overhead caused by the algorithm itself is huge, however. The scheduler would have top
implement some way to time the CPU usage of processes and predict it, or the user should tell
the scheduler how long a job (this is really a word that comes from very early computer design,
when Batch Job Operating Systems were used would take. So, it is impossible to implement this
algorithm without hurting performance very much.

Advantage

Minimizes average waiting times.

Disadvantages

1. How to determine length of next CPU burst?
2. Starvation of jobs with long CPU bursts.

Example:

Process Arrival Time Burst Time
P 1 0.0 7
P 2.0 4
2
P 4.0 1
3
P 5.0 4
4
1. SJF (non-preemptive)

76 LOVELY PROFESSIONAL UNIVERSITY