之前提到了O(1)的调度器，这在当前的绝大部分RTOS中已经运用了，但是为什么Linux要在O(1)调度器上进一步开发完全公平的调度器CFS呢。主要原因是动态优先级本身是基于定制策略设置的，这就意味着它不是非常的通用，当系统运行在不同的环境中，需要不断的调整其设定规则来调整优先级。

所以Linux这种面向更通用的内核，更需要一个通用性强的调度策略，而非定制式的调度策略。同样的，在RTOS中，本身很多业务就是定制化的，所以可以看到RTOS的演进中，在动态优先级这里就逐渐停止，因为用户直接定制优先级就可以获得最优调度策略。

启式算法

Heuristic algorithms 本身是用来解决复杂问题的一种思路，当一个问题需要解决的时候，如果使用明确的解题步骤去解决，那么可能耗费的人力物力和财力都不成正比，那么我们可以从找到正确答案的角度转换成找到近似解的角度。
所以启发式算法的目的并不是找到正解，而是通过简单的尝试来猜测可能解。

在Linux内核中，很多时候都可以看到启发式算法。最简单最常见的是panic。当某个核心panic的时候，内核总是打印那个核心上的kworker，通常我们查看panic日志的时候，有可能分析的kworker并不代表问题出在当前kworker上，而是出现在可能其相关的kworker上。这里总是打印当前核心的panic日志就是启发式搜索

另一个例子，lockup detector和hung task detector 在检测死锁的时候，默认按照预设的时间判断timeout，如果超时，则打印panic日志。这里timeout值就是启发式算法

说回调度，CFS为了保证所有的任务一定的公平性，设计了vruntime的概念，如果某个任务分配到的实际时间少，那么cfs给他补足时间，允许接下来给他更多的机会获取使用时间。就好像吃奶的小孩似的，vruntime越小，说明要给他的时间越多，也就是越应该容易被调度的任务。

值得注意的是，我们在rtos中查看的调度器实现，对于io的停滞时间都是事后计算的，因为没法统计需要实际io出去了多久。在linux中也一样，cfs调度器给vruntime越小的任务分配更多的资源就是为了弥补io出去后的时间过多的任务，下次让vruntime更小的任务运行。所以vruntime就是一种典型的启发式算法。

启发式算法的优点是将定制转向通用，在面对通用下出现的庞大数量级的场景下，提供尽可能正确的局部最优解。CFS的算法的核心就是尽可能的提供公平。

《我只说三件事：公平，公平，还是公平》

调度类

说起调度，一个非常重要的思想也是必须要说明的，这就是 struct sched_class

首先，我们知道不同的调度器都是通过 struct sched_class 实现，同样的，对于新增的调度器也可以通过实例化这个调度类来完成。对于这个类本身，只需要实现调度器该有的函数回调，例如enqueue，dequeue，yield，pick_next_task 这种调度操作，如下


struct sched_class {
        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 (*yield_task)   (struct rq *rq);
        bool (*yield_to_task)(struct rq *rq, struct task_struct *p);

        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 *p);
        void (*set_next_task)(struct rq *rq, struct task_struct *p, bool first);
        void (*task_tick)(struct rq *rq, struct task_struct *p, int queued);
        void (*task_fork)(struct task_struct *p);
        void (*task_dead)(struct task_struct *p);

        void (*switched_from)(struct rq *this_rq, struct task_struct *task);
        void (*switched_to)  (struct rq *this_rq, struct task_struct *task);
        void (*prio_changed) (struct rq *this_rq, struct task_struct *task,
                              int oldprio);

        unsigned int (*get_rr_interval)(struct rq *rq,
                                        struct task_struct *task);

        void (*update_curr)(struct rq *rq);
} __aligned(STRUCT_ALIGNMENT);

其次，有哪些调度器基于调度类实现呢，这个问题其实就是内核有哪些调度器实例化了sched_class，如下


