【Linux 内核源码分析】进程调度 -CFS 调度器

Linux调度器

Linux内核调度器是负责决定哪个进程在何时执行的组件。它管理着CPU资源的分配和任务的调度，以确保系统资源的合理利用和任务的高效执行。Linux内核中常见的调度器有多种，包括经典的O(1)调度器、CFS（Completely Fair Scheduler）调度器等。这些调度器根据不同的策略和算法来进行任务切换，如时间片轮转、优先级抢占等，以满足不同场景下的性能要求和公平性需求。通过合理配置和选择适当的调度策略，可以提高系统吞吐量、响应时间，并实现更好地负载均衡和公平竞争。

调度：Linux内核调度器中的调度是指决定哪个进程将获得CPU时间片来执行任务。调度器根据一定的策略和算法，从就绪队列中选择一个最合适的进程，使其在给定的时间间隔内运行。这个过程称为上下文切换，其中保存当前进程的上下文信息，并加载即将执行的进程的上下文信息。不同调度器使用不同的算法和策略来确定进程执行顺序，如时间片轮转、优先级抢占等。目标是提高系统整体性能、资源利用率和用户体验，同时保证公平性和响应性。

Linux内核调度器的主要作用是合理地分配CPU时间片给就绪状态的进程，以实现以下几个目标：

  1. 公平性：调度器通过公平地分配CPU时间片给就绪进程，确保每个进程都有机会执行，避免某个进程长期占用CPU而导致其他进程无法获得执行机会。

  2. 高性能：调度器根据不同的调度策略（如CFS、Real-Time等）和优先级，动态地选择最适合的进程来运行，以提高系统整体的性能和吞吐量。

  3. 响应性：调度器及时响应用户或系统事件，尽可能减少任务切换的延迟，提供良好的交互性能和实时响应。

  4. 资源利用率：调度器根据不同的负载情况和系统资源状况，动态地分配CPU时间片给不同的进程，最大限度地利用CPU资源并避免资源浪费。

  5. 能耗管理：一些先进的调度算法还可以考虑节能策略，在需要时降低CPU频率或将其置于休眠状态，以降低功耗和延长电池寿命。

kernel/sched/sched.h

kernel/sched/sched.h 是 Linux 内核中的一个头文件，它定义了与调度器相关的数据结构、函数和宏。该文件是内核调度子系统的一部分，其中包含了调度器实现的相关信息。

具体来说，sched.h 文件中定义了以下内容：

  1. 调度策略和优先级：定义了不同的调度策略（如CFS、实时调度等）以及进程的优先级相关信息。

  2. 调度器数据结构：包括用于表示进程控制块（task_struct）、运行队列（runqueue）等数据结构。

  3. 调度算法和函数：包括实现不同调度策略所使用的具体算法和相关函数，如CFS调度算法、优先级计算函数等。

  4. 宏定义和辅助函数：提供了一些辅助性宏和函数，用于在调度过程中进行状态转换、时间计算等操作。

可以在内核源代码中使用其中定义的数据类型、函数和宏来实现对进程调度的操作和管理。

struct sched_class 是 Linux 内核中用于描述调度器类别的结构体。它定义了每种调度策略（如 CFS、实时调度等）的相关操作和属性。

在内核源码中，struct sched_class 结构体通常会有多个实例，每个实例对应一个特定的调度策略。不同的调度策略有不同的名称和实现方式，但它们都需要遵循 struct sched_class 结构体所定义的接口。

struct sched_class {
    // 指向下一个 sched_class 结构体的指针，用于形成链表结构
    const struct sched_class *next;

    // 将一个进程添加到运行队列中（即调度器将该进程调度到 CPU 上执行）
    void (*enqueue_task) (struct rq *rq, struct task_struct *p, int flags);
    
    // 将一个进程从运行队列中移除（即调度器取消对该进程的调度）
    void (*dequeue_task) (struct rq *rq, struct task_struct *p, int flags);

    // 检查调度器是否应该抢占当前进程
    void (*check_preempt_curr) (struct rq *rq, struct task_struct *p, int flags);

    // 选取下一个要运行的进程（即进行进程调度）
    struct task_struct *(*pick_next_task) (struct rq *rq);

    // 当前进程时间片结束时调用的回调函数
    void (*put_prev_task) (struct rq *rq, struct task_struct *prev);

    // 获取进程的优先级
    int (*get_priority) (struct task_struct *p);

    // 设置进程的优先级
    void (*set_curr_task_priority) (struct rq *rq, struct task_struct *p, int prio);

    // 检查进程是否具有实时调度策略
    bool (*task_has_rt_policy)(struct task_struct *p);

    // 检查进程是否具有分时调度策略
    bool (*task_has_dl_policy)(struct task_struct *p);

    // 检查进程是否具有负载平衡调度策略
    bool (*task_can_attach)(struct task_struct *p);

    // 进行运行队列的初始化
    void (*set_cpus_allowed)(struct task_struct *p, const struct cpumask *new_mask);

