1 嵌入式Linux体系剖析
1.1 嵌入式体系
嵌入式体系（Embedded Systems）是以使用为中心，以核算机技能为根底，软件硬件可取舍（可编程、可重构），适用于使用体系对功用、可靠性、本钱、体积、功耗有严厉要求的专用核算机体系。它一般由嵌入式微处理器、外围硬件设备、嵌入式操作体系以及用户的使用程序等四个部分组成，用于完结对其它设备的操控、监督或办理等功用。其间，嵌入式处理器是嵌入式体系中的中心部件。
1.2 实时操作体系
实时操作体系（RTOS，Real-Time OperaTIon System）是指一个能够在指定的时刻范围内完结特定的功用或许对外部的异步时刻做出呼应的操作体系［3］。其操作的正确性不只依赖于逻辑判别和逻辑设计的正确程度，而且跟这些操作进行的时刻有关。“在指定的时刻范围内”是这个界说的中心，也便是说，实时体系是对呼应时刻有严厉要求的。这个界说要求了：体系应该有在事前界说的时刻范围内辨认和处理离散事情的才干；体系能够处理和存储操控体系所需求的很多的数据。
1.3 嵌入式实时操作体系
由嵌入式体系的概念和特色能够看出，一个嵌入式体系对操作体系的可靠性、实时性都有很高的要求。尤其在嵌入式技能广泛使用的工业操控、航空军事等范畴，对嵌入式操作体系的实时呼应才干提出了十分严厉的要求，哪怕呈现很小的时刻误差，都有或许形成无法挽回的丢失。这便是为何绝大多数嵌入式操作体系都选用实时操作体系的首要原因。实时操作体系使用到嵌入式范畴，便呈现了嵌入式实时操作体系，它是实时操作体系与嵌入式体系相结合的产品，具有实时性的一起又具有嵌入式体系的特色。
2 实时进程调度算法剖析
2.1 Linux进程调度相关概念
进程调度分红两个部分，一个是调度的机遇，即什么时候调度；一个是调度的算法，即怎么调度和调度哪个进程。
Linux进程调度机遇 ：
调度机遇是指在什么状况下运转调度程序来挑选进程运转。在Linux体系中调度程序是经过函数schedule（）来完结的，这个函数被调用的频率很高，由它来决议要运转的进程。
Linux调度机遇首要分两种状况：自动调度和被迫调度。自动调度是指当进程状况发生变化时直接调用schedule（）来完结调度。被迫调度是指当一个进程运转时刻片到或安排妥当行列中增加了一个进程，此刻体系并不当即进行调度，而仅仅是将当时进程的调度标志方位1，当体系由中心态向用户态改变之前查看当时进程的调度标志是否为1，若为1，则调用schedule（）进行调度。
2.2 进程调度的原理
进程调度分红两个部分，一个是调度的机遇，即什么时候调度；一个是调度的算法，即怎么调度和调度哪个进程。
调度程序运转时，要在一切可运转的进程中挑选最值得运转的进程。挑选进程的依据首要有进程的调度战略（policy）、静态优先级（priority）、动态优先级（counter）、以及实时优先级（rt-priority）四个部分。首要，Linux从全体上区分为实时进程和一般进程，二者调度算法不同，实时进程优先于一般进程运转。进程按照优先级的凹凸被顺次调用，实时优先级等级最高 。
2.3 实时调度算法及缺点
现在，实时调度算法首要能够分为三大类：时刻驱动调度、优先级驱动调度、份额同享调度。三者各有优缺点，时刻驱动调度、优先级驱动调度侧重于结实时使命，份额同享调度更为适合于软实时使命，在网络体系中使用较多。份额同享调度基本思想便是按照必定的权重份额对一组需求调度的使命进行调度，让它们的履行时刻与它们的权重成正比，是一种加权轮转调度 。
Linux进程选用的是多级轮转调度算法，尽管Linux经过将进程划分为实时进程和一般进程，按照优先级进行调度来完结实时的特性，但是仅能取得秒级呼应时刻，Linux尽管给实时进程供给了较高的优先级，但是没有参加时刻约束，在高实时呼应状况下还不能满足要求。当进程进入中心态时，其它进程不论优先级多高也有必要等候。
3 实时调度算法的改善
3.1 实时模型
作为实时体系调度算法应归纳考虑进程的价值和截止两个概念，以确保实时进程在截止期内尽或许多地完结，在这儿提出新的调度算法，改善Linux的实时性。
即：进程的优先级数（Vi）=该进程重要程度（Wi）+其急迫度（pi/（d-TI））*系数k。急迫度的值越大，阐明从时刻上看这个使命越急迫。优化后调度算法仍以进程的价值为根底，一起也重视了完结进程的急迫度，关于优先级相同的进程，选用FIFO调度战略。进程的价值越大阐明该进程越重要，CPU越应完结它。
优化后调度算法仍以进程的价值为根底，一起也重视了完结进程的急迫度，关于优先级相同的进程，选用FIFO调度战略。进程的价值越大阐明该进程越重要，CPU越应完结它，但是对一些价值和它相差不多，而急迫度要比它大得多的进程来说，就不公平了。例如，有两个进程A，B一起提交，A的价值是1001，估量履行时刻是1ms，相对截止期是5ms，B的价值是1000，估量履行时刻是1ms，相对截止期是2ms，假定这儿的系数因子k是10，则更应该履行进程B。这是由于进程A，B的价值附近，而B的急迫度要比A的大一些，A的优先级＝1001+1/5*10=1003，B的优先级=1000+1/2*10=1005，因而挑选B先运转，以避免B的夭亡（注：Linux中实时进程的值设为从1000到1099，非实时进程的值设为从1到99，因而挑选系数因子k为10）优化后的调度算法仍然选用时刻片轮转战略，按照Linux分配给进程的时刻片为20次时钟滴哒，也便是200ms =20*10ms 。
3.2 结构界说
本文给出实时进程的结构界说，非实时进程仍然选用原有的动态优先级调度战略，其结构界说省略。
#define SCHED RR
typedef struct TaskNode {
int dTIme； //进程的截止期
int T；//进程提交时刻
int pTIme；//进程没有完结时刻，初值等于使命的履行时刻估量
int flag； //其值为1时阐明是实时进程，为0时阐明对错实时进程
int v；//进程的优先级数
int w；//进程的价值
struct TaskNode *next
}TaskNode *prior，*next；
3.3 链表界说
整个调度算法能够用双链表来描绘，即两级行列，分别用两个指针指向。开始，这两部分的头指针都指向“0”，标明这两个行列均为空。其间实时进程的安排妥当等候行列用一个循环单链表完结。
开始时的一级行列，是新到的比当时运转进程优先级低的实时进程。假如一个进程由于时刻片届时或被更高优先级使命抢占，依据它的优先级将其刺进到第二级行列。
若当时进程的时刻片届时，CPU便挑选当时行列中第二个节点的进程来判别，假如它的急迫度大于1的话，阐明这个进程在规则时刻内不能完结，它必定夭亡，将其放入一般进程行列中，再挑选链表的第三个节点判别，假如急迫度小于等于1便运转它，状况如图１所示。
图１ 优化后调度算法的实时进程优先级表
当一级行列为空时，二级行列便升成一级行列。
一般进程的调度经过单链表来完结。假如新来的进程归于一般进程，则依据优先级凹凸刺进一般行列。只要实时行列（一级和二级行列）为空时，一般行列才干被调度。
3.4 实时进程的调度战略算法描绘
1）实时安排妥当行列的初始化
#define LEN sizeof（TaskNode）
创立空链表：
TaskNode*creat new line（）
{
TaskNode* head；
head=（TaskNode））malloc（LEN）；
head-》w=-1；
Head1=Head2=head：
Head1-》next=Head2-》next=head；
return head；
}
2） 实时进程接纳战略
#define K 10
void* pnow；
pnew指向新来的实时进程，pnow指向当时运转的实时进程。
新来的进程是实时进程：
if（（*pnew）.flag ==1）
{
当时运转的进程是实时进程：
if （（*pnow）.flag ==1）
{
W =（*pnew）.v+（*pnew）.ptime）/（（*pnew）.dtime-（*pnew）.T））*K；
if（w》（*pnow）.v+（（*pnow）.ptime/（（*pnow）.dtime-（*pnow）.T））*K））
{
当时运转进程刺进二级行列：
move last runqueue（Head2，pnow）；
新来的进程抢占CPU：
pnow=pnew；
}
else
将新来的进程刺进到等候链表的一级行列：
move last runqueue（Head1，pnow）；
}
Else
当时运转的进程对错实时进程，将当时进程刺进非实时行列，非实时进程的刺进算法：
move last（pnow）；
move last略
}
else//新来的进程对错实时进程
move last（pnew）；//将新来的非实时进程刺进非实时行列刺进算法略
3）实时进程刺进战略
move last runqueue（h，p）；
TaskNode*h，*p；
{
TaskNode*p1，*p2，*t；
P1=h；
P2=pl-》next；
if （h==Head1）//刺进一级行列
while（（*p）.w《=（*p2）.w&&pl！=Head2）//优先级相同的进程选用FIFO调度战略
{
pl=p2；
p2=（*p2）.next；
}
（*p）.next=p2；
（*p1）.next=P；
if（P1==Head2）//该节点刺进到一级行列的结尾，则该节点便成了一级行列的结尾
Head2=P；
else
{
While（（*p）.w《=（*p2）.w） //刺进二级行列
{
P1=p2；
p2=（*p2）.next；
（*p）.next=p2；
（*p1）.next=P；
}
}
}
阐明：依据传来的h值，决议在一级行列h的值是Headl时仍是在二级行列h的值是Head2时中查找刺进的适宜方位。
当P是新来的使命时，h的值是Head1，p被括入一级行列。p2是p1的后继节点。在循环体中，当新来的进程P高于一级行列的进程p2时，中止循环，将P刺进到p1的后边；当p1等于Head2时，阐明一级行列的节点的优先级都比P节点的高，中止循环，把P插在p1的后边，则该节点便成了一级行列的结尾。
当P是被抢占的使命时，h的值是Head2，p被刺进二级行列。在循环体中，当P的优先级高于二级行列的进程p2时，中止循环，将P刺进到p1的后边；假如P高于二级行列的一切进程时，也会在p2指向Head时，因（*p）.w《=（*p2） .w而中止，则该节点便成了二级行列的结尾。由于（（head1）.w=-1，而任何进程的优先级数都不会小于1因而当p1，p2在这二级行列中遍历时，必定能有时机中止。
4） 调度等候链表中的一级行列
当时进程完结或时刻片届时，调度等候链表中的一级行列中最前面的实时进程：
PnowTime；//当时的时刻
run list（pnow）；
TaskNode*pnow；
{
if（*pnow）.ptime！=0）//该进程未完结
{
if（*pnow）.flag==1）
if（PnowTime-（*pnow）.T》=（*pnow）.dtime）
move-last-runqueue（head2，now）；//将未完结的进程刺进到 二级行列
else
pnow； //被夭亡
else
move last（pnow）； //将未完结的非实时进程刺进到非实时行列
}
p=get node（ ）；从安排妥当链表中取得优先级最大的进程
while（1）
{
if （p！ =NULL）
{
if （（*p）.time 《= （*p）.dtime-PnowTime）） //实时进程而且没超越截止期
pnow=P；
break；
else//该进程己经不能完结，所以从头从安排妥当链表中取得优先级最大的进程
p=get node；
}
else//实时安排妥当链表中无等候的进程调用非实时安排妥当行列
return p；
}
5）实时进程删去战略
//curtime是当时的时刻
get node（）
{
p=（Headl）.next；
while（1）
if （Head1）.next！= Head1）//有进程安排妥当等候
{
p=（Headl）.next；
if（（*p）.ptime》（（*p）.dtime-Pnowllme）） //进程未完结的时刻大于相对截止期，该进程夭亡
{
（Head1）.next=（*p）.next；
if（p= =Head2）//删去的节点是一级行列的尾节点时
{
Head2=Head3；//二级行列荣升为一级行列
Head3=Head2；//新二级行列为空
}
}
else
else //p进程能够在规则时刻完结
return p； //无进程等候
return NULL；
针对现在Linux实时体系调度算法中仅用进程的价值来确认优先级的现象，本文提出了归纳考虑进程的重要性和急迫度来决议优先级的调度算法。算法将进程的截止期和价值两个不相关的概念，经过公式结合在一起，用来核算安排妥当等候行列中进程的优先级数。
该算法经过双链表来完结。在CPU正常负载的状况下，优化后的调度算法表现了更优的实时功能。
