){kind=link}
·
FCFS is very simple – Just a FIFO queue,
like customers waiting in line at the bank or the post office or at a copying
machine.
·
Unfortunately, however, FCFS can yield
some very long average wait times, particularly if the first process to get
there takes a long time. For example, consider the following three processes:
|
Process |
Brust
Time |
|
P1 |
24 |
|
P2 |
3 |
|
P3 |
3 |
· In the first Gantt chart below, process P1 arrives first. The average waiting for the three processes is (0 + 24 + 27) / 3 = 17.0 ms.
·
In the second Gantt chart below, the same
three processes have an average wait time of (0 + 3 + 6) / 3 = 3.0 ms. The
total run time for three bursts is the same, but in the second case two of the
three finish much quicker, and the other process is only delayed by a short
amount.
.png)
.png)
· FCFS can also block the system in a busy dynamic system in another way, known as the convoy effect. When CPU intensive process blocks the CPU, a number of I/O-intensive processes can get backed up behind it, leaving the I/O devices idle, When the CPU hog finally relinquishes the CPU, then the I/O processes pass through the CPU quickly, leaving the CPU idle while everyone queues up for I/O and then the cycle repeats itself when the CPU intensive process gets back to the ready queue.
Shortest-Job-First Scheduling, SJF
·
The idea behind the SJF algorithm is to
pick the quickest fastest little job that needs to be done, get it out of the
way first, and pick the next smallest fastest job to do next.
·
Technically this algorithm picks a process
based on the next shortest CPU burst, not the overall process time.
·
For example, the Gantt chart below is a follow-on
the following CPU burst times, (and the assumption that all jobs arrive at the
same time).
|
Process |
Brust Time |
|
P1 |
6 |
|
P2 |
8 |
|
P3 |
7 |
|
P4 |
3 |
.png)
·
In the case above the average wait time is
(0 + 3 + 9 + 16) / 4 = 7.0 ms, (as opposed to 10.25 ms for FCFS for the same
processes).
·
SJF can be proven to be the fastest
scheduling algorithm, but it suffers from one important problem: How do you know
how long the next CPU burst is going to be?
Ø For
long-term batch jobs, this can be done based on the limits that users set for
their jobs when they submit them, which encourages them to set low limits but
risks their having to re-submit the job if they set the limit too low. However,
that does not work for short-term CUP scheduling on an interactive system.
Ø Another
option would be to statistically measure the run time characteristics of jobs,
particularly if the same tasks are run repeatedly and predictably. But once
again that really isn’t a viable option for short-term CPU scheduling in the
real world.
Ø A
more practical approach is to predict the length of the next
burst, based on some historical measurement of recent burst times for this
process. One simple, fast, and relatively accurate method is the exponential
average, which can be defined as follows
estimate
[i + 1] = alpha * burst [i] + (1.0 – alpha) * estimate [i]
Ø In
this scheme, the previous estimate contains the history of all previous times,
and alpha serves as a weighting factor for the relative importance of recent
data versus past history. If the alpha is 1.0, then past history is ignored, and
we assume the next burst will be the same length as the last burst. If alpha is
0.0, then all measured burst times are ignored, and we just assume a constant burst
time.
· SJF can be either preemptive or non-preemptive. Preemption occurs when a new one arrives in the ready queue that has a predicted burst time shorter than the time remaining in the process whose burst is currently on the CPU. Preemptive SJF is sometimes referred to as the shortest remaining time first scheduling.
· For example, the following Gantt chart is based on the following data:
|
Process |
Arrival Time |
Burst Time |
|
P1 |
0 |
8 |
|
P2 |
1 |
4 |
|
P3 |
2 |
9 |
|
P4 |
3 |
5 |
.png)
·
The average wait time in this case is ((5 –
3) + (10 – 1) + (17 – 2)) / 4 = 6.5 ms (
As opposed to 7.75 ms for non-preemptive SJF or 8.75 for FCFS).
Post a Comment