    // 从当前运行队列中移除一个进程
    void (*rq_online)(struct rq *rq);

    // 将一个进程添加到当前运行队列中
    void (*rq_offline)(struct rq *rq);

    // 将进程迁移至另一个 CPU 的运行队列中
    int (*task_waking)(struct task_struct *p, unsigned int state);

    // 在进程状态改变时调用的回调函数
    void (*task_change_group)(struct task_struct *p, int type);

    // 在进程 CPU 绑定发生变化时调用的回调函数
    void (*task_set_group)(struct task_struct *p);

    // 获取当前正在运行的进程
    struct task_struct *(*get_rr_interval)(struct rq *rq, struct task_struct *task);
};

调度类

常见的调度类：

  1. 实时调度类（Real-Time Scheduling Class）：用于实时任务，具有最高优先级，并且可以通过固定时间片或基于优先级的抢占来进行调度。

  2. 实时负载均衡调度类（Real-Time Load Balancer Scheduling Class）：用于负载均衡操作，以确保系统中的实时任务得到合理分配和调度。

  3. 实时限制调度类（Real-Time Throttle Scheduling Class）：用于限制实时任务的执行资源，以避免其他重要任务被过多耗费。

  4. CFS（Completely Fair Scheduler）调度类：用于普通进程的抢占式多任务调度。CFS通过红黑树来组织运行队列，并为每个进程分配时间片以平等分享CPU资源。

  5. Idle（空闲）调度类：用于处理空闲CPU时间，在没有可执行任务需要运行时将CPU置于休眠状态，以节省能源。

  6. 停机调度类（Stop Scheduling Class）：如前面提到的，用于处理被标记为停机状态的进程，这些进程不再参与正常的调度过程。

实时调度类

实时调度类是操作系统中用于处理具有严格时间约束的实时任务的一种调度类。在大多数现代操作系统中，通常会提供多个不同的实时调度类，以满足不同类型和需求的实时任务。

常见的实时调度类包括：

  1. SCHED_FIFO：使用先进先出（FIFO）调度策略，根据优先级确定任务执行顺序。具有较高优先级的任务将一直执行，直到它们自愿放弃CPU资源。
  2. SCHED_RR：使用轮转（Round-Robin）调度策略，在相同优先级任务之间进行时间片轮转。每个任务都有一个固定时间片来执行，如果时间片耗尽，则会被放回队列等待下次轮转。
  3. SCHED_DEADLINE：基于最后期限（Deadline）的调度策略，允许开发者为每个任务指定绝对截止日期，并确保在截止日期之前完成任务。这种调度类主要用于周期性实时任务。

实时负载均衡调度类

实时负载均衡调度类是一种用于在实时系统中分配任务和资源的调度算法。其目标是确保实时任务在多个处理器或核心上平衡地分布，以提高系统的性能和可靠性。

这些调度类通常考虑以下因素：

  1. 实时任务的优先级：根据任务的紧急程度和重要性确定优先级顺序。
  2. 处理器或核心的负载状况：监测各个处理器或核心的负载情况，包括当前执行的任务数量和运行时间等。
  3. 任务之间的依赖关系：考虑到实时任务之间可能存在的依赖关系，确保满足这些依赖关系以避免延迟。

一些常见的实时负载均衡调度算法包括：
4. 最小负载优先（Least Load First）：选择最空闲的处理器或核心来分配新任务。
5. 最短剩余时间优先（Shortest Remaining Time Next）：选择剩余执行时间最短的任务进行调度，以最小化响应时间。
6. 周期性负载均衡（Periodic Load Balancing）：周期性地检查处理器或核心之间的负载，并重新分配任务以保持平衡。

实时限制调度类

实时限制调度类是一种用于在实时系统中管理和控制任务执行速率的调度算法。该调度类主要用于限制任务的执行频率，以确保系统资源的合理利用和任务的可靠性。

实时限制调度类通常考虑以下因素：

  1. 任务的执行时间：监测每个任务的执行时间，包括开始时间和结束时间。
  2. 任务之间的时间间隔：确定每个任务之间需要保持的最小时间间隔。
  3. 系统负载情况：根据系统当前负载情况动态调整任务的执行速率。

基本原理是通过控制每个任务之间的最小时间间隔或执行次数来限制其执行速率。这可以防止某些耗时较长或资源占用较高的任务对系统产生过大影响，从而提高系统稳定性和可靠性。

CFS调度类

CFS调度类是一个在Linux内核中用于多任务调度的算法。它旨在以公平和高效的方式分配CPU时间片给各个运行的进程。

CFS通过使用红黑树数据结构来管理进程，并基于进程的虚拟运行时间（vruntime）进行排序。每个进程都被赋予一个虚拟运行时间，该时间反映了该进程应该获得的CPU时间片相对于其他进程的优先级。较短虚拟运行时间的进程会被放在红黑树的前面，有更高的优先级，可以获得更多的CPU执行时间。

