A Tool to Compute
Task Response Times

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:

• 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%.

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 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 will be 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 full response-time information for the system. If no priority assignment works, no response time information is reported.
5. If priorities were supplied in the input, the response time analysis algorithm is used and the results are reported.
6. The 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.
   • Priorities must either not be assigned, or they must be assigned in a rate-monotonic fashion.
   • The tasks must have zero blocking time.

   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.

   
   If any deadlines are not equal to their respective periods, the system is analyzed using the method from Baker and Cirinei, "A Unified Analysis of Global EDF and Fixed-Task-Priority Schedulability of Sporadic Task Systems on Multiprocessors." Technical Report TR-060501, Department of Computer Science, Florida State University, Tallahassee, FL, May 2006.

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,
• compute worst-case completion times
• generate priority assignments other than deadline monotonic.

Moving the processor-count slider causes immediate recalculation and refresh of the results table.

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.

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

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.

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

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

Peter Dibble

The applet requires Java 5. If the JVM attached to your browser does not support Java 5 class files, you will probably get a error when the applet tries to load...or it may just fail to run.

Fine print: Use results from this tool at your own risk.