x86linux的进程调度,x86体系结构下Linux2.6.26的进程调度和切换

进程调度相关数据结构

task_struct

task_struct是进程在内核中对应的数据结构&＃xff0c;它标识了进程的状态等各项信息。其中有一项thread_struct结构的变量thread&＃xff0c;记录了CPU相关的进程状态信息&＃xff0c;如内核控制的断点和栈指针等。

在内核中获得当前进程task_struct结构使用宏current&＃xff0c;该宏读取变量current_task得到指针。

thread_union和thread_info

thread_union用于表示一个进程的内核态堆栈&＃xff0c;当进程进入内核态时就会使用该进程对应的内核态堆栈。

thread_union是一个联合体&＃xff0c;由stack和thread_info两项组成。其中的stack用于直接访问内核态堆栈的各项&＃xff0c;而thread_info表示了堆栈顶部(低地址部分)用于特殊用途的部分。

thread_info结构定义在include/asm-x86/thread_info_32.h&＃xff0c;定义了本进程task_struct结构的指针等在进入内核初期马上要访问的辅助数据。

在内核中得到当前thread_info用current_thread_info函数得到&＃xff0c;它通过对当前栈指针进行计算得到thread_info的指针。

sched_class

sched_class是Linux2.6中调度算法对外的统一界面。Linux使用这个概念将进程调度的具体策略和进程切换的过程隔离开&＃xff0c;使得组织有序且可以实现对不同类进程采用不同的调度策略。

在Linux-2.6.26中sched_class有fair_sched_class&＃xff0c;rt_sched_class和idle_sched_class三个实例&＃xff0c;分别组织在kernel下的sched_fair.c、sched_rt.c、sched_idletask.c中。这三个实例在初始化时被串成了一个链表&＃xff0c;依次为&＃xff1a;rt&＃xff0c;fair&＃xff0c;idle。

sched_entity和sched_rt_entity

内核中对sched_entity的解释为“CFS stats for a schedulable entity (task, task-group etc)”&＃xff0c;sched_rt_entity可类似解释。从这里可以看出这个结构的作用是存储一些调度算法相关的进程的状态。

rq

rq是当前CPU上就绪进程所组织成的队列。这个结构体记录了每个队列的状态。rq结构体中有cfs_rq和rt_rq两个子结构&＃xff0c;分别描述了该CPU上fair类型和rt类型进程的信息。

schedule函数分析

schedule函数是进程调度的入口&＃xff0c;在kernel/sched.c中。除去繁琐的检查、统计、上锁等操作&＃xff0c;仔细观察&＃xff0c;其主流程是4187行到4205行&＃xff1a;

prev->sched_class->put_prev_task(rq, prev);

next &＃61; pick_next_task(rq, prev);

if (likely(prev !&＃61; next)) {

sched_info_switch(prev, next);

rq->nr_switches&＃43;&＃43;;

rq->curr &＃61; next;

&＃43;&＃43;*switch_count;

context_switch(rq, prev, next); /*unlocks the rq*/

/** the context switch might have flipped the stack from under

* us, hence refresh the local variables.*/

cpu &＃61; smp_processor_id();

rq &＃61; cpu_rq(cpu);

} else

spin_unlock_irq(&rq->lock);

第一句中的prev在之前被赋值为rq->curr&＃xff0c;因此是当前运行队列正在运行的进程。从字面看是将当前进程放回队列。第二句是从队列中取出下一个可运行的进程&＃xff0c;叫next。

接下来是进程的上下文切换工作。首先判断prev和next是否是同一个进程&＃xff0c;若是&＃xff0c;则不必切换。否则统计信息&＃xff0c;接着设置rq->curr为next&＃xff0c;然后调用context_switch来进行实际的上下文切换。

schedule函数的简要分析结束。可见&＃xff0c;理解进程的调度&＃xff0c;核心是put_prev_task和pick_next_task&＃xff1b;而理解进程的切换&＃xff0c;核心是context_switch。下面就分两条线索&＃xff0c;分别说明进程的切换和调度的流程。

