2003/07/01 by Enrico Bini, Giuseppe Buttazzo · 1 citation
Computer Science · Mathematics · #Real-Time Systems Scheduling #Embedded Systems Design Techniques #Petri Nets in System Modeling #Aperiodic graph #Monotonic function #Computer science #Upper and lower bounds #Algorithm #Concurrency #Function (biology) #Task (project management) #Set (abstract data type) #Mathematics #Combinatorics #Distributed computing
paper · doi:10.1109/tc.2003.1214341
openalex publication_date 2003/07/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/04
We propose a novel schedulability analysis for verifying the feasibility of large periodic task sets under the rate monotonic algorithm when the exact test cannot be applied on line due to prohibitively long execution times. The proposed test has the same complexity as the original Liu and Layland (1973) bound, but it is less pessimistic, thus allowing it to accept task sets that would be rejected using the original approach. The performance of the proposed approach is evaluated with respect to the classical Liu and Layland method and theoretical bounds are derived as a function of n (the number of tasks) and for the limit case of n tending to infinity. The analysis is also extended to include aperiodic servers and blocking times due to concurrency control protocols. Extensive simulations on synthetic tasks sets are presented to compare the effectiveness of the proposed test with respect to the Liu and Layland method and the exact response time analysis.