Search

This survey covers probabilistic timing analysis techniques for real-time systems. It reviews and critiques the key results in the field from its origins in 2000 to the latest research published up to the end of August 2018. The survey provides a taxonomy of the different methods used, and a classification of existing research. A detailed review is provided covering the main subject areas: static probabilistic timing analysis, measurement-based probabilistic timing analysis, and hybrid methods. In addition, research on supporting mechanisms and techniques, case studies, and evaluations is also reviewed. The survey concludes by identifying open issues, key challenges and possible directions for future research.

This survey covers schedulability analysis techniques for probabilistic real-time systems. It reviews the key results in the field from its origins in the late 1980s to the latest research published up to the end of August 2018. The survey outlinesfundamental concepts and highlights key issues. It provides a taxonomy of the different methods used, and a classification of existing research. A detailed review is provided covering the main subject areas as well as research on supporting techniques. The survey concludes by identifying open issues, key challenges and possible directions for future research.

In multitasking real-time systems, the choice of scheduling algorithm is an important factor to ensure that response time requirements are met while maximising limited system resources. Two popular scheduling algorithms include fixed priority (FP) and earliest deadline first (EDF). While they have been studied in great detail before, they have not been compared when taking into account cache related pre-emption delays (CRPD). Memory and cache are split into a number of blocks containing instructions and data. During a pre-emption, cache blocks from the pre-empting task can evict those of the pre-empted task. When the pre-empted task is resumed, if it then has to re-load the evicted blocks, CRPD are introduced which then affect the schedulability of the task. In this paper we compare FP and EDF scheduling algorithms in the presence of CRPD using the state-of-the-art CRPD analysis. We find that when CRPD is accounted for, the performance gains offered by EDF over FP, while still notable, are diminished. Furthermore, we find that under scenarios that cause relatively high CRPD, task layout optimisation techniques can be applied to allow FP to schedule tasksets at a similar processor utilisation to EDF. Thus making the choice of the task layout in memory as important as the choice of scheduling algorithm. This is very relevant for industry, as it is much cheaper and simpler to adjust the task layout through the linker than it is to switch the scheduling algorithm.

This survey provides an overview of the scientific literature on timing verification techniques for multi-core real-time systems. It reviews the key results in the field from its origins around 2006 to the latest research published up to the end of 2018. The survey highlights the key issues involved in providing guarantees of timing correctness for multi-core systems. A detailed review is provided covering four main categories: full integration, temporal isolation, integrating interference effects into schedulability analysis, and mapping and allocation. The survey concludes with a discussion of the advantages and disadvantages of these different approaches, identifying open issues, key challenges, and possible directions for future research. [ABSTRACT FROM AUTHOR]

This survey covers research into mixed criticality systems that has been published since Vestal’s seminal paper in 2007, up until the end of 2016. The survey is organised along the lines of the major research areas within this topic. These include single processor analysis (including fixed priority and Earliest Deadline First (EDF) scheduling, shared resources, and static and synchronous scheduling), multiprocessor analysis, realistic models, and systems issues. The survey also explores the relationship between research into mixed criticality systems and other topics such as hard and soft time constraints, fault tolerant scheduling, hierarchical scheduling, cyber physical systems, probabilistic real-time systems, and industrial safety standards. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

Recent technological advances have led to an increasing gap between memory and processor performance, since memory bandwidth is progressing at a much slower pace than processor bandwidth. Pre-fetching techniques are traditionally used to bridge this gap and achieve high processor utilization while tolerating high memory latencies. Following this trend, new computational models have been proposed to split task execution in two consecutive phases: a memory phase in which the required instructions and data are pre-fetched to local memory (M-phase), and an execution phase in which the task is executed with no memory contention (C-phase). Decoupling memory and execution phases not only simplifies the timing analysis, but also allows a more efficient (and predictable) pipelining of memory and execution phases through proper co-scheduling algorithms. This paper takes a further step towards the design of smart co-scheduling algorithms for sporadic real-time tasks complying with the memory-computation (M/C) model, by proposing a theoretical framework aimed at tightly characterizing the schedulability improvement obtainable with the adopted M/C task model on single-core systems. In particular, a critical instant is identified for M/C tasks scheduled with fixed priority and an exact response time analysis with pseudo-polynomial complexity is provided. Then, we investigate the problem of priority assignment for M/C tasks, showing that a necessary condition to achieve optimality is to allow different priorities for the two phases. Our experiments show that the proposed techniques provide a significant schedulability improvement with respect to classic execution models, placing an important building block towards the design of more efficient partitioned multi-core systems. [ABSTRACT FROM PUBLISHER]

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. [ABSTRACT FROM AUTHOR]

