中国科学技术大学计算机系 陈香兰（0551－3606864） xlanchen@ustc.edu.cn Spring 2009 Linux内核源代码导读 中国科学技术大学计算机系 陈香兰（0551－3606864） xlanchen@ustc.edu.cn Spring 2009

进程调度 调度策略 调度算法 2018/12/8 Linux内核源代码导读

进程的分类 不同类型的进程有不同的调度需求 第一种分类： I/O-bound CPU-bound 频繁的进行I/O 计算密集型 需要大量的CPU时间进行运算 2018/12/8 Linux内核源代码导读

第二种分类 交互式进程（interactive process） 需要经常与用户交互，因此要花很多时间等待用户输入操作 响应时间要快，平均延迟要低于50~150ms 典型的交互式程序：shell、文本编辑程序、图形应用程序等 2018/12/8 Linux内核源代码导读

实时进程（real-time process） 批处理进程（batch process） 不必与用户交互，通常在后台运行 不必很快响应 典型的批处理程序：编译程序、科学计算 实时进程（real-time process） 有实时需求，不应被低优先级的进程阻塞 响应时间要短 典型的实时进程：视频/音频、机械控制等 2018/12/8 Linux内核源代码导读

Linux中的进程调度 Linux既支持普通的分时进程，也支持实时进程 Linux中的调度是多种调度策略和调度算法的混合。 什么是调度策略？ 是一组规则，它们决定什么时候以怎样的方式选择一个新进程运行 Linux的调度基于分时和优先级 随着版本的变化，分时技术在不断变化 优先级越来越复杂 2018/12/8 Linux内核源代码导读

Linux的进程根据优先级排队 Linux中进程的优先级是动态的 根据特定的算法计算出进程的优先级，用一个值表示 这个值表示把进程如何适当的分配给CPU Linux中进程的优先级是动态的 调度程序会根据进程的行为周期性的调整进程的优先级 较长时间未分配到CPU的进程，通常↑ 已经在CPU上运行了较长时间的进程，通常↓ 2018/12/8 Linux内核源代码导读

与调度相关的系统调用 nice getpriority/setpriority sched_getscheduler/sched_setscheduler sched_getparam/sched_setparam sched_yield sched_get_priority_min/sched_get_priority_max sched_rr_get_interval 2018/12/8 Linux内核源代码导读

调度算法 Linux 2.4的调度算法 Linux 2.6.17的调度算法（2.6.23之前） Linux 2.6.26的调度算法 需要遍历可运行队列，算法O(n) Epoch，基本时间片，动态优先级 Linux 2.6.17的调度算法（2.6.23之前） 采用双队列（Active；expire ），按照优先级组队，O(1) Linux 2.6.26的调度算法 非实时：CFS，vruntime，红黑树 实时：优先级队列 Linux进程可以指定该进程所采用的调度策略 调度算法根据进程的调度策略，采用不同的调度算法 2018/12/8 Linux内核源代码导读

Linux 2.6.26中的 调度策略：Policy，调度类型 在task_struct中，使用数据项policy来表达该进程采用的调度策略 Idle类型的任务负载权重最低 2018/12/8 Linux内核源代码导读

查看各个policy的使用情况 2018/12/8 Linux内核源代码导读

2018/12/8 Linux内核源代码导读

调度类型 阅读const struct sched_class，调度类 rt_sched_class fair_sched_class idle_sched_class 关于调度的描述， 参见sched_coding.txt和 sched-design-CFS.txt fair_sched_class idle_sched_class rt_sched_class 2018/12/8 Linux内核源代码导读

调度类接口举例 找到主要与运行队列有关的 Idle相关：idle_sched_class Fair相关 Rt相关 enqueue_task、dequeue_task Idle相关：idle_sched_class no enqueue/yield_task for idle tasks dequeue_task_idle Fair相关 enqueue_task_fair dequeue_task_fair Rt相关 enqueue_task_rt dequeue_task_rt 2018/12/8 Linux内核源代码导读

接口关系 2018/12/8 Linux内核源代码导读

2018/12/8 Linux内核源代码导读

Idle类特殊 2018/12/8 Linux内核源代码导读

Fair类 进而查看 1）enqueue_entity 2）__enqueue_entity （红黑树） 3）sched_entity结构 4） struct rq 5）struct cfs_rq Completely Fair Scheduler 完全公平调度 2018/12/8 Linux内核源代码导读

Rt类 进而查看： 1）enqueue_rt_entity 2）__enqueue_rt_entity 每个cpu有一个队列 3）sched_rt_entity 4）struct rq 5）struct rt_rq 6） struct rt_prio_array 2018/12/8 Linux内核源代码导读 优先级队列

激活一个任务 activate_task 相对的：deactivate_task 2018/12/8 Linux内核源代码导读

TASK_RUNNING状态的进程组织 每个cpu有一个运行队列 非实时任务和实时任务各有一个子队列 2018/12/8 Linux内核源代码导读

运行队列数据结构 2018/12/8 Linux内核源代码导读

struct cfs_rq 红黑树 2018/12/8 Linux内核源代码导读 ……

struct rt_rq 基于优先级的运行队列 …… 2018/12/8 Linux内核源代码导读

调度实体 公平调度实体：sched_entity 3部分，其中调度统计和组公平调度的不看 2018/12/8 Linux内核源代码导读

实时调度实体sched_rt_entity 其中组实时调度信息不看 2018/12/8 Linux内核源代码导读

阅读2.6.26的schedule函数 调度函数的关键： 调度算法的关键 入列 CFS根据vruntime的值入列，其关键在于vruntime值的计算 RT根据优先级入列 2018/12/8 Linux内核源代码导读

CFS算法 就绪队列的组织：红黑树 进程在红黑树中的键值的调整 阅读入列操作enqueue_entity 2018/12/8 Linux内核源代码导读

Linux2.6.26中的优先级范围 优先数范围为0～139，其中0～99为实时优先数 普通任务和批处理任务的优先数在100～139之间 优先数越大，优先级越低。 2018/12/8 Linux内核源代码导读

Linux2.6.26中的nice值 Nice值用来调整进程的优先级 Nice值的范围在-20~19之间。 2018/12/8

Linux2.6.26中的USER_PRIO 2018/12/8 Linux内核源代码导读

CFS进程的优先级 prio：当前有效优先级 static_prio：根据nice设置 normal_prio：常规优先级 Init_task 2018/12/8 Linux内核源代码导读

在rt_mutex_setprio时，设置任务的当前优先级 在fork时，根据sched_fork 在wake_up_new_task时， 在rt_mutex_setprio时，设置任务的当前优先级 2018/12/8 Linux内核源代码导读

在set_user_nice时， 在__setscheduler中， 在init_idle中 2018/12/8 Linux内核源代码导读

2018/12/8 Linux内核源代码导读

schedule_tick 被时钟中断按照滴答时间单位在关中断状态下调用 在fork中，随着父进程时间片的变化，也会被调用 调度时钟的稳定性 由配置参数CONFIG_HAVE_UNSTABLE_SCHED_CLOCK来确定 假定是稳定的 2018/12/8 Linux内核源代码导读

sched_clock_tick（空函数） update_rq_clock 获得就绪队列的当前 时钟值。 参见源代码 scheduler_tick sched_clock_tick（空函数） update_rq_clock 获得就绪队列的当前 时钟值。 参见源代码 update_cpu_load 统计CPU负载信息 当前任务所在 调度类型的 task_tick方法 例如task_tick_fair entity_tick update_curr 2018/12/8 Linux内核源代码导读

Thanks！ The end.

以下内容作为参考：2.4的调度算法 epoch linux调度算法把CPU时间划分为时期（epoch） 在一个单独的时期内，每个进程有一个指定的时间片 一个进程用完它的时间片时，就会被强占 只要进程的时间片没有用完，就可以被多次调度运行 当所有的进程用完它的时间片的时候，一个时期才结束，此时要重新计算所有进程的时间片，并重新开始一个新的时期 2018/12/8 Linux内核源代码导读

基本时间片（base time quantum） 每个进程有一个基本时间片 可以通过nice、setpriority系统调用调整进程的基本时间片 新进程总是继承父进程的基本时间片 时间片的计算公式： nice缺省为0（在-20到19之间选择） 通常，基本时间片的值 为6，由于时钟中断大约10ms左右， 因此基本时间片的长度大约60ms 2018/12/8 Linux内核源代码导读

2.4调度程序使用的数据结构 进程描述符中： need_resched：是否需要调度 policy：调度策略 普通的分时进程 先入先出的实时进程 循环轮转的实时进程 当一个进程自动放弃运行时设置 2018/12/8 Linux内核源代码导读

nice：对时间片进行调节 rt_priority：实时进程的静态优先级，普通进程不用 counter：当前剩余时间片 新时期开始时根据上述计算公式计算 每次时钟中断发生，时间片都会-1，直到为0（则请求调度） 创建一个新的进程时，子进程会继承父进程的一半剩余时间片 nice：对时间片进行调节 2018/12/8 Linux内核源代码导读

schedule函数 schedule函数实现调度 目的：在运行队列中找到一个进程，把CPU分配给它 调用方法： 直接调用，如sleep_on 松散调用，根据need_resched标记 阅读schedule函数，了解如何区分实时和非实时进程 2018/12/8 Linux内核源代码导读

2.4调度算法的性能 不适合进程数量很大的情况 对高负载系统来说，预定义的时间片太长 对于I/O密集型的程序不是很有利 重新计算所有进程的动态优先级很耗时 对高负载系统来说，预定义的时间片太长 对于I/O密集型的程序不是很有利 对实时应用的支持是微弱的 2018/12/8 Linux内核源代码导读

2.6.17中的优先级队列 优先级队列的组织 双队列：active和expired 2018/12/8 Linux内核源代码导读