Sporadic task scheduling with overload conditions

Hard real-time task scheduling in a dynamic environment has been an importa nt area of research, posing difficult problems. In an overloaded system whe re periodic and sporadic tasks have computational demands that are greater than the CPU time in that interval, the scheduler faces the question of whi ch tasks must really make their deadlines. Assuming that periodic tasks hav e priority over sporadic ones, we end up with a system where some sporadic tasks may not make their deadlines. It is known that through the assignment of priorities to tasks based on the earliest deadline policy, there is no way to predict which sporadic task will miss the deadline and which will no t. In order to prevent important sporadic tasks from missing their deadline s, we assign each task an importance function that is used by the schedulin g algorithm. Generally, the summation of important function values must be maximized to allow the most important tasks to meet their timing constraint s. We present two novel scheduling algorithms that try to maximize this sum mation. We show that these algorithms have better performance compared to r elated algorithms regarding complexity and benefit optimization. (C) 1998 E lsevier Science Ltd. All rights reserved.