The integration of deadline and criticalness in hard real-time scheduling

Abstract

Two task-scheduling algorithms for distributed hard real-time computer systems are presented. Both algorithms are based on a heuristic approach and explicitly account for both the deadlines and criticality of tasks when making scheduling decisions. In analyzing the algorithms, a performance metric called the weighted guarantee ratio is defined. It reflects both the percentage of tasks that make their deadlines and their relative worth to the system. The performance is analyzed by simulating the behavior of the algorithms as well as that of several other pertinent baseline algorithms under a wide range of system conditions including a nonhomogeneous task arrival rate. The results show that the algorithms outperform all the baseline algorithms except for the ideal but impractical centralized baseline and in many cases perform close to the ideal.