DPSC: A Novel Scheduling Strategy for Overloaded Real-Time Systems

For real-time systems, the correctness of system behavior depends on not only the computed results but also on the time at which results are produced. This requires tasks in such systems to be completed before their deadlines. However, when workload is heavy, the system may become overloaded. Under such condition, some tasks may miss their deadlines. When this problem happens, it is important to minimize the degrees of system performance degradation. To achieve this objective, the design of scheduling algorithm is crucial. In this paper, we focus on designing on-line scheduling algorithm to maximize the total number of tasks that meet their deadlines. The idea of dynamic programming is used to present a dynamic programming scheduling (DPS) algorithm. In each time, DPS makes an optimum choice for currently known task set. As the uncertainty of new arriving tasks, DPS cannot make optimum choice for the set of overall tasks. To deal with this uncertainty, by applying a congestion control mechanism, a dynamic programming scheduling with congestion control (DPSC) is introduced. Three widely used scheduling algorithms and their corresponding deferrable scheduling (DS) methods are discussed and compared with DPSC. Simulation results reveal that DPSC can effectively improve system performance.