进程的切换

接上&＃xff0c;先忽略调度策略&＃xff0c;假设prev和next指向需要换走和换入的进程&＃xff0c;然后进入了context_switch函数。

context_switch在kernel/sched.c中的第2447行。

忽略prepare、finish、lazy等字样的函数&＃xff0c;忽略SMP同步操作&＃xff0c;主流程上只有switch_mm和switch_to。

switch_mm

switch_mm在x86体系结构下在include/asm-x86/mmu_context_32.h中第35行定义&＃xff0c;其中核心语句只有一句&＃xff1a;

load_cr3(next->pgd); 从名字和内容可见switch_mm是切换页表。这里切换页表&＃xff0c;即地址空间&＃xff0c;不会引起控制流程改变&＃xff0c;因为每个进程地址空间的内核部分(3G以上)的映射是一样的。然而&＃xff0c;当从内核空间返回用户空间时&＃xff0c;这里的改变就会起到本质的作用&＃xff1a;跑到next的用户代码中继续运行。

switch_to

switch_to是一个宏&＃xff0c;定义在include/asm-x86/system.h中第30行&＃xff0c;如下&＃xff1a;

#define switch_to(prev, next, last) \

do { \

/*\

* Context-switching clobbers all registers, so we clobber \

* them explicitly, via unused output variables. \

* (EAX and EBP is not listed because EBP is saved/restored \

* explicitly for wchan access and EAX is the return value of \

* __switch_to()) \*/ \

unsigned long ebx, ecx, edx, esi, edi; \

\

asm volatile("pushfl\n\t" /*save flags*/ \

"pushl %%ebp\n\t" /*save EBP*/ \

"movl %%esp,%[prev_sp]\n\t" /*save ESP*/ \

"movl %[next_sp],%%esp\n\t" /*restore ESP*/ \

"movl $1f,%[prev_ip]\n\t" /*save EIP*/ \

"pushl %[next_ip]\n\t" /*restore EIP*/ \

"jmp __switch_to\n" /*regparm call*/ \

"1:\t" \

"popl %%ebp\n\t" /*restore EBP*/ \

"popfl\n" /*restore flags*/ \

\

/*output parameters*/ \

: [prev_sp] "&＃61;m" (prev->thread.sp), \

[prev_ip] "&＃61;m" (prev->thread.ip), \

"&＃61;a" (last), \

\

/*clobbered output registers:*/ \

"&＃61;b" (ebx), "&＃61;c" (ecx), "&＃61;d" (edx), \

"&＃61;S" (esi), "&＃61;D" (edi) \

\

/*input parameters:*/ \

: [next_sp] "m" (next->thread.sp), \

[next_ip] "m" (next->thread.ip), \

\

/*regparm parameters for __switch_to():*/ \

[prev] "a" (prev), \

[next] "d" (next)); \

} while (0)

这个宏通过切换堆栈和控制流程来达到上下文切换的目的。&＃61;

切换内核堆栈

这个宏首先在保存了ebx,ecx,edx,esi,edi,flags在当前内核堆栈上&＃xff0c;然后进行关键的堆栈切换&＃xff1a;

pushl %ebp

movl %esp, %[prev_sp]

mvol %[prev_sp], %esp 首先将栈帧ebp压栈&＃xff0c;然后从prev->thread.sp中取出上个进程在上一次切换时的栈顶&＃xff0c;放到esp中。此句过后&＃xff0c;内核态的堆栈已经切换到了下一个进程的内核堆栈。由前面介绍的current_thread_info的特点&＃xff0c;此时调用此函数&＃xff0c;将得到next的thread_info。

切换内核控制流程

接着开始切换控制流程&＃xff1a;

movl $1f, %[prev_ip]

pushl %[next_ip]

jmp __switch_to

