嵌入式Linux系统实时进程调度算法改进

1 嵌入式Linux系统分析
1.1 嵌入式系统
嵌入式系统（Embedded Systems）是以应用为中心，以计算机技术为基础，软件硬件可剪裁（可编程、可重构），适用于应用系统对功能、可靠性、成本、体积、功耗有严格要求的专用计算机系统。它一般由嵌入式微处理器、外围硬件设备、嵌入式操作系统以及用户的应用程序等四个部分组成，用于实现对其它设备的控制、监视或管理等功能。其中，嵌入式处理器是嵌入式系统中的核心部件。
1.2　实时操作系统
实时操作系统（RTOS，Real-Time Operation System）是指一个能够在指定的时间范围内完成特定的功能或者对外部的异步时间做出响应的操作系统[3]。其操作的正确性不仅依赖于逻辑判断和逻辑设计的正确程度，而且跟这些操作进行的时间有关。“在指定的时间范围内”是这个定义的核心，也就是说，实时系统是对响应时间有严格要求的。这个定义要求了：系统应该有在事先定义的时间范围内识别和处理离散事件的能力；系统能够处理和存储控制系统所需要的大量的数据。
1.3　嵌入式实时操作系统
由嵌入式系统的概念和特点可以看出，一个嵌入式系统对操作系统的可靠性、实时性都有很高的要求。尤其在嵌入式技术广泛应用的工业控制、航空军事等领域，对嵌入式操作系统的实时响应能力提出了非常严格的要求，哪怕出现很小的时间偏差，都有可能造成无法挽回的损失。这便是为何绝大多数嵌入式操作系统都采用实时操作系统的主要原因。实时操作系统应用到嵌入式领域，便出现了嵌入式实时操作系统，它是实时操作系统与嵌入式系统相结合的产物，具有实时性的同时又具有嵌入式系统的特点。
2　实时进程调度算法分析
2.1　Linux进程调度相关概念
进程调度分成两个部分，一个是调度的时机，即什么时候调度；一个是调度的算法，即如何调度和调度哪个进程。
Linux进程调度时机[1]：
调度时机是指在什么情况下运行调度程序来选择进程运行。在Linux系统中调度程序是通过函数schedule（）来实现的，这个函数被调用的频率很高，由它来决定要运行的进程。
Linux调度时机主要分两种情况[2]：主动调度和被动调度。主动调度是指当进程状态发生变化时直接调用schedule（）来实现调度。被动调度是指当一个进程运行时间片到或就绪队列中增加了一个进程，此时系统并不立即进行调度，而仅仅是将当前进程的调度标志位置1，当系统由核心态向用户态转变之前检查当前进程的调度标志是否为1，若为1，则调用schedule（）进行调度。
2.2　进程调度的原理
进程调度分成两个部分，一个是调度的时机，即什么时候调度；一个是调度的算法，即如何调度和调度哪个进程。
调度程序运行时，要在所有可运行的进程中选择最值得运行的进程。选择进程的依据主要有进程的调度策略（policy）、静态优先级（priority）、动态优先级（counter）、以及实时优先级（rt-priority）四个部分。首先，Linux从整体上区分为实时进程和普通进程，二者调度算法不同，实时进程优先于普通进程运行。进程依照优先级的高低被依次调用，实时优先级级别最高[3]。
2.3　实时调度算法及缺陷
目前，实时调度算法主要可以分为三大类：时间驱动调度、优先级驱动调度、比例共享调度。三者各有优缺点，时间驱动调度、优先级驱动调度侧重于硬实时任务，比例共享调度更为适合于软实时任务，在网络系统中应用较多。比例共享调度基本思想就是按照一定的权重比例对一组需要调度的任务进行调度，让它们的执行时间与它们的权重成正比，是一种加权轮转调度[4]。
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[5]。
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）.wpl!=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正常负载的情况下，优化后的调度算法体现了更优的实时性能。