Time-triggered communication protocols rely on trusted components known as guardians to enforce adherence to predetermined network schedules. Network-agnostic guardians offer an efficient and scalable distributed solution with reduced implementation cost and complexity compared to network-aware alternatives. However, this efficiency is based on the guardian's dependence on the controlled node for clock synchronization, which introduces a vulnerability: a malicious node can exploit this dependency to launch timing attacks against its guardian and eventually interfere with messages from other nodes on the network. In this paper, we establish a theoretical lower bound on the attainable clock synchronization precision between a node and its network-agnostic guardian. Building on this result, we introduce a timing attack that leverages the unavoidably imperfect clock synchrony to cause controlled and undetected de-synchronization of the guardian. The attack enables a malicious node to cause collisions with targeted critical network messages. We evaluate the effectiveness of the attack using a FlexRay field bus network model implemented in the OMNeT++ simulation framework. Our results show that the attack is able to remain undetected with 100% success and disrupts the transmission of the critical messages of the target node by causing collisions with them with 100% success.

The Logical Execution Time (LET) model has deterministic properties which dramatically reduce the complexity of analyzing temporal requirements of multi-rate cause-effect chains. The configuration (length and position) of task's communication intervals directly define which task instances propagate data through the chain and affect end-to-end latencies. Since not all task instances propagate data through the chain, the execution of these instances wastes processing resources. By manipulating the configuration of communication intervals, it is possible to control which task instances are relevant for data propagation and end-to-end latencies. However, since tasks can belong to more than one cause-effect chain, the problem of configuring communication intervals becomes non-trivial given the large number of possible configurations. In this paper, we present a method to decrease the waste of processing resources while reducing end-to-end latencies. We use a search algorithm to analyze different communication interval configurations and find the combination that best decrease system utilization while reducing end-to-end latencies. By controlling data propagation by means of precedence constraints, our method modifies communication intervals and controls which task instances affect end-to-end latencies. Despite the sporadic release time of some task instances during the analysis, our method transforms those instances into periodic tasks. We evaluate our work using synthetic task sets and the automotive benchmark proposed by BOSCH for the WATERS industrial challenge.

With the increasing use of multicore platforms to realize mixed-criticality systems, understanding the underlying shared resources, such as the memory hierarchy shared among cores, and achieving isolation between co-executing tasks running on the same platform with different criticality levels becomes relevant. In addition to safety considerations, a malicious entity can exploit shared resources to create timing attacks on critical applications. In this paper, we focus on understanding the shared DRAM dual in-line memory module and created a timing attack, that we named the "bank & row conflict bomb", to target a victim task in a multicore platform. We also created a "navigate" algorithm to understand how victim requests are managed by the Memory Controller and provide valuable inputs for designing the bank & row conflict bomb. We performed experimental tests on a 2nd Gen Intel Xeon Processor with an 8GB DDR4-2666 DRAM module to show that such an attack can produce a significant increase in the execution time of the victim task by about 150%, motivating the need for proper countermeasures to help ensure the safety and security of critical applications.

The improvements in network latency and the advent of Edge computing have inspired industries to explore providing Real-time (RT) applications as cloud-based services and benefit from the availability, scalability, and efficient hardware resource utilization of clouds. It is crucial to improve the entire stack, including the applications’ containerization, container deployment, and orchestration across nodes to host RT applications in the cloud. However, state-of-the-art container orchestrators, e.g., Kubernetes (K8s), and the underlying Linux and containerization layer ignore orchestration and management of shared resources (e.g., memory bandwidth, cache); thus, rendering them unsuitable for RT use cases due unpredictability as a result of shared resource contention. We propose K8s extensions inspired by existing RT resource management frameworks to the underlying Linux kernel and containerization layer of each node for shared resource monitoring to help K8s maintain a cloud-wide view and allocate and dynamically orchestrate shared resources to enforce the guarantees required by the RT containers. Additionally, as a proof-of-concept, we design and implement (1) new K8s shared resource orchestration extensions to support memory bandwidth and last-level cache allocation and (2) a shared-resource controller in Linux based on a new algorithm to combine approximate but throttling-free memory bandwidth allocation by simple and efficient hardware controllers (e.g., Intel MBA) together with strict but pessimistic guarantees offered by software budget allocation and throttling (e.g., Memguard). We performed experiments to evaluate and demonstrate the newly implemented extensions on server-grade hardware.

Collision-free time-triggered communication in distributed safety- and real-time-critical systems relies on approximately synchronized clocks, a-priori-defined communication schedules, and network guardians, synchronized in the same manner, which inhibit a node’s network access outside scheduled times. However, the ever-increasing complexity and interconnectivity of such systemsrender using contemporary network-aware guardians unsuitable: firstly, significant cost, complexity and certification efforts are incurred in developing new network protocol and topology specific guardian solutions. Secondly, contemporary network guardians lack the means to protect against repetitive cyberattacks that exhaust system synchrony.In this paper, we investigate a novel class of time-domain attacks, aimed at exhausting nodes by tampering with the synchrony of their network-agnostic guardians. We counter the attacks by introducing SyncGuard, the first, network-agnostic and time-domain attack-resilient guardian. SyncGuard-equipped systems avoid synchrony exhaustion attacks by jointly coordinating network access and node-rejuvenation.

The increasing interest in adopting cloud technologies for Industry 4.0 and mixed-criticality environments is paving the way for compelling new opportunities and challenges. However, cloud deployments use multicore processors that introduce interference between co-executing applications on different cores due to contention in shared resources, such as the memory subsystem. Such interference can cause critical applications to miss their deadlines. To enable the co-execution of critical and non-critical applications on the same multicore processor, we propose an approach that guarantees memory access time isolation for critical cores, while not jeopardizing the memory bandwidth of the non-critical ones. We prove the viability of our approach using Intel’s resource director technology for memory access detection and regulation. Experiments show that queue occupancy is an excellent metric to estimate the number of interfering cores co-accessing the memory. We also assess the indirect memory bandwidth limitation achievable by applying Intel’s Memory Bandwidth Allocation technology.