const struct sched_class rt_sched_class
const struct sched_class fair_sched_class
const struct sched_class idle_sched_class
const struct sched_class stop_sched_class
const struct sched_class dl_sched_class

可以看到，内核实现了5个调度器。

在较新的linux源码上，对sched_class抽象成了宏定义，如下


#define DEFINE_SCHED_CLASS(name) \
const struct sched_class name##_sched_class \
	__aligned(__alignof__(struct sched_class)) \
	__section("__" #name "_sched_class")

其原理是不变的，可以看到不同的调度实现上是通过宏来实现

我们可以留意 __section("__" #name "_sched_class")，可以发现，其会生成一个section，所以我们从vmlinux.lds.h找答案

先看RODATA的定义


#define RO_DATA(align)                                                  \
        . = ALIGN((align));                                             \
        .rodata           : AT(ADDR(.rodata) - LOAD_OFFSET) {           \
                __start_rodata = .;                                     \
                *(.rodata) *(.rodata.*)                                 \
                SCHED_DATA                                              \
                RO_AFTER_INIT_DATA      /* Read only after init */      \
                . = ALIGN(8);                                           \
                __start___tracepoints_ptrs = .;                         \
                KEEP(*(__tracepoints_ptrs)) /* Tracepoints: pointer array */ \
                __stop___tracepoints_ptrs = .;                          \
                *(__tracepoints_strings)/* Tracepoints: strings */      \
        }                                                               \

这里留意 SCHED_DATA，查看实现


#define SCHED_DATA                              \
        STRUCT_ALIGN();                         \
        __begin_sched_classes = .;              \
        *(__idle_sched_class)                   \
        *(__fair_sched_class)                   \
        *(__rt_sched_class)                     \
        *(__dl_sched_class)                     \
        *(__stop_sched_class)                   \
        __end_sched_classes = .;

可以看到其被设计从不同的区域。那么决定不同调度器的优先级的是如何处理的呢？
可以看pick_next_task函数


static inline struct task_struct *
pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)
{
        for_each_class(class) {
                p = class->pick_next_task(rq);
                if (p)
                        return p;
        }
}

在这里，展开一下for_each_class的实现


#define sched_class_highest (__end_sched_classes - 1)
#define sched_class_lowest  (__begin_sched_classes - 1)

#define for_class_range(class, _from, _to) \
        for (class = (_from); class != (_to); class--)

#define for_each_class(class) \
        for_class_range(class, sched_class_highest, sched_class_lowest)

这些就明了了，其就是利用了ld编排的数据顺序进行遍历，那么调度类的优先级顺序如下

stop
dl
rt
fair
idle

最新新增了一个sched_ext，它的顺序如下


#define SCHED_DATA				\
	STRUCT_ALIGN();				\
	__sched_class_highest = .;		\
	*(__stop_sched_class)			\
	*(__dl_sched_class)			\
	*(__rt_sched_class)			\
	*(__fair_sched_class)			\
	*(__ext_sched_class)			\
	*(__idle_sched_class)			\
	__sched_class_lowest = .;

可以看到，ext的优先级倒数第二，关于sched_ext的设计哲学的事情，后面再详细展开。

总结

本文从调度器设计的角度提到了两个很重要的点，启发式算法和调度类。启发式算法让调度器能够看似公平的解决调度问题，从而找到局部最优解，拜托了高度定制的优先级策略，而调度类能够让内核轻松的实现多种调度器，而不是一个调度策略一个轮子。

说个实际工程中的问题，随着preempt-rt补丁兴起，很多所谓的linux操作系统高级专家们，又逐渐将cfs这类启发式的调度策略，退化成rt这样靠定制优先级来解决工程问题的局面。大家转而讨论rt线程的优先级值怎么设计的问题去了。
rt线程虽然能够解决一些实时性问题，但是也让linux从调度这件事，从通用，退化成高度定制了。

目录

启式算法

调度类

总结