A Binary-Tree Architecture for Scheduling Real-Time Systems with Hard and Soft Tasks

Complex real-time systems require jointly schedule both periodic task and aperiodic tasks with hard and soft deadlines. This problem has been subject of considerably research in real-time systems and one of the most widely accepted solutions are dynamic slack stealing algorithms (DSS) for scheduling aperiodic tasks, running with earliest deadline first (EDF) algorithms for scheduling periodic ones. However, these algorithms are rather impractical, since they all imply a considerably scheduling overhead that always results in delays and reduced CPU utilization. One of the proposed solutions to this problem is doing scheduling in hardware. This paper follows this approach and analyzes in depth a hardware design based on binary trees. The proposed solution is a circuit that behaves as a sort of sophisticated interrupt controller whose inputs are the task workload and the interrupts, and whose output interrupts the CPU exclusively when a task switch should occur, providing the identifier of the task to be resumed (the highest priority task)