A Tool to Compute Task Response Times

The Analysis Tool computes the response time of a single-processor system of tasks using Response Time Analysis. The algorithm is flexible. It handles:

Tasks with locking (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.) 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 is limited to:

Tasks with zero blocking time
Tasks with deadline ≤ period.

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 supplied in the input:: the applet uses the response time analysis algorithm and reports the results.
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.) If no priority assignment works, no response time information is reported.

The multi-processor analysis part of this tool is built on the algorithms found in Bertogna and Cirinei "Response-Time Analysis for Globally Scheduled Symmetric 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 deadline monotonic priority assignment.
The tasks must have no locking. If they do specify locks, the locking is ignored.
In addition to response time analysis, multi-processor analysis 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 supplied in two tables. The first lists lock names with the duration of their critical section. The second table lists task names with the task's attributes. Pressing submit starts real-time analsys. For SMP systems, once anaysis is started with the submit button, changing the number of processors triggers re-analysis.

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 64 under the control of the slider, and numbers up to 512 can be entered directly into the input box. The tests for SMP schedulability are less capable than uniprocessor analysis. The SMP analysis cannot consider blocking time, multiple tasks may not share priorities, and since the analysis algorithm specifies deadline-monotonic priorities, Audsley's algorithm is not applicable. Moving the processor-count slider causes immediate recalculation and refresh of the results table.

Analysis and Output

After entering task information in the lock and task tables, press submit or adjust the number of processors to start analysis. When analysis is complete the results will appear. At the top of the results are some attributes of the system. If the utilization is less than 100% times the number of processors, per-task results appear in a table (The tasks in the table are ordered as they were entered.) When the analysis has response time information, the cells in the table's Chart column contain graphical breakdowns of each task's response time.

The grey bar represents the period
The bar under that represents the response time. It is a stack of:

Ineligible time

Waiting for higher priority tasks, grey

Lock contention time

maroon

Execution time

blue
A vertical bar crosses the period and response time bars at the deadline-time. It's green if the task met the deadline, and red if it did not meet the deadline.

The information in the input table can be modified and the analysis re-run by pressing the submit button again.

Sensitivity Analysis

Sensitivity analysis measures the difference between the existing system and one with exactly enough performance to be feasible. It generates a number, Sensitivity in the results. If the sensitivity is > 1.0, the system has that amount of surplus "power." So, for instance, sensitivity of 1.500 would indicate that the system would still be feasible with 2/3 the performance. Sensitivity < 0 tells how far short of sufficient processor performance the system falls. For instance, sensitivity of 0.800 indicates that we have 80% of the necessary performance and need a 25% performance increase.

Be Patient

Analysis, especially Audsley's algorithm, takes polynomial time. It may run for a long time if you give it many tasks. Sensitivity analysis slows analysis by about a factor of 10.

Acknowledgements

Thanks to many people including Alan Burns and Andy Wellings for their help on the uniprocessor analysis algorithms, and thanks to 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.