At a high level, the parameters are task type (periodic or aperiodic), duration (execution time), period, relative deadline, and release time (a.k.a. phase). To spawn tasks, I had some arrays defined in my RTEMS code of length equal to the number of total tasks. These arrays hold the values of the period, priority (relative deadline), release time, and execution time. Then my code uses the arrays to generate tasks with the given parameters. This isn't too difficult to write up by hand, but my project also requires that I compute some runtime characteristics of the periodic tasks.
In particular, I am implementing a static slack stealer in RTEMS, which requires a pre-computed table of all the jobs released in a hyperperiod. A job is an instance of a periodic task, which is released at a specific time and has an absolute deadline by which it must complete. The absolute deadline of a job is equal to the release time plus the task's relative deadline. A hyperperiod is a length of time equal to the least common multiple of all the periods of periodic tasks, which is the time it takes for the system to "cycle" the periodic tasks. At the start of a hyperperiod, the periodic tasks execute identically the same as at time 0 (or the start of the first hyperperiod).
The pre-computed table involves computing for each job in a hyperperiod the slack of the job, which is the difference between the job's deadline and the sum of all the execution times of jobs with earlier deadlines. Then each w(i,j) entry of the pre-computed slack table w is the minimum of jobs with deadlines greater than or equal to i and less than or equal to j. The slack table is an N x N upper-triangular matrix, where N is the number of jobs in a hyperperiod. Calculating these values by hand is tedious, so I decided to implement a script to automatically generate the pre-computed slack table for a given set of periodic tasks.
I don't do very much scripting work, so I have no preference on language. Most of the time I can get away with shell scripts. But in this case, I wanted to use a language with more support for functions and string processing. I settled on either Lua and Python, and eventually went with Lua. Lua is a dynamically typed language, which is designed to be embedded in C programs. This was the tipping factor for me, I'm curious to see if there are any useful use cases for Lua in future projects. I've heard you can do the same with Python, but that it can be difficult.
For this project, I used Lua solely as a stand-alone interpreter, rather than embedding my Lua scripts in a C program. My first task was to learn Lua. I spent a morning reading the Lua reference manual, which was accessible and easy enough to get through. One of the interesting quirks of Lua is that it uses a primitive type table as the only way to implement arrays and dynamic structures!
Tables are relatively straightforward, and the language provides built-ins to manipulate the tables. I found two surprises while working with tables: first, tables are one-indexed by default (rather than zero-indexed like C arrays); and second, nil values cannot be added to tables. However, tables are extensible types, and one can use metatables to define how operations, like <, work on tables. This could be important, since there is no default way to compare two tables. Adding elements to tables is easy with the table.insert function, which by default appends to the table, but can also be used to insert relative to a table element. The table.sort operation takes a function as its second argument that defines the less than operation to use for the sort. table.concat was another useful function, which converts a table to a string, and adds an optional delimiter between each entry of the table. For example,
table.concat(t, ", ")))converts t to a comma-delimited string.
The last function that was really helpful (and non-obvious) is unpack, which returns the elements of a table as a "list", which can be used as a varargs argument to a function. For example, I found some code to implement the map function:
function map(f, ...)Which I used to convert a table to a list of numbers to pass as argument to a least common multiple function that I wrote in order to determine the length of a hyperperiod:
local function helper(f, n, a, ...)
if n > 0 then return f(a), helper(f, n-1, ...) end
end
return helper(f, select('#', ...), ...)
end
function get_hyperperiod_length(task_periods)My implementation of lcm is not particularly efficient, but it is also illustrative:
lcm(map(tonumber,unpack(task_periods)))
end
function lcm(...)Note that for x, y in ipairs(T) defines an iterator over T, where x is the key (index) and y is the value T[x]. In the lcm function, I convert the varargs argument to a table (which would discard nils!) and iterate over it. Most of the functions I wrote make use of the ipairs method to create an iterator to process a table.
local last_v = 1
local last_m = 1
for _, v in ipairs({...}) do
local m = lcm_2(last_v, v)
last_m = lcm_2(m, last_m)
last_v = v
end
return last_m
end
My script starts by parsing its arguments, which take the form -T d,e,p or -A d,e,r; T indicates a periodic task, and A indicates an aperiodic task. d is for deadline, e is for execution time, and r/p is for release time/phase. The parameters are used identically, but I need to differentiate between periodic tasks, which are used to compute the slack table, and aperiodic tasks, which are included only because the script will generate the parameters needed to run the aperiodic task in the RTEMS test program.
tasks = parse_args(arg)
Next, the script sorts the tasks, so that periodic and aperiodic tasks can be differentiated:
table.sort(tasks, task_lt)where task_lt is a function that defines how to compare the strings held in the table tasks, extracted by parse_args.
The script then splits the tasks table into aperiodic and periodic tasks:
periodic_tasks = get_periodic_tasks(tasks)
aperiodic_tasks = get_aperiodic_tasks(tasks)
Then the hyperperiod length is computed, and the jobs in a hyperperiod are generated by taking the task periods and generating jobs for each period until the hyperperiod is reached:
periods = get_deadlines(periodic_tasks)
hyperperiod_length = get_hyperperiod_length(periods)
J = get_jobs(periodic_tasks, hyperperiod_length)
All of the jobs of a hyperperiod are in J, which is a sorted table of tables, where the table at J[i], i = 1 to n, has entries J[i][1] = deadline of job i, J[i][2] = execution time of job i, and J[i][3] = release time of job i. The table is sorted by earliest deadline, with ties broken by earliest release. Now the script can compute the slack:
compute_initial_slacks(J)
slack_table = compute_slack_table(J, hyperperiod_length)
And finally, the script generates a C header file which the RTEMS test program will #include in order to get the task parameters:
write_header(aperiodic_tasks, periodic_tasks, J, slack_table, hyperperiod_length)The write_header function makes a lot of use of the string.format function, which acts like sprintf (only safer!), and the table.concat function to generate comma-delimited array initializer lists from tables.
An example execution is:
lua gen-slack-header.lua -T 6,1,0 -A 100,5,4 -T 12,1,0Which generates parameters for two periodic tasks, period (relative deadline) of 6 and 12, and with execution time of 1 and phase of 0. Parameters for an aperiodic task with deadline 100, execution time of 5, and release time of 4 are also generated. This is what the resulting C header file looks like:
/* slackparams.h
*
* This is a generated file.
* Use the gen-slack-header.lua script to create this file.
*/
#ifndef __SLACKHEADER_H_
#define __SLACKHEADER_H_
#define TABLE_SIZE (6)
#define JOBS_PER_HP (3)
#define HP_LENGTH (12)
#define NUM_PERIODIC_TASKS (2)
#define NUM_APERIODIC_TASKS (1)
#define NUM_TASKS ( NUM_PERIODIC_TASKS + NUM_APERIODIC_TASKS )
/* pre-computed slack table */
uint32_t slack_ticks[TABLE_SIZE] = { 5, 5, 5, 9, 9, 9 };
/* slack_table gets converted from ticks to timestamp later */
Timestamp_Control slack_table[TABLE_SIZE];
uint32_t jobs_per_hyperperiod = JOBS_PER_HP;
uint32_t periodic_tasks = NUM_PERIODIC_TASKS;
rtems_task_priority Priorities[1+NUM_TASKS]= { 0, 6, 12, 100 };
uint32_t Periods[1+NUM_PERIODIC_TASKS] = { 0, 6, 12 };
uint32_t Periods_us[1+NUM_PERIODIC_TASKS] = {
0*CONFIGURE_MICROSECONDS_PER_TICK,
6*CONFIGURE_MICROSECONDS_PER_TICK,
12*CONFIGURE_MICROSECONDS_PER_TICK
};
uint32_t Tick_Count[1+NUM_TASKS] = { 0, 1, 1, 5 };
uint32_t Execution[1+NUM_TASKS] = { 0, 1, 1, 5 };
uint32_t Execution_us[1+NUM_TASKS] = {
0*CONFIGURE_MICROSECONDS_PER_TICK,
1*CONFIGURE_MICROSECONDS_PER_TICK,
1*CONFIGURE_MICROSECONDS_PER_TICK,
5*CONFIGURE_MICROSECONDS_PER_TICK
};
uint32_t Phases[1+NUM_TASKS] = { 0, 0, 0, 4 };
uint32_t Phases_us[1+NUM_TASKS] = {
0*CONFIGURE_MICROSECONDS_PER_TICK,
0*CONFIGURE_MICROSECONDS_PER_TICK,
0*CONFIGURE_MICROSECONDS_PER_TICK,
4*CONFIGURE_MICROSECONDS_PER_TICK
};
#define build_task_name() { \
Task_name[ 1 ] = rtems_build_name( 'P', 'T', '1', ' ' );\
Task_name[ 2 ] = rtems_build_name( 'P', 'T', '2', ' ' );\
Task_name[ 3 ] = rtems_build_name( 'A', 'T', '3', ' ' );\
}
#endif
No comments:
Post a Comment