Patent ID: 10296382

Abstract:
Earliest deadline first (EDF) scheduling algorithm is the most celebrated result for dynamic priority scheduling in real-time systems for both preemptive and non-preemptive cases. From complexity point of view, EDF is polynomial for preemptive scheduling of tasks. However, it becomes pseudo-polynomial under non-preemptive case. Described herein is a technique that determines EDF feasibility of non-preemptive task set by analyzing schedulability of the lowest priority task at common scheduling points generated by all higher priority tasks in the task set. The adjustment results in improving the computational cost of an existing test from O(n2 pn/p1) to O(pn/p1), where n is the number of tasks in the system, while pn and p1 represent the task periods of largest and smallest periodic tasks respectively. With reduced computation cost, the described method of analyzing feasibility can be intergraded with online systems for testing feasibility of a special class of real-time systems under non-preemptive case.