CFS实现了完全公平性，即尽可能地使每个任务能够以相等或接近相等的比例共享CPU资源。这意味着没有任务会因为其他任务长期占用CPU而被饿死（starvation）。CFS会动态地计算每个进程应获得的虚拟运行时间，并将其作为参考来确定下一个要运行的进程。

Idle调度类

当CPU上没有任何活动进程需要运行时，操作系统会将CPU分配给Idle调度类来处理。Idle调度类不涉及实际的任务调度或时间片分配，而是让CPU处于空闲状态以降低功耗和热量产生。

当没有活动进程需要运行时，内核会让CPU进入Idle状态，并等待下一个事件发生。这个事件可以是外部中断、硬件触发或其他需要处理的事件。一旦有新的活动任务到达或者有其他需要处理的事件发生，内核就会切换到适当的调度类来管理CPU资源。

Idle调度类通常被认为是“什么都不做”的调度类别，在确保系统资源利用率和效能的同时节省了功耗。

停机调度类

用于处理处于停机状态的进程。当一个进程暂时不需要运行时，它可以被切换到停机调度类来节省CPU资源。

停机调度类是Completely Fair Scheduler（CFS）的一部分。当一个进程被切换到停机调度类后，它将不会被调度执行，直到满足某些条件使其重新激活。

常见的触发条件包括等待某个事件的发生、等待输入/输出操作完成或等待其他进程的信号。当这些条件满足时，进程将从停机状态恢复并转移到适当的调度类以进行执行。

通过将闲置或暂时不需要执行任务的进程切换到停机调度类，系统可以有效地管理CPU资源，并避免浪费计算能力。

优先级

Linux 内核中的优先级通常是指进程（或线程）的调度优先级，也称为 Nice 值。在 Linux 中，Nice 值的范围是 -20 到 19，其中 -20 表示最高优先级，而 19 表示最低优先级。

Nice 值越小，进程的调度优先级越高，越容易获得 CPU 时间片。例如，Nice 值为 -20 的进程会比 Nice 值为 19 的进程更容易获得 CPU 时间片。内核使用 Nice 值来决定哪个进程应该运行，以及每个进程应该获得多长时间的 CPU 时间片。

除了 Nice 值之外，Linux 还支持实时调度类和普通调度类等不同类型的调度策略。实时调度类通常用于需要快速响应的任务，如音频处理、运动控制等领域；而普通调度类则用于普通的计算任务，如文本处理、编译等。

task_struct结构体

task_struct 是 Linux 内核中用于表示进程或线程的数据结构，含了许多字段来存储与进程相关的信息，例如进程状态、调度信息、内存管理、文件描述符等。

在 task_struct 结构体中，通常有三个成员变量用于表示进程的优先级。它们分别是：

  1. prio：表示进程的静态优先级，即进程在创建时分配给它的优先级。在 Linux 中，进程的静态优先级的范围是 100（最高优先级）到 139（最低优先级）。

  2. rt_priority：表示实时优先级。对于实时进程，它的优先级可以高于普通进程的 prio 值。实时优先级的范围是 0（最高优先级）到 99（最低优先级）。

  3. normal_prio：表示动态优先级，也称为当前优先级。动态优先级是根据进程的历史行为和负载情况等动态调整的优先级。动态优先级的范围是 100（最高优先级）到 139（最低优先级）。

在 Linux 中，进程的调度策略可以是 SCHED_NORMAL、SCHED_FIFO 或 SCHED_RR 等。对于 SCHED_NORMAL 调度策略的进程，动态优先级等于静态优先级；对于 SCHED_FIFO 和 SCHED_RR 调度策略的实时进程，动态优先级等于实时优先级。

抱歉，我之前给出的路径不正确。在 Linux 内核中，进程的优先级定义可以在以下路径下找到：include/linux/sched/prio.h。

在该头文件中，定义了进程的静态优先级的范围、实时优先级的范围以及其他与优先级相关的常量和宏。

#define MAX_USER_RT_PRIO 100
#define MAX_RT_PRIO     MAX_USER_RT_PRIO
#define MAX_PRIO (MAX_RT_PRIO + NICE_WIDTH)
#define DEFAULT_PRIO (MAX_RT_PRIO + NICE_WIDTH / 2)
  • MAX_USER_RT_PRIO 定义了实时优先级中用户可用的最大优先级，其值为 100。
  • MAX_RT_PRIO 定义了实时优先级中的最大优先级，其值等于 MAX_USER_RT_PRIO。
  • NICE_WIDTH 是一个宏定义，在 Linux 内核中表示可调整的优先级范围。在这里没有给出具体定义，但通常是一个较小的正整数。
  • MAX_PRIO 定义了进程可以具有的最大优先级。它由 MAX_RT_PRIO 和 NICE_WIDTH 相加得到。
  • DEFAULT_PRIO 定义了默认进程优先级。它通过将 MAX_RT_PRIO 和 NICE_WIDTH / 2 相加得到。

