2019/11/30 by Thi Huyen Chau Nguyen, Nguyen, Thi Huyen Chau, Werner Grass +3
Computer Science · Engineering · #Distributed and Parallel Computing Systems #Distributed systems and fault tolerance #Embedded Systems Design Techniques #FOS: Computer and information sciences #Operating Systems (cs.OS) #Real-Time Systems Scheduling #Scheduling and Optimization Algorithms
paper · pdf · doi:10.48550/arxiv.1912.01161
openalex publication_date 2019/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In some important application areas of hard real-time systems, preemptive\nsporadic tasks with harmonic periods and constraint deadlines running upon a\nuni-processor platform play an important role. We propose a new algorithm for\ndetermining the exact worst-case response time for a task that has a lower\ncomputational complexity (linear in the number of tasks) than the known\nalgorithm developed for the same system class. We also allow the task\nexecutions to start delayed due to release jitter if they are within certain\nvalue ranges. For checking if these constraints are met we define a constraint\nprogramming problem that has a special structure and can be solved with\nheuristic components in a time that is linear in the task number. If the check\ndetermines the admissibility of the jitter values, the linear time algorithm\ncan be used to determine the worst-case response time also for jitter-aware\nsystems.\n