Real Time Scheduling Optimization

Real Time Scheduling Optimization

Fateh Boutekkouk (Research Laboratory on Computer Science's Complex Systems (ReLaCS2), University of Oum El Bouaghi, Algeria)
Copyright: © 2019 |Pages: 21
DOI: 10.4018/JITR.2019100107

Abstract

This article deals with real time embedded multiprocessor systems scheduling optimization using conventional and quantum inspired genetic algorithms. Real time scheduling problems are known to be NP-hard. In order to resolve it, researchers have resorted to meta-heuristics instead of exact methods. Genetic algorithms seem to be a good choice to solve complex, non-linear, multi-objective and multi-modal problems. However, conventional genetic algorithms may consume much time to find good solutions. For this reason, to minimize the mean response time and the number of tasks missing their deadlines using quantum inspired genetic algorithms for multiprocessors architectures. Our proposed approach takes advantage of both static and dynamic preemptive scheduling. This article has the developed algorithms on a typical example showing a big improvement in research time of good solutions in quantum genetic algorithms with comparison to conventional ones.
Article Preview
Top

1. Introduction

In the last years, Real Time Embedded Systems (RTES) are becoming omnipresent (Kasim Al-Aubidy, 2011; Kopetz, 2011; Shaw, 2001). This new technology is very attached to our daily life and can be nearly found in all domains such as transport, house electro manager, consumable electronics, games, Telecommunication, multimedia, aerospace, military, etc. RTES are reactive systems with sensors/actuators tailored to execute specific tasks that can be periodic, Aperiodic or sporadic. These tasks can be subjected to a variety of temporal constraints. The most important one is may be the deadline. In fact, RTES are classed to hard, soft or firm systems. This taxonomy depends on the deadline respect or not and its impact on the environment. RTES design faces a big challenge and must minimize the overall cost and the power consumption.

The design flow of such systems consists in several sequential or iterative steps starting from functional/non-functional requirements specification to hardware (technology dependent) implementation. The latter can be realized with ASICs, FPGA, DSP or general-purpose embedded processors connected with a shared bus, buses hierarchy with fast links or a communication network (NOC: Network On Chip) to satisfy high performance. In this context, we are interested in high level performance estimation and optimization of RTES with periodic/aperiodic tasks and hard/soft constraints targeting multiprocessors architecture. Here, we must note some differences between traditional multiprocessor architecture and RTES multiprocessor architecture. Firstly, RTES architecture is based on distributed memory and not shared memory. Secondly, RTES architecture includes generally an RTOS (Real Time Operating System) implemented as a kernel without conventional files, complex I/O or memory management mechanisms (like pagination). RTOS is focused on Real Time Scheduling (Andersson et al., 2000; Anderson et al., 2005; Chéramy et al., 2012; Lalatendu et al., 2012; Zhang et al., 2012). An important difference is at the microprocessor level. Embedded processor is characterized by low clock frequency, low memory capacity and low power consumption. An embedded processor may change its frequency dynamically due to the DVS (Dynamic Voltage Scaling) strategy. DVS enables designers to compromise between tasks deadlines and power consumption.

As it has been known, the scheduling problem is NP-hard. This problem can be resolved using meta-heuristics. A meta-heuristic is applied on a vast class of problems with imprecise or incomplete data.

GAs appear a good choice for solving complex, non-linear, multi-objective and multi-modal problems that is the case in RTES. We can for instance optimize many objectives like response time, power consumption, the processor usage ratio, etc. However conventional genetic algorithms may consume much time to find good solutions. For this reason, a new class of genetic algorithms inspired from the quantum mechanics called Quantum Inspired Genetic Algorithms (QIGA) has been developed (Grover, 1996; Han, 2000; Laboudi et al., 2012; Layeb et al., 2007; Shor, 1994). These algorithms try to simulate some quantum principles found in mechanics such as state superposition to reduce the research time for good solutions. Our effective contributions reside in the proposition of a mix RTES model that integrates periodic and Aperiodic tasks with hard and soft constraints and to apply QIGA to minimize tasks mean response time and the number of tasks missing their deadlines on a multiprocessor architecture under the idea of balancing between processors usages ratios. Our proposed approach takes advantage of both static and dynamic preemptive scheduling. In fact, and in order to compare the performance of QIGA with conventional GAs (CGA), we have implemented four techniques called SCGA (Static Conventional Genetic Algorithm), DCGA (Dynamic Conventional Genetic Algorithm), SQIGA (Static Quantum Inspired Genetic Algorithm) and DQIGA (Dynamic Quantum Inspired Genetic Algorithm).

Complete Article List

Search this Journal:
Reset
Open Access Articles
Volume 13: 4 Issues (2020): 2 Released, 2 Forthcoming
Volume 12: 4 Issues (2019)
Volume 11: 4 Issues (2018)
Volume 10: 4 Issues (2017)
Volume 9: 4 Issues (2016)
Volume 8: 4 Issues (2015)
Volume 7: 4 Issues (2014)
Volume 6: 4 Issues (2013)
Volume 5: 4 Issues (2012)
Volume 4: 4 Issues (2011)
Volume 3: 4 Issues (2010)
Volume 2: 4 Issues (2009)
Volume 1: 4 Issues (2008)
View Complete Journal Contents Listing