前言

调度程序负责决定将哪个进程投入运行,何时运以及运行多长时间,进程调度程序可看做在可运行态进程之间分配有限处理器时间资源的内核子系统。

一、多任务

  1. 多任务系统分为非抢占式多任务抢占式多任务
  2. 强制挂起其他进程的动作叫做抢占
  3. 进程在被抢占之前能够运行的预先设置好的时间称为时间片

二、Linux 的调度

Linux 2.之前的内核调度程序都非常简陋,在2.5开发系列内核中,采用了O(1)调度程序。在2.6.23内核中使用CFS(完全公平调度算法)。

三、策略

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

  • 进程可以分为I/O消耗型处理器消耗型进程。
  • I/O消耗型进程更多时间是在等待更多的I/O 操作。
  • 处理器消费型进程大多时间是花费在执行代码上

2、进程优先级

  • 调度算法中最基本的就是基于优先级的调度。
  • Linux 的优先级分为两种:
    • nice值:默认为0,取值-20~19。值越小优先级越高
    • 实时优先级:可配置,0~99,值越高大先级越高。
    • 实时优先级和nice值是两个互不相交的范畴。

3、时间片

时间片是一个数值,它表示进程抢占前所能运行的时间。
I/O消耗型不需要很长的时间片,处理器消耗型需要较长的时间片。

四、Linux 调度算法

1、调度器类

  • Linux 调度器是以模块方式提供的,这种模块化结构被称为调度器类
  • 完全公平调度算法(CFS)是一个针对普通进程的调度类。算法实现定义在kernel/sched_fair.c中。

2、Unix系统中的进程调度

在 Unix 系统中,优先级以 nice 值形式输出给用户空间,但是会有以下四个问题:

  1. 要将 nice 映射到时间片,就要将 nice 单位值对应到处理器的绝对时间,这样做导致进程切换无法最优化。(高nice值[低优先]的进程往往是后台进程,计算密集型,需要更多的时间片,但是这样会分配较少时间片)
  2. 相对 nice 值,把进程的 nice 值减小1,所带来的效果极大取决于其 nice 的初始值。
  3. 如果执行 nice 值映射到时间片,我们需要分配一个能在内核测试范围内的时间片。
  4. 基于优先级的调度器为了优化交互任务而唤醒相关进程的问题。提升进程优先级打破公平原则,损害其他进程利益。

nice 几何增长可以解决第二个问题,nice值到时间片与节拍器分离可解决第三个问题,但是回避了实质问题——分绝对时间片引发的固定切换频率,给公平性造成了很大变数。
CFS 摒弃时间片,采用分配给进程处理器使用权重确保了进程调度中能有恒定公平性,而将切换频率置于不断变动中。

3、公平调度

  1. CFS出发点:进程调度的效果应如同系统具备一个理想中的完美多任务处理器。
  2. CFS允许每个进程允许一段时间,循环轮转选择运行最少的进程作为下一个运行进程。
  3. nice 值对时间片的的作用不再是算术加权而是几何加权。
  4. CFS 称为公平调度器是因为它确保给每个进程公平的处理器使用比。

4、Linux 调度的实现

这部分文章比较重要这里我们单独拎出来讲