The automotive industry is looking into integrated architecture to combine multiple application subsystems of different criticalities on the readily available low-cost multicore platforms as they promise several benefits. However, it is difficult to achieve the required isolation and guarantees in such an architecture due to contention in shared resources, e.g., CPU, shared-bus, and memory (controller). This can cause unpredictable delays leading to deadline misses in real-time applications. We propose a low overhead modular monitoring framework to provide support for ensuring that the real-time applications meet their deadline when considering shared resource accesses, and helping to improve resource utilization so that best-effort applications can achieve a better Quality-of-Service despite pessimistic resource allocation assumptions of real-time applications. Our framework keeps the monitoring overheads to a minimum and triggered reaction meaningful by operating on the basis of low-level hardware and software signals, strategically checking resources, and triggering actions based on abstract availability of resources. We propose a Domain-Specific Language (DSL) to relieve the system designers from the tedious and error-prone job of configuring platform-specific parameters for the framework. Finally, this paper evaluates our monitoring framework based on an instantiation on a Xilinx Zynq UltraSacle multicore SoC running Linux and a simple industry-inspired use case.

Industries are recently considering the adoption of cloud computing for hosting safety critical applications. However, the use of multicore processors usually adopted in the cloud introduces temporal anomalies due to contention for shared resources, such as the memory subsystem. In this paper we explore the potential of Intel’s Memory Bandwidth Allocation (MBA) technology, available on Xeon Scalable processors. By adopting a systematic measurement approach on real hardware, we assess the indirect memory bandwidth limitation achievable by applying MBA delays, showing that only given delay values (namely 70, 80 and 90) are effective in our setting. We also test the derived bandwidth assured to a hypothetical critical core when interfering cores (e.g., generating a concurrent memory access workload) are present on the same machine. Our results can support designers by providing understanding of impact of the shared memory to enable predictable progress of safety critical applications in cloud environments.

This paper explores virtualization technologies and cloud computing for migrating an existing real-time safety-critical railway use-case from dedicated hardware solutions. Cloud computing is rapidly gaining popularity in many domains as they provide benefits such as higher availability, scalability, and efficient hardware resource utilization. We examine existing virtualization technologies for deploying a (private) Real-Time(RT)-Cloud on COTS server hardware to run an existing railway use-case while meeting stringent safety and security requirements. We base our migration review on comparison and relevant benchmarking of KVM and Xen virtualization technologies for the specific railway requirements. Based on the insights gained, we provide suggestions for using existing virtualization technologies with new RT-cloud components to safely and securely run the railway use-case applications.

In Mixed-Criticality Systems (MCS), low-critical applications have a larger attack surface compared to high-critical applications. Even though MCS isolate criticality domains of execution by design, a threat affecting a low-critical service can alter the execution of a high-critical task: e.g by degrading the system availability or user-experience. Such attack on low-critical tasks can even introduce an entry point for propagating the attack further to high-critical tasks. In this context, detecting such threats in applications during runtime is a major issue for MCS security. Control-Flow Integrity (CFI) monitoring is a common security technique for runtime threat detection in program execution: using a predefined policy, it identifies unauthorized control-flow (CF) transitions as malicious activity. Recent research has introduced the use of hardware-assisted CF tracing for CFI monitoring into industrial real-time systems, since such implementation does not require instrumentation of the monitored program. However, CF tracing brings a high performance overhead for monitoring, which depends on the monitored program execution path (the more executed CF transitions, the higher the overhead). On one hand to integrate the security service in a MCS, we must consider the worst-case monitoring overhead. On the other hand, this assumption is highly pessimistic for a practical deployment. We propose a first safety-aware method to integrate hardware-assisted CF based security monitoring with ARM CoreSight into a MCS, and metrics to evaluate the trade-off between performance impact and security monitoring coverage. Our security framework combines a predictable CF transition level monitoring with trace collection that can be used for CFI checking, together with an anomaly detection service to monitor the full program execution. We validate our approach on an industrial MCS platform with ARM CoreSight support, using a set of programs from TACLeBench benchmark.

Safety-Critical (SC) applications require high availability, possibility of run-time reconfiguration, and significant resource over-provisioning. Furthermore, they suffer from hardware obsolescence due to the use of custom or specialized hardware. Cloud computing could be used to resolve these issues. Moreover, they could improve SC systems suffering from scalability issues, e.g., the every growing SC railway network. However, SC applications require low latencies and guarantees that are currently not possible on clouds. In this paper, we explore the possibility of enhancing the current cloud computing paradigm by adding a resource management layer to support the deterministic execution of SC applications while providing the benefits of cloud computing principles.We provide a cloud-wide global resource manager that monitors, controls, and coordinates node-level Local Resource Managers (LRMs) placed on each private cloud node. In addition, we give guarantees to SC Virtual Machines (VMs) on each node via a novel CPU-and memory bandwidth-aware Time-Triggered (TT) offline scheduling algorithm that generates a scheduling table for use by an LRM. For improving the utilization of the cloud resources, the LRMs provide flexibility to schedule Event-Triggered (ET) SC and non-critical VMs at run-time without regenerating the offline scheduling table. We implemented our approach in a KVM-based private cloud and performed experiments to determine the relevant overheads.

Existing global resource management approaches for real-time and safety-critical applications deployed on distributed systems consisting of multicore and many -core nodes don't consider safety and security together for the global resource management itself. In this work, we propose an approach considering safety and security using distributed global resource re-orchestration decision-making to complement the existing approaches. The implemetation of our framework is based on Hyperledger Sawtooth blockchain and smart contracts.

