README.md

📔 第 04 章 进程调度 学习笔记

1. 多任务

调度程序负责决定将哪个进程投入运行，何时运行以及运行多长时间。

进程调度程序（简称调度程序）可看作是可运行态进程之间分配有限的处理器时间资源的内核子系统。

多任务操作系统就是能同时并发地交互执行多个进程的操作系统。

现在的操作系统都是多任务操作系统，通过一个管s理程序去管理多个任务可以同时运行。多任务系统分为：

• 非抢占式多任务

  • 除非进程自己主动停止，否则会一直执行。
  • 让步：进程主动挂起自己的动作。
  • 缺点
    • 调度程序无法对每个进程该执行多长时间做出统一规定。
    • 对于不做出让步的悬挂进程会使进程崩溃。

• 抢占式多任务：Linux的调度程序会决定什么时候停止一个进程的执行，便于其它进程可以执行。

  • 抢占：强制的挂起工作。
  • 时间片：分配给每个可运行进程的处理器时间段

2. 进程调度的策略

策略决定调度程序何时让进程运行。调度器的策略一定程序上，还负责优化使用处理器时间。

2.1 I/O消耗型和处理器消耗型的进程

进程分为两种：

• I/O消耗型

  • 大部分时间用来提交I/O请求或在等待更多的I/O强求时最后总会阻塞。

• 处理器消耗型

  • 进程把时间大多用在执行代码上。
  • 进程调度策略是降低调度频率，而延长其运行时间。

进程调度策略通常需要在两个矛盾的目标中间寻找平衡：

• 进程响应迅速（响应时间短）
• 最大利用率（高吞吐量）

在Linux中，为了保证交互式应用和桌面系统的性能，所以倾向于调度I/O消耗型进程。

2.2 进程优先级

调度算法中最基本的一类是基于优先级的调度：从进程的价值和其对处理器时间的需求进行分级。

• 优先级高的进程先运行，低的后运行，相同优先级的进程按轮转方式进行调度。

Linux采用两种优先级范围：

• nice值：范围从 -20 ～ +19，默认值为0。值越大优先级更低。

  • Linux中nice值表示时间片的比例
  • Mac OS X中，nice值表示分配给进程的时间片的绝对值。

• 实时优先级：可配置的值。默认范围：0～99。值越大进程的优先级越高。

2.3 时间片

时间片是一个数值，表明进程在被抢占前所能持续运行的时间。时间片的设置长短不是容易的事；

• 过长会导致系统对交互的响应表现欠佳。
• 太短会明显增大进程切换带来的处理器耗时。

Linux中的CFS调度器没有直接分配时间片到进程，奖处理器的使用比例一部分划分给进程。此时进程所获得的处理器时间其实和负载有关。

由于Linux系统是抢占式的，所以使用了新的CFS调度器后，其抢占式取决于心的课运行程序消耗了多少处理器使用比。

3. Linux调度算法

3.1 调度器类

Linux调度器是以模块方式提供。模块方式的目的：允许不同类型的进程可以有针对性地选择调度算法。

模块化结构称为调度器类。允许多种不同的可动态添加的调度算法并存，调度属于自己范畴的进程。

完全公平调度（CFS）是针对普通进程的调度类，在Linux中称为 SCHED_NORMAL（在POSIX中称为 SCHED_OTHER），CFS算法实现定义在 kernel/sched_fair.c 文件中。

3.2 Unix系统中的进程调度

在Unix系统中，优先级以nice值形式输出到用户空间。但在现实中页存在几个反常的问题：

• 如果遇到同时运行两个同等低优先级的进程时，希望能各自获取一半的处理器时间。但是这分配方式背离了初始设计。

  • 给定高nice值（低优先级）的进程往往是后台进程，且多是计算密集型。而普通优先级的进程则更多是前台用户任务。

• 如果一个进程遇到两种优先级时：

  • 实时优先级高于nice值。

• 如果一个进程同时有两种优先级时：

  • 不会存在该情况。两者不可能同时出现。

5. Linux调度的实现

CFS调度算法的相关代码位于 kernel/sched_fair.c 中。

5.1 时间记账

所有的调度器必须对进程运行时间做记账。