1:

popl %ebp 首先将标号1&＃xff0c;即该段最后一句的地址放入prev->thread.ip。可见下次prev运行时&＃xff0c;将从pop %ebp开始。然后&＃xff0c;将next->thread.ip压栈&＃xff0c;并跳转到__switch_to执行。

__switch_to返回时&＃xff0c;会从堆栈弹出一项作为返回地址&＃xff0c;由于调用__switch_to时不是通过call指令&＃xff0c;而是手工压栈加跳转&＃xff0c;所以不会返回到“这里”的标号1处&＃xff0c;而是返回到next->thread.ip处。如果next进程不是新创建出来的&＃xff0c;那么原来也是通过switch_to切换走的&＃xff0c;则断点必定是“那里”的标号1&＃xff0c;且此时next的内核堆栈上保存有那一次的ebp和flags&＃xff0c;以及ebx等。

因此通过这一次函数调用&＃xff0c;内核的控制流程也被成功转移到next&＃xff0c;在next上次切换的标号1处&＃xff0c;对上次保存的ebp和flags等内容进行恢复&＃xff0c;这就完成了整个切换过程。

切换总结

下面是switch_to整个切换过程的图示。

switch_to之前

切换堆栈之前

切换堆栈之后

push和jmp

__switch_to返回

switch_to完成

__switch_to

搞清楚switch_to的作用后&＃xff0c;下面来看__switch_to的工作。函数在arch/x86/kernel/process_32.c中&＃xff0c;该函数做的关键动作如下。

切换浮点部件寄存器和状态

__unlazy_fpu(prev_p);

/*we&＃39;re going to use this soon, after a few expensive things*/

if (next_p->fpu_counter > 5)

prefetch(next->xstate);

/*If the task has used fpu the last 5 timeslices, just do a full

* restore of the math state immediately to avoid the trap; the

* chances of needing FPU soon are obviously high now

*

* tsk_used_math() checks prevent calling math_state_restore(),

* which can sleep in the case of !tsk_used_math()*/

if (tsk_used_math(next_p) && next_p->fpu_counter > 5)

math_state_restore();

浮点部件保存与恢复用了一些lazy策略。但是当进程连续使用FPU超过5个时间片时&＃xff0c;取消使用lazy策略。

重设TSS的esp0

/** Load the per-thread Thread-Local Storage descriptor.*/

load_TLS(next, cpu);

设TSS的原因是&＃xff0c;让在next中从用户态转移到内核态时&＃xff0c;切换到next的内核堆栈&＃xff0c;以保证正确地保存用户态上下文。

设置current_task

x86_write_percpu(current_task, next_p);

在这一句以后&＃xff0c;用current宏得到的当前进程就是next了。

其他

函数中还切换了TLS、IOPL等内容。这些切换并非不重要&＃xff0c;但属于细枝末节的问题或较新的功能&＃xff0c;因此不仔细分析了。

相关问题

最后遗留的问题是__switch_to的参数传递和返回值问题。从process_32.c中可见&＃xff0c;__switch_to有两个参数和一个返回值。但是在调用前并没有按照常规对参数入栈&＃xff0c;这是什么原因呢&＃xff1f;jmp一句旁边的注释说“regparm call”&＃xff0c;提示是通过寄存器传参。而__switch_to函数定义处并没有加入任何选项&＃xff0c;应该采用默认的堆栈传参啊&＃xff01;这个问题曾经困扰我很久&＃xff0c;后来终于在Makefile中看到了原因。在arch/x86/Makefile中有下面一句&＃xff1a;

KBUILD_CFLAGS &＃43;&＃61; -msoft-float -mregparm&＃61;3 -freg-struct-return 其中-mregparm&＃61;3表示默认使用3个寄存器传参&＃xff0c;问题解决。