Low latency and on demand resource availability enable fog computing to host industrial applications in a cloud like manner. One industrial domain which stands to benefit from the advantages of fog computing is robotics. However, the challenges in developing and implementing a fog-based robotic system are manifold. To illustrate this, in this paper we discuss a system involving robots and robot cells at a factory level, and then highlight the main building blocks necessary for achieving such functionality in a fog-based system. Further, we elaborate on the challenges in implementing such an architecture, with emphasis on resource virtualization, memory interference management, real-time communication and the system scalability, dependability and safety. We then discuss the challenges from a system perspective where all these aspects are interrelated.

Much effort has been put into improving the predictability of real-time systems, especially in safety-critical environments, which provides designers with a rich set of methods and tools to attest safety in situations with no or a limited number of accidental faults. However, with increasing connectivity of real-time systems and a wide availability of increasingly sophisticated exploits, security and, in particular, the consequences of predictability on security become concerns of equal importance. Time-triggered scheduling with offline constructed tables provides determinism and simplifies timing inference, however, at the same time, time-triggered scheduling creates vulnerabilities by allowing attackers to target their attacks to specific, deterministically scheduled and possibly safety-critical tasks. In this paper, we analyze the severity of these vulnerabilities by assuming successful compromise of a subset of the tasks running in a real-time system and by investigating the attack potential that attackers gain from them. Moreover, we discuss two ways to mitigate direct attacks: slot-level online randomization of schedules, and offline schedule-diversification. We evaluate these mitigation strategies with a real-world case study to show their practicability for mitigating not only accidentally malicious behavior, but also malicious behavior triggered by attackers on purpose.

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.

Time-triggered real-time systems achieve deterministic behaviour, making them suitable for safety-critical environments. However, this determinism also allows attackers to finetune attacks after studying the system behaviour through side channels, targeting safety-critical victim tasks. Assuming fault independence, replication tolerates both random and malicious faults of up to f replicas. Yet, directed attacks violate the fault independence assumption. This violation possibly gives attackers the edge to compromise more than f replicas simultaneously, in particular if they can mount the attack from already compromised components. In this paper, we sketch mitigation strategies for time-triggered systems with task replication to withstand directed timing attacks and show preliminary results on their effectiveness and practicality.

One of the primary sources of unpredictability in modern multi-core embedded systems is contention over shared memory resources, such as caches, interconnects, and DRAM. Despite significant achievements in the design and analysis of multi-core systems, there is a need for a theoretical framework that can be used to reason on the worst-case behavior of real-time workload when both processors and memory resources are subject to scheduling decisions. In this paper, we focus our attention on dynamic allocation of main memory bandwidth. In particular, we study how to determine the worst-case response time of tasks spanning through a sequence of time intervals, each with a different bandwidth-to-core assignment. We show that the response time computation can be reduced to a maximization problem over assignment of memory requests to different time intervals, and we provide an efficient way to solve such problem. As a case study, we then demonstrate how our proposed analysis can be used to improve the schedulability of Integrated Modular Avionics systems in the presence of memory-intensive workload.

Airbus is investigating COTS multicore platforms for safety-critical avionics applications, pursuing helicopter-style autonomous and electric aircraft. These aircraft need to be ultra-lightweight for future mobility in the urban city landscape. As a step towards certification, Airbus identified the need for new methods that preserve the ARINC 653 single core schedule of a Helicopter Terrain Awareness and Warning System (HTAWS) application while scheduling additional safety-critical partitions on the other cores. As some partitions in the HTAWS application are memory-intensive, static memory bandwidth throttling may lead to slow down of such partitions or provide only little remaining bandwidth to the other cores. Thus, there is a need for dynamic memory bandwidth isolation. This poses new challenges for scheduling, as execution times and scheduling become interdependent: scheduling requires execution times as input, which depends on memory latencies and contention from memory accesses of other cores - which are determined by scheduling. Furthermore, execution times depend on memory access patterns. In this paper, we propose a method to solve this problem for slot-based time-triggered systems without requiring application source-code modifications using a number of dynamic memory bandwidth levels. It is NoC and DRAM controller contention-aware and based on the existing interference-sensitive WCET computation and the memory bandwidth throttling mechanism. It constructs schedule tables by assigning partitions and dynamic memory bandwidth to each slot on each core, considering worst case memory access patterns. Then at runtime, two servers - for processing time and memory bandwidth - run on each core, jointly controlling the contention between the cores and the amount of memory accesses per slot. As a proof-of-concept, we use a constraint solver to construct tables. Experiments on the P4080 COTS multicore platform, using a research OS from Airbus and EEMBC benchmarks, demonstrate that our proposed method enables preserving existing schedules on a core while scheduling additional safety-critical partitions on other cores, and meets dynamic memory bandwidth isolation requirements.

Wireless networks are currently considered as extension of typical wired networks to increase flexibility and scalability. However, this design freedom is accompanied by the reduced reliability and real-time capability of the wireless communication. To put these advantages and disadvantages in the required relationship, we introduce a use case analysis of typical factory automation applications within this paper. Additionally, we compare performance indicators of industrial communication systems to enable the evaluation of the arising hybrid wired/wireless networks with regard to the requirements. Especially reliability parameters like the packet error rate (PER) are often only weakly linked to their industrial application. Therefore, we finally present a bottom-up analysis of a typical factory automation machine to derive more realistic PER values based on real applications.

Mixed-criticality systems (MCS) aim at boosting the integration density in safety-critical systems, resulting into efficient systems, while simultaneously providing increased performance. The DREAMS project provides a cross-domain architectural style for MCS based on networked, virtualized multi-cores controlled by hierarchical resource managers. However, the availability of a platform is only one side of the coin: deploying mixed-critical applications to shared resources typically requires design-time configurations (e.g., to ensure real-time constraints or separation constraints mandated by safety regulations). These configurations are the outcome of complex optimization problems which are intractable in a manual process that also hardly can guarantee the consistency of all deployable artefacts nor their traceability to the requirements. However, existing toolchains lack support for MCS integration, and particularly DREAMS' advanced platform capabilities. We present an integrated model-driven toolchain and the underlying metamodels covering all relevant aspects of MCS including applications, timing, platforms, deployments, configurations and annotations for extra-functional properties such as safety. The approach focuses on the left branch of the V-cycle, and ranges from product-line and design space exploration to resource allocation and configuration generation. We report on the integration of exploration tools and a reconfiguration graph synthesizer, and evaluate the resulting toolchains in two use cases consisting of a product-line of wind power control applications and an avionic subsystem respectively.

