The Java 5 applet at the bottom of this page computes the response time of a system of tasks using Response Time Analysis. The algorithm is flexible. It handles:
but it cannot generate response time information for systems with utilization greater than 100%.
The uniprocessor analysis part of this tool is based on a technique known as Response Time Analysis. This technique is more flexible than classical rate-monotonic analysis, and it returns the worst-case response time for each task instead of just answering "feasible or infeasible" for the entire system.
If all deadlines are equal to their respective periods, the analysis uses the utilization bound from Bertogna, Cirinei,, and Lipari. "New Schedulability Tests for Real-Time Task Sets Scheduled by Deadline Monotonic on Multiprocessors." Proc. 9th International Conference on Principles of Distributed Systems, Pisa, Italy, December 2005.
The applet has a slider that specifies the number of processors on the target. The number of processors can range from 1 to 16.
The tests for SMP schedulability are less capable than the process used for a single-processor system. The SMP analysis cannot:
Moving the processor-count slider causes immediate recalculation and refresh of the results table.
Input is entered in the text area at the bottom of the applet's frame. The input can include information about any number of tasks, each task described with a comma-separated list of properties:
name, period-or-MIT, cost, deadline, blocking-time, priority
All the values for a task must be on one line.
Empty lines, lines containing only white space, and lines starting with # are comments.
Only period/MIT and cost need be supplied. All other fields have defaults:
|Name||tn Where n is a sequence number|
|Priority||If no priorities are given, compute optimal priority values. If any priorities are supplied, all must be supplied.|
For example, the input:
,100,20 task2, 150, 50 ,160, 10, 110,1Is the same as:
t1, 100, 20, 100, 0 task2, 150, 50, 150, 0 t3, 160, 10, 110, 1
If no priorities are specified, the analysis engine will compute optimal priorities based on the other values, so with all priorities auto-generated (task2 will get 1, t3 will get 2 and t1 will get 3.)
If any task is assigned a priority in the input, all tasks must have priority values in the input. Supplying only some priority values is an input error.
If the standard order of the input is inconvenient, include a re-ordering line as the first line of input. The re-ordering line starts with
#!followed by a field order specifier consisting of the letters,
|T||Period or MIT|
So the default order would be signified by this line
#!NTCDBPAn input-order override need not call for all fields, but it must include period and cost, so:
#!TCare the minimum input-order overrides.
After entering task information in the text area at the bottom of the applet's frame press the analyze bottom at the bottom of the frame.
When analysis is complete the results will appear. At the top of the frame are some attributes of the system. If the utilization is less than 100%, the results of RTA appear in a table (The tasks in the table are not ordered as they were entered. They are sorted by priority).
The cells in the table's message column contain graphical information if the task represented by the row misses its deadline or needed more than one "job" of analysis. In the later case, the reported response time is the maximum computed response time, but the message shows the response time for each job. (The white vertical line represents the period and the red vertical line represents the deadline.)
The information in the text area can be modified and the analysis re-run by pressing the analyze button again.
Try this data:
It exercises the analysis pretty hard. It finds a priority assignment that makes the system feasible, but it's not deadline monotonic, and the task with a period of 110 does need to exceed its period (as permitted.)
The output looks like:
If you look closely at the bar chart on the right you can see a vertical white line crossing the green bars. That line signifies the period for this task (which has a deadline greater than the period.) You can see that the analysis found two scenarios that gave completions greater than the period but less than the deadline and one scenario with the completion before the end of the period.
Assign priorities and increase the cost of the third task from 14 to 16:
Analyzing this new data gives the following:
Here, the bar graph has a red vertical line to the right of the white line. This line indicates the deadline, and you can see that the analysis found a scenario where the completion time falls after the deadline.
Analysis, especially Audsley's algorithm, takes polynomial time. It may run for a long time if you give it many tasks.
Thanks to many people including Alan Burns and Andy Wellings for their help on the uniprocessor analysis algorithms, and Ted Baker for the SMP algorithms. They are due much of the credit when the calculator works correctly. Of course, incorrect results probably arise from the implementation and are my fault. (Please send bug reports using a web site feedback link.