Ir al contenido

Documat

Una revisión de técnicas para la optimización del despliegue y planificación de sistemas de tiempo real distribuidos

  • Amurrio, Andoni [2] ; Azketa, Ekain [2] ; Gutiérrez, J. Javier [1] ; Aldea, Mario [1] ; Parra, Jorge [2]
    1. [1] Universidad de Cantabria

      Universidad de Cantabria

      Santander, España

    2. [2] IK4-Ikerlan Centro de Investigaciones Tecnológicas
  • Localización: Revista iberoamericana de automática e informática industrial ( RIAI ), ISSN-e 1697-7920, Vol. 16, Nº. 3, 2019, págs. 249-263
  • Idioma: español
  • DOI: 10.4995/riai.2019.10997
  • Títulos paralelos:
    • A review on optimization techniques for the deployment and scheduling of distributed real-time systems
  • Enlaces
  • Resumen
    • español

      En las últimas tres décadas, se ha realizado un gran número de propuestas sobre la optimización del despliegue y planificación de sistemas de tiempo real distribuidos bajo diferentes enfoques algorítmicos que aportan soluciones aceptables a este problema catalogado como NP-difícil. En la actualidad, la mayor parte de los sistemas utilizados en el sector industrial son sistemas de criticidad mixta en los que se puede usar la planificación cíclica, las prioridades fijas y el particionado, que proporciona aislamiento temporal y espacial a las aplicaciones. Así, en este artículo se realiza una revisión de los trabajos publicados sobre este tema y se presenta un análisis de las diferentes soluciones aportadas para sistemas de tiempo real distribuidos basados en las políticas de planificación que se están usando en la práctica. Como resultado de la comparación, se presenta una tabla a modo de guía en la que se relacionan los trabajos revisados y se caracterizan sus soluciones.

    • English

      In the last three decades, a large number of proposals has been carried out for the optimization of the deployment and scheduling of distributed real-time systems under dierent algorithmic approaches that provide acceptable solutions for this NP-hard problem. Nowadays, most of the systems used in industry are mixed-criticallity systems which use cyclic scheduling, fixed-priority scheduling and partitioning, which provides both temporal and spatial isolation in the execution of applications. Thus, in this work a review of the works published on this topic is performed, as well as an analysis of the dierent proposed solutions for distributed real-time systems based on the scheduling policies that are used in practice. As a result of the comparison, a table intended as aguide is elaborated in which all the reviewed works are reported and their solutions are characterized.

  • Referencias bibliográficas
    • Airlines Electronic Engineering Committee, A. R. I., 2009. Arinc specification 664p7: Aircraft data network, part 7 - avionics full duplex...
    • Al Sheikh, A., Brun, O., Hladik, P.-E., 2010. Partition scheduling on an imaplatform with strict periodicity and communication delays. In:...
    • Al Sheikh, A., Brun, O., Hladik, P.-E., Prabhu, B. J., 2011. A best-response algorithm for multiprocessor periodic scheduling. In: Real-Time...
    • Ali, S., Kim, J.-K., Siegel, H. J., Maciejewski, A. A., Yu, Y., Gundala, S. B., Gertphol, S., Prasanna, V. K., 2002. Greedy heuristics for...
    • Althaus, E., Homann, S., Kupilas, J., Thaden, E., 2012. A column generation approach to scheduling of real-time networks. In: Proceedings...
    • Althaus, E., Homann, S., Kupilas, J., Thaden, E., 2014. Scheduling of realtime networks with a column generation approach. In: IAENG Transactions...
    • Audsley, N. C., 1991. Optimal priority assignment and feasibility of static priority tasks with arbitrary start times. Technical Report.
    • AUTOSAR, 2003. Automotive open system architecture. URL: http://www.autosar.org/
    • Ayari, R., Hafnaoui, I., Aguiar, A., Gilbert, P., Galibois, M., Rousseau, J.-P., Beltrame, G., Nicolescu, G., 2016a. Multi-objective mapping...
    • Ayari, R., Hafnaoui, I., Beltrame, G., Nicolescu, G., 2016b. Schedulability-guided exploration of multi-core systems. In: Proceedings of the...
    • Ayari, R., Hafnaoui, I., Beltrame, G., Nicolescu, G., 2018. Imga: an improved genetic algorithm for partitioned scheduling on heterogeneous...
    • Azketa, E., Uribe, J., Marcos, M., Almeida, L., Gutiérrez, J. J., 2011a. Permutational genetic algorithm for fixed priority scheduling of...
    • Azketa, E., Uribe, J. P., Gutiérrez, J. J., Marcos, M., Almeida, L., 2012. Permutational genetic algorithm for the optimized mapping and scheduling...
    • Azketa, E., Uribe, J. P., Marcos, M., Almeida, L., Gutierrez, J. J., 2011b. Permutational genetic algorithm for the optimized assignment of...
    • Barrett, C., Tinelli, C., 2018. Satisfiability modulo theories. In: Handbook of Model Checking. Springer, pp. 305–343.
    • Baruah, S., Li, H., Stougie, L., 2010. Towards the design of certifiable mixedcriticality systems. In: Real-Time and Embedded Technology and...
    • Bhat, A., Samii, S., Rajkumar, R., 2017. Practical task allocation for software fault-tolerance and its implementation in embedded automotive...
    • Blikstad, M., Karlsson, E., Lööw, T., Rönnberg, E., 2018. An optimisation approach for pre-runtime scheduling of tasks and communication in...
    • Bosch Gmbh, R., 1991. Can specification - version 2.0. Boutekkouk, F., Oubadi, S., 2014. Periodic/aperiodic tasks scheduling optimization...
    • Boutekkouk, F., Oubadi, S., 2016. Real time tasks scheduling optimization using quantum inspired genetic algorithms. In: Artificial Intelligence...
    • Boyd, S., Kim, S.-J., Vandenberghe, L., Hassibi, A., 2007. A tutorial on geometric programming. Optimization and engineering 8 (1), 67. DOI:...
    • Braun, T. D., Siegel, H. J., Beck, N., Bölöni, L. L., Maheswaran, M., Reuther, A. I., Robertson, J. P., Theys, M. D., Yao, B., Hensgen, D.,...
    • Braun, T. D., Siegel, H. J., Maciejewski, A. A., Hong, Y., 2008. Static resource allocation for heterogeneous computing environments with...
    • Burns, A., Davis, R. I., 2017. A survey of research into mixed criticality systems. ACM Computing Surveys (CSUR) 50 (6), 82. DOI: 10.1145/3131347
    • Burns, A., Nicholson, M., Tindell, K., Zhang, N., 1993. Allocating and scheduling hard real-time tasks on a point-to-point distributed system....
    • Chen, J., Du, C., Han, P., 2016. Scheduling independent partitions in integrated modular avionics systems. PloS one 11 (12). DOI: 10.1371/journal.pone.0168064
    • Chen,W.-H., Lin, C.-S., 2000. A hybrid heuristic to solve a task allocation problem. Computers & Operations Research 27 (3), 287–303....
    • Coli, M., Palazzari, P., 1995. A new method for optimization of allocation and scheduling in real time applications. In: Real-Time Systems,...
    • Craciunas, S. S., Oliver, R. S., 2014. Smt-based task-and network-level static schedule generation for time-triggered networked systems. In:...
    • Craciunas, S. S., Oliver, R. S., Chmelík, M., Steiner,W., 2016. Scheduling realtime communication in ieee 802.1 qbv time sensitive networks....
    • Craciunas, S. S., Oliver, R. S., Ecker, V., 2014. Optimal static scheduling of real-time tasks on distributed time-triggered networked systems....
    • Crespo, A., Alonso, A., Marcos, M., Juan, A., Balbastre, P., 2014. Mixed criticality in control systems. IFAC Proceedings Volumes 47 (3),...
    • Davare, A., Zhu, Q., Di Natale, M., Pinello, C., Kanajan, S., Sangiovanni- Vincentelli, A., 2007. Period optimization for hard real-time distributed...
    • Deroche, E., Scharbarg, J.-L., Fraboul, C., 2016. Mapping real-time communicating tasks on a distributed ima architecture. In: Emerging Technologies...
    • Deroche, E., Scharbarg, J.-L., Fraboul, C., 2017. A greedy heuristic for distributing hard real-time applications on an ima architecture....
    • Di Natale, M., Stankovic, J. A., 1995. Applicability of simulated annealing methods to real-time scheduling and jitter control. In: Real-Time...
    • Dick, R. P., Jha, N. K., 1998. Mogac: a multiobjective genetic algorithm for hardware-software cosynthesis of distributed embedded systems....
    • Directorate, E. C. I. S. M., 2012. Mixed criticality systems. Report from the Workshop on Mixed Criticality Systems.
    • Eisenbrand, F., Kesavan, K., Mattikalli, R. S., Niemeier, M., Nordsieck, A. W., Skutella, M., Verschae, J., Wiese, A., 2010. Solving an avionics...
    • Ekelin, C., Jonsson, J., 2001. Evaluation of search heuristics for embedded system scheduling problems. In: International Conference on Principles...
    • Eles, P., Doboli, A., Pop, P., Peng, Z., 2000. Scheduling with bus access optimization for distributed embedded systems. IEEE Transactions...
    • Emberson, P., Bate, I., 2010. Stressing search with scenarios for flexible solutions to real-time task allocation problems. IEEE Transactions...
    • Faucou, S., Deplanche, A.-M., Beauvais, J.-P., 2000. Heuristic techniques for allocating and scheduling communicating periodic tasks in distributed...
    • Fonseca, C. M., Fleming, P. J., 1998. Multiobjective optimization and multiple constraint handling with evolutionary algorithms. i. a unified...
    • Garibay Martínez, R., Nelissen, G., Ferreira, L. L., Pinho, L. M., 2014. On the scheduling of fork-join parallel/distributed real-time tasks....
    • Garibay-Martínez, R., Nelissen, G., Ferreira, L. L., Pinho, L. M., 2015. Task partitioning and priority assignment for distributed hard real-time...
    • Glover, F., 1986. Future paths for integer programming and links to artificial intelligence. Computers & operations research 13 (5), 533–549....
    • Goldberg, D. E., Holland, J. H., 1988. Genetic algorithms and machine learning. Machine learning 3 (2), 95–99. DOI: 10.1023/A:1022602019183
    • Goossens, K., Azevedo, A., Chandrasekar, K., Gomony, M. D., Goossens, S., Koedam, M., Li, Y., Mirzoyan, D., Molnos, A., Nejad, A. B., et al.,...
    • Guevara López, P., Valdez Martínez, J. S., Delgado Reyes, G., 2014. Planificadores de tareas en tiempo real concurrentes: Una clasificación...
    • Gutiérrez, J. J., González Harbour, M., 1995. Optimized priority assignment for tasks and messages in distributed hard real-time systems....
    • Gutiérrez, J. J., Palencia, J. C., Harbour, M. G., 2014. Holistic schedulability analysis for multipacket messages in afdx networks. Real-Time...
    • Hamann, A., Jersak, M., Richter, K., Ernst, R., 2006. A framework for modular analysis and exploration of heterogeneous embedded systems....
    • He, X., Gu, Z., Zhu, Y., 2010. Task allocation and optimization of distributed embedded systems with simulated annealing and geometric programming....
    • Hladik, P.-E., Cambazard, H., Déplanche, A.-M., Jussien, N., 2008. Solving a real-time allocation problem with constraint programming. Journal...
    • Holland, J., 1975. Adaptation in artificial and natural systems. Ann Arbor: The University of Michigan Press.
    • Hou, C.-J., Shin, K. G., 1997. Allocation of periodic task modules with precedence and deadline constraints in distributed real-time systems....
    • Hou, E. S., Ansari, N., Ren, H., 1994. A genetic algorithm for multiprocessor scheduling. IEEE Transactions on Parallel and Distributed systems...
    • Hu, M., Luo, J.,Wang, Y., Veeravalli, B., 2015. Scheduling periodic task graphs for safety-critical time-triggered avionic systems. IEEE Trans....
    • IEEE Portable Application Standards Committee, P., 2003. Standard for information technology-portable operating system interface (posix) realtime...
    • ISO/IEC, 2012. Ada 2012 reference manual. language and standard libraries -international standard iso/iec 8652:2012(e).
    • Jiang,W., Pop, P., Jiang, K., 2017. Design optimization for security-and safetycritical distributed real-time applications. Microprocessors...
    • John, R., 1999. Partitioning in avionics architectures: requirements, mechanisms, and assurance.
    • Kirkpatrick, S., 1984. Optimization by simulated annealing: Quantitative studies. Journal of statistical physics 34 (5-6), 975–986. DOI: 10.1007/BF01009452
    • Klobedanz, K., Jatzkowski, J., Rettberg, A., Mueller, W., 2013. Fault-tolerant deployment of real-time software in autosar ecu networks. In:...
    • Kopetz, H., 2011. Real-time systems: design principles for distributed embedded applications. Springer Science & Business Media. DOI:...
    • Land, A. H., Doig, A. G., 1960. An automatic method of solving discrete programming problems. Econometrica: Journal of the Econometric Society,...
    • Lin, M., Karlsson, L., Yang, L. T., 2000. Heuristic techniques: Scheduling partially ordered tasks in a multi-processor environment with tabu...
    • Liu, C. L., Layland, J. W., 1973. Scheduling algorithms for multiprogramming in a hard-real-time environment. Journal of the ACM (JACM) 20...
    • Liu, J., 2000. Real-time systems. Prentice Hall 48, 42.
    • Martí, R., Lozano, J. A., Mendiburu, A., Hernando, L., 2016. Multi-start methods. Handbook of Heuristics, 1–21. DOI: 10.1007/0-306-48056-5-12
    • Mehiaoui, A.,Wozniak, E., Tucci-Piergiovanni, S., Mraidha, C., Di Natale, M., Zeng, H., Babau, J.-P., Lemarchand, L., Gerard, S., 2013. A...
    • Metzner, A., Herde, C., 2006. Rtsat–an optimal and effcient approach to the task allocation problem in distributed architectures. In: Real-Time...
    • Minaeva, A., Akesson, B., Hanzálek, Z., Dasari, D., 2018. Time-triggered coscheduling of computation and communication with jitter requirements....
    • Minoux, M., 1986. Mathematical programming: theory and algorithms. John Wiley & Sons.
    • Mitra, H., Ramanathan, P., 1993. A genetic approach for scheduling nonpreemptive tasks with precedence and deadline constraints. In: System...
    • Monnier, Y., Beauvais, J.-P., Deplanche, A.-M., 1998. A genetic algorithm for scheduling tasks in a real-time distributed system. In: Euromicro...
    • Neukirchner, M., Stein, S., Ernst, R., 2011. A lazy algorithm for distributed priority assignment in real-time systems. In: Object/Component/Service-...
    • Oh, J., Wu, C., 2004. Genetic-algorithm-based real-time task scheduling with multiple goals. Journal of systems and software 71 (3), 245–258....
    • Palencia, J. C., Harbour, M. G., Gutiérrez, J. J., Rivas, J. M., 2017. Responsetime analysis in hierarchically-scheduled time-partitioned...
    • Pearl, J., 1984. Heuristics: intelligent search strategies for computer problem solving. Addison-Wesley Pub. Co., Inc., Reading, MA.
    • Pedreiras, P., Almeida, L., 2004. Message routing in multi-segment ftt networks: The isochronous approach. In: Parallel and Distributed Processing...
    • Peng, D.-T., Shin, K. G., Abdelzaher, T. F., 1997. Assignment and scheduling communicating periodic tasks in distributed real-time systems....
    • Pishdar, M. A., Akkasi, A., 2015. Task scheduling and idle-time balancing in homogeneous multi processors: A comparison between ga and sa....
    • Pop, P., Eles, P., Peng, Z., 2000. Bus access optimization for distributed embedded systems based on schedulability analysis. In: Proceedings...
    • Pop, P., Eles, P., Peng, Z., 2004a. Analysis and synthesis of distributed real-time embedded systems. Springer Science & Business Media....
    • Pop, P., Eles, P., Peng, Z., 2004b. Schedulability-driven communication synthesis for time triggered embedded systems. Real-Time Systems 26...
    • Pop, P., Eles, P., Peng, Z., Izosimov, V., 2004c. Schedulability-driven partitioning and mapping for multi-cluster real-time systems. In:...
    • Pop, P., Eles, P., Pop, T., Peng, Z., 2001a. An approach to incremental design of distributed embedded systems. In: Proceedings of the 38th...
    • Pop, P., Eles, P., Pop, T., Peng, Z., 2001b. Minimizing system modification in an incremental design approach. In: Proceedings of the ninth...
    • Pop, T., 2007. Analysis and optimisation of distributed embedded systems with heterogeneous scheduling policies. Ph.D. thesis, Institutionen...
    • Pop, T., Eles, P., Peng, Z., 2003a. Design optimization of mixed time/eventtriggered distributed embedded systems. In: Proceedings of the...
    • Pop, T., Eles, P., Peng, Z., 2003b. Schedulability analysis for distributed heterogeneous time/event triggered real-time systems. In: Real-Time...
    • Pop, T., Pop, P., Eles, P., Peng, Z., 2005. Optimization of hierarchically scheduled heterogeneous embedded systems. In: Embedded and Real-Time...
    • Porto, S. C., Kitajima, J. P. F., Ribeiro, C. C., 2000. Performance evaluation of a parallel tabu search task scheduling algorithm. Parallel...
    • Qin, X., Jiang, H., 2006. A novel fault-tolerant scheduling algorithm for precedence constrained tasks in real-time heterogeneous systems....
    • Ramamritham, K., 1995. Allocation and scheduling of precedence-related periodic tasks. IEEE Transactions on Parallel and Distributed Systems...
    • Richard, M., Richard, P., Cottet, F., 2003. Allocating and scheduling tasks in multiple fieldbus real-time systems. In: Emerging Technologies...
    • Rivas, J. M., Gutiérrez, J. J., Palencia, J. C., et al., 2011. Schedulability analysis and optimization of heterogeneous edf and fp distributed...
    • Samii, S., Yin, Y., Peng, Z., Eles, P., Zhang, Y., 2009. Immune genetic algorithms for optimization of task priorities and flexray frame identifiers....
    • Schrijver, A., 1998. Theory of linear and integer programming. Wiley.
    • Sha, L., Abdelzaher, T., Årz´en, K.-E., Cervin, A., Baker, T., Burns, A., Buttazzo, G., Caccamo, M., Lehoczky, J., Mok, A. K., 2004. Real...
    • Shang, L., Dick, R. P., Jha, N. K., 2007. Slopes: hardware–software cosynthesis of low-power real-time distributed embedded systems with dynamically...
    • Smith, D. J., Simpson, K. G., 2004. Functional Safety: A straightforward guide to applying IEC 61508 and related standards. Routledge.
    • Szymanek, R., Krzysztof, K., 2003. Partial task assignment of task graphs under heterogeneous resource constraints. In: Proceedings of the...
    • Szymanek, R., Kuchcinski, K., 2001. A constructive algorithm for memoryaware task assignment and scheduling. In: Proceedings of the ninth...
    • Tämas¸-Selicean, D., Pop, P., 2011a. Optimization of time-partitions for mixed-criticality real-time distributed embedded systems. In: Object/Component/Service-Oriented...
    • Tämas¸-Selicean, D., Pop, P., 2011b. Task mapping and partition allocation for mixed-criticality real-time systems. In: Dependable Computing...
    • Tämas¸-Selicean, D., Pop, P., 2015. Design optimization of mixed-criticality real-time embedded systems. ACM Transactions on Embedded Computing...
    • Tindell, K., Clark, J., 1994. Holistic schedulability analysis for distributed hard real-time systems. Microprocessing and microprogramming...
    • Tindell, K.W., Burns, A.,Wellings, A. J., 1992. Allocating hard real-time tasks: an np-hard problem made easy. Real-Time Systems 4 (2), 145–165....
    • Trujillo, S., Crespo, A., Alonso, A., Pérez, J., 2014. Multipartes: Multi-core partitioning and virtualization for easing the certification...
    • Tsang, E., 2014. Foundations of constraint satisfaction: the classic text. BoD– Books on Demand.
    • Vargas, L. M. F., de Oliveira, R. S., 2005. Empirical study of tabu search, simulated annealing and multi-start in fieldbus scheduling. In:...
    • Vestal, S., 2007. Preemptive scheduling of multi-criticality systems with varying degrees of execution time assurance. In: Real-Time Systems...
    • WindRiver, 2016. Wind river vxworks 653 platform.
    • Wozniak, E., Mehiaoui, A., Mraidha, C., Tucci-Piergiovanni, S., Gerard, S., 2013. An optimization approach for the synthesis of autosar architectures....
    • Xie, G., Zeng, G., Liu, L., Li, R., Li, K., 2016. High performance real-time scheduling of multiple mixed-criticality functions in heterogeneous...
    • Yoo, M., 2009. Real-time task scheduling by multiobjective genetic algorithm. Journal of Systems and Software 82 (4), 619–628. DOI: 10.1016/j.jss.2008.08.039
    • Yoon, H., Ryu, M., 2015. Guaranteeing end-to-end deadlines for autosarbased automotive software. International Journal of Automotive Technology...
    • Zhang, L., Goswami, D., Schneider, R., Chakraborty, S., 2014. Task-and network-level schedule co-synthesis of ethernet-based time-triggered...
    • Zheng, W., Di Natale, M., Pinello, C., Giusto, P., Vincentelli, A. S., 2007a. Synthesis of task and message activation models in real-time...
    • Zheng, W., Zhu, Q., Di Natale, M., Vincentelli, A. S., 2007b. Definition of task allocation and priority assignment in hard real-time distributed...
    • Zhu, Q., Yang, Y., Scholte, E., Di Natale, M., Sangiovanni-Vincentelli, A., 2009. Optimizing extensibility in hard real-time distributed systems....
    • Zhu, Q., Zeng, H., Zheng,W., Natale, M. D., Sangiovanni-Vincentelli, A., 2012. Optimization of task allocation and priority assignment in...
Fundación Dialnet

Mi Documat

Opciones de artículo

Opciones de compartir

Opciones de entorno