Operational safety is one of the major issues in modern industrial applications. For safety critical systems, the verification and validation efforts can be reduced using temporal isolation enforced by hierarchic schedules. In 2012, Lackorzyiiski et al. demonstrated that reserving bandwidth for event-triggered (ET) activities in hierarchic schedules may lead to significant bandwidth loss. In contrast to the bandwidth reservation techniques, online admission of ET activities can help reduce bandwidth losses. However, the state-of-the-art approaches for online admission of ET activities (i) cannot be utilized in hierarchic systems and (ii) incur significant scheduling overheads. In this paper, we present a flexible scheduler design for online admission of non-preemptive a periodic tasks in a hierarchic time-triggered environment. Our approach circumvents the bandwidth loss issue in hierarchic systems, and can be implemented on top of a variety of hypervisor interfaces. In order to provide offline guarantees, we also provide a necessary test for our approach. Through evaluation, we demonstrate that our approach efficiently utilizes processor bandwidth and only incurs small overheads for a safety critical system. The experimental study also shows that our approach is comparable, in terms of execution overheads, to the state-of-the-art preemptive non-hierarchic approaches.

In many real-time systems, preemption is either impossible or prohibitively expensive. The problem of scheduling non-preemptive periodic tasks with known release offsets is known to be NP-Hard. In this paper, we investigate the existing non-preemptive scheduling algorithms in both categories of work-conserving and non-work-conserving algorithms, where in the former, the processing resource is not allowed to be idle as long as there is an unfinished job in the system. While describing the advantages and weaknesses of the existing scheduling solutions we show that using online non-work-conserving algorithms it is possible to schedule more task sets. In our work, we discuss the challenges to design the idle-time insertion policy (IIP) which can be combined with the existing scheduling policies such as the earliest deadline first (EDF), rate monotonic (RM), etc. Further we present a tighter necessary condition for schedulability of non-preemptive tasks. We also provide an IIP for EDF based on looking into a number of jobs in future. Through the experiments we show that the our IIP for EDF significantly increases the schedulability of non-preemptive tasks, particularly in periodic task sets. While our schedulability ratio is more than 80%, the state of the art work-conserving algorithms are about 15%.

This paper considers the problem of reducing the number of preemptions in a system with periodic tasks and preemption overhead. The proposed solution is based on the key observation that for periodic task sets, the task with the smallest period plays an important role in determining the maximum interval of time during which a lower priority task can be executed without being preempted. We use this property to build a new limited preemptive scheduling algorithm, named RS-LP, based on fixed-priority scheduling. In RS-LP, the length of each task's non-preemptive region is varying during the system execution so as to keep the preemptions aligned with the releases of the highest priority task. This simple mechanism allows us to reduce the overall number of preemptions. The proposed algorithm, decides whether or not to preempt the currently executing task based on the maximum blocking tolerance of the higher priority tasks. In any case, the preemptions are authorized only at release instants of the task with the smallest period, thereby limiting the maximum number of preemptions to the number of releases of the highest priority task. Moreover, in this paper, we provide two different preemption overhead aware schedulability tests for periodic and loose-harmonic task sets (i.e., where each period is an integer multiple of the smallest period), together with a lower bound on the maximum number of preemptions. To conclude, extensive experiments comparing RS-LP with the state of the art limited preemptive scheduling algorithms are finally presented.

In this work, we present an initial step towards enabling TT scheduling on a real COTS multicore platform P4080. It takes into account inter-core interferences in the on-chip network and the memory sub-system. We propose an approach comprising a runtime mechanism and an offline phase. For the runtime mechanism, we propose two servers running on each core-processing time server and memory access server implemented using built-in hardware monitors. Jointly, the two servers on each core, enforce slot-level offline computed server budget reservations, thereby limiting the maximum inter-core interferences introduced and experienced by each task considering different inter-core interference latencies. In the offline phase, we propose a procedure that can be used by any offline scheduler to compute the bound on variability in execution time of each task while allowing different slot-level memory access server budget reservations. We also did a preliminary bare-metal implementation of our proposed runtime mechanism on a real COTS multicore platform P4080. Overall, our proposed method facilitates integration of COTS multicore platforms in TT systems, while maintaining features of TT architecture like slot-level determinism, clock synchronization, etc.

During the design phase of many real-time systems, designers often have a range of acceptable period values for which some levels of safety or quality of service are guaranteed. The choice of period values influences system schedulability and computational complexity of schedulability analysis, especially for the rate monotonic (RM) scheduling algorithm. It has been shown that RM guarantees 100% utilization if the periods are harmonic, i.e., Each period is an integer multiple of shorter periods. In this paper, we address harmonic period assignment problem where each task has a given period range. We extend the results of our previous work and present an O(n^2log(n)) algorithm (where n is the number of tasks) to verify necessary and sufficient conditions for the existence of a harmonic period assignment in cases where the previous solution has pseudo-polynomial computational complexity. We provide utilization bounds of the potential assignments as well as a heuristic algorithm to construct low utilization harmonic task sets. The efficiency of our period assignment algorithms has been evaluated in terms of acceptance ratio, task set utilization, data structure size, and the number of operations required for harmonic period assignment.

