一种改进的 Linux 实时进程调度算法 —— RAD 算法

王昊

中国石化销售股份有限公司河北石油分公司，河北 ·石家庄 050000

【摘要】在Linux实时进程调度算法中，RM算法是一种针对任务周期的长短来确定优先级调度算法，EDF算法是以最后期限的顺序来指定优先级的动态调度算法，这两种算法在Linux内核调度算法中都得到广泛应用。在深入分析以上两种算法优缺点的基础上，提出将两种算法优点合并，根据进程的重要程度和紧急程度来选择确定进程调度的优先级，得到一个新的高效 RAD( Rate And Deadline) 算法。

An Improved Linux Real-time Process Scheduling Algorithm——RAD Algorithm

WANG Hao

(Hebei Petroleum Branch of Sinopec Sales Co., Ltd., Shijiazhuang, Hebei, 050000, China)

In Linux real-time process scheduling algorithm, RM algorithm is a priority scheduling algorithm according to the length of task cycle, and EDF algorithm is a dynamic scheduling algorithm that assigns priority in the order of deadlines. These two algorithms are widely used in Linux kernel scheduling algorithms. On the basis of in-depth analysis of the advantages and disadvantages of the above two algorithms, a new efficient RAD (Rate And Deadline) algorithm is proposed by combining the advantages of the two algorithms and determining the priority of process scheduling according to the importance and urgency of the process.

【关键词】 RM 算法；EDF 算法；调度

RM algorithm; EDF algorithm; scheduling

1 引言

在 Linux 实时调度算法中，EDF ( Earliest Deadline First) 算法是根据任务的资源需求来动态地分配任务的优先级，当系统的负载相对较低时，这种算法非常有效。但是，当系统负载极端沉重时，可能会使一些进程错过截止期，此时系统的性能不如FIFO方法[1-4]。RM算法在系统超载情况下，可以保证高优先级任务的顺利执行，但是不能获得全部的处理器利用率100%。最坏情况下，最大的处理器利用率只能达到69%，一般情况下，对于随机的任务集大约只有88%。69%或者88%的处理器利用率，对于许多实时应用来说是一个严重的限制。

2 RAD 调度算法描述

任务的调度优先级并不是单纯地由周期或截止期限决定，而是由数值对(priority，urgency)决定。其中，pri2ority表示重要程度，并不代表任务周期等时间属性，而是反映用户的需求或喜好，由用户决定;urgency表示紧急程度，由任务的当前截止期限动态决定。对于截止期限做如下修改，定义调度算法中优先级最高的任务为Ta，在剩下的任务中找到一个绝对时限最小而空闲时间大于Ta的任务Tmin。截止期限时间为min(Dmin(t)-La(t)，Ea(t))，Dmin(t)表示t时刻任务Tmin的相对截止期，而La(t)、Ea(t)分别表示在t时刻任务Ta的空闲时间和该时刻的剩余执行时间。

如果满足下列条件之一，任务A具有比任务B更高的优先级。

（1）任务A的priority比任务B的小，这里priority值越小表示优先级越高，任务对用户越重要；

（2）任务A和任务B具有相同的priority，但前者的urgency更小，即任务更紧急。

RAD算法主要包括任务的准入控制机制和在线调度器两部分。其中，准入控制是为了保证系统中原有重要任务的执行不受新任务影响而设计的。当有新任务到达时，准入控制将根据当前系统负载和新任务的(priority，urgency)数值对决定接纳或拒绝该任务进入系统。

记EDF-QUEUE为按最早截止期限由小到大排列的任务管理队列，PRIO-QUEUE为按优先级值由小到大排列的任务管理队列，即按优先级由高到低的顺序排列。系统中的每个任务同时存在于这两个队列中。记ti为系统任务集合中的第i个周期性任务，Jij为ti的第j个工作。当新的工作Jij到达时，RAD算法的任务准入控制首先判断新工作与系统原有工作的CPU总需求是否超过最小上界110，如果不超过，则接纳该工作，并将它同时加入EDF-QUEUE和PRIO-QUEUE这两个队列中。否则，比较新工作与PRIO-QUEUE队尾工作的优先级，即将新工作与系统中优先级最低的工作进行比较，若新工作的优先级较低，则拒绝它。否则去掉PRIO-QUEUE队尾的工作，同时将其从EDF-QUEUE队列中去除，然后再次判断新工作与系统中剩余工作的总负载是否超载，反复迭代，直至接受或拒绝该任务。

算法的具体描述如下:

BEGIN Admission - Cont rl ( J ij ) ∥J ij is a new job L 1 : IF the following relation is met

ei + ∑

ek/ pk ≤1

pi k , tk ED K - QU EU E

go to L 2 EL SE

IF non2emp ty ( PR IO - QU EU E)

Set cur - job to be the job with the lowest priority in queue PR IO - QU EU E ;

IF the priority of cur - job is higher than J ij

reject J ij

return EL SE

delete cur - job f rom queue EDF - QU EU E and PR IO - QU EU E

go to L 1 EL SE

L 2 :accept J ij

enqueue J ij into EDF - QU EU E and PR IO - QU EU E

return END

其中：pi为任务的周期，ei为任务的最坏执行时间或平均执行时间。

3 试验结果及分析

3.1 系统轻载时

设有3个任务，3个任务先后分别运行在RM、EDF、RAD算法下，任务集在不同算法下的平均执行性能，即截止期限得到满足的程度。

在RM算法下，任务1和任务2的执行均得到保证，但任务3存在期限未被满足的情况。而在EDF和RAD算法下，3个任务的执行均得到了保证。因此，实验结果表明，在系统轻载情况下，RAD具有与EDF算法同样的性能，可以充分地利用系统资源，保证所有任务的截止期限得到满足。

3.2 系统超载时

4个任务先后分别运行在RM、EDF、RAD算法下。EDF算法中，除了任务4的执行得到保证外，其余任务的执行均未被满足，而且执行结果比较相近，体现了EDF算法共享CPU的本质，尤其在系统超载情况下，每个任务都有机会执行，但执行性能比较差，任务的大部分截止期限得不到满足。在RM算法下，只有周期最短的任务1和任务2的截止期限均得到保证。同样在RAD算法下，只有最重要的任务1和任务2的截止期限得到满足。因此，实验结果表明，在超载情况下，RAD具有与RM算法同样的性能，可以保证较重要任务的顺利执行。

4 结论

实验结果表明 :

（1）RAD算法具备RM和EDF二者的优点：在轻载情况下，如EDF算法一样，充分利用系统资源，所有任务的截止期限都得到满足;在超载情况下，如RM算法一样，保证高优先级任务的顺利执行;此外，在确保重要任务顺利执行的前提下，尽可能地优先执行紧急型任务。

（2）RAD算法比SCHED-FIFO和SCHED-RR策略能更有效地支持实时任务调度。