Scheduling Strategy in Fault Tolerant Time Triggered Architectures

Author Name(s): B Abdul Rahim*, K Soundara Rajan
Author Email: abraheem@rediffmail.com

Abstract

Reliable safety critical systems are designed for fault tolerance and impose high dependability with reliability requirements. Scheduling such systems is hard in traditional event triggered systems and becomes difficult as complexity increases. Time triggered systems with timing guaranteed in task activation, avoiding the risk of missing a hard-critical deadline, overcoming the problem of time predictability. As time triggered pattern is going to take control in safety critical applications, gradually scheduling strategies to be more robust and optimal in resource allocation. Previous work has been on handling the schedule of messages within the time triggered protocol for a given TDMA configuration. The sequence and size of slots in a TDMA round are resolved to reduce the delay. Greedy heuristic and meta-heuristics like Simulated Annealing, Genetic algorithms etc., are investigated for better optimization. The Greedy Algorithm works on arriving at global optima by selecting a local optimum. The worst case here is the visit of all the nodes for best possible solution. Randomly each member is selected from the neighborhood in the simulated annealing process, thereby determining the movement to next state. Simulated Annealing parameters make easy in finding near-optimal solutions within a reasonable time. The selection, crossover and mutation, are the fundamental genetic operations of Genetic Algorithm used to modify the solution to obtain appropriate resultant offspring passing on features to succeeding generations. Genetic Algorithm scheduling in fault tolerant time triggered architectures show significant performance improvement when nodes are large in number and guaranteed for optimal solution.

Keywords

Safety Critical Systems, Time triggered Systems, Scheduling Algorithms.

Introduction

A system is said to be critical, if its malfunction leads to economic loss and/or loss of life. Hence the system to be safety critical should possess highest level of safety integrity; malfunction may cause serious consequences [1]. Reliability is the probability of no failures in the interval; this is the measure of performance for fault tolerant systems. Hence for applications of high level of safety, fault tolerant design is must [2]. Dependability is the ability of a system to deliver the service that can be trusted justifiably. The service delivered by a system as it is perceived by other which is interacting with it [3]. So the systems required to function properly while obeying the properties of cost and performance, further providing high dependability despite fault occurrences.

Conclusions

From the above discussions it is found that the best solution for optimized allocation of tasks to the nodes depends upon the number of nodes and number of tasks. The experiments were carried out with the nodes providing composability i.e, fail safe property of the architecture. With fewer nodes and less constraints, the scheduling can be simpler with Greedy algorithm.Whereas for large number of nodes the simulated annealing can be used, although constraints increases the computation time increases and it may not yield to global optimum solution. The best results are with use of Genetic algorithm, even though the number of iterations it takes is large but best result can be obtained, which can be the optimal solution. The convenient methods search from a single point, whereas GA operates on whole population of points (strings). This makes it more robust and chances of reaching to the global optimum. Thereby reducing the risk of trapped in a local optimum point. If multiple schedules are used, the scheduling time can be decreased drastically by using Genetic heuristic algorithm.

629 total views, no views today

Download PDF File

About the author: admin