CprE 458/558: Real-Time SystemsDynamic Scheduling ModelResource ReclaimingProperties of Reclaiming AlgorithmsResource Reclaiming AlgorithmsReclaiming -- ExampleReclaiming – Example (contd.)CprE 458/558: Real-Time Systems (G. Manimaran) 1CprE 458/558: Real-Time Systems Resource ReclaimingCprE 458/558: Real-Time Systems (G. Manimaran) 2Dynamic Scheduling Model•Schedulability checking (on-line) - by the scheduler •Schedule construction (on-line) - by the scheduler •Dispatching, Task execution, & Resource reclaiming - by the processorsCprE 458/558: Real-Time Systems (G. Manimaran) 3Resource ReclaimingResource reclaiming refers to the problem of utilizing resources left unused by a task when:•it executes less than its worst case computation time. The actual computation time of a task can be less than its worst case computation time due to– data dependent loops and conditional statements in the task code.–architectural features of system such as cache hits and branch predictions. •it is deleted from the current schedule. Deletion of a task takes place when extra tasks are initially scheduled to account for fault tolerance. •it is dropped to make room for more critical tasks.CprE 458/558: Real-Time Systems (G. Manimaran) 4Properties of Reclaiming Algorithms •Correctness: No run-time anomaly.•inexpensive: The overhead cost of a resource reclaiming should be very low compared to tasks’ computation times. •bounded complexity: The complexity of a resource reclaiming algorithm should be independen t of the number of tasks in the schedule. •Effectiveness: A resource reclaiming algorithm is effective only when its performance is better than that of when no resource reclaiming is used.CprE 458/558: Real-Time Systems (G. Manimaran) 5Resource Reclaiming Algorithms•Basic Algorithm: If there are “simultaneous holes,” in the schedule, it can be reclaimed.•Early Start Algorithm: reclaims resources with the condition that if two tasks are non-overlapping in the pre-run schedule, then they should not overlap in the post-run schedule. •RV Algorithm: Based on a data structure, called Restriction Vector.•RV with Migration: Allows task migration from one processor to another.CprE 458/558: Real-Time Systems (G. Manimaran) 6Reclaiming -- ExampleCprE 458/558: Real-Time Systems (G. Manimaran) 7 Reclaiming – Example
View Full Document
Unlocking...