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

Abstract

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.

This research addresses the critical challenge of quantifying parallelism in embedded systems modeled with S3PR Petri nets, where deadlock prevention policies often impose restrictive constraints that limit concurrency. We introduce a novel algorithm to compute the Average Parallelism Index (AvPI), a metric evaluating the average number of concurrently executable tasks across all reachable states. The methodology leverages structural analysis of transition invariants and reachability graphs while excluding resource/buffer places to isolate actionable parallelism. Validated through a case study comparing deadlock-prone and deadlock-free configurations, results demonstrate that overly restrictive policies (ej., siphon control) reduce AvPI by 82% (to 0.9) and states by 99%, while selective control preserves high concurrency (AvPI=4.5953, 1017 states) without deadlocks. The AvPI bridges theoretical modeling and practical design, enabling early-stage optimization of resource allocation and reliability in critical systems like autonomous vehicles and industrial IoT. Future work will extend to timed Petri nets to incorporate temporal dynamics.