Prediction-Based Asynchronous CPU-Budget Allocation for Soft-Real-Time Applications

An application is said to be soft real-time if it is able to tolerate occasional violations of its timing constraints. The overall CPU utilization of a soft real-time system can be improved by exploiting the relaxed nature of its timing constraints. One possible approach is by adapting CPU-budgets in reservation-based schedulers. Reservation-based schedulers allow parts of the system and groups of tasks to be isolated from one another. By making the reservations adaptive, resources such as CPU can be allocated to tasks based on current usage rather than worst-case usage, which can help to improve the overall utilization of CPU time committed to tasks. This paper presents an adaptive budget allocation algorithm where the allocated budget is adapted at reservation-period boundaries based on predictions of future CPU usage. This approach differs from previous algorithms where adaptations are performed on job completion. Simulation results show that adaptations at reservation-period boundaries allow for a faster response time. Results from experiments performed on a prototype demonstrate the robustness and effectiveness of the proposed system.