调度程序负责决定将哪个进程投入运行，何时运行以及运行多长时间。进程调度程序可看作在可运行态进程之间分配有限的处理器时间资源的内核子系统，是像Linux这样的多任务操作系统的基础。

一、多任务

多任务操作系统就是能同时并发地交互执行多个进程的操作系统。可以分为两类：

• 非抢占式多任务：除非进程自己主动停止运行，否则它会一直执行。进程主动挂起自己的操作称为让步。
• 抢占式多任务：调度程序来决定什么时候停止一个进程的运行，以便其他进程能够得到执行机会。强制挂起的动作就是抢占，进程在被抢占之前能够运行的时间是预先设置好的，叫进程的时间片。

二、策略

1.I/O消耗型和处理器消耗型

进程可以分为I/O消耗型和处理器消耗型（进程可以同时展示这两种行为）。

• I/O消耗型：进程的大部分时间用来提交I/O请求或是等待I/O请求；
• 处理器消耗型：把时间大多用在执行代码上。

调度策略通常要在两个矛盾的目标中寻找平衡：进程响应迅速和最大系统利用率。Linux为了保证交互式应用和桌面系统的性能，对进程的响应做了优化（缩短响应时间），更倾向于优先调度I/O消耗型进程。

2. 进程优先级

Linux采用了两种不同的优先级范围：

• nice值：范围在[-20, 19]，默认值为0，nice值越大优先级越低；
• 实时优先级：其值可配置，默认变化范围[0, 99]，越高的实时优先级数值意味着进程优先级越高。

实时优先级和nice值处于互不相交的两个范畴，任何实时进程的优先级都高于普通进程。

3. 时间片

时间片是一个数值，它表明进程在被抢占前所能持续运行的时间。

Linux自2.6内核系统开始引入新的进程调度算法，其中最著名的是“反转楼梯最后期限调度算法（rotating staircase deadline scheduler，RSDL）”，被称为“完成公平调度算法（CFS）”。

Linux的CFS调度器并没有直接分配时间片到进程，而是将处理器的使用比例划分给进程，也就是说，进程所获得的处理器时间和系统负载密切相关的。当一个进程进入可运行状态，他就被准许投入运行。Linux的CFS调度器，其抢占时机取决于新的可运行进程消耗了多少处理器使用比。如果消耗的使用比例比当前进程小，则新的进程立刻投入运行，抢占当前进程，否则推迟运行。

三、Linux调度算法

1. 调度器类

Linux调度器是以模块方式提供的，以允许不同类型的进程可以有针对性地选择调度算法。这种模块化结构被称为调度器类，它允许多种不同的可动态添加的调度算法并存，调度属于自己范畴的进程。每个调度器都有一个优先级，基础调度器会按照优先级顺序进程遍历调度类，拥有一个可执行进程的最高优先级的调度类胜出，去选择接下来要执行的程序。

2. 公平调度

CFS允许每个进程运行一段时间、循环轮转、选择运行最少的进程作为下一个运行的进程。nice值作为进程获得的处理器运行比的权重，nice值越低权重越高。每个进程都按照其权重在全部可行进程中所占比例的“时间片”来运行，任何进程所获的处理器时间是由它自己和其他所有可运行进程nice值的相对差值决定的。为了计算准确的时间片，CFS为完美多任务中的无限小调度周期的近似值设立了一个目标，称为目标延迟。

四、Linux调度的实现

CFS调度算法的实现，主要关注：

• 时间记账
• 进程选择
• 调度器入口
• 睡眠和唤醒

1. 时间记账

所有的调度器都必须对进程运行时间做记账。CFS通过时间记账确保每个进程只在公平分配给它的处理器时间内运行。

CFS使用调度器实体结构来追踪进程运行记账，该结构为进程描述符（struct task_struct的成员变量）：

struct sched_entity {
    /* For load-balancing: */
    struct load_weight      load;
    struct rb_node          run_node;
    struct list_head        group_node;
    unsigned int            on_rq;

    u64             exec_start;
    u64             sum_exec_runtime;
    u64             vruntime; // 虚拟实时
    u64             prev_sum_exec_runtime;

    u64             nr_migrations;

