Abstract In multicore scheduling of hard real-time systems, there is a significant source of unpredictability due to the interference caused by the sharing of hardware resources. This paper deals with the schedulability analysis of multicore systems where the interference caused by the sharing of hardware resources is taken into account. We rely on a task model where this interference is integrated in a general way, without depending on a specific type of hardware resource. There are similar approaches but they consider fixed priorities. The schedulability analysis is provided for dynamic priorities assuming constrained deadlines and based on the demand bound function. We propose two techniques, one more pessimistic than the other but with a lower computational cost. We evaluate the two proposals for different task allocators in terms of the increased estimated utilization. The results show that both bounds are valid for ensuring schedulability although, as expected, one is tighter than the other. The evaluation also serves to compare allocators to see which one produces less interference.

In hard real-time embedded systems, switching to multicores is a step that most application domains delay as much as possible. This is mainly due to the number of sources of indeterminism, which mainly involve shared hardware resources, such as buses, caches, and memories. In this paper, a new task model that considers the interference that task execution causes in other tasks running on other cores due to memory contention is proposed. We propose a scheduling algorithm that calculates the exact interference. We also analyse and compare existing partitioning algorithms and propose three strategies to allocate tasks to cores to schedule as many tasks as possible and minimise total interference.

Heterogeneous parallel devices are becoming widely diffused in the embedded systems application field since they allow to improve time performances and other orthogonal metrics (e.g., cost, power, size, etc.) at the same time. In such a context, the introduction of safety requirements, as dictated by the relevant standards (i.e., DO-178 B/C and RTCA/DO-254 in airborne systems, ARINC 653 for avionics software, ISO-26262 in automotive domain, etc.) while considering shared resources on a heterogeneous parallel HW platform, adds further challenges to industrial and academic research. This kind of platforms that execute tasks with different levels of criticality are commonly called mixed-criticality embedded systems. So, the main problem in their management is to ensure that low criticality tasks do not interfere with high criticality ones. The final goal is to allow several applications to interact and coexist on the same platform. For this, the exploitation of virtualization technologies (i.e., hypervisors) allows to guarantee isolation and to satisfy certification requirements but introduces scheduling overhead and new HW/SW partitioning challenges. In such a scenario, this work focuses on a framework for modeling, analysis, and validation of mixed-criticality and real-time systems based on an existing "Model-Based Electronic System Level HW/SW Co-Design" methodology. The main contribution of this work is the integration of the considered framework with Xamber tool in order to provide systems implementations by exploiting a design space exploration able to consider Xtratum-based SW partitions.

Demand for Advanced Driver Assistance Systems (ADAS) is growing larger with the key focus of increased road safety, driver comfort and the futuristic autonomous vehicles. ADAS is typically a mixed-criticality system (MCS) with interdependent tasks which change their criticality level with the dynamic changes in the environment. In an MCS, the timing of safety-critical tasks must be strictly guaranteed to prevent accidents. From the conventional scheduling techniques in ADAS, more challenge is involved in meeting the timing performance of task scheduling and resource sharing while ADAS as MCS. This is a work-in-progress paper. Its objective is the design of ADAS with multicore partitioned architecture on the Xtratum hypervisor with the improved load and resource sharing among the subsystems. This is to address the dynamic changes in criticality and later to reduce the make-span for high critical tasks so as to prevent accidents. Two safety-critical ADAS subsystems Forward Collision Avoidance System (FCAS) and Blind Spot Avoidance System (BSAS) help to illustrate the architecture in this paper.

This paper proposes an architecture for combining the execution of time- and event-triggered real-time task sets. This makes it possible for the designer to choose the most appropriate mechanism depending on the role and nature of each task in the system. The proposed architecture allows one to choose the priority levels at which time- and event-triggered tasks are executed. This gives the designer an additional degree of freedom to make compromise decisions upon contradicting timing requirements, such as granting reduced jitter and at the same time providing prompt service to non-periodic events, for example. The proposed model is accompanied with a Ravenscar implementation of the time-triggered scheduler and a library of utilities for specifying time-triggered schedules and reusing time-triggered task patterns.