这些常量用于确定进程或线程在调度器中的相对优先级。实时优先级（Real-Time Priority）用于处理时间关键任务，而普通进程则根据静态优先级和动态调整因子（如 NICE 值）来进行调度。

调度策略

调度策略是操作系统用来决定哪个进程或线程应该在给定时间片内运行的算法。不同的调度策略可以根据不同的需求和目标进行选择。

以下是一些常见的调度策略：

  1. SCHED_OTHER（CFS调度器）：标准的时间片轮转调度算法。

  2. SCHED_FIFO（实时先进先出）：按照优先级进行调度，直到任务完成或者被更高优先级任务抢占。

  3. SCHED_RR（实时轮转）：按照优先级进行调度，每个任务都有一个固定的时间片来执行，超过时间片后被放到队列尾部继续等待。

  4. SCHED_BATCH（批处理）：为了提高系统整体性能而设计的调度策略，在CPU空闲时运行批处理任务。

  5. SCHED_IDLE（空闲）：只有当没有其他可运行任务时才会运行该任务。

这些常量可以通过使用sched_setscheduler()和sched_getscheduler()等系统调用函数来设置和获取进程或线程的调度策略。

多处理器系统

Linux内核中有几种常见的多处理器调度策略：

  1. 对称多处理（SMP）调度：在对称多处理系统中，每个处理器核心都可以独立地运行任务。Linux使用完全公平调度（CFS）算法来均衡负载并按照优先级进行任务分配。

  2. 实时多处理（RT-MP）调度：实时多处理调度针对具有严格时间限制和实时需求的应用程序。它提供了精确的响应时间保证，并通过确定性调度算法将任务分配给不同的处理器核心。

  3. CPU集群调度：CPU集群指的是一组紧密连接的处理器核心，可以共享缓存和其他资源。Linux通过自适应层次调度算法将任务动态地分配到合适的CPU集群中，以最大程度地利用共享资源。

CFS 调度器

CFS是Linux内核中默认的进程调度器，引入于Linux 2.6.23版本。CFS调度器旨在提供公平、高效和可扩展的进程调度。

CFS调度器使用红黑树数据结构来维护任务队列，并通过动态地分配时间片给每个任务来实现公平性。它以时间片（称为虚拟运行时间）的方式对任务进行量化，较长时间未被执行的任务将获得更多的虚拟运行时间。

在这里插入图片描述

在Linux内核中，根据任务的权重值（也称为nice值）和调度策略，可以计算出任务的运行时间。

在CFS（Completely Fair Scheduler）调度器中，任务的权重值由其nice值决定，通过对比不同任务的权重值，CFS会分配合理的CPU时间片给每个任务。其中较高权重（较低nice值）的任务将获得更多的CPU时间片用于执行。

在每个sched_latency周期内，CFS会动态地根据任务的权重来计算各个任务应该获得的运行时间。这种计算方式被称为"虚拟运行时间"（virtual runtime），它反映了每个任务相对于其他任务应该占有CPU资源的比例。

通过不断更新和调整虚拟运行时间，CFS能够实现公平而均衡的任务调度，并尽量保证所有进程都能获得合理的CPU执行时间。这种机制使得低优先级或高负载情况下的进程仍然能够被适当地执行，并防止某些进程长期霸占CPU资源。

是的，Linux 内核通过抽象出调度类 struct sched_class 来封装具有共性特征的调度算法，并在实例化各个调度器时根据具体的调度算法来实现。

struct sched_class 定义了一组函数指针，这些函数指针对应了调度算法中的各个操作。通过这些函数指针，可以实现对进程的调度、挂起、恢复等操作。

在 Linux 内核中，每个调度器都会定义自己的 struct sched_class 实例，并根据具体的调度算法来实现这些函数指针。CFS（完全公平调度器）就定义了自己的 struct sched_class 实例，并实现了对应的函数指针，来实现公平调度算法。

当内核需要进行进程调度时，会根据进程的调度策略选择相应的调度器，并调用该调度器的 struct sched_class 实例中相应的函数指针进行操作。

在调度核心代码 kernel/sched/core.c 中，通过 task->sched_class->xxx_func 的方式来执行具体的调度函数，这可以看作是一种类似于 C++ 中的多态机制。

在 Linux 内核中，struct task_struct 是描述进程或线程的数据结构，它包含了许多与进程相关的信息，其中之一就是调度器的指针 sched_class。

当需要对任务进行调度时，内核会根据任务的调度器指针 sched_class 来查找对应的调度类，并使用其中的函数指针来完成具体的调度操作。这种方式实现了一种类似于多态的效果，即不同的任务可以使用不同的调度算法，而调度器的函数指针则根据具体的调度器类型来指向对应的函数。

通过这种方式，Linux 内核可以根据任务的调度器类型来调用相应的调度函数，实现了灵活的调度策略，并且能够方便地扩展和切换不同的调度器。这种设计使得内核的调度器模块具有良好的可扩展性和可维护性。

