AvPI: un algoritmo para cuantificar el paralelismo promedio en redes de Petri S3PR con políticas de prevención de interbloqueos

Resumen

Esta investigación aborda el desafío crítico de cuantificar el paralelismo en sistemas embebidos modelados con redes de Petri S3PR, donde las políticas de prevención de deadlock imponen restricciones que limitan la concurrencia. Presentamos un algoritmo innovador para calcular el Índice de Paralelismo Promedio (AvPI), métrica que evalúa el número promedio de tareas ejecutables concurrentemente en todos los estados alcanzables. La metodología integra análisis estructural de invariantes de transición y grafos de alcanzabilidad, excluyendo plazas de recursos/buffers para aislar el paralelismo accionable. Validado mediante un caso de estudio que compara configuraciones propensas y libres de deadlocks, los resultados demuestran que políticas sobre-restrictivas (ej. control de sifones) reducen el AvPI en un 82% (a 0,9) y los estados en un 99%, mientras que controles selectivos preservan alta concurrencia (Av-PI=4,5953; 1017 estados) sin bloqueos. El AvPI conecta modelado teórico y di-seño práctico, permitiendo optimizar asignación de recursos y confiabilidad en etapas tempranas para sistemas críticos como vehículos autónomos e IoT industrial. Futuros trabajos se extenderán a redes temporizadas.