Feasibility analysis of fixed priority systems has been widely studied in the real-time literature and several acceptance tests have been proposed to guarantee a set of periodic tasks. They can be divided in two main classes: polynomial time tests and exact tests. Polynomial time tests are used for on-line guarantee of dynamic systems, where tasks can be activated at runtime. These tests introduce a negligible overhead, when executed upon a new task arrival, however provide only a sufficient schedulability condition, which may cause a poor processor utilization. On the other hand, exact tests, which are based on response time analysis, provide a necessary and sufficient schedulability condition, but are too complex to be executed on line for large task sets. As a consequence, for large task sets, they are often executed off line. This paper proposes a novel approach for analyzing the schedulability of periodic task sets under the Rate Monotonic priority assignment. Using this approach, we derive a new schedulability test which can be tuned through a parameter to balance complexity vs. acceptance ratio, so that it can be used on line to better exploit the processor, based on the available computational power. Extensive simulations show that our test, when used in its exact form, is significantly faster than the current response time analysis methods. Moreover the proposed approach, for its elegance and compactness, offers an explanation of some known phenomena of fixed priority scheduling and could be helpful for further work on the Rate Monotonic analysis.

The Space of Rate Monotonic Schedulability

BINI, Enrico;
2002-01-01

Abstract

Feasibility analysis of fixed priority systems has been widely studied in the real-time literature and several acceptance tests have been proposed to guarantee a set of periodic tasks. They can be divided in two main classes: polynomial time tests and exact tests. Polynomial time tests are used for on-line guarantee of dynamic systems, where tasks can be activated at runtime. These tests introduce a negligible overhead, when executed upon a new task arrival, however provide only a sufficient schedulability condition, which may cause a poor processor utilization. On the other hand, exact tests, which are based on response time analysis, provide a necessary and sufficient schedulability condition, but are too complex to be executed on line for large task sets. As a consequence, for large task sets, they are often executed off line. This paper proposes a novel approach for analyzing the schedulability of periodic task sets under the Rate Monotonic priority assignment. Using this approach, we derive a new schedulability test which can be tuned through a parameter to balance complexity vs. acceptance ratio, so that it can be used on line to better exploit the processor, based on the available computational power. Extensive simulations show that our test, when used in its exact form, is significantly faster than the current response time analysis methods. Moreover the proposed approach, for its elegance and compactness, offers an explanation of some known phenomena of fixed priority scheduling and could be helpful for further work on the Rate Monotonic analysis.
2002
IEEE Real-Time Systems Symposium
Austin, TX, USA
2002
Proceedings of the 23rd IEEE Real-Time Systems Symposium
IEEE
0
169
178
9780769518510
Bini, Enrico; Buttazzo, G. C.
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2318/1608710
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 44
  • ???jsp.display-item.citation.isi??? 20
social impact