Linux O(1)调度器
Linux O(1)调度器
前面我们学习了O(n)调度器的设计，以及它的核心算法。在这里复习下。
O(n)调度器核心：
O(n)调度器采用一个runqueue运行队列来管理所有可运行的进程，在主调度schedule函数中会选择一个优先级最高，也就是时间片最大的进程来运行，同时也会对喜欢睡眠的进程做一些补偿，去增加此类进程的时间片。当runqueue运行队列中无进程可选择时，则会对系统中所有的进程进行一次重新计算时间片的操作，同时也会对剩余时间片的进程做一次补偿。
O(n)调度器的缺陷：
- 时间复杂度是O(n)
- SMP系统扩展不好，访问runqueue需要加锁
- 实时进程不能及时调度
- CPU空转的现象存在
- 进程在各个CPU之间跳跃，性能影响
O(1)调度器的引入
基于O(n)调度器的种种问题，linux内核社区则在2.6内核版本引入了O(1)调度器，当然了引入的目的也正是要解决O(n)调度器面临的问题。我们这片文章以Linux2.6.2版本来学习，在Linux内核文档中有一篇关于O(1)调度器的目的，如何设计的，以及实现有一个详细的介绍：sched-design.txt文档，有兴趣的可以去阅读。
O(1)调度器的工作原理
- 系统中的runqueue是一个PER_CPU变量，也就是说每一个CPU维护这一个runqueue，这样在SMP系统就可以有效的避免多个CPU去访问同一个runqueue。
- 每一个runqueue运行队列维护两个链表。一个是active链表，表示运行的进程都挂载active链表中；一个是expired链表，表示所有时间片用完的进程都挂载expired链表中。
- 为了解决O(n)中所有的进程都无序排列在runqueue中，O(1)算法中奖进程按照优先级排列，而且相同优先级的都挂在同等优先级的链表中
- 同时提供了一个bitmap结构，用来存放那些优先级中有可以运行的进程。当每次pciknext的时候，只需要坚持bitmap，然后去对应的优先级列表中按照优先级策略选择进程。
- 当acitve中无进程可运行时，说明系统中所有进程的时间片都已经耗光，这时候则只需要调整active和expired的指针即可。
从以上几点来看，可以看出O(1)的算法的改进都是针对O(n)算法存在的问题来修改的。
O(1)调度器涉及的数据结构
struct runqueue {
spinlock_t lock;
unsigned long nr_running, nr_switches, expired_timestamp,
nr_uninterruptible, timestamp_last_tick;
task_t *curr, *idle;
struct mm_struct *prev_mm;
prio_array_t *active, *expired, arrays[2];
int best_expired_prio, prev_cpu_load[NR_CPUS];
task_t *migration_thread;
struct list_head migration_queue;
atomic_t nr_iowait;
};
static DEFINE_PER_CPU(struct runqueue, runqueues);可以看到struct runqueue是一个PER_CPU的变量，则对应的是SMP系统中每一个CPU都维护一个struct runqueue结构。
/*
* These are the runqueue data structures:
*/
#define BITMAP_SIZE ((((MAX_PRIO+1+7)/8)+sizeof(long)-1)/sizeof(long))
typedef struct runqueue runqueue_t;
struct prio_array {
int nr_active;
unsigned long bitmap[BITMAP_SIZE];
struct list_head queue[MAX_PRIO];
};struct prio_array就代表的两个优先级数组，nr_active代表当前有多少进程处于active或者expried。bitmap是为了方便查找进程引入的，这样当寻找进程的时候只需要查询bitmap,而bitmap的大小是固定的，则算法的时间复杂度是O(1)
O(1)调度器的核心算法
O(1)的核心算法，我们可以直接看schedule函数
array = rq->active;
idx = sched_find_first_bit(array->bitmap);
queue = array->queue + idx;
next = list_entry(queue->next, task_t, run_list);这三行就是算法的核心，首先去从runqueue的active队列中的bitmap找到一个下标，这个下标就是对应的优先级，然后获取到对应优先级的链表，然后从中获取一个next进程。后面的操作就是执行进程切换，调度了。
系统中无可运行进程时
当系统中无可运行进程时，也就是进程的时间片都耗光了，则需要重新给进程设置时间片
array = rq->active;
if (unlikely(!array->nr_active)) {
/*
* Switch the active and expired arrays.
*/
rq->active = rq->expired;
rq->expired = array;
array = rq->active;
rq->expired_timestamp = 0;
rq->best_expired_prio = MAX_PRIO;
}操作也是相当的简单，只需要切换active和expried的指针即可。
O(1)调度器优先级的设置
进程的优先级分为静态优先级和动态优先级。普通优先级是进程创建时默认设置的优先级，动态优先级会在进程运行时经过动态的调整。
普通进程的静态优先级为static_prio
实时进程的静态优先级为rt_priority
O(1)调度器中所有进程的动态优先级为p->prio。
#define CURRENT_BONUS(p) \
(NS_TO_JIFFIES((p)->sleep_avg) * MAX_BONUS / \
MAX_SLEEP_AVG)
static int effective_prio(task_t *p)
{
int bonus, prio;
if (rt_task(p))
return p->prio;
bonus = CURRENT_BONUS(p) - MAX_BONUS / 2;
prio = p->static_prio - bonus;
if (prio < MAX_RT_PRIO)
prio = MAX_RT_PRIO;
if (prio > MAX_PRIO-1)
prio = MAX_PRIO-1;
return prio;
}在系统运行中，会跟踪此函数来重新计算进程的动态优先级。实时进程只需要返回对应的p->prio。而普通进程则就需要进行赏罚了。通过进程的睡眠时间sleep_avg来计算进程是否需要赏罚。当一个进程经常睡眠，则会增加它的优先级。当一个进程常占CPU，则需要惩罚，降低其优先级
时间片的更新
当系统的tick到来时，会走到schedule_tick函数中
if (!--p->time_slice) {
dequeue_task(p, rq->active);
set_tsk_need_resched(p);
p->prio = effective_prio(p);
p->time_slice = task_timeslice(p);
p->first_time_slice = 0;
if (!rq->expired_timestamp)
rq->expired_timestamp = jiffies;
if (!TASK_INTERACTIVE(p) || EXPIRED_STARVING(rq)) {
enqueue_task(p, rq->expired);
if (p->static_prio < rq->best_expired_prio)
rq->best_expired_prio = p->static_prio;
} else
enqueue_task(p, rq->active);
}当时间片耗完时，则需要将进程从active队列中移除掉，需要设置需要重新调度的标志TIF_NEED_RESCHED。同时还需要重新计算此进程的优先级，时间片。而O(1)调度器算法比O(n)不是那么的粗暴，还需要判断是否是交互式进程，或者此进程是不是饥饿进程，如果是则将又添加到active队列中，否则添加到expried队列。
总结：
- O(1)调度器的引入主要是为了解决O(n)调度器的不足
- O(1)调度器在赏罚机制上比O(n)调度器考虑的因素比较多，不再时像O(1)那样直接考时间片的大小来调度
- 但是O(n)和O(1)调度算法上核心还是通过判断一个进程的行为，比如爱睡眠来进程赏罚机制，爱睡眠来增大优先级，增大时间片的机制来获取更多的运行时间。
- 如果去看O(1)调度器的实现，没有O(n)算法那么简单明了，O(1)中加了需要时间的判断，各种情况的考虑，导致代码的阅读性很差，读起来很费劲。
- 当然了时代还是要前进的，O(n)和O(1)调度器是为CFS调度器出现地提供了很好的环境。