This paper addresses the problem of energy characterization in partitioned systems. The goal is to use this model to minimize energy consumption. Controlling the frequency at which CPUs can operate is a common technique to reduce the system energy consumption. Techniques as DVFS assume that decreasing the system frequency decreases the system energy, in spite of increasing the time the processor is busy. This relationship between temporal load, frequency and energy is studied in this paper. All works assume that this relationship is linear but we provide a new energy model that relates the previous variables through a non-linear relation. We also present a comparison in terms of energy between the linear and the non-linear model.

With time and space partitioned architectures becoming increasingly appealing to the European space sector, the dependability of separation kernel technology is a key factor to its applicability in European Space Agency projects. This paper explores the potential of the data type fault model, which injects faults through the Application Program Interface, in separation kernel robustness testing. This fault injection methodology has been tailored to investigate its relevance in uncovering vulnerabilities within separation kernels and potentially contributing towards fault removal campaigns within this domain. This is demonstrated through a robustness testing case study of the XtratuM separation kernel for SPARC LEON3 processors. The robustness campaign exposed a number of vulnerabilities in XtratuM, exhibiting the potential benefits of using such a methodology for the robustness assessment of separation kernels.

With the ever increasing industrial demand for bigger, faster and more efficient systems, a growing number of cores is integrated on a single chip. Additionally, their performance is further maximized by simultaneously executing as many processes as possible not regarding their criticality. Even safety critical domains like railway and avionics apply these paradigms under strict certification regulations. As the number of cores is continuously expanding, the importance of cost-effectiveness grows. One way to increase the cost-efficiency of such System on Chip (SoC) is to enhance the way the SoC handles its power resources. By increasing the power efficiency, the reliability of the SoC is raised, because the lifetime of the battery lengthens. Secondly, by having less energy consumed, the emitted heat is reduced in the SoC which translates into fewer cooling devices. Though energy efficiency has been thoroughly researched, there is no application of those power saving methods in safety critical domains yet. The EU project SAFEPOWER1 targets this research gap and aims to introduce certifiable methods to improve the power efficiency of mixed-criticality real-time systems (MCRTES). This paper will introduce the requirements that a power efficient SoC has to meet and the challenges such a SoC has to overcome.

Modern embedded applications typically integrate a multitude of functionalities with potentially different criticality levels into a single system. Without appropriate preconditions, the integration of mixed-criticality subsystems can lead to a significant and potentially unacceptable increase of engineering and certification costs. A promising solution is to incorporate mechanisms that establish multiple partitions with strict temporal and spatial separation between the individual partitions. In this approach, subsystems with different levels of criticality can be placed in different partitions and can be verified and validated in isolation. The MultiPARTES FP7 project aims at supporting mixed-criticality integration for embedded systems based on virtualization techniques for heterogeneous multicore processors. A major outcome of the project is the MultiPARTES XtratuM, an open source hyper visor designed as a generic virtualization layer for heterogeneous multicore. MultiPARTES evaluates the developed technology through selected use cases from the offshore wind power, space, visual surveillance, and automotive domains. The impact of MultiPARTES on the targeted domains will be also discussed. In a number of ongoing research initiatives (e.g., RECOMP, ARAMIS, MultiPARTES, CERTAINTY) mixed-criticality integration is considered in multicore processors. Key challenges are the combination of software virtualization and hardware segregation and the extension of partitioning mechanisms to jointly address significant non-functional requirements (e.g., time, energy and power budgets, adaptivity, reliability, safety, security, volume, weight, etc.) along with development and certification methodology.

Developing embedded control systems requires to have the possibility of analyzing and evaluating new control algorithms before their implementation in the final system as well as their robust operation once implemented. For that purpose, a generic platform composed by the hypervisor XtratuM and RTOS PaRTiKLe is introduced in this paper. The interaction between the user and the process is generated by using Linux, while the realtime execution of the process is ensured by PaRTiKLe. Moreover, hypervisor XtratuM provides the facilities to execute several partitions with different guest OSs as well as the mechanisms to communicate PaRTiKLe partition and the control environment. By means of this platform the performance of future partitioned embedded systems are analyzed, evaluated and improved. Experimental tests are carried out in order to prove the effectiveness of the system. The reported results show the good performance of the designed system and the robustness of the platform.

