Method for the real-time ordering of a set of noncyclical multi-frame tasks

摘要

A method for real-time scheduling of an application having a plurality m of software tasks executing at least one processing operation on a plurality N of successive data frames, each of said tasks i being defined at least, for each of said frames j, by an execution time Cij, an execution deadline Dij and a guard time Pij with respect to the next frame j+1, said guard time Pij being greater than or equal to said deadline Dij,includes: for each task i, calculating the ratios;CijDij
and then searching for the maximum over all frames j of ratios
;max(CijDij),
comparing the sum
;∑i=0m-1⁢max0≤j≤N-1⁢(CijDij)
with the number of processors operating in parallel over which the total computation load of the real-time application is distributed, and, if said sum
;∑i=0m-1⁢max0≤j≤N-1⁢(CijDij)
is less than or equal to the number of processors, concluding on the feasibility of the real-time execution of all said software tasks distributed over said processors.

主权项

1. A method for the real-time dynamic priority scheduling of an application executed on at least one processor, said application consisting of a plurality m of software tasks executing at least one processing operation on a plurality of N successive data frames, each of said tasks i being defined at least, for each of said frames j, by an execution time Cij, an execution deadline Dij and a guard time Pij with respect to the next frame j+1, said guard time Pij being greater than or equal to said deadline Dij, said method comprising:
for each task i, calculating the ratiosCijDijbetween the execution time Cij of each frame j and the corresponding deadline Dij ,
for each task i, searching for the maximum of said ratios over all of said frames jmax(CijDij), comparing the sum∑i=0m-1⁢max0≤j≤N-1⁢(CijDij)over all of said tasks i of said maxima with the number p of processors operating in parallel over which the total computation load of said real-time application is distributed,
if said sum∑i=0m-1⁢max0≤j≤N-1⁢(CijDij)is less than or equal to the number p of processors, then concluding on the feasibility of the real-time execution of all of said software tasks distributed over said processors and associating a dynamic execution priority with the task i according to its execution deadline Dij so that, at a given instant, the task which has the highest priority is the one whose deadline is the closest in time Dij ,
if said sum∑i=0m-1⁢max0≤j≤N-1⁢(CijDij)is strictly greater than the number p of processors, rejecting the task i and/or redefining its execution time Cij and execution deadline Dij parameters so as to satisfy the inequality∑i=0m-1⁢max0≤j≤N-1⁢(CijDij)≤p.