第4章 进程调度

0. 总结

• 调度：调度是一个平衡的过程。一方面，它要保证各个运行的进程能够最大限度的使用CP；另一方面，保证各个进程能公平的使用CPU。

• 调度功能：决定哪个进程运行以及进程运行多长时间。

• 调度实现原理：与进程的优先级有关

• Linux上调度实现的方法：O（1）的调度算法

• 调度相关的系统调用

4.1 多任务

• 能同时并发地交互执行多个进程。

• 非抢占式多任务：主动停止运行。

• 抢占式多任务：进程时间片。

4.2 Linux的进程调度

• O(1)拥有数以十计的多处理器的环境，但缺少交互进程。

4.3 策略

• 决定调度程序在何时让进程运行。

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

• I/O消耗型：大多时间在提交或等待I/O请求。

• 处理器消耗型：大多时间在执行代码。不属于I/O驱动类型。

4.3.2 进程优先级

• 相同优先级按照轮转方式进行调度。

• 调度程序总是选择时间片未用尽且优先级高的进程运行。

• Linux两种不同的优先级范围：

nice值：-20~+19，默认0，值越大优先级越低。

实时优先级：可配置，范围0~99，值越大与优先级越大。

4.3.3 时间片

• nice值作为权重将调整进程所使用的处理器时间使用比。

• I/O消耗型：不需要长的时间片。

• 处理器消耗型：需要越长越好的时间片。

4.3.4 调度策略的活动

• 文字编辑程序显然是 1/0 消耗型的，因为它大部分时间都在等待用户的键盘输入〈无论用户的输入速度有多快，都不可能赶上处理的速度λ 用户总是希望按下键系统就能马上响应。

• 视频编码程序是处理器消耗型的。

4.4 Linux调度算法

4.4.1 调度器类

• 以模块方式提供的，这样做的目的是允许不同类型的进程可以有针对性地选
  
  择调度算哉。

4.4.2 Unix系统中的进程调度

4.4.3 公平调度

• CFS的做怯是允许每个进程运行一段时间、循环轮转、选择运行最少的进程作为下一个运行进程，而不再采用分配给每个进程时间片的做法了，在所有可运行进程总数基础上计算出一个进程应该运行多久。 - -

• nice 值在 CFS 中被
  
  作为进程获得的处理器运行比的权重：越高的nice 值（越低的优先级）进程在得更低的处理器
  
  使用权重。

• 可运行进程数量趋于无穷，每个最少也能获得 lms 的运行时间。

• 任何进程所获得的处理器时间是由它自己和其他所有可运行进程nice 值的相对差值决定的。

4.5 Linux调度的实现

4.5.1 时间记账

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

• CFS 使用调度器实体结构（定义在文件＜linux/sched.h＞的 struct_sched _entity 中）来追踪进程运行记账。

• CFS 使用 vruntime 变量来记录一个程序到底运行了多长时间以及它还应该再运行多久。

• 定义在kemeVsched_fair.c 文件中的 update_curr(）函数实现了该记账功能。

• update_ currO 计算了当前进程的执行时间，并且将其存放在变量delta_exec 中，update_ curr（）是囱系统定时器周期性调用。

4.5.2 进程选择

• 红黑树rbtree——自平衡二叉搜索树

1.挑选下一个任务

• 你从树的根节点沿着左边的子节点向下找，一直找到叶子节点，你便找到了其vruntime 值最小的那个进程。

2.向树中加入进程

• 发生在进程变为可运行状态（被唤醒〉或者是通过fork（）调用第一次创建进程时。

• 调用＿enqueue_entity（）进行繁重的插入操作，把数据项真正插入到红黑树中。

3.从树中删除进程

• 发生在进程堵塞（变为不可运行态〉或者终止时（结束运行〉。

• 由辅助函数＿dequeue_entityO 完成的。

4.5.3 调度器入口

• 主要入口点是函数schedule（），它定义在文件kemel/sched.c中。

4.5.4 睡眠和唤醒

• 睡眠：为了等待一些事件。

• 内核的操作都相同 2 进程把自己标记成休眠状态，从可执行红黑树中移出，放入等待队列，然后调用 schedule（）选择和执行一个其他进程。

• 唤醒的过程刚好相反进程被设置为可执行状态，然后再从等待队列中移到可执行红黑树中。

4.6 抢占和上下文切换

• 上下文切换，也就是从一个可执行进程切换到另一个可执行进程，由定义在 kernel/ sched.c 中
  
  的 context_switch（）函数负责处理。

• ．每当一个新的进程被选出来准备投入运行的时候， schedule()就会调用该函数。两项基本的工作：

调用声明在 ＜asm/mmu_ context.h＞中的 switch_mm()

调用声明在 <asm/system.h> 中的 switch_to()

4.6.1 用户抢占

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

从系统调返回用户空间时；

从中断处理程序返回用户空间时；

4.6.2 内核抢占

• 内核抢占会发生在：

中断处理程序正在执行，且返回内核空间之前

内核代码再一次具有可抢占性

如果内核中的任务显式地调用 schedule()

如果内核中的任务阻塞（这同样也会导敖调用 schedule()

4.7 实时调度策略

两种策略

SCHED_FIFO和 SCHED_RR

SCHED_FIFO 实现了一种简单的、先入先出的调度算怯

SCHED_RR 是带有时闹片的 SCHED_FIFO，一种实时轮流调度算挂．

4.8 与调度相关的系统调用

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

• sched_setparam（）和sched__getparam（）分别用于设置和获取进程的实时优先级

• nice（）函数会调用内核的 set_ user_ nice（）函数，这个函数会设置进程的 task_struct 的 static_prio 和prio 值。

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

-强制指定“这个进程无论如何都必须在这些处理器上运行”。

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

4.8.3 放弃处理器时间

• 通过 sched_yieldO 系统调用，提供了一种让进程显式地将处理器时间让给其他等待执行进程的机制。

• 先要确定给定进程确实处于可执行状态，然后再调用 sched__yield() o 用户空间的应用程序直接使用 sched__yield（）系统调用就可以了。