1. 概述
调度是计算机操作系统中一个重要的组成部分,它决定了在系统中运行的进程如何分配 CPU 时间。在 Linux 系统中,调度器的主要任务是通过选择合适的进程使系统能够高效地运行。
2. Linux 调度器
2.1 CFS(Completely Fair Scheduler)
CFS 是 Linux 内核中默认的调度器。它通过一个红黑树来维护系统中所有进程的运行队列,每个进程都有一个虚拟运行时间(virtual runtime)来衡量其应该获得 CPU 的权重。CFS 通过不断选择虚拟运行时间最小的进程来分配 CPU 时间,以实现公平的调度。
关键代码:
static struct sched_entity * pick_next_entity(struct cfs_rq *cfs_rq, struct sched_entity *curr)
{
struct sched_entity *se = NULL;
// 从红黑树中选择下一个实体
se = rb_entry(cfs_rq->rb_node, struct sched_entity, run_node);
return se;
}
CFS 的核心思想是尽量使所有进程都能获得公平的 CPU 时间,避免某个进程长期霸占 CPU 而导致其他进程被饿死的情况。
2.2 O(1) 调度器
O(1) 调度器是 Linux 内核早期版本所使用的调度算法。它通过使用一个优先级数组来维护进程队列,每个进程的优先级根据其运行时间和 I/O 等待时间进行动态调整。
关键代码:
static inline struct task_struct * __pick_next_task_rt(struct rq *rq)
{
struct task_struct *next_p = NULL;
// 遍历优先级数组,选择优先级最高的进程
next_p = __pick_next_task(rq);
return next_p;
}
O(1) 调度器的优势是在任何情况下都能够保证对实时进程的响应。然而,它无法提供像 CFS 那样公平的调度。
2.3 实时调度器
Linux 还提供了实时调度器(Real-time Scheduling),用于满足对实时性要求较高的应用程序。实时调度器根据进程的优先级和任务类型将进程分为实时进程和普通进程,并采用不同的调度算法。
3. 调度策略
3.1 分时调度
分时调度是一种基于时间片轮转的调度策略,在 Linux 中通过 CFS 调度器实现。它将 CPU 时间划分为若干个时间片,每个进程在一个时间片内执行,超过时间片则放回队列等待。
关键代码:
static void check_preempt_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr)
{
// 检查是否需要抢占当前进程
if (entity_tick(cfs_rq, curr))
resched_curr(rq_of(cfs_rq));
}
分时调度策略适用于多任务环境,能够保证每个进程获得公平的 CPU 时间。
3.2 实时调度
实时调度分为硬实时调度和软实时调度。硬实时调度要求在严格的时间限制下完成任务,而软实时调度则对时间限制更加宽松。
4. 调度器的改进
4.1 调度策略的优化
为了解决某些特定场景下的性能问题,Linux 内核做了一些调度策略的优化。例如,在 CFS 调度器中引入了调度域(sched_domain)的概念,将系统的 CPU 资源划分为多个调度域,每个调度域都有自己的调度器和调度策略。
关键代码:
struct sched_domain_topology_level {
enum sched_domain_flags flags;
struct sched_domain_topology_level *down;
struct sched_domain_topology_level *up;
struct sched_domain_topology_level *next;
struct sched_group *groups;
};
通过优化调度策略,可以提高系统的整体性能和响应速度。
4.2 热更新调度器
为了避免内核升级时需要重启系统,Linux 内核还支持热更新调度器的功能。通过这个功能,我们可以在不重启系统的情况下动态切换调度器,以适应不同的工作负载需求。
关键代码:
int switch_sched(char *new_scheduler)
{
// 切换调度器的实现逻辑
// ...
}
热更新调度器可以提高系统的可用性和稳定性,减少系统维护的停机时间。
5. 总结
本文介绍了 Linux 下的调度方式。CFS 是 Linux 默认的调度器,它通过红黑树和虚拟运行时间实现了公平的调度。O(1) 调度器是早期版本使用的调度算法,它通过优先级数组和动态调整进程优先级来提供实时性。除了这两种调度器,Linux 还提供了实时调度器来满足对实时性要求较高的应用程序。此外,调度器的优化和热更新都为系统性能和可用性带来了一定的提升。