AvPI: análisis extendido del paralelismo promedio en sistemas modelados con redes de Petri S3PR bajo políticas de prevención de interbloqueos
DOI:
https://doi.org/10.24215/15146774e113Palabras clave:
redes de Petri S3PR, sistemas embebidos, invariantes de transición, prevención de bloqueos, AvPI, cuantificación del paralelismoResumen
Este artículo presenta un análisis formal y experimental ampliado del Average Parallelism Index (AvPI), una métrica destinada a cuantificar el paralelismo efectivo en redes de Petri S3PR bajo diferentes políticas de prevención de interbloqueos. Sobre la base del trabajo previamente presentado, esta versión extendida incorpora una formalización completa del método, incluyendo la caracterización algebraica de los invariantes de transición, la identificación de plazas de acción y la definición matemática del AvPI sobre la proyección del espacio de estados alcanzables. A partir de este marco formal, se profundiza la evaluación de tres configuraciones representativas —red original, control basado en sifones y control selectivo— poniendo de manifiesto los compromisos estructurales entre seguridad, concurrencia y utilización de recursos. Los resultados muestran que políticas excesivamente restrictivas, aunque libres de interbloqueos, pueden degradar severamente el paralelismo del sistema, mientras que estrategias de control selectivo permiten preservar tanto la vivacidad como la eficiencia operativa. La discusión ampliada posiciona al AvPI como un complemento cuantitativo de las propiedades cualitativas clásicas, y la sección final presenta las limitaciones del enfoque actual junto con su potencial extensión hacia redes temporizadas y flujos de diseño temprano para sistemas embebidos.
Referencias
Abdul-Hussin, M. (2015). Design of a Petri net based deadlock prevention policy supervisor for S3PR [ponencia]. 2015 6th International Conference on Intelligent Systems, Modelling and Simulation. Kuala Lumpur, Malaysia. https://doi.org/10.1109/ISMS.2015.5
Computing, I. C. L. D. o. (2002). Platform Independent Petri Net Editor 2. PIPE. Recuperado el 25 de abril de 2025 de https://pipe2.sourceforge.net/
Cassandras, C. G. y Lafourtune, S. L. (Eds.). (2010). Introduction to discrete event systems. (2ª ed.). Springer. https://doi.org/10.1007/978-0-387-68612-7
Culler, D., Singh, J. P. y Gupta, A. (1998). Parallel computer architecture: A hardware/software approach. Morgan Kaufmann Publishers. https://dl.acm.org/doi/book/10.5555/2821564
Ezpeleta, J., Colom, J. M. y Martinez, J. (1995). A Petri Net based deadlock prevention policy for flexible manufacturing systems. IEEE Transactions on Robotics and Automation, 11(2), 173-184. http://dx.doi.org/10.1109/70.370500
Ezpeleta, J., Tricas, F., Garcia-Valles, F. y Colom, J. M. (2002). A banker's solution for deadlock avoidance in FMS with flexible routing and multiresource states. IEEE Transactions on Robotics and Automation, 18(4), 621-625. https://doi.org/10.1109/TRA.2002.801048
Hu, H., Zhou, M., Li, Z. y Tang, Y. (2012). Deadlock-free control of automated manufacturing systems with flexible routes and assembly operations using Petri nets. IEEE Transactions on Industrial Informatics, 9(1), 109-121. https://doi.org/10.1109/TII.2012.2198661
Hu, L., Liu, Z., Hu, W., Wang, Y., Tan, J. y Wu, F. (2020). Petri-net-based dynamic scheduling of flexible manufacturing system via deep reinforcement learning with graph convolutional network. Journal of Manufacturing Systems, 55, 1-14. https://doi.org/10.1016/j.jmsy.2020.02.004
Li, Z., Wu, N. y Zhou, M. (2011). Deadlock control of automated manufacturing systems based on Petri nets—A literature review. Paper presented at the IEEE Transactions on Systems, Man, and Cybernetics, Part C (Applications and Reviews), https://doi.orig/10.1109/TSMCC.2011.2160626
Liu, H., Xing, K., Wu, W., Zhou, M. y Zou, H. (2014). Deadlock prevention for flexible manufacturing systems via controllable siphon basis of Petri nets. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 45(3), 519-529. https://doi.org/10.1109/TSMC.2014.2347267
Liu, Y., Li, X. y Li, Z. (2023). Control strategy of discrete event systems modeled by labeled Petri nets based on transition priority. IEEE Access, 11, 45442-45455. https://doi.org/10.1109/ACCESS.2023.3272404
Marwedel, P. (2021). Embedded system design: Embedded systems foundations of cyber-physical systems, and the internet of things. (4ª ed.). Springer. https://doi.org/10.1007/978-3-030-60910-8
Murata, T. (1989). Petri nets: Properties, analysis and applications. IEEE, 77(4), 541-580. http://dx.doi.org/10.1109/5.24143
Navet, N. y Simonot-Lion, F. (2017). Automotive embedded systems handbook. CRC Press. https://doi.org/10.1201/9780849380273
Popova-Zeugmann, L. (2013). Time and Petri Nets. Springer. https://doi.org/10.1007/978-3-642-41115-1
Rawson, M. y Rawson, M. G. (2022). Petri nets for concurrent programming. arXiv, 2208.02900. https://doi.org/10.48550/arXiv.2208.02900
Real Academia Española. (s.f.). Par. En Diccionario de la lengua española. Recuperado el 25 de abril de 2025 de https://dle.rae.es/par
Roszkowska, E. (2004). Supervisory control for deadlock avoidance in compound processes. IEEE Transactions on Systems, Man, and Cybernetics - Part A: Systems and Humans, 34(1), 52-64. https://doi.org/10.1109/TSMCA.2003.820572
Smiri, K., Dimerad, R. B. y El Ayeb, F. (2024). Hardware/Software Co-design in Multiprocessors Embedded Systems and IoT. Journal of Theoretical and Applied Information Technology, 102(2), 719-726.
Tanenbaum, A. S. (2016). Structured computer organization. Computer Languages, 10(3-4), 237. https://doi.org/10.1016/0096-0551(85)90019-0
Tricas, F., Garcia-Valles, F., Colom, J. M. y Ezpeleta, J. (2005). A Petri net structure-based deadlock prevention solution for sequential resource allocation systems.Proceedings of the 2005 IEEE International Conference on Robotics and Automation, Barcelona, 2005, 271-277. https://doi.org/10.1109/ROBOT.2005.1570131
Ventre, L. O. y Micolini, O. (2021). Extended Petri net processor and threads quantity determination algorithm for embedded systems. En P. Pesado y J. Eterovic (Eds.), Computer Science – CACIC 2020. CACIC 2020. Communications in Computer and Information Science (vol. 1409). Springer. https://doi.org/10.1007/978-3-030-75836-3_14
Ventre, L. O. y Micolini, O. (2022). Algoritmos para determinar cantidad y responsabilidad de hilos en sistemas embebidos modelados con Redes de Petri S3PR [ponencia]. XXVII Congreso Argentino de Ciencias de la Computación. Red de Universidades con Carreras en Informática. Ciudad Autónoma de Buenos Aires, Argentina. https://sedici.unlp.edu.ar/handle/10915/130440
Wolf, W. (2010). High-performance embedded computing: architectures, applications, and methodologies. Morgan Kaufmann. https://doi.org/10.1016/B978-0-12-369485-0.X5000-3
Zhao, M. y Hou, Y. (2013). An iterative method for synthesizing non-blocking supervisors for a class of generalized Petri nets using mathematical programming. Discrete Event Dynamic Systems, (23), 3-17. https://doi.org/10.1007/s10626-011-0124-9
Zhou, F., Cao, Z., Ge, Q., Zhang, Q., Zhao, D., Liu, S. y Chen, Y. (2023). A real-time phase processing system for phase sensitive optical time domain reflectometer. Review of Scientific Instruments, 94(1),014710. https://doi.org/10.1063/5.0132420
Descargas
Publicado
Número
Sección
Licencia
Derechos de autor 2026 Luis O. Ventre, Orlando Micolini, Mauricio Ludemann, Gabriel Valenzuela
Esta obra está bajo una licencia internacional Creative Commons Atribución-NoComercial-CompartirIgual 4.0.
Aquellos autores/as que tengan publicaciones con esta revista, aceptan los términos siguientes:
- Los autores/as conservarán sus derechos de autor y garantizarán a la revista el derecho de primera publicación de su obra, el cuál estará simultáneamente sujeto a la Creative Commons Atribución-NoComercial-CompartirIgual 4.0 Internacional (CC BY-NC-SA 4.0) que permite a terceros compartir la obra siempre que se indique su autor y su primera publicación esta revista, no hagan uso comercial de ella y las obras derivadas de hagan bajo la misma licencia.
- Los autores/as podrán adoptar otros acuerdos de licencia no exclusiva de distribución de la versión de la obra publicada (p. ej.: depositarla en un archivo telemático institucional o publicarla en un volumen monográfico) siempre que se indique la publicación inicial en esta revista.
- Se permite y recomienda a los autores/as difundir su obra a través de Internet (p. ej.: en archivos telemáticos institucionales o en su página web) antes y durante el proceso de envío, lo cual puede producir intercambios interesantes y aumentar las citas de la obra publicada. (Véase El efecto del acceso abierto).
