Search

We herein propose a heuristic redundancy selection algorithm that combines resubmission, replication, and checkpointing redundancies to reduce the resiliency overhead in fault‐tolerant workflow scheduling. The appropriate combination of these redundancies for workflow tasks is obtained in two consecutive phases. First, to compute the replication vector (number of task replicas), we apportion the set of provisioned resources among concurrently executing tasks according to their needs. Subsequently, we obtain the optimal checkpointing interval for each task as a function of the number of replicas and characteristics of tasks and computational environment. We formulate the problem of obtaining the optimal checkpointing interval for replicated tasks in situations where checkpoint files can be exchanged among computational resources. The results of our simulation experiments, on both randomly generated workflow graphs and real‐world applications, demonstrated that both the proposed replication vector computation algorithm and the proposed checkpointing scheme reduced the resiliency overhead.

The paper proposes a practical framework for implementing a fault-tolerant scheduling of hybrid assembly systems which combine humans and automated technical systems. The crucial difficulty with this kind of systems is related to delays which may inevitably occur with human involvement. In this paper, such delays are treated as faults and suitably accommodated. The paper starts with a detailed overview of a case study being a battery assembly system. Subsequently, an intuitive modelling approach is used to describe the evolution of its state. Since the system contains a humans and automated technical systems, its is proposed to analyse the system with an innovative IoT platform called KIS.ME. As a result, a reference human performance model is obtained using a fuzzy logic approach. Having a human reference model, a predictive fault-tolerant scheduling is proposed along with suitable performance constraints. The final part of the paper shows the obtained results, which clearly exhibit potential benefits, which can be obtained by merging KIS.ME with a proposed scheduling approach.

In this paper, we focus on two major problems in hard real-time embedded systems fault tolerance and energy minimization. Fault tolerance is achieved via both checkpointing technique and active replication strategy to tolerate multiple transient faults, whereas energy minimization is achieved by adapting Dynamic Voltage Frequency Scaling (DVFS) technique. First, we introduce an original fault-tolerance approach for hard real-time systems on multiprocessor platforms. Based on this approach, we then propose DVFS_FTS algorithm for energy-efficient fault-tolerant scheduling of precedence-constrained applications. DVFS_FTS is based on a list scheduling heuristics, it satisfies real-time constraints and minimizes energy consumption even in the presence of faults by exploring the multiprocessor architecture. Simulation results reveal that the proposed algorithm can save a significant amount of energy while preserving the required fault-tolerance of the system and outperforms other related approaches in energy savings.

With the increasing functionality of multi-agent systems, fault tolerance has become an essential requirement, especially for workflow with interdependencies among tasks. In this paper, we propose a scheme that combines a novel intrinsic-plasticity-inspired rescheduling execution model (IPIREM) with an improved NSGA-III with knee points. The IPIREM provides a relatively stable evaluation without any estimation of the failure distribution when transient failures happen. Based on the evaluation result of IPIREM, the multi-objective optimization problem is solved by use of an improved NSGA-III, which accelerates convergence and promotes diversity. Finally, experimental results show that the proposed algorithm is effective in enhancing efficiency of the workflow.

Many High Performance Computing (HPC) and resource intensive applications have been tested and migrated to the Cloud. These applications may have high data input size, which often has a high correlation to execution performance and time. Migration to the Cloud demands adaptation of the fault tolerance (FT) and scheduling approaches. Although those topics are well connected, they are often treated separately. This work proposes a novel integrated scheduling and FT model which takes into account the characteristics of the tasks and the target execution nodes. Preliminary results indicate good potential to improve system reliability and execution makespan of scientific workflows.

A permanent growth of forklifts’ indoor practical applications such as high-storage warehouses makes them dominating transportation tools. It rises the need for their coordinated scheduling including uncertainties related to the human operator behaviour. To tackle this problem, in the paper a novel comprehensive fuzzy logic-based methodology enabling modeling cooperating forklifts and their robust fault-tolerant scheduling is proposed. The advantage of the developed methodology is that it can overcome inevitable conditions like faults, environmental or human-like disturbances and uncertainties. To settle this problem a fuzzy algebraic max plus algebra-based model is proposed and accompanied with a suitable predictive scheduling algorithm. Subsequently, the proposed approach is extended by fault diagnosis mechanisms resulting in a new centrally managed predictive fault-tolerant scheduling system. The efficiency of the proposed approach is evaluated using various simulation scenarios which involve cooperating forklifts transportation tasks operating in a high-storage warehouse of RAFI GmbH & Co. KG company.

