Greedy scheduling with feedback control for overloaded real-time systems

In real-time systems, a task is required to be completed before its deadline. When workload is heavy, the system may become overloaded. Under such condition, some tasks may miss their deadlines. To deal with this overload problem, the design of scheduling algorithm is crucial. In this paper, we focus on studying on-line scheduling for overloaded realtime systems. The objective is to maximize the total number of tasks that meet their deadlines. To achieve this goal, the idea of greedy algorithm is used to propose a greedy scheduling (GS) algorithm. In each time, GS makes an optimum choice for currently known task set. As the uncertainty of new arriving tasks, GS cannot make an optimum choice for the set of overall tasks. To deal with this uncertainty, by applying feedback control, a greedy scheduling with feedback control (GSFC) is introduced. Three widely used scheduling algorithms and their corresponding deferrable scheduling (DS) methods are discussed and compared with GSFC. Simulation results reveal that GSFC can effectively improve the system performance.