至于返回值&＃xff0c;是按照常规通过eax传递。由代码&＃xff0c;__switch_to会将prev返回。而eax最终被绑定到switch_to的last参数上。那么这里last的意义就值得探讨了。根据上面的分析&＃xff0c;__switch_to是从prev到next的一座“桥”。调用前&＃xff0c;代码是在prev的控制中&＃xff1b;调用后&＃xff0c;代码就跑到next的控制中了。然而&＃xff0c;寄存器信息在调用后却从prev传递到了next。因此&＃xff0c;last就是之前一直讲的prev。需要注意的是&＃xff0c;现在控制和上下文都跑到了next中&＃xff0c;next中的prev并不是之前的prev&＃xff0c;因此要凭空生出一个last的概念来维护真实的进程切换关系&＃xff1a;对next而言&＃xff0c;last是物理时间上的上一个运行的进程&＃xff0c;而next中的prev则是next自己&＃xff0c;next中的next是next上次切换走时切换到的进程。

从context_switch对switch_to的使用看&＃xff0c;last参数又被绑定到了prev。因此&＃xff0c;对某一个进程p&＃xff0c;它被切换走后&＃xff0c;途径各种进程兜一圈回来&＃xff0c;prev被赋值为last。从而“保持了”prev的直观意义。

这里描述起来非常绕&＃xff0c;原因是prev和next的含义是随着进程的改变而改变的&＃xff0c;理解时必须自己在不同的“世界”中来回切换。关键点是&＃xff0c;prev和next是和一个进程相绑定的“状态量”&＃xff0c;last则是描述两个进程的切换时刻的“过程量”。

总结

总结整个进程切换过程&＃xff0c;其中做的关键操作是&＃xff1a;切换地址空间、切换内核堆栈、切换内核控制流程&＃xff0c;加上一些必要的寄存器保存和恢复。这里&＃xff0c;除去地址空间的切换&＃xff0c;其他操作要强调“内核”一词。这是因为&＃xff0c;这些操作并非针对用户代码&＃xff0c;切换完成后&＃xff0c;也没有立即跑到next的用户空间中执行。用户上下文的保存和恢复是通过中断和异常机制&＃xff0c;在内核态和用户态相互切换时才发生的。从这个意义上讲&＃xff0c;切换地址空间才是本质上想要达到的“用户代码和数据的切换”&＃xff0c;其余的切换不过是内核中不同的控制流程在“交接棒”而已。

进程切换这里当初领会起来比较难&＃xff0c;但是一旦理解&＃xff0c;就会深深佩服这一系列过程的巧妙。特别是switch_to宏&＃xff0c;几乎就是多一句嫌多&＃xff0c;少一句嫌少。

进程的调度

现在回过头来看选择next的过程。

不同类型的进程之间的调度选择

schedule函数中对不同类型的进程之间的调度选择是由pick_next_task函数确定的。这个函数在kernel/sched.c的第4106~4136行&＃xff1a;

/** Pick up the highest-prio task:*/

static inline struct task_struct *

pick_next_task(struct rq *rq, struct task_struct *prev)

{

const struct sched_class *class;

struct task_struct *p;

/** Optimization: we know that if all tasks are in

* the fair class we can call that function directly:*/

if (likely(rq->nr_running &＃61;&＃61; rq->cfs.nr_running)) {

p &＃61; fair_sched_class.pick_next_task(rq);

if (likely(p))

return p;

}

class &＃61; sched_class_highest;

for ( ; ; ) {

p &＃61; class->pick_next_task(rq);

if (p)

return p;

/** Will never be NULL as the idle class always

* returns a non-NULL p:*/

class &＃61; class->next;

}

}

这个函数的中心环节是一个for循环&＃xff0c;它遍历sched_class的每一个实例&＃xff0c;并依次调用各个实例的pick_next_task函数。若返回非空&＃xff0c;则将下一个进程设为它。

