logo móvil
Contáctanos

Verificación de la corrección de algoritmos de exclusión mutua mediante verificación de modelos

Autores: Nigro, Libero; Cicirelli, Franco

Idioma: Inglés

Editor: MDPI

Año: 2024

Descargar PDF

Acceso abierto

Artículo científico
2024

Verificación de la corrección de algoritmos de exclusión mutua mediante verificación de modelos


Categoría

Procesos industriales

Subcategoría

Simulación de procesos industriales

Palabras clave

Algoritmos de exclusión mutua
Libertad de inanición
By-passes
Tiempo de espera acotado
Autómatas Temporizados
Conjunto de herramientas Uppaal

Licencia

CC BY-SA – Atribución – Compartir Igual

Consultas: 20

Citaciones: Sin citaciones


Descripción
Los algoritmos de exclusión mutua son el corazón de los sistemas concurrentes/paralelos y distribuidos. Es bien sabido que tales algoritmos son muy difíciles de analizar, y en la literatura existen diferentes conjeturas sobre la libertad de inanición y el número de adelantamientos (también llamado factor de adelantamiento). El factor de adelantamiento afecta el tiempo de espera (con suerte) acotado que un proceso compitiendo por entrar en la sección crítica tiene que sufrir antes de acceder al recurso compartido. Este artículo propone un enfoque de modelado novedoso basado en Autómatas Temporizados y el conjunto de herramientas Uppaal, que resulta efectivo para estudiar todas las propiedades de un algoritmo de exclusión mutua para procesos, mediante verificación exhaustiva del modelo. Aunque el enfoque, como ya han confirmado experimentos similares reportados en la literatura, no es escalable debido a problemas de explosión de estados y solo puede aplicarse en la práctica hasta , es de gran valor para revelar las verdaderas propiedades de los algoritmos analizados. Para dimensiones , se puede utilizar el Verificador de Modelos Estadísticos de Uppaal, que, aunque basado en simulaciones, puede confirmar propiedades mediante estimaciones y probabilidades. Este artículo describe el método de modelado y verificación propuesto y lo aplica a varios algoritmos de exclusión mutua, recuperando así propiedades conocidas pero también mostrando nuevos resultados sobre propiedades a menudo estudiadas mediante razonamiento informal.

Otros recursos que podrían interesarte

Temas Virtualpro