Mobile cloud computing is a form of cloud computing that incorporates mobile devices such as smartphones and tablet PCs into the cloud infrastructure. As mobile devices are resource-constrained in nature, new scheduling strategies are required when using them as resource providers. Based on our previous group-based scheduling algorithm, we present fault-tolerant scheduling algorithms considering checkpoint and replication mechanisms to actively cope with faults. We carried out the performance evaluation with simulation to demonstrate that our algorithm is more efficient than the existing one lacking fault tolerance in terms of accuracy rate, resource consumption, and average execution time. In particular, the average execution time was reduced by about 60%, resulting in the reduction of resource consumption.

In this paper, fault tolerant task scheduling algorithms are proposed for mapping task graphs to heterogeneous processing nodes. These scheduling heuristics that we propose are redundancy-based software to tolerate hardware faults. We consider only processor permanent failures with a fail-silent behavior. The proposed heuristics generate automatically a real-time fault distributed schedule of dependent and independent tasks into heterogonous multiprocessors architecture. The heuristics are based on active and passive redundancy.

Distributed integrated modular avionics (DIMA) system design through the distributed integrated technology, mixed critical task scheduling, real-time fault tolerant scheduling and time triggered communication mechanism, greatly enhance the reliability, safety and real-time performance of integrated electronic system. The DIMA represents the development trend of future avionics systems. This paper studies and discusses the architecture characteristics of DIMA. Then it studies and analyzes the development of key technologies in DIMA system in detail. Finally, it looks into the development trend of DIMA technology.

Divisible task fault-tolerant scheduling problems for a heterogeneous system on a general and realistic platform are addressed in this paper, where the communication is in non-blocking message receiving mode, and the processors and communication links may have different speeds and startup overheads. For this kind of problems, the optimal sequence and the fraction of task for each processor are derived first when the fault checkout overhead and checkout time consumption are considered. Then, to decrease the time consumption and checkout overheads, a checkout strategy, which is more suitable for divisible task, is employed. Moreover, an efficient algorithm with the fault fraction units re-allocated is proposed. Finally, the experiments on some simulation examples are conducted and the experimental results indicate that the proposed algorithm is effective, can minimize the expected execution time, and can save the time on fault-tolerant consumption.

Clouds are becoming a very important platform for hybrid real-time tasks. To enhance the reliability of cloud, fault tolerance of cloud becomes a critical issue. However, the complexities and specialties of traditional fault-tolerant mechanisms cannot meet the fault-tolerant requirements of clouds. To address this issue, we propose a novel fault-tolerant scheduling algorithm named ARCHER for hybrid tasks in cloud. ARCHER has three significant characteristics: 1) it integrates the traditional primary/backup model and checkpoint technology which can flexibly determine the execution time of the backup copies of tasks, so it greatly enhances the resource utilization and produces more time slots to execute tasks as many as possible; 2) it employs task classification mechanism to realize precise scheduling for different types of tasks and virtual machines, which reduces the response time of clouds; and 3) it uses time slot exploiting mechanism, task forward mechanism, and task transform mechanism to achieve high-resource utilization. We conduct extensive simulations to evaluate the performance of ARCHER by comparing it with four baseline algorithms. The experimental results show that ARCHER can effectively improve the resource utilization of cloud while guaranteeing fault tolerance.

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.

Safety-critical systems employ fault-tolerant strategies in order to provide predictable performance despite the occurrence of faults. Majority of faults that affect such systems are transient (i.e., momentary) in nature which can easily be tolerated through the re-execution of the affected task before its deadline. However, evaluating all possible fault patterns to provide an optimal re-execution based fault-tolerant scheduling strategy for a given task set is an intractable problem, and is prohibitively expensive to be applied on-line. Hence, off-line techniques are often preferred over on-line techniques for solving such problems. This work proposes an off-line optimal fault-tolerant scheduler synthesis mechanism for non-preemptive periodic real-time tasks on uniprocessors. Practical applicability of the above scheduler synthesis procedure has been illustrated through a motor network example.

