Minimizing the Worst Case Execution Time of Diagnostic Fault Queries in Real Time Systems Using Genetic Algorithm

The number of embedded systems in safety-critical applications are continuously increasing. These systems requires high level of reliability and have strict timing constraints specially in case of fault occurrence. One method to enhance the reliability and availability of these systems is to introduce the concept of optimization of diagnostic fault queries and real time database management systems. Both of them can be used to trace back failures to faults and trigger suitable recovery actions. Our major concern is the completion of diagnostic query in bounded time in order to satisfy timing constraints for fault recovery (e.g. actuator freezing). For this purpose it is important to provide a solution which can optimize the diagnostic fault queries in a manner that they can complete their execution within the pre-defined deadline of the real time system. Our proposed algorithm optimize the diagnostic fault queries using genetic algorithm, so that the overall Worst Case Execution Time (WCET) of these queries can be minimized. A diagnostic query is represented in the form of (i) Left Deep Tree (LDT) and (ii) Bushy Tree (BT). Each query tree is converted into multiple task graphs by considering different combinations of nodes (in query tree). Our genetic algorithm selects the task graph with minimum make span (scheduling length), so that the goal of fault diagnosis within the defined deadline of the real time system can be achieved. The evaluation based on our results shows that the WCET of the diagnostic queries is better in case of bushy trees and ring topology.