Polynomial time approximate schedulability tests for fixed-priority real-time tasks: some numerical experimentations

Efficient schedulability tests are required for analyz-ing large task systems or for designing on-line admission controllers. We next focus on periodic fixed-priority tasks. For fixed-priority tasks with constrained deadlines (i.e., deadlines are less than or equal to periods), no exact poly-nomial time feasibility test is known. We propose several polynomial time algorithms with performance guarantees (with an ijnput accuracy parameter) and compare them with known exact feasibility tests (running in pseudo-polynomial time) and a fully polynomial time approxima-tion scheme (FPTAS). Our main objective is to define the capabilities of such algorithms according to the system workload and an accuracy parameter defining the quality of results to compute.