Linux是一套免费运用和自在传达的类Unix操作体系，是一个根据POSIX和UNIX的多用户、多使命、支撑多线程和多CPU的操作体系。它能运转首要的UNIX工具软件、运用程序和网络协议。
1.前语
处理机（CPU）是整个核算机体系的中心资源，在多进程的操作体系中，进程数往往多于处理机数，这将导致各进程相互抢夺处理机。进程调度对体系功用的完结 及各方面的功能都有着决定性的影响，其实质便是把处理机公正、合理、高效地分配给各个进程。调度是完结多使命并发履行的必要手法，不同的操作体系有着不同 的调度方针。在传统的Unix类分时体系中，保证多个进程公正地运用体系资源，供给较好的呼应时刻是调度的首要方针;而在强实时操作体系中，总是优先级高 的使命优先取得处理机的运用权。
Linux具有内核安稳、功用强大、可削减、低成本等特色，十分合适嵌入式运用。可是Linux内核自身并不具有 强实时特性，且内核体积较大，因而，想要把Linux用于嵌入式体系，有必要对Linux进行实时化、嵌入式化。Linux结合实时进程和非实时进程（一般 进程）自身的特色，归纳了上述几种调度战略，完结了高效、灵敏的进程调度。
2.Linux进程调度剖析
2.1 Linux进程状况的描绘
Linux将进程状况描绘为如下五种：
TASK_RUNNING：可运转状况。处于该状况的进程能够被调度履行而成为当时进程。
TASK_INTERRUPTIBLE：可中止的睡觉状况。处于该状况的进程在所需资源有用时被唤醒，也能够经过信号或守时中止唤醒。
TASK_UNINTERRUPTIBLE：不行中止的睡觉状况。处于该状况的进程仅当所需资源有用时被唤醒。
TASK_ZOMBIE：僵尸状况。表明进程完毕且已开释资源，但其task_STruct仍未开释。
TASK_STOPPED：暂停状况。处于该状况的进程经过其他进程的信号才干被唤醒。
2.2 调度办法
Linux中的每个进程都分配有一个相对独立的虚拟地址空间。该虚存空间分为两部分：用户空间包含了进程自身的代码和数据;内核空间包含了操作体系的代码和数据。
Linux选用“有条件的可掠夺”调度办法。关于一般进程，当其时刻片完毕时，调度程序选择出下一个处于TASK_RUNNING状况的进程作为当时进程 （自愿调度）。关于实时进程，若其优先级足够高，则会从当时的运转进程中抢占CPU成为新的当时进程（强制调度）。产生强制调度时，若进程在用户空间中运 行，就会直接被掠夺CPU;若进程在内核空间中运转，即便迫切需求其抛弃CPU，也仍要比及从它体系空间回来的前夕才被掠夺CPU。
3.调度战略
3.1 三种调度战略
（1）SCHED_OTHER。SCHED_OTHER是面向一般进程的时刻片轮转战略。选用该战略时，体系为处于TASK_RUNNING状况的每个进程分配一个时刻片。当时刻片用完时，进程调度程序再选择下一个优先级相对较高的进程，并颁发CPU运用权。
（2）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（）对进程进行加权处理：
StaTIc inline goodness （struct task_struct * pint this_cpu， struct mm_struct *this_mm）{
Int weight;
Weight=-1;
/*判别假如使命的调度战略被置为SCHED_YIELD的话，则置权值为-1，回来。体系调用SCHED_YIELD表明为“礼让”进程，其权值为最低*/If （p-》policy & SCHED_YIELD）
goto out;
/*先对一般进程进行处理（由于多数是一般进程，这样做有利于进步体系功率）*/If （p-》policy==SCHED_OTHER）{
weight=p-》counter; /*回来权值为进程的counter值*//*假如当时进程的counter为0，则表明当时进程的时刻片已用完，直接回来*/If （！ weight）
Goto out;
#Ifdef CONFIG_SMP
If （p-》processor==this_cpu）
Weight+=PROC_CHANGE_PENALTY;
#Endif
/*对进程权值进行微调，假如进程的内存空间运用当时正在运转的进程的内存空间，则权值额外加1*/If （p-》mm==this_mm||！ p-》mm）
Weight+=1;
/*将权值加上20与进程优先级nice的差。一般进程的权值首要由counter值和nice值组成*/Weight+=20-p-》nice;
Goto out;
}
/*对实时进程进行处理，回来权值为rt_priority+1000，保证优先级高于一般进程*/Weight=1000+p-》rt_priority;
Out：
return weight;
}
从goodness（）函数能够看出，关于一般进程，其权值首要取决于剩下的时刻配额和nice两个要素。nice的规则取值规模为19～-20，只要特 权用户才干把nice值设为负数，而表达式（20-p-》nice）掉转方向成为1～40。所以，归纳的权值在时刻片没有用完时基本上是两者之和。 假如是内核进程，或许其用户空间与当时进程相同，则权值将额外加1作为奖赏。关于实时进程，其权值为1000+p-》rt_priority，当 p-》counter到达0时该进程将移到行列的尾部，但其优先级仍不少于1000。可见当有实时进程安排妥当时，一般进程是没时机运转的。
由此能够看出，经过goodness（）函数，Linux从优先考虑实时进程动身，完结了多种调度战略的一致处理，其规划思维可谓十分奇妙。
3.3 进程调度
Linux的进程调度由调度程序schedule（）完结，经过对schedule（）的剖析能更好了解调度的进程。schedule（）首要判别当时运转进程是否具有SCHED_RR 标志，本文取一部分加以剖析：
if （prev-》policy==SCHED_RR） /*假如是轮转调度，先作goto特别处理*/Goto move_rr_last;
……
Move_rr_last：
If （！ prev-》counter）{ /*假如counter减至0*/Prev-》counter=NICE_TO_TICKS （prev-》nice）;Move_last_runqueue （prev）;
}
Goto move_rr_back;
prev-》counter代表当时进程的运转时刻配额，其值逐步减小。一旦减至0，就要从可履行行列runqueue中当时的方位移到结尾，宏操 作NICE_TO_TICKS根据体系时钟的精度将进程的优先等级换算成能够运转的时刻配额，即康复其初始的时刻配额。把该进程移到结尾意味着：假如没有 权值更高的进程，可是有一个权值与这相同的进程存在，那么，那个权值相同而摆放在前的进程就会被选中，然后保全了全局。
接下来调度函数查询当时运转进程的状况是否改动：
Move_rr_back：
switch（prev-》state）{ /*检查进程当时的状况*/Case TASK_INTERRUPTIBLE：
if （signal pending（prev））{ /*判别运转期间是否收到信号*/Prev-》state=TASK_RUNNING;
Break;
}
default： /*当时运转进程处于非TASK_RUNNING状况*/Del_from_runqueue （prev）;
Case TASK_RUNNING：
}
Prev-》need_resched=0;
简单了解：假如发现进程处于TASK_INTERRUPTIBLE状况且有信号等候处理，则内核将其状况设为TASK_RUNNING，让其处理完信号， 接下来仍有时机取得CPU;假如没有信号等候，则将其从可运转行列中撤下来;假如处于TASK_RUNNING状况，则持续进行。然后，将 prev-》need_resched的值康复成0，由于所需的调度已经在运转。
Repeat schedule （）：
next=idle_task（this_cpu）; /*next指向最佳候选进程*/c=-1000; /*进程的归纳权值，初始时是0号进程，-1000是或许的最低值*/If （prev-》state==TASK_RUNNING）
Goto still_running;
Still_running_back：
List_for_each （tmp， &runqueue_head）{
P=list_entry （tmp， struct task_struct， run_list）;if （can_schedule（p，this_cpu））{ /*核算p指向的进程的权值*/Int weight=goodness （p， this_cpu， prev-》active_mm）;if （weight》c） /*比较权值巨细*/
C=weight， next=p;
}
}
调度之前，将待调度的进程默以为0号进程，权值置为-1000。0号进程比较特别，既不会睡觉，又不能被杀死。接下来内核遍历可履行行列run queue中的每个进程，为每个进程经过goodness（）函数核算出它当时所具有的权值，然后与当时的最高值c比较。假如两个进程具有相同权值的话， 那么排在前面的进程胜出。
Still_running：
C=goodness （prev， this_cpu， prev-》active_mm）;Next=prev;
Goto still_running_back;
上面的代码告知咱们，假如当时进程想要持续运转，那么在选择进程时以当时进程此时的权值开端。这意味着，相关于权值相同的其他进程来说，当时进程优先。
若发现当时已选进程的权值为0，则需求从头核算各个进程的时刻配额，schedule（）将转入recalculate部分。限于篇幅，在此不再打开。
4.完毕语
以上结合代码扼要介绍了Linux中进程调度的基本思维、根据和战略，简单发现Linux高功率和较强支撑并发进程等特色。近年来，嵌入式Linux的研 究正在成为一个热门，了解Linux进程调度的原理，并在此基础上改善调度算法或许存在的缺点，能够进一步增强其对实时性的支撑，使之进一步适应在嵌入式 体系领域内的运用。
责任编辑：ct
