本文同步自（如浏览不正常请点击跳转）：https://zohead.com/archives/linux-kernel-learning-process-scheduling/ 接着上面进程基本概念的文章，进程调度器决定系统中什么进程需要运行，运行多长时间。Linux kernel 实现的是抢占式的时间片调度方式，而不是进程主动让出时间片的方式。 Linux 从 2.5 开始使用名为 O(1) 的调度器，它解决了 2.4 及之前早期的调度器中很多设计上就存在的问题，O(1) 就表示该算法可以在常数时间内完成工作。在 ULK3 对应的 2.6.11 内核中仍然在使用此调度器，它对于很大的服务器负载的情况是很理想的，但由于 O(1) 调度器对于延迟敏感的程序（被称为交互式进程）而言却有缺陷，因此从 2.6.23 内核开始 Linux 引入一种调度器类的框架，并且默认使用一种新的调度器：Completely Fair Scheduler（CFS）完全公平调度器，鉴于历史的车轮在前进着，本文就主要讨论 CFS 调度器了。 进程通常可以分为两类：I/O密集型 和 计算密集型。I/O密集型进程花费更多的时间在等待 I/O 请求上（不一定是磁盘I/O，也可以是键盘、网络 I/O 等），大多数的 GUI 程序都是 I/O密集型进程。计算密集型的进程则要求运行频率小些但运行时间更多，像各种加解密程序和 MATLAB 这种就是典型的计算密集型进程。一个好的调度策略应该能同时满足低延迟和高吞吐量，Linux 调度器会采取偏向I/O密集型进程的策略。 Linux kernel 实现了两种独立的进程优先级：一种是 nice 值，从 -20 到 +19，默认值为 0，越大的值表示优先级越低（表示你对其它进程更加 “nice”，哈哈），nice 值在所有 Unix 系统中是一个通用的进程优先级范围，运行 ps -el 可以看到进程的 nice 值；第二种是可配置的实时优先级，范围从 0 到 99，越大的值表示优先级越高，实时进程比普通进程的优先级高，Linux 根据 POSIX.1b Unix 标准实现了实现了实时优先级，运行 ps 时增加 rtprio 参数可以在 RTPRIO 栏中看到实时优先级（如果值为 - 表示不是实时进程）。 Linux 2.6.34 默认的 CFS 完全公平调度器并不像传统调度器那样，根据 nice 绝对值为相应的进程分配固定的时间片，它没有明确的时间片概念，而是根据每个进程的 nice 相对差异值作为权重得到进程可以运行的时间在处理器时间中的比例。CFS 设置了一个预定的 targeted latency 值作为调度持续时间来根据比例计算时间片，当然此值越小越接近完全公平。假设 targeted latency 值为 20 毫秒，系统中有两个进程 nice 值分别为 0 和 5，根据权重计算出来的时间片分别为 15 和 5 毫秒，当两个进程为 10 和 15 时，计算出来的仍然为 15 和 5 毫秒，因为 nice 值的相对差异值并没有变。在系统中进程不是特别多时，CFS 调度器可以做到接近完全公平，而进程数量特别多甚至接近无限时，每个进程获得的时间片将非常小，为了避免进程切换导致的开销，CFS 又规定了一个 minimum granularity 值作为每个进程最小的时间片，默认为 1 毫秒，也即即使进程无限，每个进程也最少能运行 1 毫秒的时间，因此进程特别多时 CFS 就不会那么公平了。 1、CFS调度器： CFS 调度器实现在 kernel/sched_fair.c 文件中，这在上面一篇博文：进程基本 中有简单的介绍的。CFS 使用 sched_entity 调度实体结构，task_struct 中就有这个成员，看看 sched_entity 的定义，它定义在 include/linux/sched.h 头文件中： 可以看到此结构中下面很大一部分是开启了 CONFIG_SCHEDSTATS 之后才有用的。其中 vruntime 为进程的虚拟运行时间（实际运行时间经可运行的进程个数进行权重计算后的结果），在理想的 CFS 环境中，处理器都处于理想状态，所有同级别的进程的 vruntime 值应该都相同。但实际上多处理器不能做到完美多任务，CFS 调度器就用 vruntime 记录进程的运行时间并得到它应当还要运行多长时间。 再看到下面会用到的 cfs_rq 运行队列属性的定义，在 kernel/sched.c 中定义： cfs_rq 中的 curr 字段即指向当前队列上正在运行的实体（如果没有则为 NULL 了），rq 字段即为 CPU 运行队列。 来看看 sched_entity 的 vruntime 是如何在 update_curr 函数中更新的： update_curr 会被系统定时器周期性的调用，进程转变为可运行或不可运行状态时都会被调用，而 update_curr 本身则调用 __update_curr 增加实际运行时间和 vruntime 虚拟运行时间。 由于实际情况下，每个进程的 vruntime 并不会像理想状况那样完全一样，CFS 调度器在需要调度时从运行队列里中取 vruntime 最小的那个进程来运行。CFS 调度器使用一个红黑树来管理可运行进程的列表，并用于快速查找最小的 vruntime 进程。 红黑树在 Linux 中被称为 rbtree，可以用于存储任意数据的节点，由特定的关键字来标识。sched_entity 调度实体中的 run_node 就是一个红黑树节点，cfs_rq 中的 rb_leftmost 即是红黑树最左边的节点（缓存在 cfs_rq 结构中以加快访问速度，这样可以避免遍历红黑树），最小的 vruntime 进程就在此节点上，如果找不到此进程（返回 NULL），CFS 唤醒 idle 任务。 看看将进程加到红黑树的实现： enqueue_entity 中更新了当前进程的 vruntime，并最终调用 __enqueue_entity 将进程加到红黑树中。__enqueue_entity 中先通过遍历找到正确位置，遍历过程中就能确定红黑树中最左边的节点是什么，然后设置红黑树中节点左右信息，调用 rb_link_node 添加节点，必要时更新 cfs_rq 中保存的最左边的节点缓存。 好吧，看了添加过程再看从红黑树中删除进程： 同样 dequeue_entity 先调用 update_curr 更新当前进程的 vruntime，删除的实际操作由 __dequeue_entity 来完成。__dequeue_entity 中判断如果最左边节点正是要删除的进程，必须更新最左边的节点缓存，然后调用 rb_erase 删除节点。 Linux 中进程调度入口是 schedule() 函数，定义在 kernel/sched.c 中。对于一个进程，schedule() 会先查找最高优先级的调度器类并调用此调度器类中的函数进行调度。看看 pick_next_task 的实现： 首先由于 Linux 普通进程默认使用 CFS 调度器，pick_next_task 先判断是不是所有进程都在 CFS 调度器中，如果是就直接调用 CFS 的 pick_next_task 函数节省遍历时间。sched_class_highest 的定义在上面也可以看到，就是 RT 调度器类，for_each_class 用于遍历调度器类。而其它类中找不到时，idle 调度器类的 pick_next_task 就返回一个有效 task_struct。在 CFS 调度器中 pick_next_task 会调用 pick_next_entity 函数选择下一个运行的进程。 2、睡眠与唤醒： 进程需要睡眠时，kernel 的处理大体如下：进程将自己标记为睡眠状态，将自己加到等待队列，从记录可运行进程的红黑树上删除自己，调用 schedule() 选择新进程来运行，schedule() 会调用 deactivate_task() 函数将进程从运行队列中移除。唤醒的过程则相反：进程被设置为可运行，从等待队列删除，重新加回到红黑树中。 等待队列在 kernel 中以 wait_queue_head_t 表示，定义在 include/linux/wait.h 头文件中，它其实是一个 __wait_queue_head 结构，下面的头文件中有一些经常用到的声明： 需要注意的是每个等待队列都需要可以在中断时被修改，因此操作等待队列之前必须获得一个自旋锁。而在实际使用中等待时需要处理竟态条件，为此 kernel 定义了几个很好用的等待条件的宏，为调用者减少操作，这些宏也是定义在上面的文件中。常用的有 wait_event 根据条件在队列上无限等待，wait_event_timeout 相对加了超时处理，它是调用 schedule_timeout 进行调度，wait_event_interruptible 即在等待时进程是可以响应信号之类的唤醒。 内核中的 completion 完成量机制也是基于等待队列的，用于等待某一操作结束。__wait_queue 结构的 task_list 成员通过双链表链接到 __wait_queue_head 中，__wait_queue 中的 private 成员指向等待进程的 task_struct。__wait_queue 中 […]