A Novel Genetic Admission Control for Real-Time Multiprocessor Systems

摘要

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.