Linux内核O(1)调度算法
目录
一、引言
二、调度策略和时间片
2.1 调度策略
2.2 时间片
三、进程
3.1 进程分类
3.2 进程优先级
3.3 影响进程动态优先级的因素
3.4 静态优先级与时间片
3.5 静态优先级与动态优先级的关系
四、调度算法
4.1 概念铺垫
4.2 核心算法
五、结语
一、引言
在电脑上，我们可以同时打开多个程序。这很容易让人产生一种错觉，好像这些程序都在同时运行。但实际上并非如此。真正的原因是操作系统在内部进行进程的切换与调度，才使得我们可以同时打开多个程序。由于这一过程完成得非常迅速，我们几乎感觉不到，从而产生了多个程序同时执行的错觉。本文将重点探讨Linux 2.6中普通进程的调度机制。
二、调度策略和时间片
时间片是系统中一个很重要的概念，有必要了解一下。至于调度策略，知道了什么样的调度策略是比较理想的才有助于我们明确方向。
2.1 调度策略
理想的调度策略要确保公平，同时还要有高的吞吐量。所有的进程都应该获得公平的CPU时间分配，避免出现一些进程长时间得不到服务，也就是避免进程饥饿。理想的调度策略事实上并不存在，但是一个好的调度策略要尽量往这个方向靠，协调好各个方面，尽可能的提高进程调度的效率。
2.2 时间片
时间片是指分配给进程或线程的CPU时间。进程只有分配到了时间片才可以被调度执行，一旦进程的时间片耗尽，就立刻被调度器从CPU上剥离下来。不过，时间片的划分可不是一件容易的事情。时间片既不能过长，也不能过短。过长的时间片会导致系统的响应慢，反应不及时；过短的时间片会让进程切换过于频繁。我们知道，进程的切换是有代价的，既要保存旧进程的上下文（如果没有执行完毕），又要加载新进程的上下文。
三、进程
谈调度策略，是绕不开进程的，所以很有必要来重新认识一下进程。
3.1 进程分类
这里不在把进程分为僵尸进程、孤儿进程等，本文谈的不是进程概念，而是进程调度。进程可以分为两种类型，一种是I/O消耗型，另一种是CPU消耗型。前者频繁的进行I/O操作，大部分时间都是在等待I/O资源就位，比如键盘事件；后者则是大部分时间都在占用CPU。
为了使系统有较强的响应能力，I/O消耗型进程必须能够很快被唤醒，否则可能导致用户察觉到系统反应迟钝，影响用户体验。而对于CPU消耗型进程，它们常常在后台运行，偶尔进行I/O操作，不需要系统对这类进程做出快速反应。
3.2 进程优先级
进程的优先级有两种，静态优先级和动态优先级。
静态优先级在进程被创建的时候就有，而且在整个执行过程中保持不变。平时我们使用命令在Linux系统上查出来的就是静态优先级。它主要反映了进程的相对重要程度。静态优先级的范围在0到139，其中0到99是给实时进程用，100到139才是给普通进程。
动态优先级（100到139），是在进程的运行过程中，根据运行的情况进行动态调整的优先级。它比静态优先级更加灵活，可以根据进程的实际运行状况来更好的进行调度。
在谈影响动态优先级调整的因素之前，先对静态优先级和动态优先级做一个理解上的区分。进程的调度顺序主要是基于动态优先级的，而时间片的计算主要基于静态优先级。也就是说，一个进程的动态优先级越高（值小）它越可能被先调度，而与它的静态优先级无关。
3.3 影响进程动态优先级的因素
影响进程动态优先级的因素主要有三个：进程的等待时间、进程的运行时间以及进程的类别和资源需求。
如果一个进程的等待时间过长，那么它的动态优先级很可能会被提高（值减小），因为调度策略要尽可能的确保公平，将这类进程的动态优先级提高（值减小）有助于它更快的被CPU执行。如果一个进程的运行时间过长，那么它的动态优先级很可能会被降低（值增大），因为这类进程长时间占用CPU，让等待的进程得不到运行。对于实时进程，比如说音频播放进程，它需要再规定时间内完成数据处理和播放任务。如果这类进程的资源得不到满足，那么操作系统会提高它们的动态优先级（值减小），以确保实时性要求。
3.4 静态优先级与时间片
上面说到，时间片的计算主要基于静态优先级。以下是时间片的计算公式：
静态优先级 < 120
基本时间片 = max((140 - 静态优先级) * 20，MIN_TIMESLICE）
静态优先级 >= 120
基本时间片 = max((140 - 静态优先级) * 5，MIN_TIMESLICE）
其中MIN_TIMESLICE为系统规定的最小时间片
通过以上公式，不难看出静态优先级越高，获得的时间片就越长，反之，则越短。所以说，静态优先级反应了进程的重要程度。
3.5 静态优先级与动态优先级的关系
动态优先级 = max(100，min(静态优先级 - bonus + 5,139))
可以看出，静态优先级是可以影响到动态优先级的，进而影响进程的调度顺序。其中，bonus是根据进程过去的平均睡眠时间做出的惩罚或奖励。
所谓平均睡眠时间（sleep_avg，位于task_struct结构中）就是进程在睡眠状态所消耗的总时间数，这里的平均并不是直接对时间求平均数。平均睡眠时间随着进程的睡眠而增长，随着进程的运行而减小。因此，平均睡眠时间反映了进程的睡眠时间和运行时间占总时间的比重，它是用来判断进程交互性强弱的关键数据。如果一个进程的平均睡眠时间很长，那么它很可能是一个交互性很强的进程。如果一个进程的平均睡眠睡眠时间很短，那么它很可能是一个CPU消耗型进程。
交互性强的进程会得到调度器的奖励（bonus为正），而那些一直霸占CPU的进程会得到相应的惩罚（bonus为负）。这样就有利于交互性强的进程能够优先被调度，确保了较快的响应速度。
四、调度算法
4.1 概念铺垫
在继续往下理解之前，需要知道关于活动进程和过期进程的概念。所谓活动进程，就是时间片尚未耗尽的进程；过期进程就是时间片已耗尽的进程。
4.2 核心算法
调度器在每次发生进程切换时，都要在就绪队列中选取一个最合适的进程来运行。Linux中使用runqueue结构来表示就绪队列，每一个CPU有且只有一个就绪队列。runqueue结构中有很多字段，但这里仅列举一小部分。
prio_arrray_t* active;/ /指向活动队列的指针
prio_arrray_t* expired;/ /指向过期队列的指针
prio_array_t arrays[2];/ /包含活动进程集合和过期进程集合的数组
另一个核心数据结构是prio_array，它的定义如下：
#define MAX_USER_RT_PRIO 100
#define MAX_RT_PRIO MAX_USER_RT_PRIO
#define MAX_PRIO (MAX_RT_PRIO + 40)
typedef struct prio_array prio_array_t;
struct prio_array {
unsigned int nr_active;
unsigned long bitmap[BITMAP_SIZE];
struct list_head queue[MAX_PRIO];
};
prio_array结构体中包含三个字段。nr_active表示当前队列中可执行进程的总数；bitmap是一张位图——优先级位图，0到139共140个数，只需要5个32位的整形即可，所以BITMAP_SIZE的值是5，优先级位图中的每一个位对应一个优先级，若该位为1，则表示对应的优先级队列中有进程存在，反之则表示该优先级对列为空。优先级队列就是在第三个字段queue中，MAX_PRIO为140，queue数组中的每一个元素是一个是双向链表，链入对应优先级的进程。因此，queue数组中的140条链表中，同一条链表上的进程具有相同的优先级。
假设array[0]是活动进程集合，active指针指向它；array[1]是过期进程集合，expired指向它。进程切换时，调度器通过active指针找到活动进程集合，然后访问优先级位图，从高为到低位依次查找，发现第一个为1的位置后找到它对应的优先级队列，拿出该队列的队头去执行。相比于Linux2.4需要遍历所有活动进程计算优先级（时间复杂度O(N))，遍历优先级位图只需要常数时间，而且不受活动进程个数的影响。这就是为什么叫做O(1)调度算法的缘故。
如果活动进程集合中的所有进程都已经将时间片耗尽，那么只需要交换active指针和expired中指针即可。这也仅仅需要常数时间。
五、结语
我在写这篇文章的时候，只是内核的初学者，难免有错误，还请指出！
完~