The fundamental target of real-time scheduling is to execute the task set, such that their deadlines are never missed. The major concern in safety-critical and mixed criticality real-time systems is that correct output should be generated before deadline even in the presence of faults. With the advent of low cost COTS there is rise in the transient faults. This lay off can be met by using fault tolerant techniques to make the system reliable. The empirical evaluation and simulation of partitioned and global approaches of scheduling for the avionics task set gives an insight of issues in achieving reliability.

To improve the reliability of heterogeneous realtime system, researchers often use task replication technology to achieve fault tolerance and improve system reliability. At the same time, real-time tasks in heterogeneous systems need to be completed within very strict time constraints. Usually, reducing time and improving reliability are two conflict factors. In order to balance these two factors, we propose a novel scheduling algorithm-adaptive fault-tolerant scheduling algorithm (AFTSA). The algorithm first generates a dynamic number of replicas for each real-time task according to given deadlines, and then allocate these tasks to appropriate processors to achieve high reliability under time constraints. Experimental results show that our proposed algorithm improves the reliability on average by 26.9% and 30.0% as compared with the existing DB-FTSA and FTSA algorithms while meeting the time constraint, respectively.

Provisioning fault-tolerant scheduling in computational grid is a challenging task. Most of the existing fault tolerant scheduling schemes are either geared toward proactive or reactive. Proactive schemes emphasize on the reasons responsible for generating faults, whereas reactive mechanisms come into effect after failure detection. Unlike most existing mechanisms, we present a novel, dynamic, adaptive, and hybrid fault-tolerant scheduling scheme based on proactive and reactive approaches. In the proactive approach, the resource filtration algorithm picks resources based on resource location, availability, and reliability. Unlike most existing schemes, which rely on remotely connected resources, the proposed algorithm prefers to employ locally available resources as they might have less failure tendency. To cope with the frequent turnover problem, the proposed scheme calculates resource availability time based on various newly identified parameters (e.g., mean time between availability) and picks highly available nodes for task execution. Resource reliability is an indispensable consideration in the proposed scheme and is calculated based on parameters such as jobs success or failure ratio and the types of failures encountered. We employ an optimal resource identification algorithm to determine and select optimal resources for job execution. The performance of the proposed scheme is validated through the GridSim toolkit. Compared with contemporary approaches, experimental results demonstrate the effectiveness and efficiency of the proposed scheme in terms of various performance metrics, such as wall clock time, throughput, waiting and turnaround time, number of checkpoints, and energy consumption.

Efficient energy management and fault tolerance are two key issues that demand judicious handling while scheduling real-time task-sets. Standby-sparing technique is available in literature for fault tolerance, while dynamic power management (DPM) and dynamic voltage scaling (DVS) schemes are exploited for energy management. However, usage of auxiliary processor for running backup jobs leads to increased energy consumption making fault tolerant scheduling energy inefficient. In the current work, overloading of backup jobs in overlapping time intervals is proposed, implemented and investigated for reducing energy consumption on auxiliary processor for scheduling real-time periodic tasks. Two energy efficient fault tolerant scheduling algorithms FEED-O and FEED-OD are proposed and extensive performance analysis through simulations is carried out indicating their usefulness especially at higher task-set utilization in comparison to other state-of-the-art algorithms.

Fog environment is a distributed system model that can utilise the processing abilities of fog devices (FDs) and is growing as an essential platform for IoT. Network failures become inevitable, with the growing scale of IoT. To achieve high performance, should attend to communication reliability. Fault tolerance becomes a necessary matter to enhance the reliability of the fog. Notably, fault tolerance studies have been performed only on the cloud system. To counter this issue, we propose a novel fault-tolerant scheduling algorithm for hybrid modules in fog. One of the main innovations of this approach is a classification method for different modules by the side of computing the energy consumption of all fog nodes and finding minimal fog node's energy consumption. Proposing ECRBC model, which composes the profits of extended checkpoint-restart and primary back up model with classification, is leading to superior energy-efficiency and reliability. We evaluate the performance of the proposed method by comparing it with four methods in terms of delay, energy consumption, execution cost, network usage, and total executed modules. Analysis and simulation results show, our method augments high reliability and efficiency to the system.