rq/cfs_rq/task_struct/task_group/sched_entity 结构体

在这里插入图片描述

  1. task_struct：是Linux内核中表示进程或线程的数据结构。它包含了进程的各种属性和状态信息，如进程ID、调度策略、优先级等。

  2. rq：运行队列（runqueue）是一个用于存储可运行进程的队列。每个CPU核心都有一个运行队列，其中包含了在该核心上等待执行的任务。

  3. task_group：任务组是一组相关联的进程，通常由一个父进程和其所有子进程组成。它们共享资源限制和调度策略，并通过signal_struct来进行统一管理。

  4. sched_entity：调度实体是用于跟踪和管理每个进程/线程在调度器中的状态和属性的数据结构。它包含了诸如运行时间、虚拟运行时间、权重值等信息，并与其他数据结构相互关联以进行调度决策。

  5. cfs_rq：CFS（Completely Fair Scheduler）队列是用于实现公平调度的数据结构。每个CPU核心都有一个CFS队列，负责管理可运行的进程集合。

struct task_struct 结构体

struct task_struct {
    volatile long state;                        // 进程状态（运行、等待等）
    void *stack;                                // 进程堆栈指针
    atomic_t usage;                             // 引用计数
    unsigned int flags;                         // 进程标志位
    unsigned int ptrace;                        // ptrace标志
    
    struct llist_node wake_entry;                // 等待队列节点

    int on_cpu;                                 // 当前运行进程所在的 CPU 编号
    int on_rq;                                  // 是否在运行队列上

    int prio;                                   // 动态优先级，用于调度算法
    int static_prio;                            // 静态优先级，用于调度算法的基准值
    int normal_prio;                            // 平均动态优先级，考虑了任务执行历史和时间片轮转
    unsigned int rt_priority;                   // 实时进程优先级

#ifdef CONFIG_SCHED_DEBUG
	unsigned long sleep_avg;
	unsigned long long timestamp, last_ran;
#endif

	struct sched_class	*sched_class;
	struct sched_entity	se;
	struct sched_rt_entity	rt;

#ifndef CONFIG_PREEMPT_NOTIFIERS
	// ...
#endif

	// ...
};

struct task_group 结构体

struct task_group {
	/* 该组的父组 */
	struct task_group *parent;

	/* 与该组关联的 cgroup */
	struct cgroup_subsys_state css;

#ifdef CONFIG_CGROUP_CPUACCT
	/*
	 * cpuacct 和 cpu 变量需要在同一个缓存行上，因为它们在频繁访问和更新时使用。
	 *
	 * 不要将这两个变量分开，否则可能会导致不同 CPU 上的伪共享。
	 */
	struct task_group_cpuacct cpuacct;
#endif

#ifdef CONFIG_CGROUP_CPUSET
    // ...
#endif

#ifdef CONFIG_FAIR_GROUP_SCHED
	/* 调度策略相关字段 */
	struct sched_entity **se;          /* 指向每个调度实体结构体（sched_entity）的指针数组 */

    // ...

    /* 这些字段用于统计信息和负载均衡操作 */
	unsigned long load_last_balance;   /* 上次平衡时的负载值 */
	u64 load_prev_update;              /* 上次更新平均负载时间戳 */
	unsigned long aggregated_load_avg; /* 平均聚合负载值 */
	int nr_running;                    /* 组内正在运行任务数量 */

	atomic_long_t util_avg[CPU_STAT_NSTATES];  /* CPU 利用率统计信息 */

    // ...
#endif

    // ...

};

struct sched_entity 结构体

struct sched_entity {
    struct load_weight        load;                   // 进程的负载权重
    struct rb_node            run_node;               // 在运行队列中以红黑树形式组织的节点
    unsigned int              on_rq;                  // 标志位，指示进程是否在运行队列中
    u64                       exec_start;             // 进程最近一次执行开始时间戳
    u64                       sum_exec_runtime;       // 总执行时间（包括所有CPU核心）
    u64                       vruntime;               // 进程虚拟运行时间（Fair调度算法使用）
#ifdef CONFIG_SCHED_DEBUG
    u64                       prev_sum_exec_runtime;  // 上一个统计周期内的总执行时间
#endif

#ifndef CONFIG_64BIT
    unsigned int              __pad;
#endif

    struct sched_statistics  statistics;              // 调度统计信息

#ifdef CONFIG_FAIR_GROUP_SCHED
    struct sched_entity      *parent;                 // 父进程的调度实体指针（任务组）
#endif

#ifdef CONFIG_UCLAMP_TASK
    struct uclamp_se          clamp[UCLAMP_CNT];      // 进程对应每个UCLAMP档案级别的约束值
#endif

#ifdef CONFIG_SCHED_WALT        
        /* ... */
#endif   
};

实际运行时间（runtime）和一个虚拟运行时间（vruntime）