Current trends in the development of industrial applications enforce the use of wireless networks to communicate the system nodes mainly to increase flexibility and reliability of these applications and to reduce the implementation cost. However, in control applications, as consequence of the latency and jitter generated by the network, not always the results achieved by the experimental results and desired performance are coherent. This is due to the imprecise models for system analysis and design used and the non appropriated validation methods and platforms to support these models. Therefore this paper presents a method to achieve an optimal system configuration in order to fulfil the desired performance in control applications with a significant energy saving and minimum delay.

Hierarchical scheduling has recently been used to provide temporal isolation to embedded virtualised systems. Response time analysis is a common way to derive a schedulability test for these systems. This paper points out that response time analysis for hierarchical fixed-priority scheduling found in the literature is only exact for tasks of the highest priority domain. For the rest of the tasks is an upper bound. In our work, we provide the exact analysis and we compare it with previously published works.

Nowadays, systems often integrate a variety of applications whose service requirements are heterogeneous. Consequently, systems must be able to concurrently serve applications which rely on different constraints. This raises the problem of the dynamic distribution of the system resources (CPU, memory, network, etc.). Therefore, an integrated Quality of Service (QoS) management is needed so as to efficiently assign resources according to the various application demands. Within this paper, we focus on a dynamic approach of QoS management for memory resource allocation based on the Skip-Over model. We detail our solution and we show how it improves the service of task memory requests while providing them guarantees. Quantitative results using the TLSF allocator have been performed in order to evaluate the memory failure probability with and without memory QoS manager.

Abstract This paper describes the design criteria and implementation details of a dynamic storage allocator for real‐time systems. The main requirements that have to be considered when designing a new allocator are concerned with temporal and spatial constraints. The proposed algorithm, called TLSF (two‐level segregated fit), has an asymptotic constant cost,O(1), maintaining a fast response time (less than 200 processor instructions on a x86 processor) and a low level of memory usage (low fragmentation). TLSF uses two levels of segregated lists to arrange free memory blocks and anincomplete searchpolicy. This policy is implemented with word‐size bitmaps and logical processor instructions. Therefore, TLSF can be categorized as a good‐fit allocator. The incomplete search policy is shown also to be a good policy in terms of fragmentation. The fragmentation caused by TLSF is slightly smaller (better) than that caused by best fit (which is one of the best allocators regarding memory fragmentation). In order to evaluate the proposed allocator, three analyses are presented in this paper. The first one is based on worst‐case scenarios. The second one provides a detailed consideration of the execution cost of the internal operations of the allocator and its fragmentation. The third analysis is a comparison with other well‐known allocators from the temporal (number of cycles and processor instructions) and spatial (fragmentation) points of view. In order to compare them, a task model has been presented. Copyright © 2007 John Wiley & Sons, Ltd.

Real-time systems are often designed using a set of periodic tasks. Task periods are usually set by the system requirements, but deadlines and computation times can be modified in order to improve system performance. Sensitivity analysis in real-time systems has focused on changes in task computation times using fixed priority analysis. Only a few studies deal with the modification of deadlines in dynamic-priority scheduling. The aim of this work is to provide a sensitivity analysis for task deadlines in the context of dynamic-priority, preemptive, uniprocessor scheduling. In this paper, we present a deadline minimization method that computes the shortest deadline of a periodic task. As undertaken in other studies concerning computation times, we also define and calculate the critical scaling factor for task deadlines. Our proposal is evaluated and compared with other works. The deadline minimization proposed strongly reduces jitter and the response time of control tasks, which can lead to a significant improvement in system performance.