The periodic task model has been widely used in real-time systems due to the periodic behavior of many applications or periodic observation patterns of environmental events as in control applications. While the tasks of some applications have inherent values for periods, many can be defined via ranges of acceptable values. The designer choice of period values has consequences w.r.t. To utilization of the task set and the resulting hyper period. Harmonic task sets are favored, e.g., for their polynomial-time worst case response time analysis or their small hyper periods, which is of major concern e.g., for hyper visors used in virtualization or time triggered systems. In this paper we present a model to describe harmonic relations between ranges of period values, rather than single numbers only. We derive sufficient conditions for the existence of a linear-time solution, as well as a graph representation for the relations between period ranges. We provide utilization bounds of each resulting harmonic range, giving the designer flexibility to select a harmonic task set with high or low utilization. The tightness of the bounds as well as efficiency of our period assignment algorithms have been evaluated by synthetic experiments via system utilization and feasibly constructed harmonic task sets.

Slot shifting is a method to combine time-triggered and event-triggered scheduling of real-time systems. It analyzes offline constructed scheduling tables for the amount and location of unused resources, called spare capacities, which are used to accommodate event-triggered activities, such as aperiodic tasks. Spare capacities are efficiently represented to indicate available resources and the flexibility to shift offline scheduled tasks while maintaining their feasibility with respect to their original timing constraints. In this paper, we study the overhead costs involved in the practical implementation of slot shifting. We present results from measurements on the cycle accurate multi-processor systems-on-chip simulator MPARM, which indicate the execution time and memory costs of the various steps of online slot shifting for the ARM architecture. These allow a designer to select configurations and trade-offs for the implementation. We present the insights gained which lead to a redesign of the original algorithm.

Target sensitive tasks have an execution window for feasibility and must execute at a target point in time for maximum utility. In the gravitational task model, a task can express a target point, and the utility decay as a function of the deviation from this point. A method called equilibrium approximates the schedule with maximum utility accrual based on an analogy with physical pendulums. In this paper, we propose a scheduling algorithm for this task model to schedule periodic tasks. The basic idea of our solution is to combine the equilibrium with Earliest Deadline First (EDF) in order to reuse EDF's well studied timeliness analysis. We present simulation results and an example multimedia application to show the benefits of our solution.

Network dynamics, such as mobility and increase in network load, can influence the performance of a Wireless Sensor Network (WSN). In this paper, we introduce a method which exploits design-time knowledge of the application scenario dynamics to construct a proactive run-time reconfiguration approach. The approach anticipates for the impact that predefined dynamic events can have on the performance of the WSN by switching between various modes of operation defined at design-time. A mode defines the values for the controllable parameters of the network protocol stack. Our approach explicitly differentiates between parameters that can be adapted locally, per node, and those that should be considered globally for the whole WSN. Design-time definition of modes results in a very low run-time overhead as we only require detection of the mode to use and a low overhead synchronization to change global parameters. The approach is made robust by using a recovery approach for nodes unaware of their global mode after, for example, (re-)joining the network. Experiments with an office monitoring deployment and extensive simulations of a cow-health monitoring scenario show that our approach can easily be adopted by practical WSN deployments and results in a significant reduction in resource usage, e.g., power consumption in our examples, at a very low run-time overhead cost.

In many modern embedded platforms, safety-critical functionalities that must be certified correct to very high levels of assurance co-exist with less critical software that are not subject to certification requirements. Recent research in real-time scheduling theory has yielded some promising techniques for meeting the dual goals of (i) being able to certify the safety-critical functionalities under very conservative assumptions, and (ii) ensuring high utilization of platform resources under less pessimistic assumptions. This research has centered on an event-triggered/ priority-driven approach to scheduling. However current practice in many safety-critical domains, including (the safety-critical components of) automotive and avionics systems and factory automation, favors a time-triggered approach. In such time-triggered systems, non-interference of safety-critical components by non-critical ones is ensured by strict isolation between components of different criticalities, although such isolation facilitates the certification of the safety-critical functionalities, it can cause very low resource utilization. The research reported in this document is, to our knowledge, the first to study time-triggered scheduling from the perspective of both ensuring certifiability of high-criticality functionalities, and obtaining high resource utilization as in (i) and (ii) above. We present algorithms for time-triggered scheduling of mixed-criticality systems that offers resource utilization guarantees similar to those of event-triggered scheduling. Since the time-triggered approach currently seems to find greater acceptability with certification authorities, it is hoped that this research will hasten the adoption of these results in building embedded systems that are subject to mandatory certification.

In this paper, we propose a novel method for real- time stream adaptation of live MPEG-4 Visual advanced simple profile (ASP) and simple profile (SP) bit streams to limited and varying network bandwidth. The proposed method operates by dropping higher order AC DCT coefficients present in blocks. Unlike frame dropping, the proposed method delivers finer granularity during adaptation and therefore smaller resource under-utilization. Furthermore, to optimize the resource utilization and consequently the perceptive video quality, the method attempts to represent the adapted block with the least possible number of bits. The low computation requirements of the proposed method qualifies its application to adaptation of live streams. Additionally, the method can be applied for other constrained resources as well (e.g. CPU bandwidth). Implementation and case study of the proposed method show that, on an average, a bit rate reduction of up to 50% and a decoding time speedup up to 20% are achieved when compared with that of the original bitstream. Results also affirm the efficiency in resource usage.

In this demo, we present three lean methods for real-time adaptation of live MPEG-2 video to limited and varying network bandwidth. Our methods use real-time resource management techniques to determine available resources and steer adaptation decisions. Then, the modified stream consists only of frames with a high likelyhood of being processed completely, the resulting stream will only use resources when they are effectively used. We present three related approaches, based on skipping entire frames, or frames and DCT coefficients for finer granularity and thus smaller underutilization.

Some applications for real-time scheduling have target demands in addition to the commonly used starttime and deadline constraints: a task should be executed at a target point in time for maximum utility, but can execute around this point, albeit at lower utility. Examples for such applications include control and media processing.In this paper, we present a scheduling algorithm for the gravitational task model that we proposed in~\cite{Guerra:ECRTS08,Guerra:Kluwer09}.This model allows tasks to express their utility as a function of the point of execution and the target point.The proposed scheduler is divided into $2$ phases: ordering and timing. The former uses a heuristic to order the jobs in the ready queue and the latter schedules the execution based on the equilibrium~\cite{Guerra:ECRTS08,Guerra:Kluwer09}.The new ordering heuristic accounts for both acceptance ratio and utility accrual, hence achieving better results than the scheduler proposed in~\cite{Guerra:ECRTS08,Guerra:Kluwer09}. Besides, the scheduler proposed here uses a heuristic for the ordering phase of complexity $O(n \times log (n))$ and a timing phase of complexity $O(n)$.These complexities represent a significant reduction compared to previous work.Moreover, this paper contains an analysis of the complexity of the proposed scheduler and an evaluation through simulation.

The inherent properties of wireless sensor networks (WSN) disqualify most classic methods targeting timeliness guarantees. Assumptions of such methods as well as a restrictive notion of timeliness borrowed from classic real-time systems clash with the indeterminism of realistic scenarios. In this paper, we introduce a generalized notion of timeliness which allows to provide meaningful performance metrics under unreliable conditions, common in WSN. We present a probabilistic metric to capture the level of confidence for the timeliness performance without restricting its applicability. It consists of the estimation of the end-to-end delay distribution function by using current local state information of intermediate hops, which requires low memory and computational resources. This metric represents a hook to adaptive QoS as it is constantly updated at run-time and reflects the actual network status. Extensive simulation results underline the validity of the method and its applicability.

Portability is a major concern in developing applications for embedded devices such as Wireless Sensor Networks (WSN). Abstractions of the hardware platform which are introduced by the operating system (OS) make possible to develop code independent of the hardware, which can be reused in later deployments. However, the lack of standard APIs for the variety of OS in the domain of WSN restricts portability to those systems running the same OS.We present on-going work on the design and development of a portable operating system abstraction layer (OSAL), which achieves a complete abstraction of the OS architecture as well as a common API across multiple OS. Portability at the application level is effectively achieved thanks to a common set of primitives which abstract the underlaying OS and its particular architecture.We provide argumentation to highlight the efficiency of the OSAL and a general introduction to its features and design considerations. Moreover, we present a preliminary evaluation of the current implementation, which has proven to introduce minimal run-time overhead as well as negligible increase on the software footprint.

The commonly used task models for real-time systems focus on execution windows expressing earliest start times and deadlines of tasks for feasibility. Within these windows, execution of tasks is considered of uniform utility.Some applications, however, have target demands in addition: a task should be executed at a target point in time for maximum utility, but can execute around this point, albeit at lower utility. Examples for such applications include control and media processing.In this paper, we present a gravitational based task model to address these issues. Tasks are considered as massive bobs hanging on a pendulum: a single task, left to itself, will execute at the bottom, the target point. If a force, such as the weight of other tasks, is applied, it can be shifted around this point. Thus, tasks' importance and their utility around target points can be expressed. Additionally, we show a scheduling example of how this model can be used to find the best compromise of tasks' interests based on the equilibrium state of a pendulum. Nonetheless, this task model is not restricted to a particular scheduling algorithm.Results from a simulation study show the effectiveness of the approach.

With the growing popularity of variable network technologies, it is highly desirable to enable effective and quick browsing of remote multimedia content. In this paper we present a method for quick access of remote video content as an initial step towards a full digital Video Cassette Recording functionality in multimedia streaming applications such as Video-On-Demand, video broadcasting and remote video editing.We propose a transcoding scheme for H.264/AVC video that fully utilizes the benefits of recently proposed SP- and SI-frames to facilitate user-friendly remote stream browsing and editing. The transcoding parameters can be adaptively changed and optimized to support different characteristics of H.264 video streams.

The design of embedded real-time systems requires skills from multiple specific disciplines, including, but not limited to, control, computer science, and electronics. This often involves experts from differing backgrounds, who do not recognize that they address similar, if not identical, issues from complementary angles. Design methodologies are lacking in rigor and discipline so that demonstrating correctness of an embedded design, if at all possible, is a very expensive proposition that may delay significantly the introduction of a critical product. While the economic importance of embedded systems is widely acknowledged, academia has not paid enough attention to the education of a community of high-quality embedded system designers, an obvious difficulty being the need of interdisciplinarity in a period where specialization has been the target of most education systems. This paper presents the reflections that took place in the European Network of Excellence Artist leading us to propose principles and structured contents for building curricula on embedded software and systems.

A preschedule is a static schedule without assuming constant and completely predictable rate of resource supply. A generalized prescheduling framework and a sound, complete, and PTIME preschedule generator was proposed in Wang et al. (2004) based on linear programming (LP). Since infinitely small time slices are not implementable for resources with context switch overhead, it is desirable to define and solve the prescheduling problem on the domain of integers so that context switching can occur only at boundaries of time quantums. However, integral LP (ILP) is NP-hard in the strong sense in general, so the ILP approach is not applicable and better techniques are needed. This paper answers this challenge by giving a sound, complete and PTIME rational-to-integral preschedule transformer based on a technique which we call "round-and-compensate".

Decoding MPEG-2 video streams imposes hard real-time constraints for consumer devices such as TV sets. The freedom of encoding choices provided by the MPEG-2 standard results in high variability inside streams, in particular with respect to frame structures and their sizes. In this paper, we identify realistic timing constraints demanded by MPEG-2 video decoding. We present results from a study of realistic MPEG-2 video streams to analyze the validity of common assumptions for software decoding and identify a number of misconceptions. Furthermore, we identify constraints imposed by frame buffer handling and discussed their implications on decoding architecture and timing constraints.