Fault tolerance plays an important role in guaranteeing the reliability of cloud systems. Task scheduling is an efficient approach to realize fault tolerance. Existing periodic task scheduling algorithms typically consider homogeneous processors. However, the cloud systems consist of heterogeneous hosts and virtual machines. In this paper, we propose a fault-tolerant scheduling algorithm for periodic real-time tasks in clouds (FTPC). The FTPC algorithm sufficiently considers the elasticity and heterogeneity of cloud computing. Moreover, the widely-used Fault-Tolerant Rate-Monotonic First-Fit scheduling algorithm is tailored to meet the characteristics of clouds. Simulation experiments are conducted to evaluate the feasibility and effectiveness of FTPC.

Fault tolerant scheduling of many jobs in an environment with millions of unpredictable nodes is not an easy issue. To the best of our knowledge, no work in the literature has proposed a solution that combines the merits of active and passive replication schemes of fault tolerance with the advantages of performance-driven load balancing so as to make the most of the strong points of each. While extensive fault tolerant scheduling and load balancing methods have been presented for the sequential jobs, none have taken into account fault-tolerant load balancing that minimizes the job make-span, provides efficient network and node utilization, achieves a Ill-balanced load and high system flexibility even during the resource failures. Hence, in this article, I present an Adaptive Scheduling Algorithm namely ASA that overcomes these problems. With thorough simulations, I conclude that ASA allocates any number of jobs to a million nodes with relatively low overhead and high flexibility. Experimental results show that the performance of ASA is better than those of its counterparts.

Fault-tolerance plays an important role in improving the reliability of multiple earth-observing satellites, especially in emergent scenarios such as obtaining photographs on battlefields or earthquake areas. Fault tolerance can be implemented through scheduling approaches. Unfortunately, little attention has been paid to fault-tolerant scheduling on satellites. To address this issue, we propose a novel dynamic fault-tolerant scheduling model for real-time tasks running on multiple observation satellites. In this model, the primary-backup policy is employed to tolerate one satellite’s permanent failure at one time instant. In the light of the fault-tolerant model, we develop a novel f ault- t olerant s atellite s cheduling algorithm named FTSS. To improve the resource utilization, we apply the overlapping technology that includes primary-backup copy overlapping (i.e., PB overlapping) and backup-backup copy overlapping (i.e., BB overlapping). According to the satellites characterized with time windows for observations, we extensively analyze the overlapping mechanism on satellites. We integrate the overlapping mechanism with FTSS, which employs the task merging strategies including primary-backup copy merging (i.e., PB merging), backup-backup copy merging (i.e., BB merging) and primary-primary copy merging (i.e., PP merging). These merging strategies are used to decrease the number of tasks required to be executed, thereby enhancing system schedulability. To demonstrate the superiority of our FTSS, we conduct extensive experiments using the real-world satellite parameters supplied from the satellite tool kit or STK; we compare FTSS with the three baseline algorithms, namely, NMFTSS, NOFTSS, and NMNOFTSS. The experimental results indicate that FTSS efficiently improves the scheduling quality of others and is suitable for fault-tolerant satellite scheduling.

In the article ‘Supervisory control for fault-tolerant scheduling of real-time multiprocessor systems with aperiodic tasks’, Park and Cho presented a systematic way of computing a largest fault-tolerant and schedulable language that provides information on whether the scheduler (i.e., supervisor) should accept or reject a newly arrived aperiodic task. The computation of such a language is mainly dependent on the task execution model presented in their paper. However, the task execution model is unable to capture the situation when the fault of a processor occurs even before the task has arrived. Consequently, a task execution model that does not capture this fact may possibly be assigned for execution on a faulty processor. This problem has been illustrated with an appropriate example. Then, the task execution model of Park and Cho has been modified to strengthen the requirement that none of the tasks are assigned for execution on a faulty processor.