Dynamic memory storage has been widely used for years in computer science. However, its use in real-time systems has not been considered as an important issue, and memory management has not receive much consideration, whereas today's real-time applications are often characterized by highly fluctuating memory requirements. In this paper we present an approach to dynamic memory management for real-time systems. In response to application behavior and requests, the underlying memory management system adjusts resources to meet changing demands and user needs. The architectural framework that realizes this approach allows adaptive allocation of memory resources to applications involving both periodic or aperiodic tasks. Simulation results demonstrate the suitability of the proposed mechanism.

Real-time systems are often designed using a set of periodic tasks. Task periods are usually set by the system requirements, but deadlines and computation times can be modified in order to improve system performance. Sensitivity analysis in real-time systems has focused on changes in task computation times using fixed priority analysis. Only a few studies deal with the modification of deadlines in dynamic priority scheduling. The aim of this work is to provide a sensitivity analysis for task deadlines in the context of dynamic-priority, pre-emptive, uniprocessor scheduling. In this paper, we present a deadline minimisation method that achieves the maximum reduction. As undertaken in other studies concerning computation times, we also define and calculate the critical scaling factor for task deadlines. Our proposal is evaluated and compared with other works in terms of jitter. The deadline minimisation can be used to strongly reduce jitter of control tasks, in a real-time control application

The real-time implementation of a controller typically introduces artefacts like delay and jitters that have not been considered at the design stage. As a consequence, the system behaves in a non-periodic manner, and the real performance is degraded with respect to the expected response. This paper proposes a hybrid task model to reduce the impact of the scheduling on the control performance. For a large batch of typical plants, we analyze how sensitive the control system is to jitter when the sampling rate is slow or fast compared to the bandwidth of the system

In this paper we present a new algorithm for CPU resource reservation in real-time systems that allows the coexistence of hard, soft and non real-time tasks. The proposed algorithm is specifically designed to handle computational overload. A task that needs more CPU-time than reserved can reuse the spare bandwidth, without interfering with the others tasks. With respect to other reclamation schemes, the novelty of the proposed algorithm is that the spare bandwidth is fairly distributed among the needing servers. The effectiveness of the algorithm is demonstrated with an extensive set of experiments. We also propose a methodology to set scheduling parameters depending on the type of the task and on the time constraints needed.

Currently, containers are used in the transport of products because of the point-to-point service they offer. By using specialized cranes, operation in maritime transport and land transport can be achieved quickly. To optimize the operation costs, the whole management of terminal is computerized proportionally with the complexity of the problem. The multi-agent system paradigm seems suitable to solve the computational problem. The communication between agents and the corresponding data warehouse is made by means of a number of content-oriented communication channels. For supplying an organized message routes to the system, an event oriented communication system has been developed. The communication channels determine the communication system architecture. This paper describes how common communications architecture for agents can facilitate the management of an industrial system. The aim is to separate the agents of the communications. The communications system used is based on the distributed blackboard architecture.

Feasibility tests for hard real-time systems provide information about the schedulability of a set of tasks. However, this information is a yes or no answer whether the task set achieves the test or not. From the system design point of view, it would be useful to have more information, for example, how much can one vary some task parameters, such as computation time, without jeopardizing the system feasibility. The aim of the work is to provide a method to determine how much a task can increase its computation time, maintaining the system feasibility under a dynamic priority scheduling. This extra time can be determined not only in all the task activations, but in n of a window of m task invocations. This is what we call a window-constrained execution time system. In control applications, this information can be used to execute supervision activities, such as model updating which is not required to be executed in all the periods, or to determine new controller parameters for the current operating conditions. In fault tolerance, this information allows us to recover n faults in m activations.

Autonomous mobile robots perform their activities in unstructured, dynamic and unpredictable environments. The robot state, the objectives to be fulfilled and the environmental conditions have influence in the variability of the system load. In the face of such environmental uncertainty, the computational requirements of recognition tasks are variable and dependent on the number of objects perceived in the scenes. It also arises that to ensure robot safety, the temporal requirements of reactive tasks have to be proportionally adjusted to the actual robot speed. Traditional robot control architectures have been designed ignoring these aspects and hence lead to extremely expensive and underutilised system designs. To overcome such drawbacks a feedback control scheduler (FCS) together with a task model that permit the adaptation of the temporal requirements of the tasks depending on the robot speed and on the environmental conditions are proposed. Furthermore, to undertake robot QoS improvement, a flexible server (FS) is integrated with the FCS in a global real-time architecture.