在CFS调度器中，没有固定的时间片概念。相反，它使用了实际运行时间和虚拟运行时间来进行任务排序和选择调度。

实际运行时间是指任务在CPU上真正执行的时间。每当任务被选中并分配给CPU时，它会累积实际运行时间。

虚拟运行时间是一个相对概念，它取决于任务在CFS队列中的位置以及其他相关因素。具体而言，虚拟运行时间与进程优先级有关。高优先级的任务会获得更多的虚拟运行时间，在排序和选择调度时更容易被选中。

计算虚拟运行时间涉及到一些复杂的算法和数据结构，主要目标是使各个任务能够公平地竞争CPU资源。通过动态调整虚拟运行时间，CFS调度器可以保持系统的负载均衡，并提供对不同优先级任务的适当响应。

每个任务都有一个实际运行时间（runtime）和一个虚拟运行时间（vruntime）。这两个参数用于计算任务的优先级和选择下一个要执行的任务。

  1. 实际运行时间（runtime）：表示任务在CPU上真正执行的时间。每当任务被选中并分配给CPU时，它会累积实际运行时间。通过记录实际运行时间，CFS可以了解每个任务在过去多长时间内使用了CPU资源。

  2. 虚拟运行时间（vruntime）：是一个相对概念，用于衡量任务的优先级。较高优先级的任务会获得更多的虚拟运行时间，从而在排序和选择调度时更容易被选中。虚拟运行时间与进程优先级有关，并根据一定的算法进行动态调整。

CFS调度器使用vruntime来进行任务排序和选择调度。它根据每个任务的vruntime值来确定下一个要执行的最合适的任务。通过比较不同任务之间的vruntime值，CFS可以保持系统负载均衡，并确保按照其优先级公平地分配CPU资源。

CFS（完全公平调度器）的主要流程调用：

  1. 初始化：在系统启动时，初始化 CFS 调度器相关数据结构和参数。

  2. 进程创建：当一个新进程被创建时，为其分配调度实体 struct sched_entity，并初始化相关属性。

  3. 进程插入调度队列：通过调用 enqueue_task_fair() 函数，将进程插入 CFS 调度队列中，并更新调度信息。

  4. 选择下一个运行进程：在每个时钟中断时，调用 pick_next_task_fair() 函数选择下一个应该运行的进程。

  5. 上下文切换：如果选定的进程与当前正在运行的进程不同，则进行上下文切换，将 CPU 分配给新的进程。

  6. 时间片耗尽：当当前运行进程的时间片耗尽时，调用 put_prev_task_fair() 函数更新运行进程的虚拟运行时间，并重新插入调度队列。

  7. 进程退出或挂起：当一个进程退出或被挂起时，调用 dequeue_task_fair() 函数将其从调度队列中移除。

  8. 时钟中断处理：在每个时钟中断处理程序中，调用 task_tick_fair() 函数更新当前运行进程的虚拟运行时间，并检查是否需要进行调度决策。

  9. 负载均衡：定期进行负载均衡，调用相关的负载均衡函数，如 load_balance()，以确保各个 CPU 上的任务分布均衡。

  10. 循环调度：重复执行步骤 4-9，不断选择下一个运行进程并进行调度，以实现公平的 CPU 时间片分配。

虚拟运行时间是通过以下公式计算得出的：

虚拟运行时间 = 实际运行时间 * NICE_0_LOAD / 该任务的权重

时钟中断事件

CFS 调度器的 tick 是一个时钟中断事件，它用于触发调度器进行调度决策。在 Linux 内核中，CFS 调度器通过时钟中断来进行时间片的分配和进程的切换。

每当一个 tick 发生时，内核会调用相关的时钟中断处理程序。在 CFS 调度器中，这个处理程序主要做两件事情：

  1. 更新当前运行进程的虚拟运行时间：通过调用 task_tick_fair() 函数，更新当前运行进程的虚拟运行时间。这个虚拟运行时间的增加，可以理解为当前进程消耗了一个时间片（time slice）的时间。

  2. 进行调度决策：在更新了虚拟运行时间之后，时钟中断处理程序会检查是否需要进行调度决策。这个决策是通过调用 check_preempt_curr() 函数来完成的。该函数会比较当前运行进程与其他就绪队列中的进程的优先级，如果有更高优先级的进程等待运行，则会触发上下文切换，将 CPU 分配给新的进程。

通过这样的方式，CFS 调度器能够在每个 tick 中根据进程的虚拟运行时间和优先级进行调度决策，以确保公平地分配 CPU 时间片。这种基于时钟中断的调度机制使得 CFS 能够动态地根据进程的运行情况进行调度，以实现更好的系统性能和响应性。