• 调度器实体结构

  • CFS不再有时间片的概念，但它必须维护每个进程运行的时间记账。
  • 定义在 <linux/sched.h> 的struct_sched_entity 中。

  struct sched_entity {
      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; // 存放
      // ....
  }

  • 调度器实体结构作为一个名为 se 的成员变量，嵌入到进程描述符 struct task_struct 中。

• 虚拟实时

  • vruntime 变量存放进程的虚拟运行时间。
  • 单位以 ns 为单位。
  • CFS使用 vruntime 变量来记录一个程序到底运行了多长时间以及它还应该再运行多久。

5.2 进程选择

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

CFS使用红黑树来组织可运行进程队列，并利用其迅速知道最小vruntime值的进程。Linux中红黑树称为 rbtree，是一个自平衡二叉搜索树。

对于如何实现选择具有最小 vruntime 值的进程，步骤如下：

• 挑选下一个任务

  • CFS调度器选取待运行的下一个进程，是所有进程中vruntime值最小的那个，对应树中的最左侧的叶子节点。

  • 这个过程的函数是 ： __pick_next_entity()

    // 函数返回指向下一个可运行进程的指针，或者没有时返回NULL
    static struct sched_entity *__pick_next_entity(struct cfs_rq *cfs_rq)
    {
        struct rb_node *left = cfs_rq->rb_leftmost;
        if (!left)
        {
            return NULL;
        }
    
        return rb_entry(left, struct sched_entity, run_node);
    }

  • __pick_next_entity() 函数本身并不会遍历知道最左叶子节点，但值已缓存在 rb_leftmost 字段中。如果函数返回NULL，表示没有最左叶子节点。

• 向树中加入进程

  • 过程发生在进程变为可运行状态（被唤醒）或者通过 fork() 调用第一次创建进程时。
  • enqueue_entity() 函数调用更新运行时间和其它统计数据，然后调用 __enqueue_entity() 函数将数据插入到红黑树中。

• 从树中删除进程

  • 发生在进程堵塞（变为不可运行状态）或者终止时（结束运行）。
  • 和添加进程类似，rbtree实现了 rb_erase() 函数，所以该函数会更新rb_leftmost缓存。

5.3 调度器入口

进度调度的主要入口点时函数是 schedule() ，定义在 kernel/sched.c 中。也是内核其它部分用于调用进程调度器的入口：选择哪个进程可以运行，何时将其投入运行。

schedule() 函数会调用 pick_next_task()。

• pick_next_task() 会以优先级为序，从高到低，依次检查每一个调度类，并从最高优先级的调度类中，选择最高优先级的进程。

5.4 休眠和唤醒

休眠（被阻塞）的进程处于一个特殊的不可执行状态。

• 休眠

  • 内核中进程把自己标记成休眠状态，从可执行红黑树中移出，放入等待队列，然后调用 schedule() 选择和执行一个进程。
  • 两种进程状态：
    • TASK_INTERRUPTIBLE：处于此状态的进程会忽略信号。
    • TASK_UNINTERRUPTIBLE：处于此状态的进程如果收到一个信号，会被提前唤醒并响应该信号。

• 唤醒

  • 和休眠相反，进程被设置为可执行状态，然后再从等待队列中移到可执行红黑树中。

对于两种状态的进程位于同一个等待队列，等待某些事件，不能运行。等待队列是由某些事件发生的进程组成的简单链表。

6. 抢占和上下文切换

上下文切换：从一个执行过程切换到另一个可执行过程。由定义在 kernel/sched.c 中的 context_switch() 函数负责处理。

context_switch() 完成两个工作：

• 调用声明 <asm/mmu_context.h> 中 switch_mm()，该函数负责把虚拟内存从上一个进程映射切换到新进程中。
• 调用声明在 <asm/system.h> 中的 switch_to()，该函数负责从上一个进程的处理器状态切换到新进程的处理器状态。

每个进程都包含一个 need_resched 标志，因为访问进程描述符内的数值要比访问一个全局变量快。

6.1 用户抢占

• 内核即将返回用户空间时，如果 need_resched 标志被设置，会导致 schedule() 被调用，此时会发生用户抢占。

