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.