A Tool to Compute
Task Response Times

RTSJ Main Page

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.

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.

  1. It computes the total utilization, and the RMA maximum utilization for the system.
  2. If the total utilization is greater than 100%, there is no way the system can be feasible, so the analysis process stops.
  3. 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.
  4. 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.
  5. 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:

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, 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.

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.

lock name

none

lock time NA

For example, the input:

,100,20
task2, 150, 50
,160, 10, 110,1		
Is 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

Lock names and times are not re-orderable.

So the default order would be signified by this line

#!NTCDBP
An input-order override need not call for all fields, but it must include period and cost, so:
#!CT
or
#!TC

are the minimum input-order overrides.

SMP Support

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.

Computation of Blocking Time

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.

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:

Sample output

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:

,110,40,120,,1
,150,60,,,3
,200,16,170,,2

Analyzing this new data gives the following:

Results of above data

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.

Result of analyzing input with computed blocking time

Note that, though blocking time was not specified in the input it appears in the output.

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.

Response Time Calculator