A Tool to Compute
Task Response Times
The Java 5 RT Analysis applet computes the response time of a single-processor system of tasks using Response Time Analysis. The algorithm is flexible. It handles:
- Tasks with blocking time.
- Tasks with deadline not equal to period, or even deadline greater than period. (Note that the RTSJ does not support deadline greater than period.)
but it cannot generate response time information for systems with utilization greater than 100%.
It uses a different response time analysis algorithm to compute the response times of a multi-processor system of tasks. That algorithm handles:
- Tasks with zero blocking time
- Tasks with deadline not equal to period, but the deadline must not be greater than the period.
It cannot generate response times for systems with utilization greater than the number of processors.
Process
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.
- It computes the total utilization, and the RMA maximum utilization for the system.
- If the total utilization is greater than 100%, there is no way the system can be feasible, so the analysis process stops.
- If priorities were not supplied in the input, and no deadlines are greater than the corresponding periods, priorities are assigned using the deadline-monotonic algorithm, and then the analyzer uses the Response Time Analysis algorithm (Audsley, Burns, Richardson, Tindell, and Wellings "Applying New Scheduling Theory to Static Priority Preemptive Scheduling." Software Engineering Journal, Vol. 8, No. 5, pp. 284–292, September 1993) to compute the worst-case response time for each task. The system is feasible if the worst-case response time for each task does not exceed its deadline, but even if the system is infeasible, response time information for all tasks is computed and displayed.
- If priorities were not supplied in the input, and at least one deadline is greater than the corresponding period, priorities are assigned using Audsley's algorithm (Audsley, "Optimal Priority Assignment and Feasibility of Static Priority Tasks With Arbitrary Start Times," Dept. Computer Science, University of York, December 1991.) The response time analysis algorithm from (3) is incorporated in the priority-assignment process, so if a priority assignment renders the system feasible, the analysis reports response-time information for each task. If no priority assignment works, no response time information is reported.
- If priorities were supplied in the input, the applet uses the response time analysis algorithm from (3) reports the results.
The multi-processor analysis part of this tool is also based on Response Time Analysis. It is built on the algorithms found in Bertogna and Cirinei "Response-Time Analysis for Globally Scheduled Symetric Multiprocessor Platforms", RTSS 2007, pages 149-158.
This analysis process can handle some MP systems:
- Utilization must not be greater than the number of processors.
- The platform must use global scheduling; that is, a priority scheduling queue is shared among all processors.
- It will attempt to determine a feasible priority assignment if no priorities are given. It uses a version of Audsley's algorithm (see above.)
- The tasks must have zero blocking time.
Multi-processor analysis does not use a utilization bound, but it computes the utilization and 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.
Input
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.
Time units are not important to the analysis, and they are not included in the input. They must, however, be consistent. For instance,
work, 20, 2, 8, , 50
might have units of days and mean that the task has a period of 20 days, a cost of 2 days, and a deadline of 8 days. It might also have units of nanoseconds and mean that work has a period of 20 nanoseconds, a cost of 2 nanoseconds, and a deadline of 8 nanoseconds. There is no way to mix time units in the input.
A higher value of priority reflects greater scheduling priority.
Comments
Empty lines, lines containing only white space, and lines starting with # are comments.
Defaults
Only period/MIT and cost need be supplied. All other fields have defaults:
| Name | tn Where n is a sequence number |
| Deadline | period |
| Blocking | 0 |
| 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.
Input Order Override
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,
| N | Name |
| T | Period or MIT |
| C | Cost |
| D | Deadline |
| B | Blocking time |
| P | Priority |
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:
#!CTor
#!TC
are the minimum input-order overrides.
SMP Support (preliminary)
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:
- consider blocking time.
Moving the processor-count slider causes immediate recalculation and refresh of the results table.
Analysis and Output
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 ordered as they were entered.)
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.
Sample Data
Try this data:
,110,40,120
,150,60
,200,14,170
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:
,110,40,120,,1
,150,60,,,3
,200,16,170,,2
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.
Be Patient
Analysis, especially Audsley's algorithm, takes polynomial time. It may run for a long time if you give it many tasks.
Acknowledgements
Thanks to many people including Alan Burns and Andy Wellings for their help on the uniprocessor analysis algorithms, and Ted Baker for help with 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 the developer's fault.
