Analysis Module

Generic Compositional Performance Analysis Algorithms

Copyright (C) 2007-2017 Jonas Diemer, Philip Axer, Daniel Thiele, Johannes Schlatow
TU Braunschweig, Germany
All rights reserved.
See LICENSE file for copyright and license details.
Authors:
  • Jonas Diemer
  • Philip Axer
  • Johannes Schlatow

Description

This module contains methods for real-time scheduling analysis. It should be imported in scripts that do the analysis.

class pycpa.analysis.GlobalAnalysisState(system, task_results)[source]

Everything that is persistent during one analysis run is stored here. At the moment this is only the list of dirty tasks. Half the anlysis context is stored in the Task class itself!

clean()[source]

Clear all intermediate analysis data

clean_analysis_state()[source]

Clean the analysis state

get_dependent_tasks(task)[source]

Return all tasks which immediately depend on task.

class pycpa.analysis.JunctionStrategy[source]

This class encapsulates the junction-specific analysis

propagate(junction, task_results)[source]

Propagate event model over a junction

reload_in_event_models(junction, task_results, non_cycle_prev)[source]

Helper function, reloads input event models of junction from tasks in non_cycle_prev

exception pycpa.analysis.NotSchedulableException(value)[source]

Thrown if the system is not schedulable

class pycpa.analysis.Scheduler[source]

This class encapsulates the scheduler-specific analysis

b_min(task, q)[source]

Minimum Busy-Time for q activations of a task.

This default implementation should be conservative for all schedulers but can be overridden for improving the results with scheduler knowledge.

Parameters:
  • task (model.Task) – the analyzed task
  • q (integer) – the number of activations
Return type:

integer (max. busy-time for q activations)
b_plus(task, q, details=None, **kwargs)[source]

Maximum Busy-Time for q activations of a task.

This default implementation assumes that all other tasks disturb the task under consideration, which is the behavior of a “random priority preemptive” scheduler or a “least-remaining-load-last” scheduler. This is a conservative bound for all work-conserving schedulers.

Warning

This default implementation should be overridden for any scheduler.

Parameters:
  • task (model.Task) – the analyzed task
  • q (boolean) – the number of activations
  • details – reference to a dict of details on the busy window (instead of busy time)
Return type:

integer (max. busy-time for q activations)
compute_bcrt(task, task_results=None)[source]

Return the best-case response time for q activations of a task. Convenience function which calls the minimum busy-time. The bcrt is also stored in task_results.

compute_max_backlog(task, task_results, output_delay=0)[source]

Compute the maximum backlog of Task t. This is the maximum number of outstanding activations. Implemented as shown in Eq.17 of [Diemer2012].

compute_service(task, t)[source]

Computes the worst-case service a Task receives within an interval of t, i.e. how many activations are at least computed within t.

Call System.analyze() first if service depends on other resources to make sure all event models are up-to-date! This service is higher than the maximum arrival curve (requested service) of the task if the task is schedulable.

compute_wcrt(task, task_results=None)[source]

Compute the worst-case response time of Task

Warning

This default implementation works only for certain schedulers and must be overridden otherwise.

Parameters:
Return type:

integer (worst-case response time)

For this, we construct busy windows for q=1, 2, … task activations (see [Lehoczky1990]) and iterate until a stop condition (e.g. resource idle again). The response time is then the maximum time difference between the arrival and the completion of q events. See also Equations 2.3, 2.4, 2.5 in [Richter2005]. Should not be called directly (use System.analyze() instead).

stopping_condition(task, q, w)[source]

Return true if a sufficient number of activations q have been evaluated for a task during the busy-time w.

This default implementation continues analysis as long as there are new activations of the task within its current busy window.

Warning

This default implementation works only for certain schedulers (e.g. SPP) and must be overridden otherwise.

Parameters:
  • task (model.Task) – the analyzed task
  • q (integer) – the number of activations
  • w (integer) – the current busy-time
Return type:

integer (max. busy-time for q activations)
class pycpa.analysis.TaskResult[source]

This class stores all analysis results for a single task

b_wcrt_str()[source]

Returns a string with the components of b_wcrt sorted alphabetically

clean()[source]

Clean up

exception pycpa.analysis.TimeoutException(value)[source]

Thrown if the analysis timed out

pycpa.analysis.analyze_system(system, task_results=None, only_dependent_tasks=False, progress_hook=None, **kwargs)[source]

Analyze all tasks until we find a fixed point

system – the system to analyze task_results – if not None, all intermediate analysis results from a previous run are reused

Returns a dictionary with results for each task.

This based on the procedure described in Section 7.2 in [Richter2005].

pycpa.analysis.analyze_task(task, task_results)[source]

Analyze Task BUT DONT propagate event model. This is the “local analysis step”, see Section 7.1.4 in [Richter2005].

pycpa.analysis.check_violations(constraints, task_results, wcrt=True, path=True, backlog=True, load=True)[source]

Check all if all constraints are satisfied. Returns True if there are constraint violations. :param task_results: dictionary which stores analysis results :type task_results: dict (analysis.TaskResult) :param wcrt: if True, check wcrt :param path: if True, check path latencies :param backlog: if True, check buffersized :param load: if True, check loads :rtype: boolean

pycpa.analysis.out_event_model(task, task_results, dst_task=None)[source]

Wrapper to call the out_event_model() method of the actual propagation strategy in order to compute the output event model of a task. See Chapter 4 in [Richter2005] for an overview.

Parameters: