Emerging real-time applications increasingly rely on multicore embedded systems, where tasks must coordinate access to shared local and global resources. Such accesses are protected by critical sections and managed by resource-sharing protocols to ensure mutual exclusion and timing predictability. However, transient faults occurring inside critical sections can corrupt execution and propagate errors across tasks, while directly com- bining conventional locking with fault-tolerance mechanisms can significantly increase blocking. Recent fault-tolerant resource- sharing approaches improve recovery through parallel replica execution, but still suffer from sequential global access and coordination overhead. In previous work, we proposed the Lock- frEe Fault-Tolerant Resource Sharing (LEFT-RS) protocol, which improves fault-tolerant global resource access by allowing con- current critical-section execution. However, LEFT-RS enforces non-preemptive global resource access, which can cause excessive arrival blocking for high-priority tasks and limit schedulability. This paper introduces the CAFT-RS (Ceiling-based Access for Fault-Tolerant Resource Sharing) protocol, which applies a priority-ceiling mechanism to both local and global resource ac- cesses. CAFT-RS allows higher-priority tasks to preempt ongoing global accesses while preserving correctness through dedicated post-preemption rules. We develop a worst-case response-time analysis that accounts for both the reduction in arrival blocking and the additional preemption overhead. Extensive evaluation results show that CAFT-RS improves schedulability by up to 188.5% on average over LEFT-RS.

An IDK classifier is a learning-enabled software component that attempts to categorize each input provided to it into one of a fixed set of base classes, returning IDK (“I Don't Know”) if it is unable to do so to a required level of confidence. We consider the use of IDK classifiers in applications where it is natural to consider the base classes as comprising the leaves of a class hierarchy. Classification into higher levels of such a hierarchy may be easier than classification into base classes. Given a collection of different IDK classifiers that have been trained to classify at different levels of a class hierarchy, we derive algorithms for determining the order in which to use these classifiers so as to minimize the expected duration to successful classification (whilst guaranteeing to meet a hard deadline).

Emerging real-time applications have driven the transition to multicore embedded systems, where tasks must share resources due to functional demands and limited availability. These resources, whether local or global, are protected within critical sections to prevent race conditions, with locking protocols ensuring both exclusive access and timing requirements. However, transient faults occurring within critical sections can disrupt execution and propagate errors across multiple tasks. Conventional locking protocols fail to address such faults, and integrating traditional fault tolerance techniques often increases blocking. Recent approaches improve fault recovery through parallel replica execution; however, challenges remain due to sequential accessing, coordination overhead, and susceptibility to common-mode faults. In this paper, we propose a Lock-frEe Fault-Tolerant Resource Sharing (LEFT-RS) protocol for multicore real-time systems. LEFT-RS allows tasks to concurrently access and read global resources while entering their critical sections in parallel. Each task can complete its access earlier upon successful execution if other tasks experience faults, thereby improving the efficiency of resource usage. Our design also limits the overhead and enhances fault resilience. We present a comprehensive worst-case response time analysis to ensure timing guarantees. Extensive evaluation results demonstrate that our method significantly outperforms existing approaches, achieving up to an 84.5% improvement in schedulability on average.

Motivated by the performance demands and stringent timing requirements of safety-critical systems like avionics and autonomous vehicles, research has focused on providing timing guarantees for the scheduling of Directed Acyclic Graph (DAG) tasks in multicore systems. The structural complexity and timing anomalies make this problem challenging. Existing methods bound the Worst-Case Response Time (WCRT) of tasks through static analysis, but these bounds are complicated, difficult to validate, and often remain pessimistic for many scheduling scenarios. Runtime intervention can be effective in eliminating timing anomalies and providing timing guarantees; however, it is ineffective for anomaly-free scheduling scenarios, leads to non-work-conserving schedules, and incurs additional overhead. This paper proposes a hybrid approach to identify timing anomalies in DAG scheduling scenarios within a system, providing tighter WCRT solutions. The static analysis first offers a sufficient anomaly test to directly identify some anomaly-free DAG scheduling scenarios. Leveraging a wide range of scheduling data collected from the running system or its simulator, we then apply a machine learning approach to train a binary classification model, achieving an accuracy of 99.5%. Identifying the anomaly status enables the application of more precise WCRT bounds for different scheduling scenarios, leading to improved system performance. Specifically, we shorten the WCRT bounds for anomaly-free DAG scheduling by an average of up to 21.58%, with a maximum reduction of up to 55.47% compared to the state-of-the-art method.

This article presents a general formal framework for describing the relationship between a criticality-aware scheduler, a set of application jobs that are assigned different criticality levels, and an environment that generates both work and faults that the run-time system must control. The proposed formalism extends the rely-guarantee approach, which facilitates formal reasoning about the functional behaviour of concurrent systems, to address real-time properties. The exposition of the general framework is supplemented by a seven step approach that enables it to be instantiated to deliver the formal specification of any proposed mixed-criticality scheduling protocol. The expressive power of the approach is explored via a non-trivial instantiation.

An IDK classifier is a computational element that classifies an input provided to it into one of a set of predefined categories provided that it can achieve the necessary confidence level to do so; otherwise, it outputs “I Don't Know” (IDK). The concept of IDK classifier cascades has emerged as a strategy for striking a balance between the requirements of rapid response and precise classification in machine perception. Effective algorithms for constructing IDK classifier cascades have recently been developed. Here we extend these prior approaches by incorporating fault-tolerance: enabling classification that is concurrently rapid and accurate even in the event of some of the IDK classifiers exhibiting faulty behavior.

An IDK classifier is a software component that attempts to categorize each input provided to it into one of a fixed set of classes, returning IDK (“I Don’t Know”) if it is unable to do so with the required level of confidence. Several different IDK classifiers may be available for the same classification problem, each offering a different trade-off between execution duration and the likelihood of successful classification. Algorithms have been obtained for determining the order in which such classifiers should be called such that the expected duration to successfully classify an input is minimized-such an ordering of classifiers is called an IDK cascade. Cascade-synthesis algorithms make the assumption that each input to be classified is drawn from the same underlying distribution. We derive runtime algorithms that seek to further reduce the expected response time of IDK cascades upon input sequences for which successive inputs are ‘similar’ in the following sense: if a particular classifier successfully classifies some input it is likely to also be able to classify the next input. We evaluate the effectiveness of our algorithms in the context of the algorithms using predictions framework by showing that it significantly reduces expected response time when the desired similarity between successive inputs exists, while suffering only a minor increase in expected response time in the absence of such similarity. We describe how our algorithm is able to learn during runtime whether similarities exist (and if so, to what degree) amongst its inputs.

Abstract The reference point for developing any artefact is its specification; to develop software formally, a formal specification is required. For sequential programs, pre and post conditions (together with abstract objects) suffice; rely and guarantee conditions extend the scope of formal development approaches to tackle concurrency. In addition, real-time systems need ways of both requiring progress and relating that progress to some notion of time. This paper extends rely-guarantee ideas to cope with specifications of—and assumptions about—real-time schedulers. Furthermore it shows how the approach helps identify and specify fault-tolerance aspects of such schedulers by systematically challenging the assumptions.

In many real-time application domains, there are execution dependencies, such tasks may be formulated as multiple Directed Acyclic Graphs (DAGs) and scheduled with intra-task (i.e., intra-DAG) priority assignment. The worst-case completion time of a DAG must be bounded and schedulability analysis must be conducted during the design phase to estimate the required hardware resources. Typical examples include automotive systems and Ultra-Reliable Low Latency Communications (URLLC), which is the “to-business” protocol in 5G technologies, deployed in industrial automation for instance. To bound the execution time of multiple DAGs, there are two key factors to analyze: the intra-task interference for a single DAG and the inter-task interference between DAGs. While extensive efforts have been invested, the existing methods either still contain a large degree of pessimism or are even erroneous due to errors in the derived analysis. In this paper, we first provide an indepth analysis of the limitation and defects of the existing methods. Inspired by these observations, we construct novel response time analysis for multiple DAG tasks with arbitrary intra-task priority assignment. Our analysis precisely accounts for both the intra- and inter-task interference by fully exploring the node parallelism in each DAG as well as between DAGs. Extensive experimental results show that the proposed analysis obtains tighter bounds and improves the system scheduability by at least 300 % compared to state-of-the-art approaches. This improvement is even larger when the scheduling pressure is relatively high, up to 100 % versus 0 % in many cases. This work notably advances the use of response time analysis in industry. Practitioners have to resort to either potentially unsafe measurement results or significant resource over-provisioning when precise analysis is unavailable.

Abstract This paper introduces and evaluates a general construct for trading off accuracy and overall execution duration in classification-based machine perception problems—namely, the generalized IDK classifier cascade . The aim is to select the optimal sequence of classifiers required to minimize the expected (i.e. average) execution duration needed to achieve successful classification, subject to a constraint on quality, and optionally a latency constraint on the worst-case execution duration. An IDK classifier is a software component that attempts to categorize each input provided to it into one of a fixed set of classes, returning “I Don’t Know” (IDK) if it is unable to do so with the required level of confidence. An ensemble of several different IDK classifiers may be available for the same classification problem, offering different trade-offs between effectiveness (i.e. the probability of successful classification) and timeliness (i.e. execution duration). A model for representing such characteristics is defined, and a method is proposed for determining the values of the model parameters for a given ensemble of IDK classifiers. Optimal algorithms are developed for sequentially ordering IDK classifiers into an IDK cascade, such that the expected duration to successfully classify an input is minimized, optionally subject to a latency constraint on the worst-case overall execution duration of the IDK cascade. The entire methodology is applied to two real-world case studies. In contrast to prior work, the methodology developed in this paper caters for arbitrary dependences between the probabilities of successful classification for different IDK classifiers. Effective practical solutions are developed considering both single and multiple processors.

Abstract A classifier is a software component, often based on Deep Learning, that categorizes each input provided to it into one of a fixed set of classes. An IDK classifier may additionally output “I Don’t Know” (IDK) for certain inputs. Multiple distinct IDK classifiers may be available for the same classification problem, offering different trade-offs between effectiveness, i.e. the probability of successful classification, and efficiency, i.e. execution time. Optimal offline algorithms are proposed for sequentially ordering IDK classifiers such that the expected duration to successfully classify an input is minimized, optionally subject to a hard deadline on the maximum time permitted for classification. Solutions are provided considering independent and dependent relationships between pairs of classifiers, as well as a mix of the two.

Conventional mixed-criticality systems (MCS)s are designed to terminate the execution of less critical tasks in exceptional situations so that the timing properties of more critical tasks can be preserved. Such a strategy can be controversial and has proven difficult to implement in practice, as it can lead to hazards and reduced functionality due to the absence of the discarded tasks. To mitigate this issue, the imprecise mixed-critically system model (IMCS) has been proposed. In such a model, instead of completely dropping less-critical tasks, these tasks are executed as much as possible through the use of decreased computation precision. Although IMCS could effectively improve the survivability of the less-critical tasks, it also introduces three key drawbacks - run-time computation errors, real-time performance degradation, and lack of flexibility. In this paper, we present a novel IMCS framework, which can (i) mitigate the computation errors caused by imprecise computation; (ii) achieve real-time performance near to that of a conventional MCS; (iii) enhance system-level throughput; and (iv) provide flexibility for run-time configuration. We describe the design details ofHIART-MCS, and then present the corresponding theoretical analysis and optimisation method for its run-time configuration. Finally,HIART-MCS is evaluated against other MCS frameworks using a variety of experimental metrics.

An IDK classifier is a computing component that categorizes inputs into one of a number of classes, if it is able to do so with the required level of confidence, otherwise it returns “I Don’t Know” (IDK). IDK classifier cascades have been proposed as a way of balancing the needs for fast response and high accuracy in classification-based machine perception. Efficient algorithms for the synthesis of IDK classifier cascades have been derived; however, the responsiveness of these cascades is highly dependent on the accuracy of predictions regarding the run-time behavior of the classifiers from which they are built. Accurate predictions of such run-time behavior is difficult to obtain for many of the classifiers used for perception. By applying the algorithms using predictions framework, we propose efficient algorithms for the synthesis of IDK classifier cascades that are robust to inaccurate predictions in the following sense: the IDK classifier cascades synthesized by our algorithms have short expected execution durations when the predictions are accurate, and these expected durations increase only within specified bounds when the predictions are inaccurate.

This article considers the use of routerless networks-on-chip as an alternative on-chip interconnect for multi-processor systems requiring hard real-time guarantees for inter-processor communication. It presents a novel analytical framework that can provide latency upper bounds to real-time packet flows sent over routerless networks-on-chip, and it uses that framework to evaluate the ability of such networks to provide real-time guarantees. Extensive comparative analysis is provided, considering different architectures for routerless networks and a state-of-the-art wormhole network based on priority-preemptive routers as a baseline.

In this paper, we use the term “Analysis-Runtime Co-design” to describe the technique of modifying the runtime protocol of a scheduling scheme to closely match the analysis derived for it. Carefully designed modifications to the runtime protocol make the schedulability analysis for the scheme less pessimistic, while the schedulability guarantee afforded to any given application remains intact. Such modifications to the runtime protocol can result in significant benefits with respect to other important metrics. An enhanced runtime protocol is designed for the Adaptive Mixed-Criticality (AMC) scheduling scheme. This protocol retains the same analysis, while ensuring that in the event of high-criticality behavior, the system degrades less often and remains degraded for a shorter time, resulting in far fewer low-criticality jobs that either miss their deadlines or are not executed.

Driven by applications such as autonomous vehicles, spacecrafts, robotics, and industrial automation, real-time systems are required to implement ever more complex functionalities with high performance, while maintaining conventional timing predictability, reliability, and cost efficiency. Necessarily, large-scale resource sharing on multiprocessor architectures has to be deployed. Unfortunately, existing protocols that manage shared resources and bound blocking delay have not considered reliability, i.e. how to handle faults. Contention over shared resources may be seriously aggravated by re-executions that are essential to satisfy a system’s reliability requirements. Hence, there exists a significant barrier to applying resource sharing in the mission-critical sector. This paper fills that gap between reliability and resource sharing. Focusing on mixed-criticality systems (MCS), which widely exist in practice and make the problem more challenging, we propose a fault-tolerance solution which includes the first fault-tolerance multiprocessor resource sharing protocol (namely MSRP-FT) and a system execution model that supports the application of MSRP-FT in MCS. Our aim is to minimize blocking time while satisfying reliability requirements. A schedulability analysis is reported which can guarantee that timing constraints are respected. Compared to the state-of-the-art method, developed for fault-tolerant MCS without resource sharing, we improve the system schedulability by an average of $ 1.28\times$ in stable modes and $ 1.1\times$ during the mode switch.

While academia favours general research that is applicable to a large class of systems, this paper highlights the necessity of research into specific scenarios and aims to increase its acceptance in the real-time systems community. We argue that such research is not only motivated by greater applicability to industry, but that specialization can also provide valuable information from a purely academic perspective. In addition, the trade-offs between generalization and specialization are examined, considering not only theoretical performance, but also the impact on essential non-functional properties that are important for industry, namely composability, robustness, extensibility, and parametric simplicity.

Development of dependable multi-/many-core systems requires assurance that the system is operable in a range of conditions, subjected to both functional and non-functional requirements. To achieve this, tools need to be implemented that can enable exploration of design options and be able to detect deficiencies earlier to avoid costly system re-design. In this work we discuss the challenges of design of multi-core realtime systems with timing assurance and discuss what are the requirements for modelling, testing and analysis tools. Digital Twin-based predictive modelling and fast design space evaluation are studied that work toward addressing these challenges.

Driven by industry demand, there is an increasing need to develop real-time multiprocessor systems which contain shared resources. The Multiprocessor Stack Resource Policy (MSRP) and Multiprocessor resource sharing Protocol (MrsP) are two major protocols that manage access to shared resources. Both of them can be applied to Fixed-Priority Preemptive Scheduling (FPPS), which is enforced by most commercial real-time systems regulations, and which requires task priorities to be assigned before deployment. Along with MSRP and MrsP, there exist two forms of schedulability tests that bound the worst-case blocking time due to resource accesses: the traditional ones being more widely adopted and the more recently developed holistic ones which deliver tighter analysis. On uniprocessor systems, there are several well-established optimal priority assignment algorithms. Unfortunately, on multiprocessor systems with shared resources, the issue of priority assignment has not been adequately understood. In this article, we investigate three mainstream priority assignment algorithms-Deadline Monotonic Priority Ordering (DMPO), Audsley's Optimal Priority Assignment (OPA), and Robust Priority Assignment (RPA), in the context of partitioned multiprocessor systems with shared resources. Our contributions are multifold: First, we prove that DMPO is optimal with the traditional schedulability tests. Second, two counter examples are given as evidence that DMPO is not optimal with the tighter holistic schedulability tests. Third, we then analyze the pessimism arising from the adoption of OPA and RPA with the holistic tests. Lastly, we propose a Slack-based Priority Ordering (SPO) algorithm that minimises such pessimism, and has polynomial time complexity. Comprehensive experiments show that SPO outperforms (i.e., results in a larger number of schedulable systems) DMPO, OPA, and RPA in general with the holistic schedulability tests, by up to 15 percent. With the theoretical contributions, this paper is a useful guide to priority assignment in real-time partitioned multiprocessor systems with shared resources.

Autonomous systems are increasingly using components that incorporate machine learning and other AI-based techniques in order to achieve improved performance. We address the problem of assuring correctness in safety-critical systems that use such components. We investigate an approach which formulates the problem as one in which performance is an objective function to be optimized while safety is a hard constraint that must be satisfied. We then apply heuristics and algorithmic techniques from optimization theory in order to solve the resulting constrained optimization problem.

Autonomous systems increasingly use components that incorporate machine learning and other AI-based techniques in order to achieve improved performance. The problem of assuring correctness in safety-critical systems that use such components is considered. A model is proposed in which components are characterized according to both their worst-case and their typical behaviors; it is argued that while safety must be assured under all circumstances, it is reasonable to be concerned with providing a high degree of performance for typical behaviors only. The problem of assuring safety while providing such improved performance is formulated as an optimization problem in which performance under typical circumstances is the objective function to be optimized while safety is a hard constraint that must be satisfied. Algorithmic techniques are applied to derive an optimal solution to this optimization problem. This optimal solution is compared with an alternative approach that optimizes for performance under worst-case conditions, as well as some common-sense heuristics, via simulation experiments on synthetically-generated workloads.

The recently uncovered problem of multi-point progressive blocking (MPB) has significantly increased the complexity of schedulability analysis of priority-preemptive wormhole networks-on-chip. While state-of-the-art analysis is currently deemed safe, there is still significant inherent pessimism when it comes to considering backpressure issues caused by downstream indirect interference. In this paper, we attempt to simplify the problem by considering a novel flow control protocol that can avoid backpressure issues, enabling simpler schedulability analysis approaches to be used. Rather than construct the analysis to fit the protocol, we modify the protocol so that effective analysis applies. We describe the changes to a baseline wormhole router in order to implement the proposed protocol, and comment on the impact on hardware overheads. We also examine the number of routers that actually require these changes. Comparative analysis of FPGA implementations show that the hardware overheads of the proposed NoC router are comparable or lower than those of the baseline, while analytical comparison shows that the proposed approach can guarantee schedulability in up to 77% more cases.

With ever more complex functionalities being implemented in emerging real-time applications, multiprocessor systems are demanded for high performance, and directed acyclic graphs (DAGs) are used to model functional dependencies. In this work, we study a single periodic non-preemptive DAG running on a homogeneous multiprocessor platform, which is a common setup in many domains, such as automotive, robotics, and industrial automation. Aiming to reduce the makespan of the DAG and provide a tight yet safe bound, our contributions involve the exploitation of node-level parallelism and inter-node dependency, which are the two key factors of a DAG topology. First, we introduce a concurrent provider and consumer (CPC) model that precisely captures the above two factors, and can be recursively applied when parsing a DAG. Building upon CPC, we propose a novel scheduling method focused on reducing the makespan that orders the nodes in the following sequence: (i) the critical path, (ii) early predecessor paths of the critical path, and (iii) longer paths. Secondly, new response time analysis is presented, which provides a generic bound for any execution order of the non-critical nodes and a specific (tighter) bound for a fixed such order. Comprehensive evaluation demonstrates that our scheduling approach and analysis outperforms the state-of-the-art methods.

This paper provides analysis of the Adaptive Mixed Criticality (AMC) scheduling scheme for mixed-criticality systems that include tasks with arbitrary deadlines and semi-clairvoyant behavior. An arbitrary deadline task is one that can have a deadline that may be greater than its period. A semi-clairvoyant task is one that upon arrival of each job, reveals which of its two WCET parameters will be respected. This enables an earlier switch to be made from the normal mode of operation to the abnormal mode. The previously published schedulability test AMC-max is modified to cater for both of these extensions. Evaluation shows that there is a significant improvement in schedulability for semi-clairvoyant tasks over non-clairvoyant, and for arbitrary-deadline tasks over considering those deadlines as being constrained by the task's period.

Abstract Cyber physical systems (CPS) exist in a physical environment and comprise both physical components and a control program. Physical components are inherently liable to failure and yet an overall CPS is required to operate safely, reliably and cost effectively. This paper proposes a framework for deriving the specification of the software control component of a CPS from an understanding of the behaviour required of the overall system in its physical environment. The two key elements of this framework are (i) an extension to the use of rely/guarantee conditions to allow specifications to be obtained systematically from requirements (as expressed in terms of the required behaviour in the environment) and nested assumptions (about the physical components of the CPS); and (ii) the use of time bands to record the temporal properties required of the CPS at a number of different granularities. The key contribution is in combining these ideas; using time bands overcomes a significant drawback in earlier work. The paper also addresses the means by which the reliability of a CPS can be addressed by challenging each rely condition in the derived specification and, where appropriate, improve robustness and/or define weaker guarantees that can be delivered with respect to the corresponding weaker rely conditions.

Long-lived, non-stop cyber-physical systems (CPS) are subject to evolutionary changes that can undermine the guarantees of schedulability that were verified at the time of deployment. At the same time, knowledge gleamed from extended periods of execution can be exploited to reduce the uncertainties that were inevitably presented in the system models that are used to define the temporal behaviours of the control tasks. In this paper we utilise this knowledge and present an adaptation method that actively extends the period of control tasks at run-time based on historical measurements. This can lead to lower power consumption or to the accommodation of increased computation resource demands from other components of the CPS. The method relies on online monitoring and model-based prediction to degrade control performance while having a minimal and acceptable impact on ongoing operations. Cloud-based computing is used to facilitate decision making and offload the local computation. We evaluate the effectiveness of the proposed method through control-scheduling co-simulation.

This article describes the motivation, design, analysis, and configuration of the criticality-aware multi-hop wireless communication protocol AirTight. Wireless communication has become a crucial part of the infrastructure of many cyber-physical applications. Many of these applications are real-time and also mixed-criticality, in that they have components/subsystems with different consequences of failure. Wireless communication is inevitably subject to levels of external interference. In this article, we represent this interference using a criticality-aware fault model; for each level of temporal interference in the fault model, we guarantee the timing behaviour of the protocol (i.e., we guarantee that packet deadlines are satisfied for certain levels of criticality). Although a new protocol, AirTight is built upon existing standards such as IEEE 802.15.4. A prototype implementation and protocol-accurate simulator have been produced. This article develops a series of schedulability analysis techniques for single-channel and multichannel wireless Cyber-Physical Systems (CPS). Heuristics are specified and evaluated as the starting point of design space exploration. Genetic algorithms are then defined and evaluated to assess their performance in developing schedule tables incorporating multichannel allocations in these systems.

Many applications in emerging scenarios, such as autonomous vehicles, intelligent robots, and industrial automation, are safety-critical with strict timing requirements. However, the development of real-time systems is error prone and highly dependent on sophisticated domain expertise, making it a costly process. This article utilises the principles of model-driven engineering (MDE) and proposes two methodologies to automate the development of real-time Java applications. The first one automatically converts standard time-sharing Java applications to real-time Java applications, using a series of transformations. It is in line with the observed industrial trend, such as for the big data technology, of redeveloping existing software without the real-time notion to realise the real-time features. The second one allows users to automatically generate real-time Java application templates with a lightweight modelling language, which can be used to define the real-time properties—essentially a synthesis process. This article opens up a new research direction on development automation of real-time programming languages and inspires many research questions that can be jointly investigated by the embedded systems, programming languages as well as MDE communities.

Mixed-criticality scheduling theory (MCSh) was developed to allow for more resource-efficient implementation of systems comprising different components that need to have their correctness validated at different levels of assurance. As originally defined, MCSh deals exclusively with pre-runtime verification of such systems; hence many mixed-criticality scheduling algorithms that have been developed tend to exhibit rather poor survivability characteristics during run-time. (E.g., MCSh allows for less-important (“Lo-criticality”) workloads to be completely discarded in the event that run-time behavior is not compliant with the assumptions under which the correctness of the LO-criticality workload should be verified.) Here we seek to extend MCSh to incorporate survivability considerations, by proposing quantitative metrics for the robustness and resilience of mixed-criticality scheduling algorithms. Such metrics allow us to make quantitative assertions regarding the survivability characteristics of mixed-criticality scheduling algorithms, and to compare different algorithms from the perspective of their survivability. We propose that MCSh seek to develop scheduling algorithms that possess superior survivability characteristics, thereby obtaining algorithms with better survivability properties than current ones (which, since they have been developed within a survivability-agnostic framework, tend to focus exclusively on pre-runtime verification and ignore survivability issues entirely).

Real-time systems are receiving increasing attention with the emerging application scenarios that are safety-critical, complex in functionality, high on timing-related performance requirements, and cost-sensitive, such as autonomous vehicles. Development of real-time systems is error-prone and highly dependent on the sophisticated domain expertise, making it a costly process. There is a trend of the existing software without the real-time notion being re-developed to realise real-time features, e.g., in the big data technology. This paper utilises the principles of model-driven engineering (MDE) and proposes the first methodology that automatically converts standard time-sharing Java applications to real-time Java applications. It opens up a new research direction on development automation of real-time programming languages and inspires many research questions that can be jointly investigated by the embedded systems, programming languages as well as MDE communities.

In the Vestal model of mixed-criticality systems, jobs are characterized by multiple different estimates of their actual, but unknown, worst-case execution time (WCET) parameters. Prior work on mixed-criticality scheduling theory assumes that the execution duration of a job is only revealed by actually executing the job through to completion. We consider a different *semi-clairvoyant* model here, in which it is assumed that upon arrival a job reveals which of its WCET parameters it will respect. We identify circumstances under which this is a reasonable model, and design and evaluate scheduling algorithms appropriate for this model. We show that such semi-clairvoyance yields a significant quantifiable benefit over non-clairvoyance, in terms of both the complexity of schedulability analysis and the speedup needed to ensure schedulability.

For the power and space sensitive systems such as automotive/avionic computers, an important trend is isolating and integrating multiple Operating Systems (OSs) in one physical platform, which is named as hybrid multi-OS system. Generally, in a commonly used hybrid dual-OS system, a RTOS (realtime operating system) and a GPOS (general-purpose operating system) are integrated. Cooperation (among the OSs) is a vital feature of a hybrid system to obtain the necessary capabilities, and inter-OS communication is the key. However, it is difficult to satisfy the real-time metrics of inter-OS communication required by the RTOS, due to the uncertainty in communication maintenance and the time-sharing policy of the GPOS. This paper aims to build a time predictable and secure RPC mechanism (i.e., the primary and critical communication unit in a hybrid multi-OS system). Afterwards, a real-time RPC scheme (termed RTRGRPC) is proposed, which is applied to a ready-built TrustZonebased hybrid dual-OS system (i.e., TZDKS). RTRG-RPC achieves accurate time control through three mechanisms: SGI message transforming, interrupt handler RPC servicing, and priorityswapping. Evaluations show that RTRG-RPC can achieve realtime predictability and can also reduce priority inversion.

The emerging scenarios of cyber-physical systems (CPS), such as autonomous vehicles, require implementing complex functionality with limited resources, as well as high performances. This paper considers a common setup in which multiple control and non-control tasks share one processor, and proposes a dual-mode strategy. The control task switches between two sampling periods when rejecting (coping with) a disturbance. We create an optimisation framework looking for the switching sampling periods and time instants that maximise the control performance (indexed by settling time) and resource efficiency (indexed by the number of tasks that are schedulable on the processor). The latter objective is enabled with schedulability analysis tailored for the dual-mode model. Experimental results show that (i) given a set of tasks, the proposed strategy improves the control performances whilst retaining schedulability; and (ii) given requirements on the control performances, the proposed strategy is able to schedule more tasks.

This paper aims to reduce the pessimism of the analysis of the multi-point progressive blocking (MPB) problem in real-time priority-preemptive wormhole networks-on-chip. It shows that the amount of buffering on each network node can influence the worst-case interference that packets can suffer along their routes, and it proposes a novel analytical model that can quantify such interference as a function of the buffer size. It shows that, perhaps counter-intuitively, smaller buffers can result in lower upper-bounds on interference and thus improved schedulability. Didactic examples and large-scale experiments provide evidence of the strength of the proposed approach.

This paper describes four impact case studies where real-time systems research has been successfully transferred into industrial practice. In three cases, the technology created was translated into a viable commercial product via a start-up company. This technology transfer led to the creation and sustaining of a large number of high technology jobs over a 20 year period. The final case study involved the direct transfer of research results into an engineering company. Taken together, all four case studies have led to significant advances in automotive electronics and avionics, providing substantial returns on investment for the companies using the technology.

A system is said to be resilient if slight deviations from expected behavior during run-time does not lead to catastrophic degradation of performance: minor deviations should result in no more than minor performance degradation. In mixed-criticality systems, such degradation should additionally be criticality-cognizant. The applicability of control theory is explored for the design of resilient run-time scheduling algorithms for mixed-criticality systems. Recent results in control theory have shown how appropriately designed controllers can provide guaranteed service to hard-real-time servers; this prior work is extended to allow for such guarantees to be made concurrently to multiple criticality-cognizant servers. The applicability of this approach is explored via several experimental simulations in a dual-criticality setting. These experiments demonstrate that our control-based run-time schedulers can be synthesized in such a manner that bounded deviations from expected behavior result in the high-criticality server suffering no performance degradation and the lower-criticality one, bounded performance degradation.

In mixed criticality systems, it is vital to ensure that there is sufficient separation between tasks of LO- and HI-criticality applications, so that the behavior or mis-behavior of the former cannot affect the functional or timing correctness of the latter. To ensure appropriate spatial isolation, the memory address spaces and cache use by LO- and HI-criticality tasks must be distinct. A consequence of this separation is that the cost of switching between tasks of the same criticality can be small, whereas the cost of context switching between tasks of different criticality levels can be much larger. In this paper, we focus on integrating the differing context switch costs into fixed priority preemptive scheduling, and the two mixed criticality scheduling schemes based on it: SMC and AMC. We derive simple, refined, and multi-set analyses for each scheme. Further, we show that the refined and multi-set analyses are not compatible with Audsley's Optimal Priority Assignment algorithm, we therefore propose a heuristic priority assignment policy aimed at reducing the number of high cost context switches. Our evaluation is grounded in measurements of context switch times (save and restore costs) from a prototype implementation of an explicitly managed cache on an FPGA. The evaluation shows the effectiveness of the derived analyses and the proposed priority assignment policy.

This paper describes the motivation, design, analysis and implementation of a new protocol for critical wireless communication called AirTight. Wireless communication has become a crucial part of the infrastructure of many cyber-physical applications. Many of these applications are real-time and also mixed-criticality, in that they have components/subsystems with different consequences of failure. Wireless communication is inevitably subject to levels of external interference. In this paper we represent this interference using a criticality-aware fault model; for each level of interference in the fault model we guarantee the timing behaviour of the protocol (i.e. we guarantee that packet deadlines are satisfied for certainly levels of criticality). Although a new protocol, AirTight is built upon existing standards such as IEEE 802.15.4. A prototype implementation and protocol-accurate simulator, which are also built upon existing technologies, demonstrate the effectiveness and functionality of the protocol.

Many mixed-criticality systems are composed of a RTOS (Real-Time Operating System) and a GPOS (General Purpose Operating System), and we define them as mixed-time-sensitive systems. Complexity, isolation, real-time latency, and overhead are the main metrics to evaluate such a mixed-time-sensitive system (MTSS). These metrics may conflict with each other, so it is difficult for them to be consistently optimized. Most existing implementations only optimize part of the above metrics but not all. As the first contribution, this paper provides a detailed analysis of performance influencing factors which are exerted by various runtime mechanisms of existing MTSSs. We figure out the difference in performance across system designs, including task switch, memory management, interrupt handling, and resource isolation. We propose the philosophy of utilizing TrustZone characteristics to optimize various mechanisms in MTSS. The second contribution is to propose a TrustZone-based solution - termed TZDKS - for MTSS. Appropriate utilization of TrustZone extensions helps TZDKS to implement (i) virtualization environment for GPOS and RTOS, (ii) high efficient task switch, memory access, interrupt handling and device access which are verified by experiments. Therefore, TZDKS can achieve a full-scale balance amongst aforementioned metrics.

Certification authorities require correctness and survivability. In the temporal domain this requires a convincing argument that all deadlines will be met under error free conditions, and that when certain defined errors occur the behaviour of the system is still predictable and safe. This means that occasional execution-time overruns should be tolerated and where more severe errors occur levels of graceful degradation should be supported. With mixed-criticality systems, fault tolerance must be criticality aware, i.e. some tasks should degrade less than others. In this paper a quantitative notion of robustness is defined, and it is shown how fixed priority-based task scheduling can be structured to maximise the likelihood of a system remaining fail operational or fail robust (the latter implying that an occasional job may be skipped if all other deadlines are met). Analysis is developed for fail operational and fail robust behaviour, optimal priority ordering is addressed and an experimental evaluation is described. Overall, the approach presented allows robustness to be balanced against schedulability. A designer would thus be able to explore the design space so defined.

In this paper we consider a spin-based multi-processor locking protocol, named the Multiprocessor resource sharing Protocol (MrsP). MrsP adopts a helping-mechanism where the preempted resource holder can migrate. The original schedulability analysis of MrsP carries considerable pessimism as it has been developed assuming limited knowledge of the resource usage for each remote task. In this paper new MrsP schedulability analysis is developed that takes into account such knowledge to provide a less pessimistic analysis than that of the original analysis. Our experiments show that, theoretically, the new analysis offers better (at least identical) schedulability than the FIFO non-preemptive protocol, and can outperform FIFO preemptive spin locks under systems with either intensive resource contention or long critical sections. The paper also develops analysis to include the overhead of MrsP's helping mechanism. Although MrsP's helping mechanism theoretically increases schedulability, our evaluation shows that this increase may be negated when the overheads of migrations are taken into account. To mitigate this, we have modified the MrsP protocol to introduce a short non-preemptive section following migration. Our experiments demonstrate that with migration cost, MrsP may not be favourable for short critical sections but provides a better schedulability than other FIFO spin-based protocols when long critical sections are applied.

The AMC-IA mixed-criticality scheduling analysis was proposed as an improvement to the AMC-MAX adaptive mixed-criticality scheduling analysis. However, we have identified several necessary corrections to the AMC-IA analysis. In this article, we motivate and describe those corrections, and discuss and illustrate why the corrected AMC-IA analysis cannot be shown to outperform AMC-MAX.

To move mixed criticality research into industrial practice requires models whose run-time behaviour is acceptable to systems engineers. Certain aspects of current models, such as abandoning lower criticality tasks when certain situations arise, do not give the robustness required in application domains such as the automotive and aerospace industries. In this paper a new bailout protocol is developed that still guarantees high criticality software but minimises the negative impact on lower criticality software via a timely return to normal operation. We show how the bailout protocol can be integrated with existing techniques, utilising both offline slack and online gain-time to further improve performance. Static analysis is provided for schedulability guarantees, while scenario-based evaluation via simulation is used to explore the effectiveness of the protocol.

Many reactive systems must be designed and analyzed prior to deployment in the presence of considerable epistemic uncertainty: the precise nature of the external environment the system will encounter, as well as the run-time behavior of the platform upon which it is implemented, cannot be predicted with complete certainty prior to deployment. The widely-studied Vestal model for mixed-criticality workloads addresses uncertainties in estimating the worst-case execution time (WCET) of real-time code. Different estimations, at different levels of assurance, are made about these WCET values, it is required that all functionalities execute correctly if the less conservative assumptions hold, while only the more critical functionalities are required to execute correctly in the (presumably less likely) event that the less conservative assumptions fail to hold but the more conservative assumptions do. A generalization of the Vestal model is considered here, in which a degraded (but non-zero) level of service is required for the less critical functionalities even in the event of only the more conservative assumptions holding. An algorithm is derived for scheduling dual-criticality implicit-deadline sporadic task systems specified in this more general model upon preemptive uniprocessor platforms, and proved to be speedup-optimal.

To move mixed criticality research into industrial practice requires models whose run-time behaviour is acceptable to systems engineers. Certain aspects of current models, such as abandoning lower criticality tasks when certain situations arise, do not give the robustness required in application domains such as the automotive and aerospace industries. In this paper a new bailout protocol is developed that still guarantees high criticality tasks but minimises the negative impact on lower criticality tasks via a timely return to normal operation. We show how the bailout protocol can be integrated with existing techniques, utilising offline slack to further improve performance. Static analysis is provided for the strong schedulability guarantees, while scenario based evaluation via simulation is used to explore the effectiveness of the protocol.

Historically safety-critical real-time systems have been implemented using a cyclic executive (CE). Here a series of frames (minor cycles) are executed in sequence. Once the series is complete the sequence is repeated. The duration of the full sequence is often known as the major cycle. Within each frame, units of computation (jobs) are executed, again in sequence. Although there are a number of drawbacks to the use of CEs they have the advantage of being fully deterministic and efficiently implemented. For multi-core platforms, running a set of frames on each core is an obvious extension to the single core approach. Here there is advantage in coordinating the execution of the cores so that frames are released at the same time across all cores. For mixed criticality systems, the requirement for separation would imply that, at any time, code of the same criticality must execute on all cores. In this paper we consider how this requirement can be met and the performance, in terms of schedulability, it delivers. We consider partitioned and globally allocated work. For partitioned systems an allocation scheme is developed. For globally scheduled schemes we develop a polynomial-time sufficient schedulability test that determines whether a given mixed-criticality system is schedulable, and constructs a schedule if it is.

Mixed-criticality applications executing over a multiprocessor platform based on Network-on-Chip (NoC) exchange packets of different criticality levels through the same communication infrastructure, and transmission of a packet has potential impact over the latency of all the others. This paper presents NoC architectural improvements to output port arbitration and mode change signalling. The first aim is to improve the average latency of low-criticality packets following a mode change by allowing NoC arbiters to service them during cycles in which no high-criticality flows can be transmitted. The second aim is to reduce the worst-case latency of high-criticality packets transmitted by the NoC. The former objective improves the system's responsiveness, while the latter contributes to increased resource efficiency. The achieved improvements are evaluated, respectively, by cycle-accurate simulation and by schedulability analysis, showing full delivery of low-criticality packets following a criticality change, and achieving full schedulability in 8.2% more flow sets than the state of the art.

This paper extends the Abort-and-Restart (AR) model by defining the Deferred Abort (DA) model, Both models support Priority-based Functional Reactive Programming (P-FRP). Higher priority tasks sometimes do not need an immediate abort to meet their deadlines. The technique of deferred pre-emption is employed for the DA model, which provides better schedulability and dominates the non-pre-emptive model. In this paper, we also provide a final non-pre-emptive region assignment, and a heuristic priority assignment scheme. In the experimental evaluation, the schedulability of the DA model demonstrated a clear improvement compared to the AR model.

Most resource control protocols such as IPCP (Immediate Priority Ceiling Protocol) require a kernel system call to implement the necessary control over any shared data. This call can be expensive, involving a potentially slow switch from CPU user-mode to kernel-mode (and back). In this paper we look at two anticipatory schemes (IPCP and DFP - Deadline Floor Protocol) and show how they can be implemented with the minimum number of calls on the kernel. Specifically, no kernel calls are needed when there is no contention, and only one when there is. A standard implementation would need two such calls. The protocols developed are verified by the use of model checking. A prototype implementation is described for POSIX pThreads (thus opening up improvements to a range of programming approaches). Experimental results demonstrate the effectiveness of the scheme, showing average case savings of 86%.

Earliest Deadline First (EDF) is the most widely studied optimal dynamic scheduling algorithm for uniprocessor real-time systems. For realistic programs, tasks must be allowed to exchange data and use other forms of resources that must be accessed under mutual exclusion. With EDF scheduled systems, access to such resources is usually controlled by the use of Baker’s Stack Resource Protocol (SRP). In this paper we propose an alternative scheme based on deadline inheritance. Shared resources are assigned a relative deadline equal to the minimum (floor) of the relative deadlines of all tasks that use the resource. On entry to the resource a task’s current absolute deadline is subject to an immediately reduction to reflect the resource’s deadline floor. On exit the original deadline for the task is restored. We show that the worst-case behaviour of the new protocol (termed DFP—Deadline Floor inheritance Protocol) is the same as SRP. Indeed it leads to the same blocking term in the scheduling analysis. We argue that the new scheme is however more intuitive, removes the need to support preemption levels and we demonstrate that it can be implemented more efficiently.

This article introduces schedulability analysis for Global Fixed Priority Scheduling with Deferred Preemption (gFPDS) for homogeneous multiprocessor systems. gFPDS is a superset of Global Fixed Priority Preemptive Scheduling (gFPPS) and Global Fixed Priority Nonpreemptive Scheduling (gFPNS). We show how schedulability can be improved using gFPDS via appropriate choice of priority assignment and final nonpreemptive region lengths, and provide algorithms that optimize schedulability in this way. Via an experimental evaluation we compare the performance of multiprocessor scheduling using global approaches: gFPDS, gFPPS, and gFPNS, and also partitioned approaches employing FPDS, FPPS, and FPNS on each processor.

Adaptive Mixed Criticality (AMC) scheduling has previously been shown to be the most effective fixed priority approach for scheduling mixed criticality systems, while the idea of final non-preemptive regions has been shown to improve the schedulability of systems with a single criticality level. In this paper, we combine AMC with the concept of non-preemptive regions by making the final part of each task's execution at each criticality level non-preemptive. We derive schedulability analysis for this approach, and provide an effective algorithm for choosing each task's priority and the durations of its non-preemptive regions. Evaluations illustrate the benefits of this approach in terms of increased schedulability.

Lack of scalability and difficulties in predicting the temporal behaviour of bus-based architectures has lead to the development of Network-on-Chip (NoC) protocols that provide a schedulable resource for moving data across multi-core platforms. Wormhole switching and credit-based flow control protocols have been used to support flit-level priority-preemptive link arbitration in NoCs, which leads to analysable temporal behaviour. In this paper we develop a new protocol (WPMC), based on the same family of protocols, that gives full support to mixed-criticality on-chip communications. WPMC is defined to give adequate partitioning between criticality levels, and to use resources efficiently. Analysis is developed and implementation aspects are considered. A cycle accurate simulator is used for scenario-based verification, and the effectiveness of the protocol and its scheduling model is evaluated via message-set generation.

An increasingly important trend in the design of real-time and embedded systems is the integration of components with different levels of criticality onto a common hardware platform. Where the platform incorporates a communication media it is necessary for that media to be able to safely and efficiently transfer messages of different criticality levels. In this paper we consider the Controller Area Network (CAN), and define mixed criticality protocols that could form the basis of a Trusted Network Component for CAN. Sufficient response-time analysis is derived for these protocols and an optimal priority assignment scheme is provided. Evaluations illustrate the benefits of the schemes.

Lock-based resource sharing protocols for single processor systems are well understood and supported in programming languages and in Real-Time Operating Systems. In contrast, multiprocessor resource sharing protocols are less well developed with no agreed best practice. In this paper we propose a new multiprocessor variant of a protocol based on the single processor priority ceiling protocol. The distinctive nature of the new protocol is that tasks waiting to gain access to a resource must service the resource on behalf of other tasks that are waiting for the same resource (but have been preempted). The form of the protocol is motivated by the desire to link the protocol with effective schedulability analysis. The protocol is general purpose, but is developed in this paper for partitioned fixed priority systems with the sporadic task model. Two methods of supporting the protocol are described, as is a prototype `proof of concept' implementation for one of these schemes.

This paper introduces schedulability analysis for global fixed priority scheduling with deferred pre-emption (gFPDS) for homogeneous multiprocessor systems. gFPDS is a superset of global fixed priority pre-emptive scheduling (gFPPS) and global fixed priority non-pre-emptive scheduling (gFPNS). We show how schedulability can be improved via appropriate choice of priority assignment and final non-pre-emptive region lengths, and we provide algorithms which optimize schedulability in this way. An experimental evaluation shows that gFPDS significantly outperforms both gFPPS and gFPNS.

Expression evaluation in programming languages is normally assumed to be deterministic; however, if an expression involves variables that are being modified by the environment of the process during its evaluation, the result of the evaluation can be non-deterministic. Two common scenarios in which this occurs are concurrent programs within which processes share variables and real-time programs that interact to monitor and/or control their environment. In these contexts, although any particular evaluation of an expression gives a single result, there is a range of possible values that could be returned depending on the relative timing between modification of a variable by the environment and its access within the expression evaluation. To compare the semantics of non-deterministic expression evaluation, one can use the set of possible values the expression evaluation could return. This paper formalizes three approaches to non-deterministic expression evaluation, highlights their commonalities and differences, shows the relationships between the approaches and explores conditions under which they coincide. Modal operators representing that a predicate holds for all possible evaluations and for some possible evaluation are associated with each of the evaluation approaches, and the properties and relationships between these operators are investigated. Furthermore, a link is made to a new notation used in reasoning about interference.

SUMMARY Lock‐based resource sharing protocols for single processor systems are well understood and supported in programming languages such as Ada and the Real‐Time Specification for Java, and in Real‐Time Operating Systems, such as those that conform to the Real‐Time POSIX standard. In contrast, multiprocessor resource sharing protocols are still in their infancy with no agreed best practices, and yet current real‐time programming languages and operating systems claim to be suitable for multiprocessor applications. This paper reviews the currently available multiprocessor resource allocation policies and analyzes their applicability to the main industry standard real‐time programming languages. It then proposes a framework that allows programmers to define and implement their own locking policy. A prototype implementation of the framework for Ada is presented and evaluated. Copyright © 2012 John Wiley & Sons, Ltd.

Earliest Deadline First (EDF) is the most widely studied optimal dynamic scheduling algorithm for uniprocessor real-time systems. In the existing literature, however, there is no complete exact analysis for EDF scheduling when both resource sharing and release jitter are considered. Since resource sharing and release jitter are important characteristics of embedded real-time systems, a solid theoretical foundation should be provided for EDF scheduled systems. In this paper, we extend traditional processor demand analysis to let arbitrary deadline real-time tasks share non-preemptable resources and suffer release jitter. A complete and exact schedulability analysis for EDF scheduled systems is provided. This analysis is incorporated into QPA (Quick Processor-demand Analysis) which provides an efficient implementation of the exact test.

This tutorial reviews four popular mathematical formalisms -- dataflow analysis, schedulability analysis, network calculus, and queueing theory -- and how they have been applied to the analysis of Network-on-Chip (NoC) performance. We review the basic concepts and results of each formalism and provide examples of how they have been used in on-chip communication performance analysis. The tutorial also discusses the respective strengths and weaknesses of each formalism, their suitability for a specific purpose, and the attempts that have been made to bridge these analytical approaches. Finally, we conclude the tutorial by discussing open research issues.

With increasing use of embedded systems in safety critical systems, architectures and design processes for safety have become a primary objective in systems design. Most such systems are also time critical leading to safety and time critical systems. Safety standards impose strong requirements on such systems challenging system performance and cost. Very often, however, only part of the functions is safety and time critical calling for a design approach that both meets the safety requirements and provides efficiency and flexibility for less critical functions. These conflicting requirements have given rise to the new research area of mixed critical system design with enormous practical relevance. The tutorial addresses key aspects of mixed critical system design.

Timed Circus is a compact extension to Circus, that is, it inherits only the CSP part of Circus while introducing time. Although it looks much like timed CSP from the viewpoint of syntax, its semantics is very different from that of timed CSP because it uses a complete lattice in the implication ordering instead of the complete partial order of the standard failures-divergences model of CSP. The complete lattice gives rise to a number of strange processes which violate some axioms of CSP, especially when the miracle (the top element) and SKIP meet time. In this paper, compared with timed CSP, we will extensively explore such strange processes which turn out to be very useful in specifying a distinct property that "something must occur". Finally, we use a simple example to demonstrate how our model can contribute to modelling temporal behaviours with multiple time scales in complex systems.

This paper presents the Fixed Priority until Zero Laxity (FPZL) scheduling algorithm for multiprocessor realtime systems. FPZL is similar to global fixed priority preemptive scheduling, however, whenever a task reaches a state of zero laxity it is given the highest priority. FPZL is a minimally dynamic algorithm, in that the priority of a job can change at most once during its execution, bounding the number of pre-emptions. Polynomial time and pseudopolynomial time sufficient schedulability tests are derived for FPZL. These tests are then improved by computing upper bounds on the amount of execution that each task can perform in the zero laxity state. An empirical evaluation shows that FPZL is highly effective, with a significantly larger number of task sets deemed schedulable by the tests derived in this paper, than by state-of-the-art schedulability tests for Earliest Deadline until Zero Laxity (EDZL) scheduling.

Many safety-critical embedded systems are subject to certification requirements. However, only a subset of the functionality of the system may be safety-critical and hence subject to certification, the rest of the functionality is non safety-critical and does not need to be certified, or is certified to a lower level. The resulting mixed criticality system offers challenges both for static schedulability analysis and run-time monitoring. This paper considers a novel implementation scheme for fixed priority uniprocessor scheduling of mixed criticality systems. The scheme requires that jobs have their execution times monitored (as is usually the case in high integrity systems). An optimal priority assignment scheme is derived and sufficient response-time analysis is provided. The new scheme formally dominates those previously published. Evaluations illustrate the benefits of the scheme.

The most important character of real-time systems is that they have stringent timing deadlines that must be guaranteed. A hard real-time system is required to complete its operations before all its timing deadlines. For a given task set, it is useful in an engineering context to know what changes to period can be made to a task that will deliver a schedulable system. In this paper, we develop the sensitivity analysis of task period for EDF scheduled systems on a uniprocessor. We prove that a minimum task period can be determined by a single pass of the QPA algorithm, an improved scheme is presented by using different initial values of the period. The approaches developed for sensitivity analysis of task period are therefore as efficient as QPA, and are easily incorporated into a system design support tool.

The correctness of a real-time system depends on not only the system's output but also on the time at which results are produced. A hard real-time system is required to complete its operations before all its timing deadlines. For a given task set it is useful to know what is the minimum speed of the processor that will deliver a schedulable system. It is also beneficial in an engineering context to know what changes to computation time can be made to a task that will result in a system that is borderline schedulable. In this paper, we address the sensitivity analysis (parameter calculations) for task execution times and speed of the processor for EDF-scheduled systems on a uniprocessor. We prove that an optimal (minimum or maximum) task parameter can be determined by a single pass of the QPA algorithm. This algorithm provides efficient and exact sensitivity analysis for arbitrary deadline real-time systems. The approaches developed for task parameter computations are therefore as efficient as QPA, and are easily incorporated into a system design support tool.

This paper is concerned with the development of reliable real-time systems for use in high integrity applications. It advocates the use of diverse replicated channels, but does not require the dependencies between the channels to be evaluated. Rather it develops and extends the approach of Little wood and Rush by (for general systems) by investigating a two channel system in which one channel, A, is produced to a high level of reliability (i.e. has a very low failure rate), while the other, B, employs various forms of static analysis to sustain an argument that it is perfect (i.e. it will never miss a deadline). The first channel is fully functional, the second contains a more restricted computational model and contains only the critical computations. Potential dependencies between the channels (and their verification) are evaluated in terms of aleatory and epistemic uncertainty. At the aleatory level the events ''A fails" and ''B is imperfect" are independent. Moreover, unlike the general case, independence at the epistemic level is also proposed for common forms of implementation and analysis for real-time systems and their temporal requirements (deadlines). As a result, a systematic approach is advocated that can be applied in a real engineering context to produce highly reliable real-time systems, and to support numerical claims about the level of reliability achieved.

We propose a timed model of Circus which is a compact extension of original Circus. Apart from introducing time, this model uses UTP-style semantics to describe each process as a reactive design. One of significant contributions of our timed model is to extensively explore the reactive design miracle, the top element of a complete lattice with respect to the implication ordering. The employment of the miracle brings a number of brand-new features such as deadline and urgent events, which provide a more powerful and flexible expressiveness in system specifications.

Wormhole switching with fixed priority preemption has been proposed as a possible solution for real-time on-chip communication. However, the hardware implementation cost is expensive and hence constrains its practical deployment. To address this problem, we propose a new solution by utilizing a priority share policy to reduce the resource overhead while still achieving the hard real-time service guarantees. The composite model-based schedulability analysis technique and relevant priority allocation scheme are represented in this paper. Experiment results show that significant resource saving can be achieved with no performance degradation in terms of missed deadlines. By using this approach, a broad class of real-time communication with different QoS requirements can be explored and developed in a SoC/NoC communication platform.

Earliest Deadline First (EDF) is an optimal scheduling algorithm for uniprocessor real-time systems. Quick Processor-demand Analysis (QPA) provides efficient and exact schedulability tests for EDF scheduling with arbitrary relative deadline. In this paper, we propose Improved Quick Processor-demand Analysis (QPA*) which is based on QPA. By extensive experiments, we show that QPA* can significantly reduce the required calculations to perform an exact test for unschedulable systems. We prove that the computation time for testing schedulable systems is hardly affected. Hence the required calculations for general systems can be significantly decreased.

This paper addresses the problem of priority assignment in multiprocessor real-time systems using global fixed task-priority pre-emptive scheduling. In this paper, we prove that Audsley's Optimal Priority Assignment (OPA) algorithm, originally devised for uniprocessor scheduling, is applicable to the multiprocessor case, provided that three conditions hold with respect to the schedulability tests used. Our empirical investigations show that the combination of optimal priority assignment policy and a simple compatible schedulability test is highly effective, in terms of the number of tasksets deemed to be schedulable. We also examine the performance of heuristic priority assignment policies such as Deadline Monotonic, and an extension of the TkC priority assignment policy called DkC that can be used with any schedulability test. Here we find that Deadline Monotonic priority assignment has relatively poor performance in the multiprocessor case, while DkC priority assignment is highly effective.

Real-time scheduling is the theoretical basis of real-time systems engineering. Earliest deadline first (EDF) is an optimal scheduling algorithm for uniprocessor real-time systems. Existing results on an exact schedulability test for EDF task systems with arbitrary relative deadlines need to calculate the processor demand of the task set at every absolute deadline to check if there is an overflow in a specified time interval. The resulting large number of calculations severely restricts the use of EDF in practice. In this paper, we propose new results on necessary and sufficient schedulability analysis for EDF scheduling; the new results reduce, exponentially, the calculation times, in all situations, for schedulable task sets, and in most situations, for unschedulable task sets. For example, a 16-task system that in the previous analysis had to check 858,331 points (deadlines) can, with the new analysis, be checked at just 12 points. There are no restrictions on the new results: each task can be periodic or sporadic, with relative deadline, which can be less than, equal to, or greater than its period, and task parameters can range over many orders of magnitude.

An exact scheduling test for AM multiframe tasks executing on a uniprocessor according to the fixed priority scheduling scheme is presented in this paper. The test is given as a generalization of the exact worst case response time of AM multiframe tasks in two directions. First is an improvement of the exact analysis to be applicable to systems that are subjected to release jitter. Whilst the second is to cope with the arbitrary deadline scenario. A combined analysis of both scenarios is also introduced in this paper.

This paper derives closed form upper bounds on the response times of tasks in fixed priority real-time systems. These bounds are valid for tasks with arbitrary deadlines, release jitter, and blocking. Response time upper bounds are given for tasks that are scheduled pre-emptively, cooperatively with intervals where pre-emption is deferred, and non-preemptively. The set of upper bounds for n tasks can be computed in O(n) time, providing a linear-time sufficient schedulability test, applicable to complex commercial real-time systems.

Wormhole switching with fixed priority preemption has been proposed as a possible solution for real-time on-chip communication. However, none of current priority assignment policies works well in on-chip networks due to some inherent properties of the protocol. In this paper, a novel heuristic branch and bound search algorithm is introduced to explore the possible priority ordering. Differing from the traditional exhaust algorithm which costs exponential complexity, our algorithm can effectively reduce the search space. In addition, this algorithm can ensure that if a priority ordering exists that makes the traffic-flows schedulable, this priority ordering will be found by the search algorithm. By combining with schedulability analysis, a broad class of real-time communication with different QoS requirements can be explored and developed in a SoC/NoC communication platform.

Efficient exact schedulability tests are required both for on-line admission of applications to dynamic systems and as an integral part of design tools for complex distributed real-time systems. This paper addresses performance issues with exact response time analysis (RTA) for fixed priority preemptive systems. Initial values are introduced that improve the efficiency of the standard RTA algorithm (i) when exact response times are required, and (ii) when only exact schedulability need be determined. The paper also explores modifications to the standard RTA algorithm, including; the use of a response time upper bound to determine when exact analysis is needed, incremental computation aimed at faster convergence, and checking tasks in reverse priority order to identify unschedulable task sets early. The various initial values and algorithm implementations are compared by means of experiments on a PC recording the number of iterations required, and execution time measurements on a real-time embedded microprocessor. Recommendations are provided for engineers tasked with the problem of implementing exact schedulability tests, as part of on-line acceptance tests and spare capacity allocation algorithms, or as part of off-line system design tools.

Constructing deliberative real-time AI systems is challenging due to the high execution-time variance in AI algorithms and the requirement of worst-case bounds for hard real-time guarantees, often resulting in poor use of system resources. Using a motivating case study, the general problem of resource usage maximization is addressed. We show how the issues can be leveraged by employing a hybrid task model for anytime algorithms, which is supported by recent advances in fixed priority scheduling for imprecise computation. In particular, with a novel scheduling scheme based on Dual Priority Scheduling, hard tasks are guaranteed by schedulability analysis and scheduled in favor of optional and anytime components which are executed whenever possible for enhancing system utility. Simulation studies show satisfactory performance on the case study with the application of the scheduling scheme. With its basis on fixed priority scheduling, it is expected that it can be easily incorporated into existing real-time operating systems, promoting wider use of imprecise computing and providing a framework where real-time AI applications can be suitably facilitated.

Priority inversion and priority inheritance protocols for bounding blocking time are well-understood topics in realtime systems research. The two most commonly used priority inheritance protocols are basic priority inheritance and priority ceiling emulation. Although both are supported in POSIX, Ada and the Real-Time Specification for Java (RTSJ), little has been written about the consequences of using both protocols concurrently in the same program. The assumption is usually that only one is in force at any particular time. For large real-time systems, this assumption may not be valid. This paper provides motivation for why a mixture of the two can occur and illustrates that this can result in the raising of unwanted asynchronous exception. This has led the Technical Interpretation Committee for the RTSJ to propose a new version of the priority ceiling emulation protocol that will enable it to work in harmony with basic priority inheritance. The protocol is described and we use the UPPAAL tool to explore formal properties using model checking

This paper focuses on priority assignment for realtime systems using fixed priority scheduling. It introduces and defines the concept of a "robust" priority ordering: the most appropriate priority ordering to use in a system subject to variable amounts of additional interference from sources such as interrupts, operating system overheads, exception handling, cycle stealing, and task execution time overruns. The paper describes a robust priority assignment algorithm that can find the robust priority ordering for a wide range of fixed priority system models and additional interference functions. Proofs are given for a number of interesting theorems about robust priority assignment, and the circumstances under which a "deadline minus jitter" monotonic partial ordering forms part of the robust ordering. The paper shows that "deadline minus jitter" monotonic priority ordering is the robust priority ordering for a specific class of system, and that this property holds essentially independent of the additional interference function.

This paper focuses on scheduling different hard real-time applications on a uniprocessor when the earliest deadline first algorithm is used as the local scheduler, and the global scheduler of the system could be fixed priority (FP) or earliest deadline first (EDF). Each application task could be periodic or sporadic, bound or unbound, with arbitrary relative deadline which could be less than, equal to or greater than its period. A number of different server types are considered. This paper presents an exact and efficient schedulability test for the application tasks based on the capacity demand criterion when the global scheduler could be FP or EDF, in some cases, it is necessary and sufficient. Schedulability tests which are necessary and sufficient for several types of dynamic servers are presented when the global scheduler is EDF.

Abstract The complete verification of the timing properties of a large critical system cannot be undertaken in a single step or with a single method. In this paper we present a process that links together a number of techniques and approaches that cover all stages of development from requirements analysis to code testing. The key elements of the process are: a constrained form of timed automata that uses delay and deadline to define temporal behaviour, notions of rely and guarantee to cover temporal dependencies, model checking for design verification, SPARK and Ravenscar restrictions for programming, and scheduling and response time analysis for asserting implementation compliance. Extended examples of the use of the process are given.

Controller Area Network (CAN) is used extensively in automotive applications, with in excess of 400 million CAN enabled microcontrollers manufactured each year. In 1994 schedulability analysis was developed for CAN, showing how worst-case response times of CAN messages could be calculated and hence guarantees provided that message response times would not exceed their deadlines. This seminal research has been cited in over 200 subsequent papers and transferred to industry in the form of commercial CAN schedulability analysis tools. These tools have been used by a large number of major automotive manufacturers in the design of in-vehicle networks for a wide range of cars, millions of which have been manufactured during the last decade. This paper shows that the original schedulability analysis given for CAN messages is flawed. It may provide guarantees for messages that will in fact miss their deadlines in the worst-case. This paper provides revised analysis resolving the problems with the original approach. Further, it highlights that the priority assignment policy, previously claimed to be optimal for CAN, is not in fact optimal and cites a method of obtaining an optimal priority ordering that is applicable to CAN. The paper discusses the possible impact on commercial CAN systems designed and developed using flawed schedulability analysis and makes recommendations for the revision of CAN schedulability analysis tools.

A schedulability test is defined to be sustainable if any task system deemed schedulable by the test remains so if it behaves "better" than mandated by its system specifications. We provide a formal definition of sustainability, and subject the concept to systematic analysis in the context of the uniprocessor scheduling of periodic and sporadic task systems. We argue that it is in general good engineering practice to use sustainable tests if possible, and classify common uniprocessor schedulability tests according to whether they are sustainable or not

Much of the research on scheduling schemes is prevented from being used in practice by the lack of implementations that provide the necessary abstractions. An example of this is the support of execution-time servers. Apart for a single mechanism (the sporadic server), which is defined in the POSIX standard, these important building blocks are not available to the system developer. Over the last few years, we have been developing the mechanisms necessary to construct execution-time servers from within an Ada context. Versions of these have now been incorporated in the Ada 2005 standard. In this paper, we show how the mechanisms can be used to construct the deferrable and sporadic servers

This paper focuses on resource sharing in hierarchical fixed priority pre-emptive systems where a number of separate applications, each with its own server, reside on a single processor. It defines the hierarchical stack resource policy, an appropriate global resource access policy that bounds priority inversion and also limits interference due to overruns during resource access. The paper provides detailed response time analysis enabling the schedulability of application servers and tasks to be determined for systems with local and global resource access. This analysis is applicable to real-world systems where server-based applications need mutually exclusive access to shared resources such as communications buffers, peripheral devices, operating system calls and data structures shared with interrupt handlers

This paper focuses on the hierarchical scheduling of systems where a number of separate applications reside on a single processor. It addresses the particular case where fixed priority pre-emptive scheduling is used at both global and local levels, with a server associated with each application. Using response time analysis, an exact schedulability test is derived for application tasks. This test improves on previously published work. The analysis is extended to the case of harmonic tasks that can be bound to the release of their server. These tasks exhibit improved schedulability indicating that it is advantageous to choose server periods that enable some tasks to be bound to the release of their server. The use of periodic, sporadic and deferrable servers is considered with the conclusion that the simple periodic server dominates both sporadic and deferrable servers when the metric is application task schedulability

As embedded systems activities are increasingly being recognized as a single coherent endeavor, it is not surprising that those concerned with education are striving to define appropriate curricula for this emerging engineering discipline.In this special issue of the Transactions on Embedded Systems, we focus on university education.We provide examples of existing practices, look at initiatives to develop new curricula, and take an educationally centered view on the evolution of this new engineering domain.Although there is a significant and growing agreement as to what defines embedded systems engineering, there is not a universal consensus as to what constitutes the discipline boundaries and, hence, what should be covered in "university provision."This special issue is, therefore, of interest to those involved in education and those interested in the development of the discipline itself.Industrial practice constrains this development, but so does the knowledge base and skills that graduates obtain.Indeed, it is perhaps only possible within universities to take a holistic view of any engineering discipline to define its core topics, necessary foundations, and linked themes.In this special issue eight papers are presented.Four describe experiences gained from teaching (partially or completely) embedded systems as a distinct subject and are from United States institutions that are well known for their research work in embedded systems. 1 What is of interest here is not only what is taught, but how the required teaching is organized.Important issues are the balance between formal lectures and project work, between student-centered and class-based learning, between theory and practice, and between methods and tools.The first paper describes the courses in embedded systems at the University of California at Berkeley with particular emphasis on the graduate curriculum.Their guiding principle is to bring together system theory and computer science.The curriculum has been growing since 1988 out of a bottom-up approach typical of U.S. institutions and is spread over a number of experimental and established courses that provide the foundation from which a future graduate and undergraduate program in embedded systems will rise as a coherent whole.At the CMU, an undergraduate course has evolved over the last three decades.Key areas covered are small and single microprocessor applications, control systems, distributed embedded control, system on chip, networking, embedded PCs, critical systems, robotics, computer peripherals, wireless data systems, signal processing, and command and control.Additional cross-cutting

With modern processors and more dynamic application requirements it is becoming increasingly difficult to produce tight upper bounds on the worst-case execution time of real-time tasks. As a result, at run-time, considerable spare CPU capacity (termed gain time) becomes available that must be usefully employed if cost effective real-time systems are to be engineered. In this paper we introduce a scheme by which gain time is exploited by retrospectively reassigning execution time from a task’s own budget to the gain time that later become available. As a result of changing the system’s execution history, spare capacity is immediately reallocated and hence preserved. The proposed scheme is shown to work with fixed priority dispatching, the use of servers to provide temporal firewalls, and other capacity sharing approaches. Evaluations are provided via simulations.

We present a guardian-based approach to detecting 'babbling idiots', faulty nodes which erroneously consume extra resource in an event triggered system. In general, one cannot detect all babbling idiots, but the maximum effect of undetected faults is bounded and small, and therefore can be taken into account in worst case response time analysis to guarantee that a babbling idiot cannot cause a timing failure elsewhere in the system. The approach is applied specifically to the CAN protocol to protect against faulty nodes transmitting message frames too often. We show that the overhead of including the effect of undetected frames into the worst case response time analysis is small enough to be of practical value.

Consensus is known to be a fundamental problem in fault-tolerant distributed systems. Solving this problem provides the means for distributed processes to agree on a single value. This, however, requires extra communication efforts. For some real-time communication networks such efforts may have undesirable performance implications due to their limited bandwidth. This is certainly the case with the controller area network (CAN), which is widely used to support real-time systems. This paper shows how some underlying properties of CAN can be used to solve the consensus problem. The proposed consensus protocol tolerates the maximum number of process crashes, is efficient and flexible. The described solution is proved correct, its complexity is analyzed and its performance is evaluated by simulation.

The main contribution of this paper is twofold. First, we present an appropriate schedulability analysis, based on response time analysis, for supporting fault-tolerant hard real-time systems. We consider systems that make use of error-recovery techniques to carry out fault tolerance. Second, we propose a new priority assignment algorithm which can be used, together with the schedulability analysis, to improve system fault resilience. These achievements come from the observation that traditional priority assignment policies may no longer be appropriate when faults are being considered. The proposed schedulability analysis takes into account the fact that the recoveries of tasks may be executed at higher priority levels. This characteristic is very important since, after an error, a task certainly has a shorter period of time to meet its deadline. The proposed priority assignment algorithm, which uses some properties of the analysis, is very efficient. We show that the method used to find out an appropriate priority assignment reduces the search space from O(n!) to O(n/sup 2/), where n is the number of task recovery procedures. Also, we show that the priority assignment algorithm is optimal in the sense that the fault resilience of task sets is maximized as for the proposed analysis. The effectiveness of the proposed approach is evaluated by simulation.

For priority based buses such as CAN, worst case response time analysis is able to determine whether messages always meet their deadlines. This can include system models with bounded network faults. However the worst-case scenario (the critical instant) used by the analysis is extremely pessimistic compared to the rest of the invocations in the hyperperiod. We use weakly hard constraints to provide upper bounds on the maximum number of missed deadlines under fault conditions. By allowing some deadlines to be missed (around the critical instant) the weakly-hard schedulability of the system can be guaranteed at much higher levels of faults. This paper presents a response time based formulation that provides a guarantee on the weakly-hard schedulability of messages. Simulation results based on CAN and the Latest Send Time-CAN protocol show that because of the pessimism of the approach, in fact almost all messages meet their deadlines.

As CANs (controller area networks) are being increasingly used in safety-critical applications, there is a need for accurate predictions of failure probability. In this paper we provide a general probabilistic schedulability analysis technique which is applied specifically to CANs to determine the effect of random network faults on the response times of messages. The resultant probability distribution of response times can be used to provide probabilistic guarantees of real-time behaviour in the presence of faults. The analysis is designed to have as little pessimism as possible but never be optimistic. Through simulations, this is shown to be the case. It is easy to apply and can provide useful evidence for justification of an event-triggered bus in a critical system.

Abstract A hard real‐time kernel is presented for distributed computer control systems (DCCS), highlighting a number of novel features, such as integrated scheduling of hard and soft real‐time tasks as well as tasks and resources; high‐performance time management supporting safe DCCS operation in a hard real‐time environment; synchronization and communication featuring event notification via vector semaphores and transparent communication through implicit (content‐oriented) message addressing. Conventional queues have been substituted by Boolean vectors and vector processing techniques throughout the kernel, resulting in efficient and highly deterministic behaviour, which is characterized by very low overhead and constant execution time of kernel operations, independent of the number of tasks involved. Copyright © 2001 John Wiley & Sons, Ltd.

We investigate timing properties of the timed token protocol that are necessary to guarantee synchronous message deadlines. A tighter upper bound on the elapse time between the token's lth arrival at any node i and its (l + /spl nu/)th arrival at any node k is found. A formal proof of this generalized bound is presented.

The key to the next generation real-time systems is flexible scheduling mechanisms that guarantee hard deadlines and use available spare resources to maximise total system utility. This is a multicriteria scheduling problem. It is argued that common approaches like eager slack usage and mandatory first schemes are not only not optimal but nor adequate for a wide class of process models. It is also shown that a late acceptance test model is preferable to an early acceptance test model due to the uncertainty of future behaviour of the system. The discussion is complemented with simulation results.

The presence of network errors such as electrical interference affects the timing properties of a CAN (Controller Area Network) bus. In hard real-time systems it is often better to not receive a message than to receive it too late. Aborting late messages is a form of real-time error confinement which prevents late messages affecting the timeliness of other messages and processes. This can be used to help guarantee hard real-time performance in a distributed system using CAN in the presence of unbounded network errors.

We propose worst-case response time schedulability analysis for fault-tolerant hard real-time systems which takes into account the effects of temporary faults. The major contribution of our approach is to consider the recovery of tasks running with higher priorities. This characteristic is very useful since faulty tasks certainly have a shorter period of time to meet their deadlines. Due to its flexibility and simplicity, the proposed approach provides an effective schedulability analysis, where system predictability can be fully guaranteed.

To perform a schedulability test, scheduling analysis relies on a known worst-case execution time (WCET). This value may be difficult to compute and may be overly pessimistic. This paper offers an alternative analysis based on estimating a WCET from test data to within a specific level of probabilistic confidence. A method is presented for calculating an estimate given statistical assumptions. The implications of the level of confidence on the likelihood of schedulability are also presented.

Finding the worst-case message response time is important for guaranteeing message deadlines in any hard real-time communication environment. This paper proposes an $O(n)$-time algorithm for exactly capturing the worst-case synchronous message response time in an FDDI network for any given set of synchronous message streams whose message deadlines are no longer than periods. The proposed algorithm can be used to form an optimal test on whether or not a given setting of network parameters can meet the message deadline constraints for a considered synchronous message set with deadlines no longer than periods.

In a hard real-time system, it is assumed that no deadline is missed, whereas, in a soft or firm real-time system, deadlines can be missed, although this usually happens in a nonpredictable way. However, most hard real-time systems could miss some deadlines provided that it happens in a known and predictable way. Also, adding predictability on the pattern of missed deadlines for soft and firm real-time systems is desirable, for instance, to guarantee levels of quality of service. We introduce the concept of weakly hard real-time systems to model real-time systems that can tolerate a clearly specified degree of missed deadlines. For this purpose, we define four temporal constraints based on determining a maximum number of deadlines that can be missed during a window of time (a given number of invocations). This paper provides the theoretical analysis of the properties and relationships of these constraints. It also shows the exact conditions under which a constraint is harder to satisfy than another constraint. Finally, results on fixed priority scheduling and response-time schedulability tests for a wide range of process models are presented.

Addresses the problem of performing worst-case execution time (WCET) analysis of Java Byte Code (JBC), which may be generated from different compilers and from different source languages. The motivation for the framework presented is to provide WCET analysis which is portable and therefore more likely to be used in an industrial context. Two issues are addressed in this paper: how to extract data flow and control flow information from JBC programs, and how to provide a compiler-/language-independent mechanism to introduce WCET annotations in the source code. We show that an annotation mechanism based on calls to a static class with empty methods result in similar code when generated by Java or Ada compilers.

Estimating computation times using analysis techniques is always safe but is becoming prohibitively complex or pessimistic with modern processors. The only alternative approach is to use measurement, but this has the significant disadvantage of optimism - the largest value seen during testing may not be the largest experienced during deployment. In this paper, we subject data obtained from measurement to statistical analysis using the techniques of extreme value estimation. A simple case study is described and the approach is illustrated via this study which focuses on the superscalar technique of branch prediction. The approach is applicable to all forms of hardware-induced temporal variability.

Fault-tolerant real-time systems are typically based on active replication where replicated entities are required to deliver their outputs in an identical order within a given time interval. Distributed scheduling of replicated tasks, however, violates this requirement if on-line scheduling, preemptive scheduling, or scheduling of dissimilar replicated task sets is employed. This problem of inconsistent task outputs has been solved previously by coordinating the decisions of the local schedulers such that replicated tasks are executed in an identical order. Global coordination results either in an extremely high communication effort to agree on each schedule decision or in an overly restrictive execution model where on-line scheduling, arbitrary preemptions, and nonidentically replicated task sets are not allowed. To overcome these restrictions, a new method, called timed messages, is introduced. Timed messages guarantee deterministic operation by presenting consistent message versions to the replicated tasks. This approach is based on simulated common knowledge and a sparse time base. Timed messages are very effective since they neither require communication between the local scheduler nor do they restrict usage of on-line flexible scheduling, preemptions and nonidentically replicated task sets.

Scheduling decisions in time-critical systems are very difficult, due to the vast number of systems' parameters and tasks' attributes involved in such decisions. Value-based scheduling heuristics have been found to experience a more graceful degradation under overload situations than various other heuristics. However, currently existing value-based heuristics utilize the tasks' static attributes, and therefore, they derive fixed scheduling priorities. In this paper, we propose value-based scheduling heuristics that utilize the tasks' dynamic attributes in order to enhance the overall system's performance under normal operating loads and to reduce performance degradation under overload situations.

The purpose of this paper is to investigate the issues related to task attribute assignment on an individual processor. The majority of papers on fixed priority scheduling make the assumption that tasks have their attributes (deadline, period, offset and priority) pre-assigned. This makes priority assignment trivial. However in practice, the system's timing requirements are specified and it is expected that the task attributes are synthesised from these. This paper is to present work that has been developed to solve this problem.

The designers of real-time systems try to avoid an under-utilization of hardware by assigning only the absolutely necessary time budget to each task. In certain cases it is also acceptable to cut the time quantum assigned to a task below its worst-case needs, provided (a) a high percentage of executions complete within this quantum and (b) the quality of the aborted computations is sufficient for further processing. In this paper we study the effect of reserving less than the worst-case execution time for different sorting algorithms. We define five metrics and use these metrics to investigate into the quality of the partial results of the sorting algorithms at the point of their termination. Further, we evaluate the sensitiveness of the results to changes in the completion rate. We present a rating of the evaluated algorithms and show how to achieve the best tradeoff between the CPU-time allocation and completion rate.

In this paper we address the real-time capabilities of P-NET, which is a multi-master fieldbus standard based on a virtual token passing scheme. We show how P-NET's medium access control (MAC) protocol is able to guarantee a bounded access time to message requests. We then propose a model for implementing fixed priority-based dispatching mechanisms at each master's application level. In this way, we diminish the impact of the first-come-first-served (FCFS) policy that P-NET uses at the data link layer. The proposed model raises several issues well known within the real-time systems community. Message release jitter; pre-run-time schedulability analysis in non pre-emptive contexts; non-independence of tasks at the application level. We identify these issues in the proposed model and show how results available for priority-based task dispatching can be adapted to encompass priority-based message dispatching in P-NET networks.

Exactly capturing the minimum available time for a network node to transmit its synchronous messages during any given length of time is important for guaranteeing the transmission of synchronous messages before their deadlines in a timed token ring network (such as FDDI) where the timed token medium access control protocol is used. Previous results which only give a lower bound on the minimum transmission time could be too pessimistic for supporting the timely delivery of synchronous traffic in a hard real-time communication environment. This paper presents an O(n)-time algorithm for exactly determining the minimum available transmission time. The algorithm can be used to test whether or not a given allocation of synchronous bandwidths can guarantee a synchronous message set with message deadlines no more than periods; the test so formed is better than any previous testing method whose test is sufficient only, in the sense that it is both sufficient and necessary and therefore optimal.

The issue of using the sporadic server (SS) for scheduling aperiodic tasks has received new attention under the POSIX standard as it has been proposed in P1003.1 d, the additional real-time extensions to POSIX. The SS has been traditionally considered a better approach to the deferrable server (DS) due to its supposed higher achievable utilisation. However, SS also has higher implementation complexity. Nevertheless, the analysis of the comparisons performed from several authors between DS and SS is not conclusive. A review on fixed priority servers is presented with a new parameter selection technique and comprehensive performance analysis based on simulation techniques. With this parameter selection, it is shown that no server performs significantly better than the other in most of the situations. This suggests that future POSIX revisions for real-time support should also consider mechanisms by which other types of servers could be implemented.

The paper describes work carried out to reduce the pessimism in distributed systems timing analysis. The starting point for the paper is the need to prove that the timing properties of a system are met in an efficient and effective manner. The paper shows that an exact approach to the analysis can be intractable, and other approaches are too pessimistic. Using extensive simulation, based on realistic requirements from the domain of interest, a new approach to distributed timing analysis is developed using an integrated approach to task attribute assignment and timing analysis. The new approach is up to 20% more effective than previous tractable approaches. An additional benefit is the approach has a greater resilience to change than the other approaches considered. The results contained within the paper demonstrate the effectiveness of our approach.

The paper presents an approach to implementing fully asynchronous reader/writer mechanisms which addresses the problems of priority inversion and blocking among tasks within multiprocessor real time systems. The approach is conceived from the concept of process consensus that the writer and the reader come to an agreement on accessing the shared data before proceeding to carry out their respective data operations. Because neither locking operations nor repeated actions of read and check are involved, the shared data can be accessed at any time by the writer and all the readers in a manner not only wait-free but also loop-free. In addition, sharing data via this approach introduces no impact upon either timing behaviour or schedulability of any task in the system. Hence the approach helps to remove priority inversion and blocking incurred by the commonly used lock based synchronization mechanisms.

One important requirement of many real-time systems is the ability to undergo several mutually exclusive modes of operation. By means of a mode change the system changes its functionality over time, thus being able to adapt to changing environmental situations. In order to successfully include mode changes in real-time systems, a mode change protocol with well known real-time behaviour is necessary. The authors provide a new model and related schedulability analysis for mode changes in flexible real-time systems.

We investigate the inherent timing properties of the timed token medium access control (MAC) protocol that are necessary for guaranteeing synchronous message deadlines in a timed token ring network such as the Fibre Distributed Data Interface (FDDI) network. As a result, the best-so-far result of the upper bound on the time possibly elapsed between any number of successive token arrivals at a particular node was derived. This result, which is particularly important for studies on real-time communications in any timed token ring network, has been published by Zhang and Burns (see IEEE/ACM Trans. on Networking, vol.3, p. 729-41, 1995) with no proof given. In this paper, we complement our early work by presenting a concise formal proof of this upper bound.

The problem of effectively scheduling soft tasks whilst guaranteeing the behaviour of hard tasks has been addressed in many papers and a large number of techniques have been proposed. The dual priority mechanism is an intuitively simple method with low overheads. A hard task is assigned two priorities. Upon invocation, the task starts executing with a low priority and it is promoted to a high priority at a time that will guarantee that its deadline is met. Soft tasks are assigned medium priorities; they can thus preempt any hard task that is executing before its promotion time. To increase the capacity for soft tasks, and therefore the effectiveness of the real-time system, hard tasks may be assigned a (/sub m//sup n/)-hard (read n in m) temporal constraint. This implies that the task must meet n deadlines in any m invocations. This paper addresses the combination of such constraints and dual priority scheduling. This approach reduces the gap between dynamic priority and fixed priority scheduling with the goal of reducing the average response time of soft tasks.

Atomic actions are an important dynamic structuring technique that aid the construction of fault-tolerant concurrent systems. Although they were developed some years ago, none of the well-known commercially-available programming languages directly support their use. This paper summarizes software fault tolerance techniques for concurrent systems, evaluates the Ada 95 programming language from the perspective of its support for software fault tolerance, and shows how Ada 95 can be used to implement software fault tolerance techniques. In particular, it shows how packages, protected objects, requeue, exceptions, asynchronous transfer of control, tagged types, and controlled types can be used as building blocks from which to construct atomic actions with forward and backward error recovery, which are resilient to deserter tasks and task abortion.

This paper is concerned with deadline guarantees of synchronous messages with deadlines equal to periods, in a timed token ring network such as FDDI where the timed token medium access control (MAC) protocol is used. The timed token protocol guarantees a bounded access time and an average bandwidth for synchronous traffic. However, this guarantee alone, though necessary, is insufficient for guaranteeing the transmission of synchronous messages before their deadlines. To ensure timely delivery, the synchronous bandwidth must be carefully allocated to individual nodes. We propose and analyse an efficient and practical local synchronous bandwidth allocation (SBA) scheme. The new scheme performs better than any previously published as it calculates the synchronous bandwidth such that during the message period, the total synchronous transmission time definitely available (when judged only by local information) is exactly equal to the transmission time required. Our scheme also differs significantly from previously reported ones by explicitly taking into account the synchronous bandwidth allocation for message sets whose minimum message deadlines (D/sub min/) are less than twice the target token rotation time (TTRT), and consequently can apply to any synchronous message set (with D/sub min/>TTRT). The feasibility of the allocations produced by the proposed scheme and the worst case achievable utilisation of the scheme are also discussed.

This paper considers the programming of passive (cold and warm standbys) and active replicated systems in Ada 95. We show that it is relatively easy to develop systems which act as standbys using the facilities provided by the language and the Distributed Systems Annex. Arguably, active replication in Ada 95 can be supported in a manner which is transparent to the application. However, this is implementation-dependent, requires a complex distributed consensus algorithm (or a carefully chosen subset of the language to be used) and has little flexibility. We therefore consider two extensions to the Distributed Systems Annex to help give the application programmer more control. The first is a via a new categorization pragma which specifies that a RCI package can be replicated in more than one partition. The second is through the introduction of a coordinated type which has a single primitive operation. Objects which are created from extensions to coordinated types can be freely replicated across the distributed system. When the primitive operation is called, the call is posted to all sites where a replica resides, effectively providing a broadcast (multicast) facility. We also consider extensions to the partition communication subsystem which implement these new features.

We study the problem of guaranteeing synchronous message sets with the minimum message deadline (D/sub min/) less than twice the target token rotation time (TTRT), i.e., D/sub min/<2/spl middot/TTRT, in an FDDI network. While the restriction of D/sub min//spl ges/2/spl middot/TTRT on a synchronous message set is generally accepted as a necessary condition for all message deadlines to be guaranteed, our study shows that this is not always the case. Some synchronous message sets with D/sub min/<2/spl middot/TTRT may still be guaranteed. We show that there is no need to retain the above restriction on a synchronous message set before determining its schedulability. Furthermore an improved version of a previously-published local synchronous bandwidth allocation scheme, with removal of this restriction, is proposed.

Abstract More and more programmers find their software being used in performance critical applications. Unfortunately, they have limited techniques at their disposal to help guarantee this particular aspect of their programs. There has been considerable activity in recent years on developing analysis techniques for hard real‐time systems. Inevitably these techniques make simplifying assumptions so as to reduce the complexity of the problem to be solved. For example hard real‐time schedulability analysis techniques often assume that the timing properties of the underlying kernel can be accounted for by incorporating extra execution time into the application tasks. Furthermore, they assume that the application task structure is very simple and uniform. This paper considers the implications of using these techniques in the analysis of a typical single processor application, the attitude and orbital control system (AOCS) for the Olympus satellite. The paper outlines a common approach for estimating the response times for tasks, and then extends the scheduling equations so that they can be used in the engineering of realistic real‐time systems.

This paper investigates the inherent timing properties of the timed-token medium access control (MAC) protocol necessary to guarantee synchronous message deadlines in a timed token ring network such as, fiber distributed data interface (FDDI), where the timed-token MAC protocol is employed. As a result, an exact upper bound, tighter than previously published, on the elapse time between any number of successive token arrivals at a particular node has been derived. Based on the exact protocol timing property, an optimal synchronous bandwidth allocation (SBA) scheme named enhanced MCA (EMCA) for guaranteeing synchronous messages with deadlines equal to periods in length is proposed. This scheme is an enhancement on the previously published MCA scheme.

There has been considerable activity in recent years in developing analytical techniques for hard real-time systems. Inevitably these techniques make simplifying assumptions so as to reduce the complexity of the problem to be solved. Unfortunately this leads to a gap between theory and engineering practice. The paper presents new analysis that enables the costs of the scheduler (clock overheads, queue manipulations and release delays) to be factored into the standard equations for calculating worst-case response times. As well as predicting the true behavior of realistic systems, the analysis also allows free parameters, such as clock interrupt rate, to be determined.>

Adaptive and dynamic behaviour is seen as one of the key characteristics of next generation hard real-time systems. Whilst fixed priority pre-emptive scheduling is rapidly becoming a de facto standard in real-time systems engineering, it remains inflexible in its purest form. One method of increasing flexibility is via the incorporation of optional components into processes with hard deadlines. Such components are not guaranteed off-line, but may be accepted at run-time if sufficient spare capacity becomes available. This paper describes new mechanisms which are required to schedule effectively optional components: mechanisms which enable spare capacity to be detected early and on-line guarantees to be given.>

In this paper we show how existing real-time scheduling theory, developed to analyse the behaviour of tasks executing on processing resources, can be applied to the problem of guaranteeing the performance of multi-media information streams read from a disk system. Analysis is derived that takes into account disk layout and predicts the worst-case response times for disk requests. It is shown how buffer size, priority of request and size of non-pre-emptable operations all crucially affect behaviour. The object of the paper is to define an effective run-time test that can be used to determine if new streams can be accommodated.

Abstract The STRESS environment is a collection of CASE tools for analysing and simulating the behaviour of hard real‐time safety‐critical applications. It is primarily intended as a means by which various scheduling and resource management algorithms can be evaluated, but can also be used to study the general behaviour of applications and real‐time kernels. This paper describes the structure of the STRESS language and its environment, and gives examples of its use.

This paper addresses the problem of jointly scheduling tasks with both hard and soft time constraints. We present a new analysis which builds upon previous research into slack stealing algorithms. Our analysis determines the maximum processing time which may be stolen from hard deadline periodic or sporadic tasks, without jeopardising their timing constraints. It extends to tasks with characteristics such as synchronization, release jitter and stochastic execution times, as well as forming the basis for a family of optimal and approximate slack stealing algorithms.>

It is noted that in many hard real-time systems, the set of functions that a system is required to provide may change over time. One way of providing this change is to allow currently running hard real-time tasks to be deleted or changed, or new tasks to be added. The authors define this change as a mode change, and seek to guarantee a priori the timing constraints of all tasks across the change from one mode to another. The authors derive a scheduling theory for static priority preemptive scheduling that can be used to make such guarantees. The schedulability test discussed could easily be incorporated into engineering support tools. The authors also discuss some of the approaches that could be taken to extend the analysis to cope with more complex and interesting scheduling problems, and to handle distributed hard real-time systems.>

We consider the distinction between the terms 'safety' and 'security' in terms of the differences in causal structure and in terms of the differences in the degree of harm caused. The discussion is illustrated by an analysis of a number of cases of system failure where the safety and security issues seem, at least at first sight, to be difficult to disentangle.

This paper describes a framework (called TARDIS) for building timely and reliable distributed systems. Such systems are increasingly needed in avionics, process control, military and other safety critical applications. TARDIS addresses non-functional requirements (e.g. safety, reliability, timeliness, dynamic change management) early in the design process, and facilities the development of arguments that these requirements will be met if the system is implemented in its target execution environment. The paper illustrates TARDIS through a substantial case study.

Though the need to provide students of concurrent programming with practical experience has been recognised in the literature, the difficulty of doing so has also been noted. In order to experience a variety of forms of inter-process communication, students have to learn several different languages. In this paper, we describe Pascal-FC, which implements four different styles of communication within a single language framework. Additional features for timing and low-level programming permit the language to be used for constructing small-scale software for embedded systems.

Abstract Many large real‐time systems are expected to have a long, non‐stop operational life. It cannot, however, be assumed that the code that initially started executing will remain appropriate for the complete lifetime of the system. Indeed it will more likely be the case that the system will be subject to evolutionary change. This can reflect bug fixes, the addition of new functionality, or redeployment of the original code. We introduce in this paper the term Dynamic change management to represent the process of controlling the modification of executing software. The Ada language will increasingly be used to program non‐stop systems. Unfortunately dynamic modifications to Ada programs appear to be invalid in terms of the Ada Language Reference Manual. This paper discusses dynamic change management within the context of distributed Ada execution. Our intention is not to provide a methodology within which such changes can take place; we believe this to be too difficult at the current time. Rather we wish to provide a focus for discussion of this important future problem area. However, we do offer a useful classification of software components, and suggest how change can be effected—the approach to be taken depending upon the structure of the component being replaced. The flexibility of dynamic change management depends upon the initial granularity of distribution and deployment. We also attempt to define rules for legally changing running Ada programs. Although this paper focuses on the Ada language, many of the issues are of general concern.

Abstract Program generation software is increasingly being used, not only to assist non‐computer professionals to produce their own applications, but also to provide tools for programmers and designers. As part of the toolkit for an Ada dialogue development system, a program generator has been written in Ada to generate the package which codes the dialogue manager for a specified user interface. The input specifications and the method of generation are described. The advantages and disadvantages of Ada as the implementation, target and specification language are discussed.

Program generation is a technique that is becoming increasingly popular, although many of the products so far developed have taken a very ad hoc approach. A definition of program generation is given together with an assessment of its applicability and a discussion of the basic structure of a program generator. An architecture is proposed. Considerations of dialogue design are given together with a number of operational criteria aimed at improving the user interface.

Abstract The use of a data‐flow diagram and data dictionary for the requirements specification of an information management system is described together with the benefits to be gained from using prototypes. Construction of such prototypes in Ada is discussed in detail with a simple example being given. The use of a flexible user interface, generic data‐flows, exception handlers for error conditions and a top‐down design method that makes use of separate compilation indicates that Ada is an appropriate language for the development of such systems. Consideration is also given to the use of Ada in the construction of actual as well as prototype information systems.

The need for tools to aid the implementation of user interfaces is highlighted. Techniques for the production of good user interfaces are outlined and facilities to ease implementation of interfaces designed using these techniques are suggested. Emphasis is placed on the need for multi-level adaptable interfaces, and the need for a separate, high-level specification of an interface. A dialogue development system intended for use with interactive systems written in Ada is proposed.

Decision support systems are described, together with previous work on how they support organizational and group tasks. A case study illustrates the need for several linked decision support systems in a manufacturing company and the nature of co-operation and conflict in organizations is discussed. The components and characteristics of Distributed Decision Making systems are then stated and justified. The possible advantages of using production systems to improve the explanations of decisions is considered. Plans for the future development of supportive software are outlined.