Time triggered methods provide deterministic behaviour suitable for critical real-time systems. The), perform less favourably, however if the arrival times of some activities are not known in advance, in particular if overload situations have to be anticipated. In many systems, the criticality of only a subset of activities justify the cost associated with the time triggered methods. In this paper we consider distributed systems where a subset of critical activities are handled in a time triggered fashion, via an offline schedule. At runtime, the arrival of aperiodic tasks may cause overload that demands to be handled in such a way that i) time triggered activities still meet all their original constraints, ii) execution of high-valued tasks are prioritised over tasks with lower value, iii) tasks can be quickly migrated to balance the overall system load. We give a precise formulation of overload detection and value based task rejection in the presence of offline scheduled tasks, and present a heuristic algorithm to handle overload. To benefit from the distributed setting, the overload handling includes an algorithm that integrates migration of rejected tasks with resource reclaiming and an acceptance test of newly arrived tasks. Simulation results underline the effectiveness of the presented approach.

Closed-loop control systems are dynamic systems subject to perturbations. One of the main concerns of the control is to design controllers to correct or limit the deviation that transient perturbations cause in the controlled system response. The smaller and shorter the deviation, the better the achieved performance. However, such controllers have been traditionally implemented using fixed timing constraints (periods and deadlines). This precludes controllers to execute dynamically, accordingly to the system dynamics, which may lead to sub-optimal implementations: although higher execution rates may be preferable when reacting to perturbations in order to minimize the response deviations, they imply wastage of resources when the system is in equilibrium. In this paper we argue and demonstrate that the responsibility of maximizing the performance of closed-loop systems relies on both the controller designer and the scheduler. We show that the dynamic optimization of the quality of the controlled system response calls for (a) flexible control task timing constraints that deliver effective control performance; flexible constraints allow us to achieve faster reaction by adaptively choosing the controller sampling rate and completion time upon transient perturbations, (b) a quality-of-control (QoC) metric; it associates with each control task timing a quantitative value expressing control performance (in terms of the closed-loop system error), and (c) new scheduling approaches; their goal is to quickly react to perturbations by dynamically scheduling tasks based on the chosen control task execution parameters to maximize the QoC. This combination offers the possibility of taking scheduling decisions based on the control information for each control task invocation, rather than using fixed timing constraints with constant periods and deadlines.

The controller area network (CAN) is widely used in a number of industrial applications. We present a method that shows how off-line scheduled messages can be scheduled on a CAN. The paper assumes that a schedule, for a set of tasks transmitting messages on a CAN, has been constructed off-line. We present a method that analyzes the off-line schedule and derives a set of periodic messages with fixed priorities, which can be scheduled on a CAN. Based on the information provided by the off-line schedule, the method derives inequality relations between the priorities of the messages under fixed priority scheduling protocols. In case the priority relations of the messages are not solvable, we split some messages into a number of artifacts, to obtain a new set of messages with consistent priorities. We use integer linear programming to minimize the final number messages.

Real-world industrial applications impose complex constraints, such as distribution, end-to-end deadlines, and jitter control on real-time systems. Most scheduling algorithms concentrate on single or limited combinations of constraints and requirements only. Offline scheduling resolves complex constraints, but provides only very limited flexibility. Online scheduling on the other hand, supports flexibility, resource reclaiming, and overload handling, but handling constraints such as distribution or end-to-end deadline can be costly, if not intractable. In the paper, we propose a method to efficiently handle soft real-time tasks in offline scheduled real-time systems using a total bandwidth server. In a first step, the offline scheduler resolves complex constraints, reduces their complexity, and provides for guaranteed available bandwidth. The constructed schedule is translated into independent tasks on single nodes with start-times and dead-line constraints only. These are then executed using earliest deadline first, total bandwidth server scheduling at runtime.

The increasing application of flexible and powerful real-time distributed control systems is presently characterizing the industrial automation field. Such systems involve three main disciplines: control systems, real-time systems, and communication systems. Control systems, due their stringent timing constraints, demand real-time computing technology. In addition, communication systems are needed for the data messaging between field devices. We propose an integrated approach to the design and implementation of such systems. We show that by a separate control design and its posterior distributed implementation, the system performance may suffer degradation. That is, when control loops are closed over communication networks, timing problems, as communication induced varying delays, can appear, decreasing the control system performance, and even leading the system to instability. However, we show that by an adequate integrated approach, that takes advantage of control theory, real-time communication properties, an adequate timing analysis, and an appropriate distribution of the control functions, the system performance increases dramatically.

Off-line scheduling and fixed priority scheduling (FPS) are often considered as complementing and incompatible paradigms. A number of industrial applications demand temporal properties (predictability, jitter constraints, end-to-end deadlines, etc.) that are typically achieved by using off-line scheduling. The rigid off-line scheduling schemes used, however do not provide for flexibility. FPS has been widely studied and used in a number of applications, mostly due to its simple run-time scheduling, and small overhead. It can provide more flexibility, but is limited with respect to predictability, as actual start and completion times of execution depend on run-time events. In this paper we show how off-line scheduling and FPS run-time scheduling can be combined to get the advantages of both the capability to cope with complex timing constraints and flexibility. The paper assumes that a schedule for a set of tasks with complex constraints has been constructed off-line. It presents a method to analyze the off-line schedule and derive an FPS task set with FPS attributes priority, offset, and period, such that the runtime FPS execution matches the off-line schedule. It does so by analyzing the schedule and setting up inequality relations for the priorities of the tasks under FPS. Integer linear programming (ILP) is then used to find a FPS priority assignment that fulfils the relations. In case the priority relations for the tasks of the off-line schedule are not solvable we split tasks into the number of instances, to obtain a new task set with consistent task attributes. Our schedule translation algorithm keeps the number of newly generated artifact tasks minimal.