As heterogeneous systems have been deployed widely in various fields, the reliability become the major concern. Thereby, fault tolerance receives a great deal of attention in both industry and academia, especially for safety critical systems. Such systems require that tasks need to be carried out correctly in a given deadline even when an error occurs. Therefore, it is imperative to support fault-tolerance capability for systems. Scheduling is an efficient approach to achieving fault tolerance by allocating multiple copies of tasks on processors. Existing fault-tolerant scheduling algorithms realize fault tolerance without energy limit. To address this issue, this paper proposes an energy-aware fault-tolerant scheduling algorithm DRB-FTSA-E. The algorithm adopts the active replication strategy and uses a high utilization of energy consumption to complete a set of tasks with given reliability and time constraints. It finds out all schemes that meet time and system reliability constraints, and chooses the scheme with the maximum utilization of energy consumption as the final scheduling scheme. Experimental simulation results show that the proposed algorithm can effectively achieve the maximum utilization of energy consumption while meeting the reliability and time constraints.

Autonomic fault tolerant scheduling is now a mandatory approach for the execution of performance-motivated Cloud applications such as scientific workflows. Since concurrent engineering is strongly associated with scientific workflows, an efficient scheduling for scientific workflows can have major impact on the performance of concurrent systems and engineering applications in Cloud computing. To facilitate the execution of concurrent tasks in scientific workflows, Cloud providers entail efficient scheduling heuristics and fault tolerant approaches. The work presented in this article formulates an effort focusing on this research problem to design an autonomic fault tolerant scheduling approach for scientific workflow applications. First, hybrid heuristic has been proposed to schedule scientific workflows effectively. Second, fault tolerant technique has been implemented using virtual machine migration approach that migrates the virtual machine automatically in case of task failure occurrences due to the overutilization of resources. Furthermore, the proposed approach has been validated through performance evaluation parameters using CloudSim and WorkflowSim toolkits. The simulation results demonstrate the effectiveness of the proposed approach to improve the performance of scientific workflows by appreciably reducing total mean execution time, standard deviation time, and makespan.

Redundancy is incorporated in safety critical systems for dependability and in traditional redundant systems, computing resources are inefficiently utilized under fault free condition. In this paper, an algorithm Resource Reclaimed Scheme (RR scheme) has been developed for scheduling of periodic tasks with critical aperiodic task arrivals in m-redundancy framework with resource augmentation. A novel task allocation and scheduling ensures effective resource utilization and simultaneous fault tolerant capability with graceful degradation. The proposed algorithm guarantees enhanced performance under fault free condition and less than full functionality up to m-1 faults. An earlier work has dealt with a similar dual system and this paper aims at a generalized m-processor scheme and in both cases, a comparison with the traditional redundant scheme has been studied for the significant impact of this novel idea. As a case study, an Avionic Mission System has being considered and simulation and performance evaluation validating the frame work. An effective use of computing resources and improved process speedup which are critical measures for avionics systems, specially the fuel/weight ratio can have wide ramifications and contribute significantly in enhanced performance capability.

For mission critical applications like Avionics, dependability is to avoid consequences of catastrophic results. Traditionally fault tolerance is implemented using hardware redundancy, the higher the redundancy, greater the cost and possibilities of more failures occurring. In this paper, an adaptive fault tolerant scheduling mechanism developed earlier with augmented performance capability and online fault recovery for a dual redundant system has been extended for an avionics mission system. An algorithm has been developed, simulated and evaluated on the practical case study vis –a- vis a traditional dual redundant system. This paper also roposes an extension of earlier scheme to schedule arrival of either/and critical and non -critical aperiodic tasks. The augmented scheme helps to achieve full functionality when no fault occurs, a fail safe mechanism for a single fault and performance metrics highlights the better computational performance. It elucidates that the use of this adaptive model leverages better in terms of enhanced performance and throughput compared to the existing dual redundant systems.