    struct sched_statistics     statistics;

#ifdef CONFIG_FAIR_GROUP_SCHED
    int             depth;
    struct sched_entity     *parent;
    /* rq on which this entity is (to be) queued: */
    struct cfs_rq           *cfs_rq;
    /* rq "owned" by this entity/group: */
    struct cfs_rq           *my_q;
    /* cached value of my_q->h_nr_running */
    unsigned long           runnable_weight;
#endif
};

vruntime变量存放进程的虚拟运行时间，经过了所有可运行进程总数的标准化（被加权的）。以ns为单位，和定时器节拍不相关。CFS使用vruntime来记录一个程序到底运行了多长时间以及它还应该再运行多久。

update_curr()函数实现了记账功能。是由系统定时器周期性调用的，无论进程处于可运行态，还是不可运行态。因此，vruntime可以准确地测量给定进程的运行时间，而且知道谁是应该被下一个运行的进程。

2. 进程选择

CFS算法的核心：选择具有最小的vruntime任务。

CFS使用红黑树（rbtree）来组织可运行进程队列，其节点的键值为可运行进程的虚拟运行时间vruntime，有利于迅速找到最小vruntime的进程（可通过__pick_next_entity()函数来访问红黑树最左的叶子即可，当然最左的叶子可能被缓存在rb_left_most字段中，可直接读取）。

另外，可通过enqueue_entity/dequeue_entity函数从红黑树中增加/删除进程。这两个函数都会调用update_curr()函数来更新所处理任务的运行时统计数据。

3. 调度器入口

进程调度的主要入口点是schedule()函数，是内核其他部分用于调用进程调度器的入口：选择哪个进程运行，何时将其投入运行。schedule()函数会通过pick_next_task()函数遍历调度类，找出优先级最高的调度类（struct sched_class），再通过调度类的pick_next_entity()函数（会调用__pick_next_entity()函数）来选择要执行的进程。

4. 睡眠和唤醒

休眠（被阻塞）的进程处于不可运行的状态。内核对其操作是：进程把自己标记称休眠状态，从可执行红黑树中删除，放入等待队列，然后调用schedule()选择和执行下一个进程。

唤醒：进程被设置为可执行状态，然后从等待队列中移到可执行红黑树中。

其中，等待队列是由等待某些事件发生的进程组成的简单链表。

image.png

五、抢占和上下文切换

上下文切换，也就是从一个可执行进程切换到另一个可执行进程，由context_switch函数处理。

用户抢占：

• 从系统返回用户空间时
• 从中断处理程序返回用户空间时

Linux完整地支持内核抢占，只要重新调度是安全的，内核就可以在任何时间抢占正在执行的任务。只要没有持有锁，内核就可以进行抢占。内核抢占主要发生在：

• 中断处理程序正在执行，且返回内科空间之前
• 内核代码再一次具有可抢占性时
• 如果内核中的任务显示调用schedule
• 如果内核中的任务阻塞

六、实时调度策略

普通的、非实时的调度策略是SCHED_NORMAL。

Linux提供两种实时调度策略：

• SCHED_FIFO：简单的、先入先出的调度算法，不使用时间片，优先级高于SCHED_NORMAL级的进程。一旦SCHED_FIFO级进程处于可执行状态，就会一直执行，知道阻塞或显示的释放处理器。不基于时间片，可以一直执行。只有更高优先级的SCHED_FIFO进程或SCHED_RR进程才能抢占SCHED_FIFO进程。多个同优先级的SCHED_FIFO进程会轮流执行，但也只能当前进程愿意让出处理器时才会退出。只要有SCHED_FIFO进程在执行，较低等级的进程就只能等待它变为不可运行状态后才有机会执行。
• SCHED_RR：一种实时轮流调度算法，进程会在耗尽事先分配的时间片后不再继续执行，是带有时间片的SCHED_FIFO。

Linux为实时调度策略提供一种软实时工作方式。也就是内核调度进程，尽力使进程在它的限定时间内运行，但内核不保证总能满足这些进程的要求。

对应的，硬实时系统保证在一定条件下，可以满足任何调度的要求。

七、与调度相关的系统调用

image.png