2003 · 23 citations · 14 references
ComputingComputer EngineeringComputer ScienceEmbedded SystemsReal-time SystemsSchedulingRate Monotonic SchedulingReal-time ControlReal-time SchedulingReal-time Systems DesignSchedulability AnalysisTask SchedulingBoolean FunctionsComplexity Of Boolean FunctionsMinimization Of Boolean FunctionsPriority AssignmentReal-time Task Scheduling
When applying the Rate Monotonic discipline to schedule a set of periodic preemptible real-time tasks, the scheduler may be able to distinguish only a limited number of priority levels. This is common in control applications using low cost embedded controllers. If the number of tasks to be scheduled is larger than the number of distinguishable levels, the set of tasks must be partitioned in a set of priority classes. RM can be used only to arbitrate conflicts between tasks of different classes. In this paper a method to determine the minimum number of priority levels necessary to schedule the set of tasks is formally proved and its complexity analysed. Finally, a systematic method to obtain all the possible partitions with the minimum number of classes, resembling the Quine's method to minimize Boolean functions, is also given.
14
Finding Response Times in a Real-Time System
M. Joseph · The Computer Journal · 1986 · 1.2K citations · Full text
Aperiodic task scheduling for Hard-Real-Time systems
Brinkley Sprunt, Lui Sha, John P. Lehoczky · Real-Time Systems · 1989 · 905 citations