OF THE DISSERTATION ENERGY-AWARE FAULT-TOLERANT SCHEDULING FOR HARD REAL-TIME SYSTEMS by Qiushi Han Florida International University, 2015 Miami, Florida Professor Gang Quan, Major Professor Over the past several decades, we have experienced tremendous growth of realtime systems in both scale and complexity. This progress is made possible largely due to advancements in semiconductor technology that have enabled the continuous scaling and massive integration of transistors on a single chip. In the meantime, however, the relentless transistor scaling and integration have dramatically increased the power consumption and degraded the system reliability substantially. Traditional real-time scheduling techniques with the sole emphasis on guaranteeing timing constraints have become insufficient. In this research, we studied the problem of how to develop advanced scheduling methods on hard real-time systems that are subject to multiple design constraints, in particular, timing, energy consumption, and reliability constraints. To this end, we first investigated the energy minimization problem with fault-tolerance requirements for dynamic-priority based hard real-time tasks on a single-core processor. Three scheduling algorithms have been developed to judiciously make tradeoffs between fault tolerance and energy reduction since both design objectives usually conflict with each other. We then shifted our research focus from single-core platforms to multi-core platforms as the latter are becoming mainstream. Specifically, we launched our research in fault-tolerant multi-core scheduling for fixed-priority tasks

The past decade has witnessed the rapid development of cloud computing. Virtualization, which is the fundamental technique in providing Infrastructure as a Service (IaaS), has led to an explosive growth of the cloud computing industry. Fault-tolerance is a significant requirement of cloud computing due to the Service Level Agreements (SLA). In order to achieve high reliability and resilience of real-time systems in virtualized clouds, a Virtualization-based Fault-Tolerant Scheduling (VFTS) algorithm is proposed. In this paper, fault tolerance is implemented by using primary-backup approach. VFTS is designed for periodic and preemptive tasks in homogeneous environment. Simulation results demonstrate an impressing saving of processing resources compared with those needed by the dual-system hot backup approach, which proves the feasibility and effectiveness of the proposed VFTS algorithm.

Fault-tolerance is very important in hard real-time heterogeneous systems, especially in safety-critical systems, since faults can result in a disaster. Such systems require that an application can operate normally even when a processor is subject to failures under a given time constraint. In this paper, we tackle the problem of scheduling tasks on heterogeneous systems with the constraint of time and the ability of fault-tolerance, while considering communication overhead. The problem is NP-hard and we propose a heuristic algorithm DB-FTSA to solve it. The heuristic algorithm is based on an active replication scheme, capable of supporting several transient failures. It incorporates the reliability calculation into the active replication scheme, and can dynamically find out fault-tolerant tasks. Experimental results demonstrate that our proposed algorithm can effectively improve the system reliability under the given time constraint.

Predictable performance when coping with transient failures is of paramount importance in safety-critical real-time systems. Various software fault-tolerant techniques are employed towards this goal among which check-pointing is a relatively cost-effective scheme. In this paper, we propose an efficient fault-tolerant scheduling framework with run-time fault handling protocol, where criticality levels can be adaptively inserted for fault handling according to run-time fault workload. In contrast to prior works which apply with task re-execution strategy, the proposed framework adaptively determines on-demand re-executions only on the faulty checkpoint segments, rather than on the whole job. Towards this, a unified overrun handling protocol is developed to handle fault recovery adaptively to avoid over-provisioning of resources. In addition, we develop an off-line schedulability analysis technique for the proposed scheduling algorithm. The simulation results show that our fault-tolerant scheduling framework can bring up to 81% improvement in supporting low-criticality service without sacrifice in the MC-schedulability compared with the existing techniques.

To classify the reliable resources accurately and perform a proactive fault tolerant scheduling in grid computing environment, a combination of support vector machine (SVM) with the quantum-behaved...

As large parallel systems increase in size and complexity, failures are inevitable and exhibit complex space and time dynamics. Most often, in real systems, failure rates are increasing or decreasing over time. Considering non-memoryless failure distributions, we study a bi-objective scheduling problem of optimizing application makespan and reliability. In particular, we determine whether one can optimize both makespan and reliability simultaneously, or whether one metric must be degraded in order to improve the other. We also devise scheduling algorithms for achieving (approximately) optimal makespan or reliability. When failure rates decrease, we prove that makespan and reliability are opposing metrics. In contrast, when failure rates increase, we prove that one can optimize both makespan and reliability simultaneously. Moreover, we show that the largest processing time (LPT) list scheduling algorithm achieves good performance when processors are of uniform speed. The implications of our findings are the accelerated completion and improved reliability of parallel jobs executed across large distributed systems. Finally, we conduct simulations to investigate the impact of failures on the performance, which is done using an actual application of biological sequence comparison.

