Linux内核调度策略与算法分析 (2)

发布于:2021-11-27 19:38:59

转自 http://hi.baidu.com/mychaoyue2011/blog/item/6df45895c3d63243d0135e01.html




4 ??? ? Linux内核调度策略与算法分析
?? ?

c = -1000;

list_for_each(tmp, &runqueue_head) {???? /* 从runqueue中选择一个最佳进程来运行 */

???? p = list_entry(tmp, struct task_struct, run_list);

???? if (can_schedule(p, this_cpu)) {???? /* 这个进程可以运行 */

???????? /* 计算它的适应度,适应度最高的进程将被选择 */

???????? int weight = goodness(p, this_cpu, prev->active_mm);

???????? if (weight > c)

???????????? c = weight, next = p;

???? }

}

算法复杂度一目了然。



?可执行队列 runqueue

Linux为每个CPU定义了一个runqueue. 此处仅讨论一个CPU,并给出runqueue结构中一些关键的内容:


struct runqueue {

???? unsigned long nr_running;??????????? /* 处于TASK_RUNNING的进程数 */

???? task_t *curr, *idle;???????????????? /* 该CPU的当前进程和空闲进程*/



???? prio_array_t *active, *expired, arrays[2];

???????????????????????????????????????? /* 活跃和过期prio_array */

???????????????????????????????????????? /* arrays[2]为他们实际占用的空间 */

???? /* other members ... */

};

这里最关键的成员是两个prio_array_t, 以及两个此类型的指针。其中active指针指向活跃进程的优先级数组,而expired指向过期进程的优先级数组。当一个进程时间片用完并且没有立刻重新激活的特权时,只需重新计算时间片,并且将它移入expired优先级数组即可。在 active数组为空时,只要将两个指针交换,由于expired数组中的时间片都已计算好,只要放到active的位置立刻可以执行,而空空如也的 active数组则恰好充当新的expired数组:


/* 以下代码位于void schedule(void)中 */

array = rq->active;

if (!array->nr_active) {???????????????? /* active数组空了 */

???? rq->active = rq->expired;

???? rq->expired = array;

???? array = rq->active;

}

对比linux-2.4内核中时间片用净后重新计算的过程:

/* 以下代码位于linux 2.4的void schedule(void)中 */

/* Do we need to re-calculate counters? */

if (unlikely(!c)) {

???? struct task_struct *p;

???? /* ... */

???? for_each_task(p)

???????? p->counter = (p->counter >> 1) + NICE_TO_TICKS(p->nice);

???? /* ... */

???? goto repeat_schedule;

}

又用了一个for循环.



有了上述准备,便可以完整地看一下scheduler_tick()和schedule()函数了:

?scheduler_tick()

Linux以频率HZ通过时钟中断调用一次会调用schedule_tick函数。它负责监控并调整当前进程的状态,并在适当的时候提出要求系统schedule的要求。以下是简化后的源代码:


void scheduler_tick(void)

{

???? runqueue_t *rq = this_rq();????? /* 取得当前可执行队列 */

???? task_t *p = current;???????????? /* 取得当前进程 */



???? /* 进程可能已经过期了,但还没被schedule下来。

????? * 什么原因呢?我能想到的例子是:????????????????????????? ?

????? * 可能从设置它为expired到schedule将它撤下前中断过于频繁,

????? * 导致执行scheduler_tick的时间又到了

????? * 肯定还有别的情况,以至于要set_tsk_need_resched(p)

????? */

???? if (p->array != rq->active) {

???????? set_tsk_need_resched(p);???? /* 标识当前进程为需要重新调度 */

???????? return;

???? }



???? if (rt_task(p)) {??????? /* 实时进程 */

???????? /* 调度策略为SCHED_RR的需要计算时间片,而SCHED_FIFO类型的则不必 */

???????? if ((p->policy == SCHED_RR) && !--p->time_slice) {? ?

???????????? /* 如果时间片已用完 */
???
?


5 ??? ? Linux内核调度策略与算法分析
?? ?

???????????? p->time_slice = task_timeslice(p);?? /* 重新计算时间片 */

???????????? set_tsk_need_resched(p);???????????? /* 标识当前进程为需要重新调度 */

???????????? requeue_task(p, rq->active);???????? /* 移到该优先级组的队列的后端 */

???????? }

???????? return;?????????? /* 实时进程调度完毕 */

???? }

???? /* 此处必为非实时进程 */

???? 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);?????? /* 根据新的优先级计算时间片 */



