1 前言

1.1 进程调度

内存中保存了对每个进程的唯一描述, 并通过若干结构与其他进程连接起来.

调度器面对的情形就是这样, 其任务是在程序之间共享CPU时间, 创造并行执行的错觉, 该任务分为两个不同的部分, 其中一个涉及调度策略, 另外一个涉及上下文切换.

1.2 进程的分类

linux把进程区分为实时进程和非实时进程, 其中非实时进程进一步划分为交互式进程和批处理进程

类型	描述	示例
交互式进程(interactive process)	此类进程经常与用户进行交互, 因此需要花费很多时间等待键盘和鼠标操作. 当接受了用户的输入后, 进程必须很快被唤醒, 否则用户会感觉系统反应迟钝	shell, 文本编辑程序和图形应用程序
批处理进程(batch process)	此类进程不必与用户交互, 因此经常在后台运行. 因为这样的进程不必很快相应, 因此常受到调度程序的怠慢	程序语言的编译程序, 数据库搜索引擎以及科学计算
实时进程(real-time process)	这些进程由很强的调度需要, 这样的进程绝不会被低优先级的进程阻塞. 并且他们的响应时间要尽可能的短	视频音频应用程序, 机器人控制程序以及从物理传感器上收集数据的程序

在linux中, 调度算法可以明确的确认所有实时进程的身份, 但是没办法区分交互式程序和批处理程序, linux2.6的调度程序实现了基于进程过去行为的启发式算法, 以确定进程应该被当做交互式进程还是批处理进程. 当然与批处理进程相比, 调度程序有偏爱交互式进程的倾向

1.3 不同进程采用不同的调度策略

根据进程的不同分类Linux采用不同的调度策略.

• 对于实时进程，采用FIFO或者Round Robin的调度策略.
• 对于普通进程，则需要区分交互式和批处理式的不同。传统Linux调度器提高交互式应用的优先级，使得它们能更快地被调度。而CFS和RSDL等新的调度器的核心思想是”完全公平”。这个设计理念不仅大大简化了调度器的代码复杂度，还对各种调度需求的提供了更完美的支持.

注意Linux通过将进程和线程调度视为一个，同时包含二者。进程可以看做是单个线程，但是进程可以包含共享一定资源（代码和/或数据）的多个线程。因此进程调度也包含了线程调度的功能.

目前非实时进程的调度策略比较简单, 因为实时进程值只要求尽可能快的被响应, 基于优先级, 每个进程根据它重要程度的不同被赋予不同的优先级，调度器在每次调度时, 总选择优先级最高的进程开始执行. 低优先级不可能抢占高优先级, 因此FIFO或者Round Robin的调度策略即可满足实时进程调度的需求.

1.4 linux调度器的演变

一开始的调度器是复杂度为O(n)的始调度算法(实际上每次会遍历所有任务，所以复杂度为O(n)), 这个算法的缺点是当内核中有很多任务时，调度器本身就会耗费不少时间，所以，从linux2.5开始引入赫赫有名的O(1)O(1)调度器

然而，linux是集全球很多程序员的聪明才智而发展起来的超级内核，没有最好，只有更好，在O(1)调度器风光了没几天就又被另一个更优秀的调度器取代了，它就是CFS调度器Completely Fair Scheduler. 这个也是在2.6内核中引入的，具体为2.6.23，即从此版本开始，内核使用CFS作为它的默认调度器，O(1)调度器被抛弃了。

所以完全有理由相信，后续如果再会出现一个更优秀的调度器，CFS也不会幸免。因为linux只要最好的那个。

2 O(n)的始调度算法

2.1 Linux2.4之前的内核调度器

早期的Linux进程调度器使用了最低的设计，它显然不关注具有很多处理器的大型架构，更不用说是超线程了。

Linux调度器使用了环形队列用于可运行的任务管理, 使用循环调度策略.

此调度器添加和删除进程效率很高（具有保护结构的锁）。简而言之，该调度器并不复杂但是简单快捷.

Linux版本2.2引入了调度类的概念，允许针对实时任务、非抢占式任务、非实时任务的调度策略。调度器还包括对称多处理 (SMP) 支持。

2.2 Linux2.4的调度器

2.2.1 概述

在Linux2.4.18中(linux-2.5)之前的内核, 当很多任务都处于活动状态时, 调度器有很明显的限制. 这是由于调度器是使用一个复杂度为 O(n)的算法实现的.

调度器采用基于优先级的设计，这个调度器和Linus在1992年发布的调度器没有大的区别。该调度器的pick next算法非常简单：对runqueue中所有进程的优先级进行依次进行比较，选择最高优先级的进程作为下一个被调度的进程。(Runqueue是Linux 内核中保存所有就绪进程的队列). pick next用来指从所有候选进程中挑选下一个要被调度的进程的过程。

这种调度算法非常简单易懂: 在每次进程切换时, 内核扫描可运行进程的链表, 计算优先级,然胡选择”最佳”进程来运行.

在这种调度器中, 调度任务所花费的时间是一个系统中任务个数的函数. 换而言之, 活动的任务越多, 调度任务所花费的时间越长. 在任务负载非常重时, 处理器会因调度消耗掉大量的时间, 用于任务本身的时间就非常少了。因此，这个算法缺乏可伸缩性

2.2.2 详情

每个进程被创建时都被赋予一个时间片。时钟中断递减当前运行进程的时间片，当进程的时间片被用完时，它必须等待重新赋予时间片才能有机会运行。Linux2.4调度器保证只有当所有RUNNING进程的时间片都被用完之后，才对所有进程重新分配时间片。这段时间被称为一个epoch。这种设计保证了每个进程都有机会得到执行。每个epoch中，每个进程允许执行到其时间切片用完。如果某个进程没有使用其所有的时间切片，那么剩余时间切片的一半将被添加到新时间切片使其在下个epoch中可以执行更长时间。调度器只是迭代进程，应用goodness函数（指标）决定下面执行哪个进程。当然，各种进程对调度的需求并不相同，Linux 2.4调度器主要依靠改变进程的优先级，来满足不同进程的调度需求。事实上，所有后来的调度器都主要依赖修改进程优先级来满足不同的调度需求。

实时进程：实时进程的优先级是静态设定的，而且始终大于普通进程的优先级。因此只有当runqueue中没有实时进程的情况下，普通进程才能够获得调度。

实时进程采用两种调度策略，SCHED_FIFO 和 SCHED_RR

FIFO 采用先进先出的策略，对于所有相同优先级的进程，最先进入 runqueue 的进程总能优先获得调度；Round Robin采用更加公平的轮转策略，使得相同优先级的实时进程能够轮流获得调度。

Linux2.4调度器是如何提高交互式进程的优先级的呢？如前所述，当所有 RUNNING 进程的时间片被用完之后，调度器将重新计算所有进程的 counter 值， 所有进程不仅包括 RUNNING 进程，也包括处于睡眠状态的进程。处于睡眠状态的进程的 counter 本来就没有用完，在重新计算时，他们的 counter 值会加上这些原来未用完的部分，从而提高了它们的优先级。 交互式进程经常因等待用户输入而处于睡眠状态，当它们重新被唤醒并进入 runqueue 时，就会优先于其它进程而获得 CPU。从用户角度来看，交互式进程的响应速度就提高了。

该调度器的主要缺点：

• 可扩展性不好
  
  调度器选择进程时需要遍历整个 run