This position paper outlines the innovative probabilistic approach being taken by the EU Integrated Project PROXIMA to the analysis of the timing behaviour of mixed criticality real-time systems. PROXIMA supports multi-core and mixed criticality systems timing analysis via the use of probabilistic techniques and hardware/software architectures that reduce dependencies which affect timing. The approach is being applied to DO-178B/C and ISO26262. [ABSTRACT FROM AUTHOR]

We describe and evaluate explicit reservation of cache memory to reduce the cache-related preemption delay (CRPD) observed when tasks share a cache in a preemptive multitasking hard real-time system. We demonstrate the approach using measurements obtained from a hardware prototype, and present schedulability analyses for systems that share a cache by explicit reservation. These analyses form the basis for a series of experiments to further evaluate the approach. We find that explicit reservation is most useful for larger task sets with high utilization. Some task sets cannot be scheduled with a conventional cache, but are schedulable with explicit reservation. [ABSTRACT FROM AUTHOR]

A series of Gaussian and non-Gaussian equal energy noise exposures were designed with the objective of establishing the extent to which the kurtosis statistic could be used to grade the severity of noise trauma produced by the exposures. Here, 225 chinchillas distributed in 29 groups, with 6 to 8 animals per group, were exposed at 97 dB SPL. The equal energy exposures were presented either continuously for 5 d or on an interrupted schedule for 19 d. The non-Gaussian noises all differed in the level of the kurtosis statistic or in the temporal structure of the noise, where the latter was defined by different peak, interval, and duration histograms of the impact noise transients embedded in the noise signal. Noise-induced trauma was estimated from auditory evoked potential hearing thresholds and surface preparation histology that quantified sensory cell loss. Results indicated that the equal energy hypothesis is a valid unifying principle for estimating the consequences of an exposure if and only if the equivalent energy exposures had the same kurtosis. Furthermore, for the same level of kurtosis the detailed temporal structure of an exposure does not have a strong effect on trauma. [ABSTRACT FROM AUTHOR]

This study examined: (1) the value of using the statistical metric, kurtosis [β(t)], along with an energy metric to determine the hazard to hearing from high level industrial noise environments, and (2) the accuracy of the International Standard Organization (ISO-1999:1990) model for median noise-induced permanent threshold shift (NIPTS) estimates with actual recent epidemiological data obtained on 240 highly screened workers exposed to high- level industrial noise in China. A cross-sectional approach was used in this study. Shift-long temporal waveforms of the noise that workers were exposed to for evaluation of noise exposures and audiometric threshold measures were obtained on all selected subjects. The subjects were exposed to only one occupational noise exposure without the use of hearing protection devices. The results suggest that: (1) the kurtosis metric is an important variable in determining the hazards to hearing posed by a high-level industrial noise environment for hearing conservation purposes, i.e., the kurtosis differentiated between the hazardous effects produced by Gaussian and non-Gaussian noise environments, (2) the ISO-1999 predictive model does not accurately estimate the degree of median NIPTS incurred to high level kurtosis industrial noise, and (3) the inherent large variability in NIPTS among subjects emphasize the need to develop and analyze a larger database of workers with well-documented exposures to better understand the effect of kurtosis on NIPTS incurred from high level industrial noise exposures. A better understanding of the role of the kurtosis metric may lead to its incorporation into a new generation of more predictive hearing risk assessment for occupational noise exposure. [ABSTRACT FROM AUTHOR]

This survey covers hard real-time scheduling algorithms and schedulability analysis techniques for homogeneous multiprocessor systems. It reviews the key results in this field from its origins in the late 1960s to the latest research published in late 2009. The survey outlines fundamental results about multiprocessor real-time scheduling that hold independent of the scheduling algorithms employed. It provides a taxonomy of the different scheduling methods, and considers the various performance metrics that can be used for comparison purposes. A detailed review is provided covering partitioned, global, and hybrid scheduling algorithms, approaches to resource sharing, and the latest results from empirical investigations. The survey identifies open issues, key research challenges, and likely productive research directions. [ABSTRACT FROM AUTHOR]

