2003 · 32 citations · 6 references
ComputingComputer EngineeringComputer SystemsCapacity PlanningReal-time SystemsSchedulingFinite Capacity SchedulingLinear SchedulingOnline SchedulingReal-time SchedulingSchedulability AnalysisScheduling TheoryAperiodic Task SchedulingFixed-priority Scheduling AnalysisOnline Interval SchedulingOnline Real-time SchedulingOverhead AnalysisPeriodic Task SchedulingSlack ManagementSporadic Task Scheduling
The paper presents linear time, online algorithms which guarantee and jointly schedule firm aperiodic, hard sporadic and periodic tasks in fixed priority real time systems. We develop and capitalize on a methodology which computes the spare capacity Z(a,b) exactly in time /spl Theta/(n), for arbitrary schedule intervals (a,b), which, to the best of our knowledge, is the first linear time algorithm reported in the literature. Previous state of the art methods incur pseudopolynomial time to guarantee online a single aperiodic and incur continuous overhead for slack maintenance. Our method guarantees and schedules firm tasks to receive FIFO or EDF service, incurring a one-time linear cost of /spl Theta/(n) and /spl Theta/(n+k) respectively, where k is the number of pending firm tasks.
6
Scheduling slack time in fixed priority pre-emptive systems
Robert I. Davis, K. Tindell, Alan Burns · 2002 · 244 citations