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:
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:
It cannot generate response times for systems with utilization greater than the number of processors.
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.
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:
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 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, lock-name, locked-time, ...
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.
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|
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|
Lock names and times are not re-orderable.
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:
are the minimum input-order overrides.
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.
Blocking time may be explicitly entered, or it can be computed. Providing the informationh for the applet to computing blocking time may be tedious, but it gives the applet the ability to re-compute blocking time when the priority of tasks is altered.
For each task, add a list of name, time pairs to the end of its like. For instance, the example above might become
,100, 20, , , , lock1, 2, lock2, 5
task2, 150, 50, , , , lock 2, 1
,160, 10, 110, , , lock1, 1
Note that the third task had an explicit blocking time given when it appeared a few paragraphs ago. Now the blocking time for that task is not specified in the input. It is computed.
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.
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 vertical white lines crossing the green bars. Those lines signify the period for each task (which has a deadline greater than the period.) You can see that the analysis found a scenario that gave two completions after the period but before the deadline followed by a 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.
When you include lock names and lock times in the input, the output shows that locking is computed instead of Unspec. Here's the analysis of the earlier example of computing locking.
Note that, though blocking time was not specified in the input it appears in the output.
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 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.