Information Technology Reference
In-Depth Information
compute-bound processes are barely affected at all. That hardly seems fair!
While there are many possible definitions of fairness, a particularly useful
one for operating system resource allocation is called max-min fairness . Max-
Definition: max-min
fairness
min fairness iteratively maximizes the minimum allocation given to a particular
process (user, application or thread) until all resources are assigned. If all
processes are compute-bound, we maximize the minimum by giving each process
exactly the same share of the processor.
The behavior of max-min fairness is more interesting if some processes cannot
use their entire share, for example, because they are short-running or are I/O-
bound. If so, we give those processes their entire request and redistribute the
unused portion to the remaining processes. Some of the processes receiving
the extra portion may not be able to use all of their revised share, and so we
must iterate, redistributing any unused portion. At some point, if the smallest
remaining request cannot be fully satisfied, we divide the remainder equally
among all remaining processes.
Consider the example in the previous section. The disk-bound process
needed only 10% of the processor to keep busy, but Round Robin only gave
it 0.5% of the processor, and each of the two compute-bound processes received
nearly 50% of the processor. Max-min fairness would assign 10% of the proces-
sor to the I/O-bound processes, and split the remainder equally among the two
compute-bound processes, with 45% each.
A hypothetical but completely impractical implementation of max-min would
be to give the processor at each instant to whichever process has received the
least portion of the processor. In the example above, the disk-bound task would
always be instantly scheduled, preempting the compute-bound processes. How-
ever, we've already seen why this wouldn't work well. With two equally long
tasks, as soon as we execute one instruction in one task, it would have received
more resources than the other one, so to preserve \fairness" we would need to
instantly switch to the next task.
We can approximate a max-min fair allocation by relaxing this constraint |
to allow a process to get ahead of its fair allocation by one time quantum. Every
time the scheduler needs to make a choice, it chooses the task for the process
with the least accumulated time on the processor. If a new process arrives on
the queue with much less accumulated time, such as the disk-bound task, it
will preempt the process, but otherwise the current process will complete its
quantum. Tasks may get up to one time quantum more than their fair share,
but over the long term the allocation will even out.
The algorithm we just described was originally defined for network, and
not processor, scheduling. If we share a link between a browser request and
a long download, we will get reasonable responsiveness for the browser if we
have approximately fair allocation | the browser needs few resources, and so
its packets will always be scheduled ahead of the packets from the download.
Even this approximation, though, can be computationally expensive, since