以下是CFS调度tick时钟中断事件的基本流程：

  1. 定时器触发：操作系统设置一个定时器，在每个时钟周期结束时触发中断。这个定时器一般以毫秒或微秒为单位。

  2. 中断处理程序执行：当定时器触发时，CPU会暂停当前正在执行的任务，并跳转到预先注册的中断处理程序（tick handler）。

  3. 更新任务信息：在tick handler中，首先需要更新运行状态、统计信息和优先级等相关数据结构。这些数据结构包括进程控制块（PCB）、红黑树等。

  4. 进程选取：在CFS调度算法中，选择下一个最公平的进程来运行是关键步骤。该算法通过维护一棵红黑树来实现公平性。

  5. 进程切换：如果需要进行进程切换，即切换到新选取的进程执行，则进行上下文切换操作。这涉及保存当前进程的寄存器状态，并恢复待执行进程的寄存器状态。

  6. 执行新进程：完成上下文切换后，CPU开始执行新选取的进程，该进程会继续运行一段时间或直到下一个时钟中断。

  7. 继续定时器：tick handler结束后，操作系统重新设置定时器，并恢复之前被中断的任务。CPU继续执行被恢复的任务，直到下一个tick事件触发。

参考推荐：Linux内核源码分析教程

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/317285.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

大模型实战笔记04——XTuner 大模型单卡低成本微调实战

大模型实战笔记04——XTuner 大模型单卡低成本微调实战

大模型实战笔记04——XTuner 大模型单卡低成本微调实战 1、Finetune简介 2、XTuner 3、8GB显存玩转LLM 4、动手实战环节 注： 笔记内容均为截图 课程视频地址：https://www.bilibili.com/video/BV1yK4y1B75J/?spm_id_from333.788&vd_source2882acf…
阅读更多...
Flink（十二）【容错机制】

Flink（十二）【容错机制】

前言 最近已经放假了，但是一直在忙一个很重要的自己的一个项目，用 JavaFX 和一个大数据组件联合开发一个功能，也算不枉我学了一次 JavaFX，收获很大，JavaFX 它作为一个 GUI 开发语言，本质还是 Java&#xff…
阅读更多...
嵌套的CMake

嵌套的CMake

hehedalinux:~/Linux/multi-v1$ tree . ├── calc │ ├── add.cpp │ ├── CMakeLists.txt │ ├── div.cpp │ ├── mult.cpp │ └── sub.cpp ├── CMakeLists.txt ├── include │ ├── calc.h │ └── sort.h ├── sort │ ├── …
阅读更多...
Spring之AOP源码（一）

Spring之AOP源码（一）

文章目录 一、动态代理1. 概念2. Cglib动态代理的使用3. JDK动态代理的使用 二、SpringAOP1. 简介2. Spring AOP使用 一、动态代理 1. 概念 动态代理（Dynamic Proxy）是一种在运行时动态生成代理对象的技术。它是一种设计模式，用于在不修改原…
阅读更多...
Web实战丨基于django+html+css+js的电子商务网站

Web实战丨基于django+html+css+js的电子商务网站

文章目录 写在前面实验目标需求分析实验内容安装依赖库1.登陆界面2.注册界面3.电子商城界面4.其他界面 运行结果写在后面 写在前面 本期内容：基于DjangoHTMLCSSJS的电子商务网站 实验环境： vscode或pycharmpython(3.11.4)django 代码下载地址&#x…
阅读更多...
Web自动化测试，一定得掌握的 8 个核心知识点

Web自动化测试，一定得掌握的 8 个核心知识点

使用 cypress 进行端对端测试，和其他的一些框架有一个显著不同的地方，它使用 javascript 作为编程语言。传统主流的 selenium 框架是支持多语言的，大多数 QA 会的python 和 java 语言都可以编写 selenium 代码，遇到需要编写 js 代…
阅读更多...
距离美赛还有20天，不要忘了阅读往年获奖论文（附04-23年美赛获奖论文）

距离美赛还有20天，不要忘了阅读往年获奖论文（附04-23年美赛获奖论文）

之前发了很多数模相关的知识，受到了一些人的关注，也有很多人私下问我，距离美赛还有20几天了，还来不来得及。 对此我想说， 来不来得及重要吗？ 你名都报了，钱也交了，还是笔不小的钱…
阅读更多...
猫狗大战（猫狗识别）

猫狗大战（猫狗识别）

1.问题简介 1.1问题描述 在这个问题中，你将面临一个经典的机器学习分类挑战——猫狗大战。你的任务是建立一个分类模型，能够准确地区分图像中是猫还是狗。 1.2预期解决方案 你的目标是通过训练一个机器学习模型，使其在给定一张图像时能够准…
阅读更多...
【模块系列】STM32BMP280

【模块系列】STM32BMP280

前言 最进想练习下I2C的应用，手上好有BMP280也没用过，就看着机翻手册和原版手册，开始嘎嘎写库函数了。库的命名应该还1是比较规范了吧，就是手册对于最终值的计算方式很迷糊，所以现在也不能保证有可靠性啊，大…
阅读更多...
关于运维·关于数据库面试题

关于运维·关于数据库面试题

