Information Technology Reference
In-Depth Information
FIFO minimizes overhead.
If tasks are variable in size, then FIFO can have very poor average response
time.
FIFO is optimal in terms of average response time if tasks are equal size.
Considering only the processor, SJF is optimal in terms of average response
time.
SJF is worst in terms of variance in response time.
Round Robin approximates SJF if tasks have different sizes.
Round Robin is the worst policy possible if tasks are of equal size.
Tasks that intermix processor and I/O benefit from SJF and can do poorly
under Round Robin.
Max-min fairness can improve response time for I/O-bound tasks.
By manipulating the assignment of tasks to priority queues, an MFQ
scheduler can achieve responsiveness, low overhead, and fairness.
In the rest of this chapter, we extend these ideas to multiprocessors, real-time
settings, energy-constrained environments, and overloaded conditions.
7.2
Multiprocessor scheduling
Today, most general-purpose computers are multiprocessors; even power-constrained
smartphones often have two or more processors. Physical constraints in circuit
design make it easier to add computational power by adding processors, or cores,
onto a single chip, rather than making individual processors faster. Many high-
end desktops and servers have multiple processing chips, each with multiple
cores, and each core with hyperthreading. This trend is likely to accelerate,
with systems of the future having dozens or perhaps hundreds of processors per
computer.
This poses two questions for operating system scheduling:
How do we make effective use of multiple cores for running sequential
tasks?
How do we adapt scheduling algorithms for parallel applications?
