Extending Periodic Task Sets with Sporadic Tasks: Computational Complexity and Exact Feasibility Tests

Given a periodic task system that is guaranteed to be schedu-lable upon a preemptive uniprocessor, this paper addresses the problemof determining whether schedulability is preserved upon the addition of aset of sporadic tasks. The precise computational complexity of the prob-lem is established, and exact tests are designed, formally proven correct,and evaluated experimentally to assess their practicality for runtime de-ployment.