Shortest Job First (SJF) scheduling is a non-preemptive discipline in which the
scheduler always schedules the shortest
of the arrived requests. Thus, a request remains pending until all shorter
request have been serviced. SJF favours short jobs at the expense of longer
ones.
SJF selects jobs for service in a manner that
ensures the next job will complete and leave the system as soon as possible.
This tend to reduce the number of waiting jobs, and also reduces the number of
jobs waiting behind large jobs. As a result, SJF can minimize the average waiting time of jobs as they pass through the
system. However, waiting times have a larger variance than FCFS, especially for
large jobs.
SJF is very difficult
to implement because it requires the precise knowledge of how long a
request will run and this information is not usually available in advance. The
best SJF can do is to depend on user estimates of run times. Relying on user
estimates leave the system open to abuse or manipulation, as user might try to
obtain good service by specifying low values for job execution times. Another
drawback of SJF scheduling is the poor service offered to long jobs. A steady
stream of short jobs arriving in the system can lead to starvation of a long
job.
For example, consider the following five processes
P1, P2, P3, P4, and P5 in the same order of arrival.
Process
|
CPU time or Burst time
(in ms)
|
P1
|
5
|
P2
|
15
|
P3
|
12
|
P4
|
25
|
P5
|
8
|
Gantt chart of the above processes in SJF is given
below; assume that all processes are arrived at time 0.
 |
| Gantt Chart of SJF |
Average
waiting time
Waiting
time for P1= 0
Waiting
time for P2= 25
Waiting
time for P3= 13
Waiting
time for P4= 40
Waiting
time for P5= 5
Average
waiting time= (0+25+13+40+5)/5
= 83/5
= 16.6 ms
We can simply calculate all other
values by using formula specified in FCFS scheduling
NEXT: Deadline Scheduling
Previous: FCFS scheduling
Index : Operating System
No comments:
Post a Comment