uClinux进程调度器的实现分析

摘要：针对操作系统中进程的调度机制，依次对其调度方式、调度策略、调度时机进行了分析，并结合uClinux中进程调度实现的核心源代码，剖析了uClinux中进程调度器的实现原理，展示了uClinux中独具特色的进程调度机制。
关键词：uClinux；调度策略；进程调度器

0. 引言

uClinux是针对控制领域的嵌入式Linux操作系统，它从Linux 2.0/2.4内核派生而来，沿袭了Linux的绝大部分特性，适合不具备内存管理单元（MMU）的微处理器或微控制器，现已经广泛应用于各种不同的微处理器平台上。因此，对uClinux操作系统核心模块的设计进行分析对于应用系统设计具有重要的现实意义。uClinux作为支持多任务的操作系统，进程调度是其重要的组成部分，本文就uClinux进程调度器的设计实现进行分析。重点讨论了uClinux的进程调度机制，主要包括调度方式、调度策略、调度时机、调度算法这四个方面。



1. uClinux进程的调度方式[1]

uClinux中每个进程的task_struct结构中有四项：policy、priority、counter、rt_priority，

它们是调度程序运行时在所有可运行状态的进程中选择调度的依据。其中，policy是进程调度策略，用来区分实时进程和非实时进程；priority是进程（包括实时进程和非实时进程）的静态优先级；counter是进程剩余的时间片，它的起始值就是priority的值，另外counter还以看作是进程的动态优先级，用于计算处于可运行状态的进程值得运行的程度goodness；rt_priority是实时进程特有的，用于实时进程间的选择。[1]

其进程调度过程可简要概述如下：首先，uClinux根据policy从整体上区分实时进程和非实时进程，其中，实时进程先于非实时进程运行，对于同一类型的不同进程，采用不同的标准来选择，对于非实时进程，uClinux根据进程counter的大小采用动态优先调度；对于实时进程，uClinux采用先来先服务调度（FIFO）和时间片轮转调度（RR）两种调度方法。



2. uClinux进程的调度策略

在uClinux操作系统中，进程的调度策略是由task_struct结构成员policy所选择的，它的值为下述三种之一，即SCHED_FIFO（先来先服务调度），SCHED_RR（时间片轮转调度）

和SCHED_OTHER（非实时调度）。

SCHED_FIFO遵循POSIX1.b标准的调度规则：CPU一直运行，直到有一个进程因I/O阻塞，或者主动释放CPU，或者是CPU被另一个更高rt_priority的实时进程抢占，进程只有当时间片用完时才能被迫释放CPU。

SCHED_RR也遵循POSIX1.b标准的调度规则：与SCHED_FIFO类似，当进程的时间片用完后，调度程序就将其加到SCHED_RR队列的末尾。对于该调度策略只要系统中有一个实时进程在运行，则任何SCHED_OTHER进程都不能在任何CPU上运行。一个进程从创建到任务完成后终止，可能需要经历多次反馈循环。

SCHED_OTHER是传统的unix调度策略，适合于交互式的分时进程。这类非实时进程的优先权取决于两个因素：一个因素是进程剩余时间配额，如果进程用完了配给的时间，则相应优先权为0；如果进程未用完时间片，则剩余时间参与其动态优先级的计算。另一个因素是进程的优先数nice，即优先数越小，优先级越高。

如果系统中有实时进程处于就绪状态，则非实时进程就不能被调度运行，直至所有实时进程都完成了，非实时进程才有机会占用CPU。



3. uClinux进程的调度时机

通过分析进程调度器的源代码，可以发现uCLinux以五种方式转入到schedule（）处理函数进行进程调度[2]。

(1) 进程状态转换时。当进程要调用sleep( )或pause( )等函数使进程状态发生改变时，这些函数会主动调用schedule（）转入进程调度。

(2) 进程终止时，永久放弃对CPU的使用。

(3) 通过时钟中断。uClinux初始化时，设定系统定时器的周期为10ms。当时钟中断发生时，时钟中断服务程序timer_interrupt立即调用时钟处理函数do_timer( )，该函数会调用mark_bh，将bh_active标志的TIMER_BH置1，接着uClinux会在时钟中断服务程序中通过代码片段

If( bh_active & bh_mask)

{ intr_count =1；

do_bottom_half（）；

intr_count = 0；
}

来判断此时是否有bottom_half服务要处理，若有则执行do_bottom_half（）。该函数

会调用时钟响应函数timer_bh( )，分别由updates_times( )、run_old_timers( )和run_timer_list( )检查、执行调用服务。Update_times( )又调用update_process_times( )函数调整进程的时间片，当时间片小于0时，need_resched( 需要重调度)标志会被置位。当时钟中断处理完毕后，系统会返回到入口ret_from_intr，ret_with_reschedule处，判断need_resched 标志是否置位，若是则转入执行schedule( )。

