为什么内核需要那么复杂的调度算法，需要不断更新新算法

accessory

回复 11# fbwww

LKD 2ND EDITION, CHAPTER 4:

The Linux Scheduling Algorithm

In the previous sections, we discussed process scheduling theory in the abstract, with only occasional mention of how Linux applies a given concept to reality. With the foundation of scheduling now built, we can dive into Linux's very own process scheduler.

The Linux scheduler is defined in kernel/sched.c. The scheduler algorithm and supporting code went through a large rewrite early in the 2.5 kernel development series.

Consequently, the scheduler code is entirely new and unlike the scheduler in previous kernels. The new scheduler was designed to accomplish specific goals:

Implement fully O(1) scheduling. Every algorithm in the new scheduler completes in constant-time, regardless of the number of running processes.

Implement perfect SMP scalability. Each processor has its own locking and individual runqueue.

Implement improved SMP affinity. Attempt to group tasks to a specific CPU and continue to run them there. Only migrate tasks from one CPU to another to resolve imbalances in runqueue sizes.

Provide good interactive performance. Even during considerable system load, the system should react and schedule interactive tasks immediately.

Provide fairness. No process should find itself starved of timeslice for any reasonable amount of time. Likewise, no process should receive an unfairly high amount of timeslice.

Optimize for the common case of only one or two runnable processes, yet scale well to multiple processors, each with many processes.

The new scheduler accomplished these goals.