We describe DBL-MBPTA, a new approach for measurement-based probabilistic timing analysis (MBPTA). Unlike the usual MBPTA, which treats the time a program executes as a random variable, we consider both the number n of instructions executed in each measurement and the time $T(n)$ they took to execute. By taking tuples $(n, T(n))$, for various values of n, DBL-MBPTA allows for multiple execution path analysis. We show that $(n, T(n))$ can be bounded from below and above by two reference lines. The modeled random variable is the relative distance ($n, T(n)$) from these lines, which explains the term distance between lines (DBL) given to the approach. According to DBL-MBPTA, samples can be analyzed and improved, for which we employ deep neural networks. Once sample coverage is deemed representative, probabilistic bounds on execution time are estimated via the modeled relative distance. We evaluate our approach using both synthetic data and data collected through measurements on a multi-core platform. The results obtained demonstrate the effectiveness of DBL-MBPTA.

Real-time applications may be comprised of both soft and hard tasks, the former being related to streaming-based or other non-critical services. For these applications one is interested in minimizing the response time of soft tasks, for which quality of service is at stake, while not jeopardizing hard deadlines. In this paper, we propose a framework for multiprocessor real-time systems, that can schedule hard and soft tasks with unconstrained deadlines according to two EDF-based configurations. Our solution relies on two special servers, which are responsible for providing temporal isolation and slack reclaiming. These strategies are combined so that the average response time of soft tasks are improved. Results are evaluated via extensive simulation, which indicates that: the available processing capacity can be effectively utilized; average response time of aperiodic tasks is significantly reduced and hard deadlines are preserved while soft deadline miss ratio is kept low.

We consider the problem of scheduling a set of preemptible independent periodic implicit-deadline hard real-time tasks on heterogeneous processors. We divide this problem into two sub-problems: (a) assigning portions of each processor (offline) to each task without jeopardizing schedulability; and (b) generating a schedule satisfying the assigned portions using an online semi-partitioned scheduler, called Heterogeneous Quasi-Partitioned Scheduling (hQPS). The scheduler handles task servers at run-time for ensuring that the processor shares assigned to tasks are timely available to them. Assessments indicate that the proposed solution (i) has good scalability (up to 64 tasks, 64 processors), (ii) is effective in generating schedules with few preemptions and few migrations, and (iii) is effective in managing resources; for task sets where an extra processor speed is required, our solution needs at most 10% extra compared to an optimal scheduler.

Intrinsic timing uncertainties present in modern hardware platforms have motivated the use of Extreme Value Theory (EVT) to timing analysis, however, the timing behaviour of a task may not entirely fulfil the necessary assumptions. To deal with this difficulty, randomisation at the hardware level has been proposed as a means of facilitating the use of statistical timing analysis. However, it has been shown that hardware randomisation does not solve all the analysis problems and importantly some projects may not wish to change the hardware that is used to support timing analysis. This paper presents an innovative approach, which does not require hardware randomisation or any special system feature, named Indirect Estimation in Statistical Time Analysis (IESTA). The main difference is that randomised hardware is performed before software instructions actually executes and is applied to parameters (e.g. cache state) only indirectly linked to timing. In contrast, IESTA adds its randomisation directly to the timing measures without affecting the way the software is executed. The IESTA approach is evaluated by experiments on two real case studies for which execution time measurements are taken from an embedded platform and from a Rolls-Royce Full Authority Digital Engine Controller.

Quasi-Partition Scheduling (QPS) is a new scheduling approach with low preemption and migration overhead. QPS was originally proposed taking into consideration hard periodic and sporadic tasks. In this paper we discuss a proposal for extending QPS to deal with soft aperiodic tasks.

Extreme Value Theory (EVT) is a powerful statistical framework for estimating maximum values of random variables and has recently been applied for deriving probabilistic bounds on task execution times (pWCET). Task execution time data are collected from measurements and the maximum measured values are fit to an extreme value model. In this paper we provide a careful study on the applicability and effectiveness of EVT in this application field. The study is based on extensive experiments for which we have designed an embedded platform equipped with random cache of configurable sizes. Based on evidences of the experiments, we provide the following contributions: we give a new definition of pWCET that conforms with the fact that pWCET estimates depend on input data distribution used during analysis, we show that using the Generalized Extreme Value (GEV) distribution is necessary since the more restrictive modeling, based on the Gumbel distribution, may yield unsafe or over-estimated values of pWCET, we confirm that hardware randomization favors the applicability of EVT, although it does not ensure it since the distribution of maxima for execution time data are not guaranteed to be analyzable via EVT.

We describe a new algorithm, called Quasi-Partitioned Scheduling (QPS), capable of scheduling any feasible system composed of independent implicit-deadline sporadic tasks on identical processors. QPS partitions the system tasks into subsets, each of which is either scheduled by EDF on a single processor or by a set of servers on two or more processors. More precisely, QPS uses an efficient scheme to switch between partitioned EDF and global-like scheduling rules in response to system load variation, providing dynamic adaptation in the system. Extensive simulation compares QPS favorably against related work, showing that it has very low preemption and migration overheads.