In multi-moded real-time systems there may exist a different set of tasks per mode. During its mission, the system may switch to a new operating mode, which will involve completing running old-mode tasks and starting new-mode tasks. This represents a transient, bounded overload, which may not be schedulable unless some new-mode tasks are delayed until the old-mode load has decreased. Although this idea has already been proposed elsewhere, a method for obtaining the shortest offsets that make a transition schedulable has not yet been devised. The management of shared resources during the transition represents an added problem to tackle. This paper presents a new mode change protocol and an algorithm to calculate the necessary offsets to schedule mode changes according to a set of requirements and in the presence of shared resources.

In complex control systems such as autonomous guided vehicles, where the environment is unpredictable, mobile robotic architectures should incorporate internal monitoring systems, in order to dynamically measure the vehicle quality of service, and adjusting the control robot parameters for the best vehicle fit. In this paper an adaptive quality of service management system (AQoSMS), integrated in an intelligent planner of a real-time mobile robotic architecture is presented. The performance parameter requirements requested from the application level, configured depending on the robot state and on the environment, the real values of the performance parameters and the available slack time in the system provided by the real-time operating system are traded off in run-time by the AQoSMS. In order to satisfy and improve the quality indexes required for the current mission, the AQoSMS performs the adaptation of robot control parameters (i.e. speed) or temporal characteristics of the heterogeneous load executed by the system (i.e. task period or computational time).

The paper introduces improvements in partitioning schemes for multiprocessor real time systems which allow higher processor utilization and enhanced schedulability by using exact feasibility tests to evaluate the schedulability limit of a processor. The paper analyzes how to combine these tests with existing bin packing algorithms for processor allocation and provides new variants which are exhaustively evaluated using two assumptions: variable and fixed number of processors. The problem of evaluating these algorithms is complex, since metrics are usually based on comparing the performance of a given algorithm to an optimal one, but determining optimals is often NP hard on multiprocessors. This problem has been overcome by defining lower or upper bounds on the performance of an optimal algorithm and then defining metrics with respect these bounds. The evaluation has shown that the algorithms exhibit extremely good behavior and they can be considered very close to the maximum achievable utilization. It is also shown that dynamic priority policies produce significantly better results than fixed priority policies when task sets require high processor utilizations.

The paper addresses the problem of jointly scheduling tasks with both hard and soft real time constraints. We present a new analysis applicable to systems scheduled using a priority preemptive dispatcher, with priorities assigned dynamically according to the EDF policy. Further, we present a new efficient online algorithm (the acceptor algorithm) for servicing aperiodic work load. The acceptor transforms a soft aperiodic task into a hard one by assigning a deadline. Once transformed, aperiodic tasks are handled in exactly the same way as periodic tasks with hard deadlines. The proposed algorithm is shown to be optimal in terms of providing the shortest aperiodic response time among fixed and dynamic priority schedulers. It always guarantees the proper execution of periodic hard tasks. The approach is composed of two parts: an offline analysis and a run time scheduler. The offline algorithm runs in pseudopolynomial time O(mn), where n is the number of hard periodic tasks and m is the hyperperiod/min deadline.

This paper presents a high-level abstraction for remote communication which allows to establish connections with real-time requirements. The approach is based on the idea of structuring applications as modules with a set of external visible data structures which act as I/O ports. Parts can be interconnected using real-time connections. This interconnection is done in a configuration phase and it allows to integrate modules or applications dynamically. Real-time connections produce streams of messages with time constraints. Messages are scheduled by means of a priority model where priorities are assigned following generalized rate monotonic scheduling (GRMS) theory. The proposed system is built over a network with the timed token protocol (TTP) medium access control (MAC). A discussion on how to provide GRMS abstractions over TTP is given. Comparison results between current scheduling algorithms and the proposed model are also provided.