Title :
A Novel Genetic Admission Control for Real-Time Multiprocessor Systems
Author_Institution :
Syst. Platforms Res. Labs., NEC Corp., Kawasaki, Japan
Abstract :
In real-time multiprocessor systems, admission control must respond to the requests of tasks quickly, otherwise some requests have to be rejected even if there are enough resources to meet the requirements of tasks running. Real-time task scheduling in multiprocessor systems has been proved to be NP-hard problems. Genetic algorithms (GAs) are known as a class of effective tools to solve NP problems, but the execution time of GAs is usually very long. In this paper, we present a novel approach of using genetic algorithms in real-time task admission control and scheduling. First our approach preserves the population of the GA and tries to use the historical information, i. e., the previous task schedules, to shorten the search time, instead of destroying and creating a population respectively after and before dealing with a new task in the standard GA procedure; second our approach dynamically updates the chromosomes in the population in terms of task arrivals and departures in order to repeatedly reuse the preserved population. Through simulations, it is demonstrated that our approach can rapidly make admission decisions and produce task schedules, meanwhile with satisfying task acceptance ratio and low preemption frequency.
Keywords :
computational complexity; genetic algorithms; multiprocessing systems; real-time systems; scheduling; NP-hard problems; genetic admission control; genetic algorithms; real-time multiprocessor systems; task acceptance ratio; task scheduling; tasks running; Admission control; Genetics; Multiprocessing systems; Real time systems; Admission Control; Genetic Alogirithm; Multiprocessor; Real-time;
Conference_Titel :
Parallel and Distributed Computing, Applications and Technologies, 2009 International Conference on
Conference_Location :
Higashi Hiroshima
Print_ISBN :
978-0-7695-3914-0
DOI :
10.1109/PDCAT.2009.10