???????? /* 如果不是交互进程或者过期队列饿了 */

???????? if (!TASK_INTERACTIVE(p) || EXPIRED_STARVING(rq)) {

???????????? /* 没有重新激活的特权,只好到过期数组等着了 */

???????????? enqueue_task(p, rq->expired); ?

???????? } else?????? /* 可以立刻重新激活的交互进程 */

???????????? enqueue_task(p, rq->active);???? /* 重新激活 */



???? } else {???????? /* 非实时进程时间片尚未用完 */

???????? /* 进行第二层轮转 */

???????? if (TASK_INTERACTIVE(p) && !((task_timeslice(p) -

???????????? p->time_slice) % TIMESLICE_GRANULARITY(p)) &&???? ?

???????????? (p->time_slice >= TIMESLICE_GRANULARITY(p)) &&??? ?

???????????? (p->array == rq->active)) {

???????????? /* 如果当前进程 是交互的 且 小时间片已到 且 */

?????????????? /* 剩余时间片还够一次小时间片调度 且 进程还活跃 */



???????????? requeue_task(p, rq->active);???? /* 从头部移出放在尾部 */

???????????? set_tsk_need_resched(p);???????? /* 标识为需要重新调度 */

???????? }

???? }

}

可以看到此处实现了前面策略中关于交互进程可以被立即再激活,以及交互进程的第二层轮转的处理。

在set_tsk_need_resched(p)后,系统会在一些特定的时刻执行schedule来完成调度。



?schedule()

schedule()函数是整个调度算法的核心。当有进程需要被调度时,系统会调用schedule函数。它被调用的方法主要有两类:

a)????? 其他内核代码主动调用

最显然的例子就是当进程需要被休眠时,便会在设置当前状态到非TASK_RUNNING后,主动调用schedule().

b)????? 在中断处理返回时调用

当系统从中断返回时,会检查当前进程是否need reschedule, 如果是则调用schedule()来调度当前进程:

# 以下代码出自arch/i386/kernel/entry.S

ret_from_intr:??????????? # 从中断返回

# ...

jz resume_kernel???????? # 如果是从内核态中断的,则返回内核态



ENTRY(resume_kernel)????? # 返回内核态

# ...

need_resched:

movl TI_flags(%ebp), %ecx

testb $_TIF_NEED_RESCHED, %cl??? # 测试need_resched是否被设置?

jz restore_all?????????????????? # 如果被设置,那么去restore_all

#...

restore_all:????????????????????? # schedule将在那里被执行

#...

work_resched:

call schedule??????????????????? # 最终在这里执行




在被调用后,schedule()完成实际的调度工作,以下是简化后的源码(但仍然不短):


asmlinkage void __sched schedule(void)