We present HIME, a new EDF-based semi-partitioned scheduling algorithm which allows at most one migrating task per processor. In a system with m processors, this arrangement limits the migrating tasks to at most m/2 and the number of migrations per job to at most m-1. HIME has a utilisation bound of at least 74.9%, and can be configured to achieve 75%, the theoretical limit for semi-partitioned schemes with at most m/2 migrating tasks. Experiments show that the average system utilisation achieved by HIME is about 95%.

Providing location privacy to users is one of the important issues that must be addressed in Vehicular Ad-Hoc Networks. Recent solutions address it by using cryptographic “mix-zones”, which are anonymizing regions where nodes change their temporary identities (pseudonym) without being tracked. However, existing solutions are vulnerable to internal attackers since within a mix-zone messages are encrypted using a group secret key. In this paper we improve location privacy of mix-zones via extensions to the CMIX protocol. By carrying out extensive simulations, we investigate and compare the effective location privacy provided by the proposed approach.

Optimal multiprocessor real-time schedulers incur significant overhead for preemptions and migrations. We present RUN, an efficient scheduler that reduces the multiprocessor problem to a series of uniprocessor problems. RUN significantly outperforms existing optimal algorithms with an upper bound of O(log m) average preemptions per job on m processors (≤ than 3 per job in all of our simulated task sets) and reduces to Partitioned EDF whenever a proper partitioning is found.

The problem of scheduling a set of tasks on a multiprocessor architecture is addressed. Tasks are assumed to be sporadic with arbitrary deadlines and may migrate between processors. The execution of migrating tasks is controlled by a bandwidth reservation scheme so that schedulability is guaranteed by EDF. Task migration costs are taken into consideration. Results from experiments indicate that the proposed approach performs well in terms of schedulability.

The complexity of real-time systems has substantially increased in the past few years regarding both hardware and software aspects. The use of modern sensors, able to capture image and audio data, demands predictable multimedia-like data processing. Moreover, applications like autonomous robots, surveillance, or modern multimedia players may well be characterized by several operation modes, each one associated with light conditions, vision angle, change in user requirements, etc. In this paper, we describe suitable scheduling mechanisms that address these aspects. Application modes are characterized by their required processing bandwidth and benefit values. By using bandwidth reservation schedulers, dynamic reconfiguring scheduling parameters is seen as an optimization problem whose goal is to maximize the overall system benefit subject to schedulability constraints. Two different models for the problem are defined, Discrete and Continuous. The former gives rise to an NP-Hard problem for which efficient approximate solutions are derived. An optimal and polynomial solution to the Continuous model is derived. Both models are then extended to incorporate task execution times described as probability distributions. Making use of this stochastic modeling one is able to dynamically reconfigure the scheduler subject to probabilistic schedulability guarantees. The derived solutions are evaluated by extensive simulation, which indicates the good performance of the proposed reconfiguration mechanisms.

Reservation-based scheduling mechanisms have successfully been used for supporting real-time applications whose tasks exhibit high variability in their execution or release times. Indeed, such mechanisms are able to preallocate system bandwidth to the application tasks so that temporal isolation between them is ensured. However, bandwidth allocation is usually based on off-line policies, which may not be suitable for real-time applications that are structured as having several modes of operation, each one requiring a distinct level of system bandwidth. Variations in light conditions, the changing of energy levels, error-detection, or operator commands are examples of events that may trigger a different mode of operation in multi-mode adaptive real-time applications. In this paper we address the problem of dynamically reconfiguring scheduling parameters of reservation-based mechanisms, offering support for multi-mode adaptive real-time applications. Assuming that each reconfiguration option gives a benefit for the system, reconfiguration is seen as an optimization problem whose objective is to maximize the overall system benefit. Two different models for the problem are formulated, the Integer Programming (IP) and the Linear Programming (LP) formulations. The IP formulation gives rise to an NP-Hard problem for which we give efficient approximate solutions. Also, an optimal and polynomial solution to the LP formulation is derived. Results obtained from extensive simulation indicate the good performance of the proposed reconfiguration mechanisms.

Modern real-time systems must be designed to be highly adaptable, reacting to aperiodic events in a predictable manner and exhibiting graceful degradation in overload scenarios whenever needed. In this context, it is useful to structure the system as a set of multiversion tasks. Task versions can be modeled to implement services with various levels of quality. In overload scenarios, for instance, a lower quality service may be scheduled for execution keeping the system correctness and providing graceful degradation. The goal of the reconfiguration mechanism is to select the versions of tasks that lead to the maximum benefit for the system at runtime. In this paper, we provide a schedulability condition based on which we derive an optimal pseudo-polynomial solution for this problem. Then, a faster approximation solution is described. Results from simulation indicate the effectiveness of the proposed approach.

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.

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.