摘 要:本文结合源代码着重分析了Linux进程调度的依据、策略和调度程序schedule()。

关键词: 嵌入式Linux；进程调度；实时进程；调度策略。

１　前言

处理机（CPU）是整个计算机系统的核心资源，在多进程的操作系统中，进程数往往多于处理机数，这把导致各进程互相争夺处理机。进程调度对系统功能的实现及各方面的性能都有着决定性的影响，其实质就是把处理机公平、合理、高效地分配给各个进程。调度是实现多任务并发执行的必要手段，不同的操作系统有着不同的调度目标。在传统的Unix类分时系统中，保证多个进程公平地使用系统资源，提供较好的响应时间是调度的主要目标；而在强实时操作系统中，总是优先级高的任务优先获得处理机的使用权。

Linux具有内核稳定、功能强大、可裁减、低成本等特点，非常适合嵌入式应用。但是Linux内核本身并不具备强实时特性，且内核体积较大，因此，想要把Linux用于嵌入式系统，必须对Linux进行实时化、嵌入式化。Linux结合实时进程和非实时进程（普通进程）自身的特点，综合了上述几种调度策略，实现了高效、灵活的进程调度。

２　Linux进程调度分析

2.1　Linux进程状态的描述

Linux把进程状态描述为如下五种：

TASK_RUNNING：可运行状态。处于该状态的进程可以被调度执行而成为当前进程。

TASK_INTERRUPTIBLE：可中断的睡眠状态。处于该状态的进程在所需资源有效时被唤醒，也可以通过信号或定时中断唤醒。

TASK_UNINTERRUPTIBLE：不可中断的睡眠状态。处于该状态的进程仅当所需资源有效时被唤醒。

TASK_ZOMBIE：僵尸状态。表示进程结束且已释放资源，但其task_struct仍未释放。

TASK_STOPPED：暂停状态。处于该状态的进程通过其他进程的信号才能被唤醒。

2　调度方式

Linux中的每个进程都分配有一个相对独立的虚拟地址空间。该虚存空间分为两部分：用户空间包含了进程本身的代码和数据；内核空间包含了操作系统的代码和数据。

Linux采用“有条件的可剥夺”调度方式。对于普通进程，当其时间片结束时，调度程序挑选出下一个处于TASK_RUNNING状态的进程作为当前进程（自愿调度）。对于实时进程，若其优先级足够高，则会从当前的运行进程中抢占CPU成为新的当前进程（强制调度）。发生强制调度时，若进程在用户空间中运行，就会直接被剥夺CPU；若进程在内核空间中运行，即使迫切需要其放弃CPU，也仍要等到从它系统空间返回的前夕才被剥夺CPU。

3 调度策略

3.1　三种调度策略

(1)SCHED_OTHER。SCHED_OTHER是面向普通进程的时间片轮转策略。采用该策略时，系统为处于TASK_RUNNING状态的每个进程分配一个时间片。当时间片用完时，进程调度程序再选择下一个优先级相对较高的进程，并授予CPU使用权。

（２）SCHED_FIFO。SCHED_FIFO策略适用于对响应时间要求比较高，运行所需时间比较短的实时进程。采用该策略时，各实时进程按其进入可运行队列的顺序依次获得CPU。除了因等待某个事件主动放弃CPU，或者出现优先级更高的进程而剥夺其CPU之外，该进程把一直占用CPU运行。

(3)SCHED_RR。SCHED_RR策略适用于对响应时间要求比较高，运行所需时间比较长的实时进程。采用该策略时，各实时进程按时间片轮流使用CPU。当一个运行进程的时间片用完后，进程调度程序停止其运行并把其置于可运行队列的末尾。

3.2 　进程调度依据

Linux只有一个可运行队列，处于TASK_RUNNING状态的实时进程和普通进程都加入到这个可运行队列中。Linux的进程调度采用了动态优先级和权值调控的方法，既可实现上述三种调度策略，又能保证实时进程总是比普通进程优先使用CPU。描述进程的数据结构task_struct中用以下几个数据作为调度依据：

Struct task_struct {
    ……
    volatile long need_resched;  /*是否需要重新调度*/
　　long counter;  /*进程当前还拥有的时间片*/
long nice;  /*普通进程的动态优先级，来自UNIX系统*/
unsigned long policy; /*进程调度策略*/
unsigned long rt_priority;  /*实时进程的优先级*/
……
}；

counter的值是动态变化的，进程运行时，每一个时钟滴答后，其值减1。当counter值为0时，表示该进程时间片已用完，该进程回到可运行队列中，等待再次调度。

为保证实时进程优于普通进程，Linux采取加权处理法。在进程调度过程中，每次选取下一个运行进程时，调度程序首先给可运行队列中的每个进程赋予一个权值weight。普通进程的权值就是其counter和优先级nice的综合，而实时进程的权值是它的rt_priority的值加1000，确保实时进程的权值总能大于普通进程。调度程序检查可运行队列中所有进程的权值，选取权值最大者作为下一个运行进程，保证了实时进程优先于普通进程获得CPU。Linux使用内核函数goodness()对进程进行加权处理：