Resource reclaiming in multiprocessor real-time systems

Abstract

Most real-time scheduling algorithms schedule tasks with regard to their worst case computation times. Resources reclaiming refers to the problem of utilizing the resources left unused by a task when it executes in less than its worst case computation time, or when a task is deleted from the current schedule. Resource reclaiming is a very important issue in dynamic real-time multiprocessor environments. In this paper, we present dynamic resource reclaiming algorithms that are effective, avoid any run time anomalies, and have bounded overhead costs that are independent of the number of tasks in the schedule. Each task is assumed to have a worst case computation time, a deadline, and a set of resourcerequirements. The algorithms utilize the information given in a multiprocessor task schedule and perform on-line local optimization. The effectiveness of the algorithms is demonstrated through simulation studies.