Exposure of chinchillas to broadband, high-level impact noise on an interrupted 6-h daily schedule over 20 days has shown that pure-tone thresholds measured immediately following each daily exposure improve as much as 30 dB despite the continuing noise exposure. The time constant of this recovery effect (toughening) and the magnitude of the effect are related to the audiometric test frequency and the exposure energy. The trauma, quantified by permanent threshold shifts and sensory cell losses, produced by the interrupted exposure paradigm is generally less than that produced by an equal-energy uninterrupted exposure. The wide variations in the temporal pattern of threshold shift across similarly exposed animals suggest that the toughening effect reflects the underlying susceptibility of that animal to noise trauma. [ABSTRACT FROM AUTHOR]

An experiment was designed to determine if, for equal SPL and power spectrum, the effects on hearing of high-kurtosis noise exposures and a Gaussian noise exposure are different and the extent to which any differences measured in terms of audiometric and histological variables are frequency specific. Three groups of chinchillas with 10 animals/group were exposed for 5 days at 90 dB SPL to one of three types of noise, each with the same power spectrum. The impulsiveness, defined by the kurtosis, and the region of the spectrum from which the impulsive components of the noise were created differed for two of the noises, while the third was a continuous Gaussian noise. The results show that the most impulsive noise produced up to 20 dB greater permanent threshold shift at the high frequencies than did the Gaussian noise exposure. However, these audiometric results were difficult to reconcile with the pattern of sensory cell losses that showed statistically significant larger losses of outer hair cells for the impulsive exposure in the 0.25-kHz region. When the impacts in a high-kurtosis noise were created from the energy in the 1-through 6-kHz region of the spectrum, the audiometric profile of hearing loss was similar to that produced by the Gaussian noise; however, inner hair cell losses were significantly greater in the 4-kHz octave band region of the cochlea. [ABSTRACT FROM AUTHOR]

Industrial noise environments usually present a complex stimulus to the exposed individual. These environments often contain mixtures of multiply reflected impact noises and a relatively Gaussian broadband noise. Noise exposure standards do not consider the possibility of interactions between the two classes of noise that can exacerbate the amount of hearing trauma. This paper presents the results of a large series of experiments designed to document the hazard posed to hearing from complex noise exposures. Twenty-three groups of chinchillas with 5 to 11 animals per group (total N=135) were exposed for 5 days to either octave bands of noise, impacts alone, or combinations of impact and octave bands of noise. Evoked potential measures of hearing thresholds and cochleograms were used to quantify the noise-induced trauma. The results show that, for sound exposure levels (SEL) which produce less than approximately 10 dB PTS (permanent threshold shift) or 5% total sensory cell loss, equal-energy exposures tend to produce equivalent effects on hearing. However, there is a range of at least 10 dB in the SEL parameter where hearing loss from equal-energy exposures at a particular SEL can be exacerbated by increasing the repetition rate of the impacts or by the addition of a Gaussian low-level noise. The exacerbation of trauma from the addition of a Gaussian continuous noise is dependent upon the spectrum of that noise. [ABSTRACT FROM AUTHOR]

There is the suggestion in the literature that vibration may potentiate the effects of noise and may thus increase the risk of hearing loss in a variety of exposure situations. However, in human experimental studies, which, by necessity, are limited to low levels of exposure, the effects measured are relatively small. A very limited number of animal studies have also shown an enhanced noise-induced hearing loss in the presence of vibration, but the scope of these studies is limited. The animal studies (chinchilla) that form the basis of this report were performed using a 30-Hz, 3g rms and a 20-Hz, 1.3g rms cage vibration separately and in combination with continuous noise (95-dB, 0.5-kHz octave band) and impact noise (113, 119, or 125 dB peak SPL) exposure paradigms. All exposures lasted for 5 days. The impact noise exposures were designed to have approximately equal total energy. Temporary and permanent threshold shifts were measured using evoked potentials, and sensory cell loss was measured using surface preparation histology. The results obtained from some of the noise/vibration paradigms showed that such exposures can alter some of the dependent measures of hearing. This effect was statistically significant only for the stronger vibration exposure conditions and was evident primarily in the extent of the outer hair cell losses and in the shape of the PTS audiogram. [ABSTRACT FROM AUTHOR]