Information Technology Reference
In-Depth Information
it requires tasks to be maintained on a priority queue. For some server environ-
ments, there can be tens or even hundreds of thousands of scheduling decisions
to be made every second. To reduce the computational overhead of the sched-
uler, most commercial operating systems use a somewhat different algorithm,
to the same goal, which we describe next.
7.1.5
Case Study: Multi-level Feedback
Most commercial operating systems, including Windows, MacOS, and Linux,
use a scheduling algorithm called Multi-level Feedback Queue (MFQ). MFQ is
Denition: Multi-level
Feedback Queue (MFQ)
designed to achieve several simultaneous goals:
Responsiveness. Run short tasks quickly, as in SJF.
Low Overhead. Minimize the number of preemptions, as in FIFO, and
minimize the time spent making scheduling decisions.
Starvation-Freedom.
All tasks should make progress, as in Round
Robin.
Background Tasks. Defer system maintenance tasks, such as disk de-
fragmentation, so they do not interfere with user work.
Fairness. Assign (non-background) processes approximately their max-
min fair share of the processor.
MFQ is an extension of Round Robin. Instead of only a single queue, MFQ
has multiple Round Robin queues, each with a different priority level and time
quantum. Tasks at a higher priority level preempt lower priority tasks, while
tasks at the same level are scheduled in Round Robin fashion. Further, higher
priority levels have shorter time quanta than lower levels.
Tasks are moved between priority levels to favor short tasks over long ones.
A new task enters at the top priority level. Every time the task uses up its time
quantum, it drops a level; every time the task yields the processor because it is
waiting on I/O, it stays at the same level (or is bumped up a level); and if the
task completes it leaves the system.
Figure 7.5 illustrates the operation of an MFQ with four levels. A new
compute-bound task will start as high priority, but it will quickly exhaust its
time-quantum and fall to the next lower priority, and then the next. Thus,
an I/O-bound task needing only a modest amount of computing will almost
always be scheduled quickly, keeping the disk busy. Compute-bound tasks run
with a long time-quantum to minimize switching overhead while still sharing
the processor.
So far, the algorithm we've described does not achieve starvation freedom or
max-min fairness. If there are too many I/O-bound tasks, the compute-bound
 
Search WWH ::




Custom Search