Resource Contention in Real-time Systems

Smart, Robert John (2003). Resource Contention in Real-time Systems. PhD thesis The Open University.

DOI: https://doi.org/10.21954/ou.ro.0000f55b

Abstract

The divide—and—conquer method is extensively used for system design. For real-time systems the separated components execute concurrently using some common computational infrastructure and this can lead to contention for system resources, such as processors, memory, communication channels, and so on. Unless the resource contention is accommodated, then a system built from the composition of components may not function as expected and the “proven” behaviour of the components can be invalid. To overcome this uncertainty a divide—conquer—and—system-composition method is required.

This thesis takes a different approach to many of the existing notations which focus on descriptions of behaviour. The Composite Transition System notation and algebra presented here enables the resource usage of the components to be specified and combined to form a composite system of concurrently executing components. By relating the composite system to the realisable behaviour of the system resources provided by the common infrastructure it becomes possible to determine any violation of the constraints imposed by the system resources. If the composite system model is then constrained by the resource behaviours then it is possible through an extraction operation to determine the modified behaviour of the components that will yield a system free of resource contention.

Component specification, concurrent composition, the application of system level constraints and extraction are applied in this thesis to a system encountered in a commercial application. The purpose of this example is to demonstrate contention modelling and the mathematics of the notation, rather than to prove any specific properties of the application. Deployment of the notation to more complex applications will require the development of software tools to compute concurrent composition and extraction, and this is the motivation for the mathematical treatment in this thesis.