Process Scheduling based on Linux3.2 孟宁 电话： 孟宁 V5 ： 主页： 地址：苏州工业园区独墅湖高等教育区仁爱路 166 号明德楼 A302 室 2012 年 5 月
进程的分类 ♦ 不同类型的进程有不同的调度需求 ♦ 第一种分类： –I/O-bound 频繁的进行 I/O 通常会花费很多时间等待 I/O 操作的完成 –CPU-bound 计算密集型 需要大量的 CPU 时间进行运算
进程的分类 ♦ 第二种分类 – 批处理进程（ batch process ） 不必与用户交互，通常在后台运行 不必很快响应 典型的批处理程序：编译程序、科学计算 – 实时进程（ real-time process ） 有实时需求，不应被低优先级的进程阻塞 响应时间要短、要稳定 典型的实时进程：视频 / 音频、机械控制等 – 交互式进程（ interactive process ） 需要经常与用户交互，因此要花很多时间等待用户输入操作 响应时间要快，平均延迟要低于 50~150ms 典型的交互式程序： shell 、文本编辑程序、图形应用程序等
Linux 中的进程调度 ♦Linux 既支持普通的分时进程，也支持实时 进程 ♦Linux 中的调度是多种调度策略和调度算法 的混合。 ♦ 什么是调度策略？ – 是一组规则，它们决定什么时候以怎样的方式 选择一个新进程运行 ♦Linux 的调度基于分时和优先级 – 随着版本的变化，分时技术在不断变化
Linux 中的进程调度 ♦Linux 的进程根据优先级排队 – 根据特定的算法计算出进程的优先级，用一个 值表示 – 这个值表示把进程如何适当的分配给 CPU ♦Linux 中进程的优先级是动态的 – 调度程序会根据进程的行为周期性的调整进程 的优先级 较长时间未分配到 CPU 的进程，通常 ↑ 已经在 CPU 上运行了较长时间的进程，通常 ↓
与进程调度相关的系统调用 ♦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
进程调度算法 ♦Linux 2.4 的调度算法 – 需要遍历可运行队列，算法 O(n) –Epoch ，基本时间片，动态优先级 ♦Linux 的调度算法（ 之前） – 采用双队列（ Active ； expire ），按照优先级组队， O(1) ♦Linux 的调度算法 – 非实时： CFS ， vruntime ，红黑树 – 实时：优先级队列 ♦Linux 进程可以指定该进程所采用的调度策略 ♦ 调度算法根据进程的调度策略，采用不同的调度算法
schedule 函数 ♦schedule 函数实现调度 ♦ 目的：在运行队列中找到一个进程，把 CPU 分配给它 ♦ 调用方法： – 直接调用，如 sleep_on – 松散调用，根据 need_resched 标记
调度的时机 ♦ 调度时机来临时，内核或驱动将调用 schedule() ♦ 在 Linux 中调度的时机主要有： –current 的状态从 running 转换为其他状态时，如： 1 ）进程终止。 exit() 在最后调用 schedule() 。 2 ）进程因某种原因进入等待状态。 比较常见的就是进程调用 nanosleep() 或者 wait 系列的系统调用。 此外，在设备驱动程序中，最常见的原因就是 驱动引发一次 I/O 操作后，为等待 I/O 操作的结 束而进入等待状态。多数情况下，驱动会直接 调用 schedule() 。
调度的时机 – 当前进程的时间片用完时。 时间片是否用完，由时钟中断处理程序进行判断。 若到期，就将 current 的 need_resched 位置 1 。 返回用户态时，根据 need_resched 调用 schedule() – 进程从中断、异常、系统调用状态（即内核态） 返回时。 若在中断、异常、系统调用中， current 的 need_resched 被置 1 ，都会导致进程调度。 包括上述时钟中断。
谢谢大家！ 把握方向、脚踏实地； 顺势而为、随遇而安。 参考资料： 《深入理解 Linux 内核》第三版