We are increasingly surrounded by computer controlled devices. Many of which are not perceived as "computers" and are called embedded systems: think of mobile phones, cars, or aircraft. Many of these systems have some sort of real-time requirements, be it responsiveness, quality of service or hard deadlines, where the miss of the latter leads to catastrophic consequences. Beyond the fact that we are more and more surrounded and dependent on such systems, there is an another trend visible. Embedded systems are often networked and/or receive upgrades and extensions during the lifetime of an individual system. These may be, for example, applications downloaded to your mobile phone or an upgrade of your motor control in a garage. A third trend is an increase in mobile systems, requiring effective power management to extend the battery lifetime.
Within this research line we address the issues associated with systems requiring temporal isolation of system parts with different criticality, as well as systems being robust and reliable in the context of additional restrictions like available energy, changing environment or a dynamic set of tasks executed on such a system.
Dynamic Server-Based Scheduling
As an increasing number of end users runs both real-time and traditional desktop applications in the same system, the issue of how to provide an efficient resource utilisation in this highly dynamic, open, and shared environment becomes very important. The need arises from the fact that independently developed services can enter and leave the system at any time. For most of these systems, the classical real-time approach based on a rigid off-line design and worst-case execution time assumptions would keep resources unused for most of the time.
We have been developing new scheduling algorithms that consider the coexistence of the traditional isolated servers with a novel non-isolated type of servers, combining an efficient reclamation of residual capacities with a controlled isolation loss. The goal is to reduce the mean tardiness of periodic guaranteed jobs by handling overloads with additional capacity available from two sources: (i) by reclaiming unused allocated capacity when jobs complete in less than their budgeted execution time; and (ii) by stealing allocated capacities to inactive non-isolated servers used to schedule aperiodic best-effort jobs. By combining such approach with the concept of bandwidth inheritance, we have recently proposed to efficiently exchange reserved bandwidth among sets of dependent tasks which share resources and exhibit precedence constraints, assuming no previous information on critical sections and computation times is available.
Component based Real-Time Systems
The increasing complexity of real-time embedded systems demands advanced methodologies that can facilitate their design and analysis, while assuring correctness, real-time, and performance requirements. Promising is a paradigm of compositional theories and technologies that allows for the decomposition of a complex system into simpler pieces (components), as well as the integration of individual components to achieve system functions collectively, while preserving the principles of
- compositionality: the system-level (global) property can be established from composing component-level (local) properties, and
- composability: the properties established and validated for components in isolation hold also after the components are assembled into the system.
Such a composition paradigm calls for new component concepts and composition mechanisms that can support various key characteristics of real-time embedded systems, including timeliness, quality of service and adaptivity. In this area, our researchers are interested in the following topics.
- Compositional Scheduling Theories: compositional schedulability and execution-time analysis; horizontal/vertical composition of various real-time resource management schemes (e.g., CPU, memory, power, thermal); composition of cluster-based multicore or multiprocessor scheduling.
- Component Model and Interface: component model for real-time embedded systems; interface theory and development for real-time embedded systems; component technology for real-time embedded systems.
- Compositional Formal Methods: compositional techniques for modeling and formal methods; composition of validation and verification techniques.
- Compositional Distributed Systems: composition of network protocol layers for real-time communications; compositional end-to-end delay analysis in distributed systems.
Anytime QoS Management Approach
The move from the traditional self-enclosed real-time system to open real-time systems is also one of moving from static to dynamic environments. Open real-time systems allow a mix of independently developed real-time and non real-time applications to coexist in the same system and even change during system lifetime. The increased complexity of dynamic open scenarios may prevent the possibility of computing optimal local and global resource allocations within a useful and bounded time, as the optimal level of deliberation varies from situation to situation.
We have been reformulating the distributed resource allocation problem as an anytime optimisation problem in which there are a range of acceptable solutions with varying qualities, adapting the distributed service allocation is to the available deliberation time that is dynamically imposed as a result of emerging environmental conditions. Nodes start by negotiating partial, acceptable service proposals that are latter refined if time permits, in contrast to a traditional QoS optimisation approach that either runs to completion or is not able to provide a useful solution. At each iteration, the proposed QoS optimisation tries to find a new feasible set of QoS levels with an increasing utility. The binary notion of correctness associated with traditional QoS optimisation algorithms is thus replaced by a set of quality measured outputs.
Middleware for Self-Managed Distributed Systems (Autonomic Computing)
Given the heterogeneity of services to be executed, users' quality preferences, underlying operating systems, networks, devices, and the dynamics of their resource usages, developing adaptive distributed embedded systems presents a number of challenges. These include (i) designing a common understanding of how QoS should be specified; (ii) the provisioning of self-management actions that allow nodes to adapt to observed changes in the environment; (iii) resource management and scheduling strategies; and (iv) the design of an efficient coordination model that regulates individual autonomous adaptive actions. Here, the term coordinated adaptation refers to the ability of a distributed adaptive system to invoke adaptive actions on multiple nodes in a coordinated manner so as to achieve a common goal.
QoS-aware adaptation in a service's distributed execution can require communication and synchronisation among nodes, used as a building block for a collective adaptation behaviour that emerges from local interactions among nodes. One challenge is controlling this exchange of information in order to achieve a convergence to a globally consistent solution without overflowing nodes with messages. With the increasing size and complexity of open embedded systems the ability to build self-managed distributed systems using centralised coordination models is reaching its limits, as solutions they produce require too much global knowledge. As such, we are working on ways to achieve higher levels of self-adaptiveness in systems required to operate in time critical environments through a fast convergence decentralised coordination model.
Many embedded systems are limited in the amount of available energy to power them. This is due to the fact that many of today's embedded and consumer devices are mobile and battery operated. Another trend is increased hardware complexity which renders traditional power models irrelevant. The arrival of multicore processors have taken this complexity to a new level. We are actively working on an approach to manage the energy consumption of an embedded system in a realistic scenario. This is based on the observation that a system is subject to several modes of operation during execution of a given task. Among others, this involves time in which a processor core is actually performing arithmetic operations and time in which the processor core is waiting for memory accesses to complete.
International Workshop on Operating Systems Platforms for Embedded Real-Time Applications (OSPERT'09 and OSPERT'10)
Area Editor for Real-Time and Embedded Systems for the Journal of Systems Architecture: Embedded Software Design (JSA).