目录 一、数据库类型 二、数据库引擎 三、mysql数据库类型 四、mysql的约束添加 五、主从复制原理 六、主从方式有几种 七、mysql主从数据不一致的原因 八、mysql的优化 九、什么是事务的特征 十、数据库读写分离的好处 十一、怎样优化sql语句 十二、mysql的同步方…
阅读更多...
基于MAP算法的Turbo译码 -- 公式推导

基于MAP算法的Turbo译码 -- 公式推导

到此为止，讲完了turbo译码器的子译码器基于MAP算法的译码过程。但在实际使用中，很少直接使用MAP算法进行译码。而是使用改进的LOG-MAP和MAX-LOG-MAP算法进行译码，因此译码的整体流程，包括外信息的计算以及先验信息的获取等。都在后…
阅读更多...
openai自定义API操作 API （openai.custom）

openai自定义API操作 API （openai.custom）

OpenAI 提供了一个自定义 API，允许开发者通过编程方式与 OpenAI 的 AI 模型进行交互。使用这个 API，你可以执行各种任务，例如文本生成、推理和翻译等。 以下是使用 OpenAI 自定义 API 的基本步骤： 创建 API 密钥：首先…
阅读更多...
谷粒商城-商品服务-品牌管理-阿里云云存储+JSR303数字校验+统一异常处理

谷粒商城-商品服务-品牌管理-阿里云云存储+JSR303数字校验+统一异常处理

阿里云云存储OSS 分布式系统上传文件 分布式系统上传文件 单体应用上传：上传文件到服务器，想获取文件时再向服务器发请求获取文件。 分布式系统上传： 因为有多台服务器，为防止负载均衡导致获取文件时没找到对应的服务器&#xf…
阅读更多...
数字信号处理教程学习笔记1-第2章时域中的离散信号和系统

数字信号处理教程学习笔记1-第2章时域中的离散信号和系统

信号处理的任务示意方框图 模拟信号和数字信号分别是啥样的，有啥区别
阅读更多...
MySQL数据库设计原则

MySQL数据库设计原则

0.简单的处理逻辑 一.MySQL完整性约束 主键约束 primary key 自增键约束 auto_increment 唯一键约束 unique 非空约束 not null 默认值约束 default 外键约束 foreign key 下面是一个sql语句创建一个表,可以看出来了使用了哪几个约束吗? create table user( id int…
阅读更多...
vue前端开发自学,借助KeepAlive标签保持组件的存活

vue前端开发自学,借助KeepAlive标签保持组件的存活

vue前端开发自学,借助KeepAlive标签保持组件的存活&#xff01;如果不想让组件在切换的时候&#xff0c;被默认操作&#xff08;卸载掉了&#xff09;。他们需要使用这个这个表情哦。 下面给大家看看代码情况。 <template><h3>ComA</h3><p>{{ messag…
阅读更多...
Arduino开发实例-AS608光学指纹传感器驱动

Arduino开发实例-AS608光学指纹传感器驱动

AS608光学指纹传感器驱动 文章目录 AS608光学指纹传感器驱动1、AS608光学指纹传感器介绍2、硬件准备及接线3、代码实现3.1 指纹录入3.2 指纹匹配验证1、AS608光学指纹传感器介绍 AS608 光学指纹传感器可用于扫描指纹，它也可以通过串行通信将处理后的数据发送到微控制器。 所有…
阅读更多...
鸿蒙(HarmonyOS)应用开发指南

鸿蒙(HarmonyOS)应用开发指南

1. 概述 1.1 简介 鸿蒙&#xff08;即 HarmonyOS &#xff0c;开发代号 Ark&#xff0c;正式名称为华为终端鸿蒙智能设备操作系统软件&#xff09;是华为公司自 2012 年以来开发的一款可支持鸿蒙原生应用和兼容 AOSP 应用的分布式操作系统。该系统利用“分布式”技术将手机、电…
阅读更多...
好用的便签有哪些？windows便签工具在哪打开？

好用的便签有哪些？windows便签工具在哪打开？

每当我8点准时上班&#xff0c;在等待电脑开机的过程&#xff0c;我都会习惯性地思考整理今天要晚上的任务&#xff0c;列出所要完成的待办事项。随着每一项任务的清晰呈现&#xff0c;我的心情也逐渐明朗起来。当然了&#xff0c;这个时候&#xff0c;我迫切需要一款好用的便签…
阅读更多...
【LeetCode】142. 环形链表 II（中等）——代码随想录算法训练营Day04

【LeetCode】142. 环形链表 II（中等）——代码随想录算法训练营Day04

题目链接&#xff1a;142. 环形链表 II 题目描述 给定一个链表的头节点 head &#xff0c;返回链表开始入环的第一个节点。 如果链表无环&#xff0c;则返回 null。 如果链表中有某个节点&#xff0c;可以通过连续跟踪 next 指针再次到达&#xff0c;则链表中存在环。 为了…
阅读更多...
最新文章

Copyright @ 2022~2023