Real-time systems are one of the most important applications of computers, both in commercial terms and in terms of social impact. Increasingly, real-time computers are used to control life-critical applications and need to meet stringent reliability conditions. Since the reliability of a real-time system is related to the probability of meeting its hard deadlines, these reliability requirements translate to the need to meet critical task deadlines with a very high probability. We survey the problem of how to schedule tasks in such a way that deadlines continue to be met despite processor (permanent or transient) or software failure.

In this paper, we propose a fault-tolerant scheduling heuristic that achieves low energy consumption and high reliability efficiency. Our scheduling algorithm is dedicated to multi-bus heterogeneous architectures, which take as input a given system description and a given fault hypothesis. It is based on active redundancy to mask a fixed number k of failures supported in the system, so that there is no need for detecting and handling such failures. In order to maximize the system's reliability, the replicas of each operation are scheduled on different reliable processors. Finally, we show with an example that our approach can maximize reliability and reduce energy consumption when using active redundancy. 

Task workload analysis for primary-alternate fault-tolerance is usually performed based on WCET (Worst-Case Execution Time), which causes excessive redundancy of processor resource reservation in conventional real-time systems. To address this issue, a novel primary-alternate fault-tolerant model based on a variable workload is built, theorems for both the alternate schedulability and the primary execution success ratio is proposed, and their correctness are proved. Motivated by these theorems, a new algorithm called BCEVW (BCE with Variable Workload) is proposed through improving the algorithm BCE. Further, a new error probability model for the primary version is proposed, which is closer to the practice than does the conventional model. Using two metrics including schedulability of a task set and execution success ratio of the primary version, simulation results show that (1) for scheduling task sets in the alternate version, backwards-EDF algorithm performs better than backwards-RM algorithm, and the necessary and sufficient conditions for its schedulability is that the processor utilization is no more than 1; (2) in the case of variable workload, BCEVW algorithm can significantly improve the schedulability of task sets in the primary version; (3) for the new error probability model, the results of the proposed scheduling algorithm show that there is an obvious linear relationship between the error probability and execution success ratio of the primary version, and further the greater processor utilization of the primary version is, the more significant linear relationship is.

This paper presents a fault-tolerant scheduling algorithm called SFTS that can tolerate multiple failures for critical tasks with survivability demand in heterogeneous system. In order to achieve this objective, models of cost and reliability based on the concept of accumulated reliability are built. Also, we design the algorithm SFTS in three steps to achieve the survivable task scheduling, where the perfect node resource is first selected, the scheduling path is then determined, and lastly the critical tasks are scheduled to the selected resources. We let the critical tasks be executed before the non-critical tasks and rank all the critical tasks to ensure guarantee ratio of critical tasks. We conduct extensive experiments to compare our SFTS with three existing schemes. Results demonstrate the effectiveness of our SFTS.

Mixed-criticality systems are real-time systems that combine both safety-critical and non-critical applications. These systems have been gaining interest due to their practical applications and their adoption in standards in several domains. On the other hand, it is often overlooked in the research on mixed-criticality systems that these systems are still safety critical and must be able to operate even when the system's processors fail. In this paper, we present an approach to design multicore mixed-criticality systems that can survive permanent processor failures. Under the proposed work, critical tasks executing on the failing cores are migrated to other cores to allow them to continue execution. Space is made on the new cores by dropping non-critical tasks. Schedulability analysis is developed by extending the AMC-rtb analysis to support processor failures. The problem of finding a mixed-criticality system configuration on a multicore architecture is formulated as a Mixed Integer Linear Programming (MILP) problem. The MILP produces a system design that is schedulable on the underlying platform and tolerant to processor failures.