• 内核不管在中断处理程序还是系统调用后返回，都会检查 need_resched 标志。

  • 如果被设置，内核会选择一个其它进程投入运行。

• 用户抢占在以下情况时产生：

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

6.2 内核抢占

Linux完整地支持内核抢占。内核中的各任务是以协作方式调度的。只要重新调度是安全的，内核就可以在任何时间抢占正在执行的任务。

• 内核抢占在以下情况时发生：
  • 中断处理程序正在执行，且返回内核空间之前
  • 内核代码再一次具有可抢占性时
  • 如果内核中的任务显式地调用 schedule()
  • 如果内核中的任务阻塞，会导致调用 schedule()

7. 实时调度策略

普通的、非实时的调度策略是 SCHED_NORMAL，对于实时调度策略实现定义为在 kernel/sched_rt.c 文件中，Linux提供了两种实时调度策略：

• SCHED_FIFO

  • 简单、先入先出的调度算法。
  • 不使用时间片。
  • 如果遇到两个或者更多同优先级的 SCHED_FIFO级进程时，轮流执行。

• SCHED_RR

  • 带有时间片的 SCHED_FIFO
  • 实时轮流调度算法
  • 时间片只是重新调度同一优先级的进程
  • 对于SCHED_FIFO进程，高优先级总是立即抢占低优先级，但低优先级进程决不能抢占 SCHED_RR 任务，即使时间片耗尽。

两种调度策略中的算法实现的是静态优先级。内核不为实时进程计算动态优先级。

Linux的实时调度算法也提供了软实时工作方式.

• 软实时：内核调度进程，尽力使进程在限定时间到来前运行，但内核不保证总能满足这些进程的要求。
• 硬实时：保证在一定条件下，可以满足任何调度的要求。

实时优先级范围从 0 到 MAX_RT_PRIO - 1。

• 默认情况下，MAX_RT_PRIO 为 100（0 ～ 99）。
• SCHED_NORMAL 级进程的nice值共享这个范围：MAX_RT_PRIO 到 MAX_RT_PRIO + 40。

8. 与调度相关的系统调用

Linux提供了系统调用族，用于管理与调度程序相关的参数。

列举几个系统调用：

系统调用	描述
nice()	设置进程的nice值
sched_setscheduler()	设置进程的调度策略
sched_getscheduler()	获取进程的调度策略
sched_setparam()	设置进程的实时优先级
sched_getparam()	获取进程的实时优先级
sched_get_priority_max()	获取实时优先级的的最大值
sched_get_priority_min()	获取实时优先级的的最小值
sched_rr_get_interval()	获取进程的时间片值
sched_setaffinity()	设置进程的处理器的亲和力
sched_getaffinity()	获取进程的处理器的亲和力
sched_yield()	暂时让出处理器

8.1 与调度策略和优先级相关的系统调用

• sched_setscheduler() 和 sched_getscheduler() 的实现由许多参数检查、初始化和清理构成。

  • 主要任务：读取或改写进程 task_struct 的 policy 和 rt_priority 的值。

• sched_setparam() 和 sched_getparam() 获取封装在 sched_param 特殊结构体的 rt_priority中。

• nice() 调用内核的 set_user_nice() 函数，而后者设置进程的 task_struct 的static_prio 和 prio值。

8.2 与处理器绑定有关的系统调用

Linux调度程序提供了强制的处理器绑定（processor affinity）机制。

• sched_setaffinity() 和 sched_getaffinity() 的值保存在进程 task_struct 的cpus_allowed 这个位掩`码标识中。

进程只运行在指定处理器上，对处理器的指定是由该进程描述符的 cpus_allowed 域设置的。

8.3 放弃处理器时间

Linux通过 sched_yield() 系统调用，提供了一种让进程显式地处理器时间让给其它等待执行进程的机制。

• 通过将进程从活动队列中（因为进程正在执行，所以肯定位于此队列中）移动到过期队列中实现的。

在Linux内核代码中，可以直接调用 yield()，先要确定给定进程确实处于可执行状态，再调用 sched_yield()。在用户空间的应用程序则直接调用 sched_yield() 即可。