GART: A Genetic Algorithm based Real-time System Scheduler

Hard real-time systems require that all jobs are assigned a deadline and the system is deemed to be correct only if all jobs complete execution at or before their deadlines. Such strict timing requirements add to the complexity of the scheduling problem. This complexity is exacerbated when the system is executed on a multiprocessor platform. Even so, scheduling overheads must be kept to a minimum in order for the runtime behavior to be predictable. Thus, real-time scheduling algorithms have the dual requirement of satisfying complex requirements while using fairly simple and straightforward logic. One way an algorithm may achieve this goal is to reduce the overhead due to preemption and migration by rearranging the schedule so as to increase the duration between preemptions. Unfortunately, determining how best to rearrange the jobs is an NP-Complete problem. Hence, we need to use heuristics when scheduling such systems. This leads us to ask a couple of questions. First, what is the best heuristic? Second, is the same heuristic best for all real-time systems? This paper uses a Genetic Algorithm to help us answer these questions. Our genetic algorithm based real-time system scheduler (GART) is based on the DP-Wrap scheduling algorithm. The genetic algorithm searches through a variety of candidate heuristics to determine the best heuristic for a given task set. Experimental results demonstrate that this approach is able to efficiently identify the best heuristic for all the systems we consider. Moreover, we find that the "best" heuristic does, in fact, depend of various system parameters.