In this paper, we first identify the potential violations of control assumptions inherent in standard real-time scheduling approaches (because of the presence of jitters) that causes, degradation in control performance and may even lead to instability. We then develop practical approaches founded on control theory to deal with these violations. Our approach is based on the notion of compensations wherein controller parameters are adjusted at runtime for the presence of jitters. Through time and memory overhead analysis, and by elaborating on the implementation details, we characterize when offline and on-line compensations are feasible. Our experimental results confirm that our approach does compensate for the degraded control performance when EDF and FPS algorithms are used for scheduling the control tasks. Our compensation approach provides us another advantage that leads to better schedulability of control tasks. This derives from the potential to derive more flexible timing constraints, beyond periods and deadlines necessary to apply EDF and FPS. Overall, our approach provides guarantees offline that the control system will be stable at runtime-if temporal requirements are met at runtime-even when actual execution patterns are not known beforehand. With our approach, we can address the problems due to (a) sampling jitters, (b) varying delays between sampling and actuation, or (c) both-not addressable using traditional EDF and FPS based scheduling, or by previous real-time and control integration approaches.

Many industrial applications with real-time demands are composed of mixed sets of tasks with a variety of requirements. These can be in the form of standard timing constraints, such as periods and deadlines, or complex, e.g. to express application-specific or nontemporal constraints, reliability, performance, etc. Arrival patterns determine whether tasks are treated as periodic, sporadic or aperiodic. As many algorithms only focus on specific sets of task types and constraints, system design has to focus on those supported by a particular algorithm, at the expense of the rest. In this paper, we present an algorithm to deal with a combination of mixed sets of tasks and constraints: periodic tasks with complex and simple constraints, soft and firm aperiodic tasks and sporadic tasks. Instead of providing an algorithm tailored to a specific set of constraints, we propose an EDF (earliest deadline first) based runtime algorithm and the use of an offline scheduler for complexity reduction to transform complex constraints into the EDF model. At runtime, an extension to EDF, two-level EDF, ensures the feasible execution of tasks with complex constraints in the presence of additional tasks or overloads. We present an algorithm for handling offline guaranteed sporadic tasks, with minimum inter-arrival times, in this context, which keeps track of arrivals of instances of sporadic tasks to reduce pessimism about future sporadic arrivals and to improve the response times and acceptance of firm aperiodic tasks. A simulation study underlines the effectiveness of the proposed approach.

Many industrial applications mandate the use of a time-triggered paradigm and consequently the use of off-line scheduling for reasons such as predictability, certification, cost, or product reuse. The construction of an off-line schedule requires complete knowledge about all temporal aspects of the application. The acquisition of this information may involve unacceptable cost or be impossible. Often, only partial information is available from the controlled environment. In this paper we present an algorithm to handle event-triggered sporadic tasks, i.e., with unknown arrival times, but known maximum arrival frequencies, in the context of distributed, off-line scheduled systems. Sporadic tasks are guaranteed during design time, allowing rescheduling or redesign in the failure case. At run-time, the sporadic tasks are scheduled dynamically, allowing the reuse of resources reserved for, but not consumed by the sporadic tasks. We provide an off-line schedulability test for sporadic tasks and apply the method to perform on-line scheduling on top of off-line schedules. Since the major part of preparations is performed off-line, the involved on-line mechanisms are simple. The on-line reuse of resources allows for high resource utilization.

Clusters of networked commercial, off the shelf (COTS) workstations are presently used for computation intensive tasks that were typically assigned to parallel computers in the past. However, it is hardly possible to predict the timing behavior of such systems or to give guarantees about execution times. We show how our SONiC (Shared Objects Net-interconnected Computer) system can control timing and partitioning of a workstation as a step towards a distributed real time system built from COTS components. SONiC provides a class based programming interface for creation of replicated shared objects of arbitrary, user defined sizes. Weak consistency protocols are employed to improve system performance. Our scheduling service ensures the requested interactive behavior of a workstation while simultaneously giving a specified number of CPU cycles to parallel tasks. Using offline scheduling methods we are able to implement real time guaranteed services on COTS workstations.

In this paper we present algorithms for the joint scheduling of periodic and aperiodic tasks in statically scheduled distributed real-time systems. Periodic tasks are precedence constrained, distributed, and communicating over the nodes of the systems. Both soft and hard aperiodic tasks are handled. After a static schedule has been created in a first step, the algorithms determine the amount and distribution of unused resources and leeway in it. These are then used to incorporate aperiodic tasks into the schedule by shifting the periodic tasks' execution, without violating their feasibility. Run-time mechanisms are simple and require only little memory. Processors and communication nodes can be utilized fully. The algorithm performs an optimal online guarantee algorithm for hard aperiodic tasks of O(N). An extensive simulation study exhibits very high guarantee ratios for various load and deadline scenarios, which underlines the efficiency of our method. 1 Introduction Processes co...

The systematic development of fault-tolerant real-time systems with guaranteed timeliness requires an appropriate system architecture and a rigorous design methodology. Those services of the architecture that help to simplify the work of the real-time programmer are described, taking the MARS architecture as an example. Programming in the large activities, i.e., the systematic derivation of task timing parameters from the requirements specification, are then addressed. Programming to meet a time budget is discussed, and the programming interface, the programming environment, and the testing and support tools are presented. The architecture and most of the tools have been implemented and can be demonstrated on a fault-tolerant prototype application.>

The authors propose a system architecture, MARS, which supports a strict separation of the issues of synchronization and timeliness, data transformation, and the dependability aspects (e.g., error detection, error handling, and redundancy management. The systematic development of fault-tolerant real-time systems with guaranteed timeliness requires an appropriate system architecture and a rigorous design methodology. The authors propose a system with strict separation of the issues of synchronization, dependability aspects, and data transformation. Dependability aspects are handled by the architecture. Synchronization and programming in the large are handled at the design level. The programmer only has to be concerned with a sequential program for which he has to meet a so-called time budget. The architecture and many tools have been implemented and can be demonstrated on a fault-tolerant prototype application.>