A Flexible Framework to Schedule Soft Aperiodic Tasks in Hard Real-Time Systems
Resumo
An EDF-based flexible scheduling framework designed for scheduling systems composed of soft aperiodic and hard periodic real-time tasks is described. Hard tasks are assigned to processors and do not migrate during their execution. Migration of soft tasks is allowed. They can be put either in a global queue, accessed by our processors, or in local processor queues. We show that using the framework in either configuration provides improvements in QoS-related metrics for soft tasks, such as deadline miss ratio and response time without compromising timeliness guarantees for hard tasks. In the core of our solution is the use of two types of servers, whose definition and correctness proofs are also presented in this paper. Our solution is evaluated via extensive simulation. Results indicate that the available processing capacity left unused by hard tasks can be effectively used for executing soft aperiodic tasks.
Palavras-chave:
Scheduling, Schedulability Analysis
Referências
J. W. S. W. Liu Real-Time Systems Upper Saddle River NJ USA:Prentice Hall PTR vol. 7 2000.
G. Buttazzo G. Lipari L. Abeni M. Caccamo Soft Real-Time Systems: Predictability vs. Efficiency New York NY United States:Springer-Verlag New York Inc vol. 3 6 2005.
M. Spuri G. C. Buttazzo "Efficient aperiodic service under earliest deadline scheduling" 1994 Proceedings Real-Time Systems Symposium pp. 2-11 Dec 1994.
L. Abeni G. Buttazzo "Integrating multimedia applications in hard real-time systems" Proceedings 19th IEEE Real-Time Systems Symposium (Cat. No.98CB36279) pp. 4-13 Dec 1998.
S. Baruah G. Lipari "A multiprocessor implementation of the total bandwidth server" 18th International Parallel and Distributed Processing Symposium 2004. Proceedings pp. 40 April 2004.
S. Baruah J. Goossens G. Lipari "Implementing constant-bandwidth servers upon multiprocessor platforms" Proceedings. Eighth IEEE Real-Time and Embedded Technology and Applications Symposium pp. 154-163 2002.
R. Pellizzoni M. Caccamo "M-cash: A real-time resource reclaiming algorithm for multiprocessor platforms" Real-Time Systems vol. 40 no. 1 pp. 117-147 Oct 2008 [online] Available: https://doi.org/10.1007/s11241-008-9051-8.
R. I. Davis A. Burns "A survey of hard real-time scheduling for multiprocessor systems" ACM Comput. Surv. vol. 43 no. 4 pp. 35:1-35:44 Oct. 2011.
S. Kato N. Yamasaki "Scheduling aperiodic tasks using total bandwidth server on multiprocessors" Embedded and Ubiquitous Computing 2008. EUC ‘08. IEEE/IFIP International Conference on vol. 1 pp. 82-89 Dec 2008.
C.-F. Kuo Y.-H. Huang Y.-F. Lu S.-C. Chou "Scheduling algorithm considering response time for mixed tasks on multiprocessor systems" Proceedings of the 31st Annual ACM Symposium on Applied Computing ser. SAC’16 pp. 1767-1770 2016.
M. Digalwar P. Gahukar S. Mohan "Design and development of a real time scheduling algorithm for mixed task set on multicore processors" Contemporary Computing (IC3) 2014 Seventh International Conference on pp. 265-269 Aug 2014.
S. Saez J. Vila A. Crespo "Soft aperiodic task scheduling on hard real-time multiprocessor systems" Proceedings Sixth International Conference on Real-Time Computing Systems and Applications. RTCSA’99 (Cat. No. PR00306) pp. 424-427 Dec 1999.
J. M. Banús A. Arenas J. Labarta "An efficient scheme to allocate soft-aperiodic tasks in multiprocessor hard real-time systems" Proceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications vol. 2 pp. 809-815 2002.
A. A. Khan A. Ali M. Zakarya R. Khan M. Khan I. U. Rahman M. A. A. Rahman "A migration aware scheduling technique for real-time aperiodic tasks over multiprocessor systems" IEEE Access vol. 7 pp. 27 859-27 873 2019.
A. B. Dorin Maxim "Analysis and simulation tools for probabilistic real-time systems" Proceedings of 8th International Workshop on Analysis Tools and Methodologies for Embedded and Real-time Systems (WATERS) pp. 1-4 June 2017.
A. M. D. M. Cheramy P. E. Hladik S. Dube "Simulation of real-time scheduling with various execution time models" Proceedings of the 9th IEEE International Symposium on Industrial Embedded Systems (SIES 2014) pp. 1-4 June 2014.
R. Davis A. Burns "Robust priority assignment for fixed priority real-time systems" 28th IEEE International Real-Time Systems Symposium (RTSS 2007) pp. 3-14 Dec 2007.
M. L. Dertouzos "Control robotics: The procedural control of physical processes" IFIP Congress pp. 807-813 1974.
G. Buttazzo G. Lipari L. Abeni M. Caccamo Soft Real-Time Systems: Predictability vs. Efficiency New York NY United States:Springer-Verlag New York Inc vol. 3 6 2005.
M. Spuri G. C. Buttazzo "Efficient aperiodic service under earliest deadline scheduling" 1994 Proceedings Real-Time Systems Symposium pp. 2-11 Dec 1994.
L. Abeni G. Buttazzo "Integrating multimedia applications in hard real-time systems" Proceedings 19th IEEE Real-Time Systems Symposium (Cat. No.98CB36279) pp. 4-13 Dec 1998.
S. Baruah G. Lipari "A multiprocessor implementation of the total bandwidth server" 18th International Parallel and Distributed Processing Symposium 2004. Proceedings pp. 40 April 2004.
S. Baruah J. Goossens G. Lipari "Implementing constant-bandwidth servers upon multiprocessor platforms" Proceedings. Eighth IEEE Real-Time and Embedded Technology and Applications Symposium pp. 154-163 2002.
R. Pellizzoni M. Caccamo "M-cash: A real-time resource reclaiming algorithm for multiprocessor platforms" Real-Time Systems vol. 40 no. 1 pp. 117-147 Oct 2008 [online] Available: https://doi.org/10.1007/s11241-008-9051-8.
R. I. Davis A. Burns "A survey of hard real-time scheduling for multiprocessor systems" ACM Comput. Surv. vol. 43 no. 4 pp. 35:1-35:44 Oct. 2011.
S. Kato N. Yamasaki "Scheduling aperiodic tasks using total bandwidth server on multiprocessors" Embedded and Ubiquitous Computing 2008. EUC ‘08. IEEE/IFIP International Conference on vol. 1 pp. 82-89 Dec 2008.
C.-F. Kuo Y.-H. Huang Y.-F. Lu S.-C. Chou "Scheduling algorithm considering response time for mixed tasks on multiprocessor systems" Proceedings of the 31st Annual ACM Symposium on Applied Computing ser. SAC’16 pp. 1767-1770 2016.
M. Digalwar P. Gahukar S. Mohan "Design and development of a real time scheduling algorithm for mixed task set on multicore processors" Contemporary Computing (IC3) 2014 Seventh International Conference on pp. 265-269 Aug 2014.
S. Saez J. Vila A. Crespo "Soft aperiodic task scheduling on hard real-time multiprocessor systems" Proceedings Sixth International Conference on Real-Time Computing Systems and Applications. RTCSA’99 (Cat. No. PR00306) pp. 424-427 Dec 1999.
J. M. Banús A. Arenas J. Labarta "An efficient scheme to allocate soft-aperiodic tasks in multiprocessor hard real-time systems" Proceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications vol. 2 pp. 809-815 2002.
A. A. Khan A. Ali M. Zakarya R. Khan M. Khan I. U. Rahman M. A. A. Rahman "A migration aware scheduling technique for real-time aperiodic tasks over multiprocessor systems" IEEE Access vol. 7 pp. 27 859-27 873 2019.
A. B. Dorin Maxim "Analysis and simulation tools for probabilistic real-time systems" Proceedings of 8th International Workshop on Analysis Tools and Methodologies for Embedded and Real-time Systems (WATERS) pp. 1-4 June 2017.
A. M. D. M. Cheramy P. E. Hladik S. Dube "Simulation of real-time scheduling with various execution time models" Proceedings of the 9th IEEE International Symposium on Industrial Embedded Systems (SIES 2014) pp. 1-4 June 2014.
R. Davis A. Burns "Robust priority assignment for fixed priority real-time systems" 28th IEEE International Real-Time Systems Symposium (RTSS 2007) pp. 3-14 Dec 2007.
M. L. Dertouzos "Control robotics: The procedural control of physical processes" IFIP Congress pp. 807-813 1974.
Publicado
19/11/2019
Como Citar
NASCIMENTO, Flávia; LIMA, George.
A Flexible Framework to Schedule Soft Aperiodic Tasks in Hard Real-Time Systems. In: SIMPÓSIO BRASILEIRO DE ENGENHARIA DE SISTEMAS COMPUTACIONAIS (SBESC), 9. , 2019, Natal.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2019
.
p. 121-128.
ISSN 2237-5430.
