Improved task packing for shared resources in multiprocessor real-time systems scheduled by RUN under SBLP
Resumo
Reduction to Uniprocessor (RUN) is an algorithm capable of efficiently and optimally scheduling a set of strictly periodic real-time tasks on a multiprocessor platform when tasks do not share any resources but processors. A basic building block of RUN is the servers, which are entities capable of scheduling a sub-set of tasks via EDF. Recently, support for resource sharing has been incorporated into RUN by the Server Based Locking Protocol (SBLP). SBLP accounts for possible interferences of resource locking times into the RUN servers. The protocol performance, however, depends on how tasks are packed into servers. In this work we describe a new task packing heuristic that outperforms those originally proposed for SBLP. Extensive evaluation experiments are conducted and show that gains of up to 25% can be obtained by the proposed heuristic.
Palavras-chave:
Resource ManagementScheduling and Schedulability Analysis
Referências
G. Lima P. Regnier E. Massa Y. Tian D. Levy Charles "Practical Considerations in Optimal Multiprocessor Scheduling" in Handbook of Real-Time Computing Singapore:Springer vol. ch. 8 2019.
R. I. Davis A. Burns "A survey of hard real-time scheduling for multiprocessor systems" ACM Computing Surveys vol. 43 no. 4 pp. 1-44 2011 [online] Available: http://dl.acm.org/citation.cfm?doid=1978802.1978814.
P. Regnier G. Lima E. Massa G. Levin S. Brandt "RUN: Optimal multiprocessor real-time scheduling via reduction to uniprocessor" Proceedings - 32th Real-Time Systems Symposium pp. 104-115 2011.
G. Nelissen V. Berten V. Nélis J. Goossens D. Milojevic "U-EDF: An unfair but optimal multiprocessor scheduling algorithm for sporadic tasks" Proceedings - Euromicro Conference on Real-Time Systems no. July 2012 pp. 13-23.
E. Massa G. Lima P. Regnier "Revealing the secrets of RUN and QPS: new trends for optimal real-time multiprocessor scheduling" Proceedings of the Brazilian Symposium on Computing Systems Engineering 2014 pp. 1-6 2014.
D. Compagnin E. Mezzetti T. Vardanega "Putting RUN into practice: Implementation and evaluation" Proceedings - Euromicro Conference on Real-Time Systems pp. 75-84 2014.
C. L. Liu J. W. Layland "Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment Scheduling Algorithms for Multiprogramming" Journal of the Association for Computing Machinery vol. 20 no. 1 pp. 46-61 1973.
L. Sha R. Rajkumar J. P. Lehoczky "Priority Inheritance Protocols: An Approach to Real-Time Synchronization" IEEE Transactions on Computers vol. 39 no. 9 pp. 1175-1185 1990.
T. P. Baker "Stack-based scheduling of realtime processes" Real-Time Systems vol. 3 no. 1 pp. 67-99 1991.
L. Bonato E. Mezzetti T. Vardanega "Supporting Global Resource Sharing in RUN-scheduled Multiprocessor Systems Our goal" International Conference on Real-Time Networks and Systems pp. 109-118 2014.
A. Burns A. J. Wellings "A Schedulability Compatible Multiprocessor Resource Sharing Protocol - MrsP" Proceedings - Euromicro Conference on Real-Time Systems pp. 282-291 2013.
S. Catellani L. Bonato S. Huber E. Mezzetti "Challenges in the implementation of MrsP" pp. 1-22 2015.
P. Gai G. Lipari M. Di Natale "Minimizing memory utilization of real-time task sets in single and multi-processor systems-on-a-chip" Proceedings - Real-Time Systems Symposium pp. 73-83 2001.
R. Rajkumar L. Sha J. P. Lehoczky "Real-time synchronization protocols for multiprocessors" Proceedings. Real-Time Systems Symposium pp. 259-269 1988 [online] Available: http://ieeexplore.ieee.org/document/51121/.
R. Rajkumar "Real-time synchronization protocols for shared memory multiprocessors" Proceedings.10th International Conference on Distributed Computing Systems 1990.
A. Block H. Leontyev B. B. Brandenburg J. H. Anderson "A flexible real-time locking protocol for multiprocessors" Proceedings - 13th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications RTCSA 2007 no. Rtcsa pp. 47-56 2007.
R. I. Davis A. Burns "Resource sharing in hierarchical fixed priority pre-emptive systems" Proceedings - Real-Time Systems Symposium pp. 257-267 2006.
A. Biondi G. Buttazzo M. Bertogna "Schedulability Analysis of Hierarchical Real-Time Systems under Shared Resources" Retis. Sssup. It vol. 65 no. 5 pp. 1-17 2013 [online] Available: http://retis.sssup.it/giorgio/paps/2013/biondi_TR13-01.pdf.
W. H. Huang M. Yang J. J. Chen "Resource-Oriented Partitioned Scheduling in Multiprocessor Systems: How to Partition and How to Share?" Proceedings - Real-Time Systems Symposium pp. 111-122 2017.
D. A. Baruah S. K. N. K. Cohen C. G. Plaxton Varvel "Proportionate progress: A notion of fairness in resource allocation" Algorithmica vol. 15 no. 6 pp. 600-625 1996.
G. C. Baruah K. Sanjoy Johannes E. Gehrke Plaxton "Fast scheduling of periodic tasks on multiple resources" Proceedings of 9th International Parallel Processing Symposium pp. 280-288 1995.
A. Anderson J.H. Srinivasan "Early-release fair scheduling" Proceedings 12th Euromicro Conference on Real-Time Systems. Euromicro RTS 2000 pp. 35-43 2000.
S. Levin G. Funk S. Sadowski C. Pye I. Brandt "DP-FAIR: A Simple Model for Understanding Optimal Multiprocessor Scheduling" 2010 22nd Euromicro Conference on Real-Time Systems pp. 3-13 2010.
E. Massa G. Lima P. Regnier G. Levin S. Brandt "Quasi-partitioned scheduling: optimality and adaptation in multiprocessor real-time systems" Real-Time Systems vol. 52 no. 5 pp. 566-597 2016.
R. I. Davis A. Burns "A survey of hard real-time scheduling for multiprocessor systems" ACM Computing Surveys vol. 43 no. 4 pp. 1-44 2011 [online] Available: http://dl.acm.org/citation.cfm?doid=1978802.1978814.
P. Regnier G. Lima E. Massa G. Levin S. Brandt "RUN: Optimal multiprocessor real-time scheduling via reduction to uniprocessor" Proceedings - 32th Real-Time Systems Symposium pp. 104-115 2011.
G. Nelissen V. Berten V. Nélis J. Goossens D. Milojevic "U-EDF: An unfair but optimal multiprocessor scheduling algorithm for sporadic tasks" Proceedings - Euromicro Conference on Real-Time Systems no. July 2012 pp. 13-23.
E. Massa G. Lima P. Regnier "Revealing the secrets of RUN and QPS: new trends for optimal real-time multiprocessor scheduling" Proceedings of the Brazilian Symposium on Computing Systems Engineering 2014 pp. 1-6 2014.
D. Compagnin E. Mezzetti T. Vardanega "Putting RUN into practice: Implementation and evaluation" Proceedings - Euromicro Conference on Real-Time Systems pp. 75-84 2014.
C. L. Liu J. W. Layland "Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment Scheduling Algorithms for Multiprogramming" Journal of the Association for Computing Machinery vol. 20 no. 1 pp. 46-61 1973.
L. Sha R. Rajkumar J. P. Lehoczky "Priority Inheritance Protocols: An Approach to Real-Time Synchronization" IEEE Transactions on Computers vol. 39 no. 9 pp. 1175-1185 1990.
T. P. Baker "Stack-based scheduling of realtime processes" Real-Time Systems vol. 3 no. 1 pp. 67-99 1991.
L. Bonato E. Mezzetti T. Vardanega "Supporting Global Resource Sharing in RUN-scheduled Multiprocessor Systems Our goal" International Conference on Real-Time Networks and Systems pp. 109-118 2014.
A. Burns A. J. Wellings "A Schedulability Compatible Multiprocessor Resource Sharing Protocol - MrsP" Proceedings - Euromicro Conference on Real-Time Systems pp. 282-291 2013.
S. Catellani L. Bonato S. Huber E. Mezzetti "Challenges in the implementation of MrsP" pp. 1-22 2015.
P. Gai G. Lipari M. Di Natale "Minimizing memory utilization of real-time task sets in single and multi-processor systems-on-a-chip" Proceedings - Real-Time Systems Symposium pp. 73-83 2001.
R. Rajkumar L. Sha J. P. Lehoczky "Real-time synchronization protocols for multiprocessors" Proceedings. Real-Time Systems Symposium pp. 259-269 1988 [online] Available: http://ieeexplore.ieee.org/document/51121/.
R. Rajkumar "Real-time synchronization protocols for shared memory multiprocessors" Proceedings.10th International Conference on Distributed Computing Systems 1990.
A. Block H. Leontyev B. B. Brandenburg J. H. Anderson "A flexible real-time locking protocol for multiprocessors" Proceedings - 13th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications RTCSA 2007 no. Rtcsa pp. 47-56 2007.
R. I. Davis A. Burns "Resource sharing in hierarchical fixed priority pre-emptive systems" Proceedings - Real-Time Systems Symposium pp. 257-267 2006.
A. Biondi G. Buttazzo M. Bertogna "Schedulability Analysis of Hierarchical Real-Time Systems under Shared Resources" Retis. Sssup. It vol. 65 no. 5 pp. 1-17 2013 [online] Available: http://retis.sssup.it/giorgio/paps/2013/biondi_TR13-01.pdf.
W. H. Huang M. Yang J. J. Chen "Resource-Oriented Partitioned Scheduling in Multiprocessor Systems: How to Partition and How to Share?" Proceedings - Real-Time Systems Symposium pp. 111-122 2017.
D. A. Baruah S. K. N. K. Cohen C. G. Plaxton Varvel "Proportionate progress: A notion of fairness in resource allocation" Algorithmica vol. 15 no. 6 pp. 600-625 1996.
G. C. Baruah K. Sanjoy Johannes E. Gehrke Plaxton "Fast scheduling of periodic tasks on multiple resources" Proceedings of 9th International Parallel Processing Symposium pp. 280-288 1995.
A. Anderson J.H. Srinivasan "Early-release fair scheduling" Proceedings 12th Euromicro Conference on Real-Time Systems. Euromicro RTS 2000 pp. 35-43 2000.
S. Levin G. Funk S. Sadowski C. Pye I. Brandt "DP-FAIR: A Simple Model for Understanding Optimal Multiprocessor Scheduling" 2010 22nd Euromicro Conference on Real-Time Systems pp. 3-13 2010.
E. Massa G. Lima P. Regnier G. Levin S. Brandt "Quasi-partitioned scheduling: optimality and adaptation in multiprocessor real-time systems" Real-Time Systems vol. 52 no. 5 pp. 566-597 2016.
Publicado
19/11/2019
Como Citar
TEIXEIRA, Ricardo; LIMA, George.
Improved task packing for shared resources in multiprocessor real-time systems scheduled by RUN under SBLP. In: SIMPÓSIO BRASILEIRO DE ENGENHARIA DE SISTEMAS COMPUTACIONAIS (SBESC), 9. , 2019, Natal.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2019
.
p. 129-136.
ISSN 2237-5430.
