The O(1) scheduler was announced
on January 4th 2002 and was subsequently accepted into the official
v2.5 Linux kernel tree. It has also found its way into various
2.4-based distributions, such as Red Hat Advanced
Server/Workstation. The O(1) scheduler has many good features but also
some down-sides. Its advantages, such as good performance with large
number of tasks and/or CPUs are well understood and widely known.
Unfortunately, the same does not appear to be the hold for the
disadvantages of the O(1) scheduler. Since the 2.6 kernel will be
released soon, we feel it is high time to at least document some of
the performance oddities exhibited by the O(1) scheduler. Some of
these oddities will probably turn out to be implementation bugs (and
hence easily fixable), some of them seem to be more fundamental design
flaws, and others still may be simply be "features" that applications
will have to learn to live with. In any case, we hope that this web
page will encourage discussion among the Linux kernel and user
communities and hope that at least some of the more severe issues can
be fixed or mitigated before v2.6 is released.
Before diving into describing some of the performance oddities, it
is worthwhile to point out some of the strengths of the O(1)
scheduler. Unless we keep these in mind, we risk "throwing out the
baby with the bath-water" when trying to fix the performance oddities.
Good features of the O(1) scheduler
- Lean and mean (low overhead).
- Scales well with the number of tasks (O(1)).
- Scales well with the number of processors (O(1) for scheduling,
O(N) for balancing).
- Strong affinity avoids tasks bouncing needlessly between CPUs.
- Initial affinity makes it likely that request/response-type
tasks stay on the same CPU (i.e., good for LMbench lat_udp
et al)
Some problems with the O(1) scheduler
If you have additions, updates, or any other comments (positive or
negative), please send them via e-mail to davidm@hpl.hp.com.
|
Printable version