(4) 当唤醒一个睡眠进程时，发现被唤醒的进程比当前进程优先级更高。www.51kaifa.com

(5) 一个进程通过执行系统调用来改变调度策略或降低自身的优先级，从而引起调度。



4. Schedule调度程序核心部分源代码分析[3]

该调度程序的目标是选择下一个要执行的进程：首先对所有进程进行检测，唤醒任何一个得到信号的进程，即改变进程的state属性；然后根据时间片和优先级调度机制来计算处于就绪队列中每个进程的综合优先级，其计算方法由goodness( )函数实现；接着选择综合优先级最高的进程作为随后要执行的进程，若就绪队列中没有可调度的，则重新分配时间片，即改变进程的counter属性值，并利用switch_to( )函数进行进程切换。



asmlinkage void schedule(void){

struct schedule_data * sched_data；

/*描述进程的数据结构，

包含指向所运行CPU的属性。*/

struct task_struct *prev, *next, *p；

struct list_head *tmp；

int this_cpu, c；

spin_lock_prefetch(&runqueue_lock)；

need_resched_back:

prev = current；

this_cpu = prev->processor；

if (unlikely(in_interrupt（）)) {

/*判断是否在中断服务程序中*/

printk("Scheduling in interruptn")； www.51kaifa.com

/*是的话则打印错误提示，退出调度器*/

BUG（）；

}

release_kernel_lock(prev, this_cpu)； /*释放全局内核锁和全局中断锁*/

sched_data=&aligned_data[this_cpu].schedule_data；

if (unlikely(prev->policy == SCHED_RR))

if (!prev->counter) {

prev->counter= NICE_TO_TICKS(prev->nice)；

move_last_runqueue(prev)；

}

switch (prev->state) {

case TASK_INTERRUPTIBLE:

/*此状态表明进程可以被信号中断*/

if (signal_pending(prev)) {

/*如果该进程有未处理的信号*/

prev->state= TASK_RUNNING； break；

}

default:

del_from_runqueue(prev)；

case TASK_RUNNING:；

}

prev->need_resched = 0；

repeat_schedule: /*缺省选择空闲进程*/

next = idle_task(this_cpu)；

c = -1000；

list_for_each(tmp, &runqueue_head) {

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；

}

}

if (unlikely(!c)) {

/*若处于运行队列中的进程没有可调度的，那么得重新分配时间片*/

struct task_struct *p；

for_each_task(p)

p->counter = (p->counter >> 1) + NICE_TO_TICKS(p->nice)；

goto repeat_schedule；

}

sched_data->curr = next；

task_set_cpu(next, this_cpu)； www.51kaifa.com

if (unlikely(prev == next)){

/*如果选中的进程和原来运行的进程是同一个*/

prev->policy &= ~SCHED_YIELD；

goto same_process；

}

kstat.context_swtch++；

/*全局统计进程上下文切换次数*/

prepare_to_switch（）；

/*准备进行进程切换*/

{

……/*进程的页表处理，代码略*/

}

switch_to(prev, next, prev)； www.51kaifa.com

/*切换到选中的进程中*/

__schedule_tail(prev)；

/*考虑将当前被切换下来的进程，放到别的CPU上运行*/

same_process:

reacquire_kernel_lock(current)；www.51kaifa.com

/*重新获得内核锁*/

if (current->need_resched)

goto need_resched_back；

return；

}





整个schedule（）的工作流程可以概述成以下几步：

1). 清理当前运行中的进程

2). 选择下一个投入运行的进程

3). 设置新进程的运行环境www.51kaifa.com

4). 执行进程上下文切换

5). 后期整理



5. 结束语

uClinux的进程调度有其独有的特征，比如为了将三种调度策略协调一致同时不增加程序复杂度，uClinux为每一个进程设置相应的调度策略，并设置实时进程的优先级远高于非实时进程，使得在调度过程中不必去区分实时进程和非实时进程，从而获得最佳响应时间。同时，uClinux操作系统采用底半部分处理策略，将中断处理服务程序分割成两部分，提高了响应时间。另外，被暂时挂起的中断处理程序及任务队列，都要放在schedule( )中去处理，并优于其它进程调度，形成了uClinux独具特色的调度风格。

参考文献：

[1] Claudia Salzberg Rodriguez，Gordon Fischer，Steven Smolski.The Linux Kernel Primer

[M].北京：机械工业出版社，2006www.51kaifa.com

[2] 邹治锋，张曦煌.Linux 2.6进程调度[J].微计算机信息.2006，1-2：77-79

[3] uClinux官方网站源码下载. http://www.uclinux.org/pub/uClinux/dist/.2007