{

???? task_t *prev, *next;

???? runqueue_t *rq;

???? prio_array_t *array;

???? struct list_head *queue;

???? unsigned long long now;

???? unsigned long run_time;

?? ?
6 ?? ?Linux内核调度策略与算法分析
?? ?

???? int idx;



need_resched:

???? /* 取得现在正在运行的进程。

????? * 需要注意的是,它未必再当前的runqueue里,

????? * 而是可能已经被scheduler_tick()挪走了

????? */

???? prev = current;

???? release_kernel_lock(prev);

need_resched_nonpreemptible:

???? rq = this_rq();

???? /* 下面统计本次运行的时间 */

???? now = sched_clock();

???? if (now - prev->timestamp < NS_MAX_SLEEP_AVG)

???????? run_time = now - prev->timestamp;

???? else

???????? run_time = NS_MAX_SLEEP_AVG;



???? /* run_time根据CURRENT_BONUS按比例缩小,以免一个交互性进程由

????? * 于这一次运行时间太长就失去了交互属性,起到“过滤高频噪声”

????? * 的作用。如果它真的开始大量占用CPU,那么在几次调整后便会*

????? * 滑地变成非交互进程。

????? */

???? run_time /= (CURRENT_BONUS(prev) ? : 1);



???? spin_lock_irq(&rq->lock);??? /* 修改rq先上锁 */



???? /* 如果刚才运行的进程的状态已经不再是runnable,

????? * 并且不是明确指明不能抢占内核(下文祥叙)

????? */

???? if (prev->state && !(preempt_count() & PREEMPT_ACTIVE)) {

???????? if ((prev->state & TASK_INTERRUPTIBLE) &&

???????????????? signal_pending(prev))

???????????? /* 最后的机会:如果可以被信号唤醒而且信号也确实来了 */

???????????? prev->state = TASK_RUNNING; /* 那就继续运行吧 */

???????? else {

???????????? /* 回天乏术 */

???????????? deactivate_task(prev, rq);?? /* 只好休息去了 */

???????? }

???? }



???? if (!rq->nr_running) {?????? /* 整个rq都没有东西在运行? */

???????? next = rq->idle;???????? /* 执行idle进程 */

???????? goto switch_tasks;

???? }



???? /* 至此看来有东西可以运行 */



???? /* 下面判断是否需要交换active和expired优先级数组 */

???? array = rq->active;

???? if (!array->nr_active) {

???????? rq->active = rq->expired;??? /* 交换 */

???????? rq->expired = array;

???????? array = rq->active;

???? }



???? /* 取得下一个应该运行的进程 */

???? idx = sched_find_first_bit(array->bitmap);?????? /* 最高优先级的 */

???? queue = array->queue + idx;?????? ?

???? next = list_entry(queue->next, task_t, run_list);??? /* 第一个进程 */



???? if (!rt_task(next) && next->activated > 0) {

???????? unsigned long long delta = now - next->timestamp;



???????? if (next->activated == 1)

???????????? delta = delta * (ON_RUNQUEUE_WEIGHT * 128 / 100) / 128;



???????? array = next->array;

???????? dequeue_task(next, array);

???????? recalc_task_prio(next, next->timestamp + delta);

???????? enqueue_task(next, array);

???? }

???? next->activated = 0;

switch_tasks:

???? clear_tsk_need_resched(prev);??? /* 已调度,清空进程的need_resched标志 */



???? prev->sleep_avg -= run_time;???? /* 调整sleep_avg */

???? if ((long)prev->sleep_avg <= 0)

???????? prev->sleep_avg = 0;



???? prev->timestamp = now;?????? /* 记录时间,用于计算sleep_avg */



???? if (prev != next) {????????? /* 确实需要切换进程 */

???????? next->timestamp = now;?? /* 记录新进程开始时间 */

???????? rq->curr = next;



???????? /* 以下进行上下文切换 */

???????? prepare_arch_switch(rq, next);

???????? prev = context_switch(rq, prev, next);

???????? barrier();



???????? finish_task_switch(prev);

???? } else

???????? spin_unlock_irq(&rq->lock);



???? prev = current;

???? if (reacquire_kernel_lock(prev) < 0)

???????? goto need_resched_nonpreemptible;



???? /* 由于有上述主动调用法,所以推测schedule是可能被打断的,

????? * 从而有必要在最后判断一下是否又需要schedule了,

????? * 以免选择了一个不想或者不能被运行的进程

????? */

???? if (test_thread_flag(TIF_NEED_RESCHED))

???????? goto need_resched;?????? /* sigh, 又要schedule了 */

}

注: 中间有一段提到了PREEMPT_ACTIVE, 而当这个值会被preempt_schedule在调用schedule前设置,然后在schedule返回后撤销。根据 preempt_schedule前的这段注释:

/*

* this is is the entry point to schedule() from in-kernel preemption

* off of preempt_enable.?? Kernel preemptions off return from interrupt

* occur there and call schedule directly.

*/

asmlinkage void __sched preempt_schedule(void)


也就是说这个函数会在内核抢占关闭,但又是返回到内核的时候被调用,那么PREEMPT_ACTIVE表示的是不能抢占内核。而当直接调用 schedule(),内核抢占会显式地发生。但从函数和常量的名字看好像意思恰恰相反,有些不解。



上面的代码实现了进程的调度和切换、优先级数组的切换。并且可以看到这里没有一个循环(那些goto只以很小的概率发生),是一个高效率的O(1)调度算法。尤其在前面对比了linux-2.4的实现后发现它的调度速度会快得多(尤其linux-2.4的schedule函数中有两个循环,而2.6中竟一个都没有),而且调度所需的时间也非常稳定,不会出现某次调度所需时间特别长的情况。

相关推荐

最新更新

猜你喜欢