由此可见&＃xff0c;Linux调度系统采用的是操作系统理论中的多级队列调度&＃xff0c;且上一个队列中进程的优先级恒比下一个队列中进程高。本文第一部分已述&＃xff0c;sched_class链表依次为rt、fair、idle。因此&＃xff0c;只要有rt类型进程就绪&＃xff0c;调度时就一定会被选择&＃xff0c;从而保证了rt类型进程的实时性。

注释中还提到一点&＃xff0c;idle队列中一定非空&＃xff0c;因此在前两个类型的进程都没有就绪时&＃xff0c;idle中的idle进程一定会被选中并调度&＃xff0c;这保证了循环一定能终止。这里可以看到系统idle进程的重要性。

同类型的进程之间的调度选择

kernel/sched.c中的pick_next_task函数依次对每个sched_class实例调用的pick_next_task&＃xff0c;成为同类型的进程之间的调度选择机制的关键。另外schedule函数在pick_next_task之前&＃xff0c;还对prev所在sched_class实例做了put_prev_task操作。

由于内核对调度算法做了一层抽象&＃xff0c;因此直接从源码分析下去得到的只能是一些函数指针。因此不另加说明时&＃xff0c;不妨假定&＃xff0c;进程的task_struct结构中sched_class为fair_sched_class。

put_prev_task

在fair类中&＃xff0c;此函数在kernel/sched_fair.c中第1246~1258行&＃xff1a;

/** Account for a descheduled task:*/

static void put_prev_task_fair(struct rq *rq, struct task_struct *prev)

{

struct sched_entity *se &＃61; &prev->se;

struct cfs_rq *cfs_rq;

for_each_sched_entity(se) {

cfs_rq &＃61; cfs_rq_of(se);

put_prev_entity(cfs_rq, se);

}

}

此函数意义很明确&＃xff1a;"Account for a descheduled task"。其具体实现是找到prev进程对应sched_entity&＃xff0c;并调用put_prev_entity。

put_prev_entity在757~773行&＃xff1a;

static void put_prev_entity(struct cfs_rq *cfs_rq, struct sched_entity *prev)

{

/** If still on the runqueue then deactivate_task()

* was not called and update_curr() has to be done:*/

if (prev->on_rq)

update_curr(cfs_rq);

check_spread(cfs_rq, prev);

if (prev->on_rq) {

update_stats_wait_start(cfs_rq, prev);

/*Put &＃39;current&＃39; back into the tree.*/

__enqueue_entity(cfs_rq, prev);

}

cfs_rq->curr &＃61; NULL;

} 此函数实现涉及具体的公平调度算法&＃xff0c;无需再仔细分析。不过由于公平调度是用红黑树实现的&＃xff0c;可以隐约看到它调用__enqueue_entity把进程重新放回了红黑树中。

从这里的分析可以看到&＃xff0c;put_prev_task实质上是在进程被调出时&＃xff0c;留给具体调度算法更新内部状态的一次机会。

pick_next_task

在fair类中&＃xff0c;此函数在kernel/sched_fair.c中第1226~1244行。类似put_prev_task&＃xff0c;它调用pick_next_entity。

pick_next_entity在744~755行&＃xff1a;

static struct sched_entity *pick_next_entity(struct cfs_rq *cfs_rq)

{

struct sched_entity *se &＃61; NULL;

if (first_fair(cfs_rq)) {

se &＃61; __pick_next_entity(cfs_rq);

se &＃61; pick_next(cfs_rq, se);

set_next_entity(cfs_rq, se);

}

return se;

} 而first_fair是一个内联函数&＃xff0c;内容只有一行&＃xff1a;

return cfs_rq->rb_leftmost;

if中前两句的工作是更新并摘取红黑树的leftmost区域的sched_entity&＃xff1b;后一句最终调用__dequeue_entity&＃xff0c;可见是将leftmost从红黑树中取出。

pick_next_entity返回后&＃xff0c;pick_next_task再将entity转为task_struct返回。这样&＃xff0c;schedule就能得到下一个将要运行的进程了。