Integrating Sporadic Events in Time-triggered Systems via Affine Envelope Approximations

We introduce a new paradigm for synthesizing time-triggered schedules that guarantees the correct temporal behavior of time-triggered (TT) tasks and the schedulability of sporadic event-triggered (ET) tasks with arbitrary deadlines at design time. The approach first expresses a constraint for the TT task schedule in the form of a maximal affine envelope that ensures that as long as the schedule generation respects this envelope, all sporadic ET tasks meet their deadline. The second step consists of modeling this envelope as a burst limiting constraint (BLC) and building the schedule. The BLC constraint can be added to any existing TT schedule generation method as an additional constraint on the TT slot positioning. Here, we propose an efficient TT schedule generation method that integrates the BLC constraint via simulating a modified Least-Laxity-First (LLF) scheduler. We show via synthetic and real-world test cases that our novel method achieves better schedulability and a faster schedule generation for most use cases compared to other approaches inspired by, e.g., hierarchical scheduling. Moreover, we present an extension to our method that finds the most favorable schedule for TT tasks with respect to ET schedulability, thus increasing the probability that the system remains feasible when ET tasks are later added or changed.