logo móvil
Contáctanos

Formalización y verificación del algoritmo de exclusión mutua de Lycklama y Hadzilacos

Autores: Nigro, Libero

Idioma: Inglés

Editor: MDPI

Año: 2024

Descargar PDF

Acceso abierto

Artículo científico
2024

Formalización y verificación del algoritmo de exclusión mutua de Lycklama y Hadzilacos


Categoría

Matemáticas

Subcategoría

Matemáticas generales

Palabras clave

Modelado
Verificación
Sistemas concurrentes
Algoritmo de exclusión mutua
Formal
LH

Licencia

CC BY-SA – Atribución – Compartir Igual

Consultas: 20

Citaciones: Sin citaciones


Descripción
Este estudio describe nuestra amplia experiencia en modelado formal y verificación exhaustiva de sistemas concurrentes, en particular algoritmos de exclusión mutua. La experiencia se centra en el algoritmo de exclusión mutua de Lycklama y Hadzilacos (LH). LH se basa en el tamaño reducido del estado compartido, contiene un mecanismo que intenta hacer cumplir un orden FCFS a los procesos que ingresan a su sección crítica, y encarna el algoritmo de exclusión mutua de Burns y Lamport (BL). La metodología de modelado se basa en autómatas temporizados y el verificador de modelos de la popular caja de herramientas Uppaal. La efectividad del enfoque de modelado y análisis se demuestra primero estudiando la solución de BL y recuperando todas sus propiedades, incluido, en general, su adelantamiento ilimitado, que es la cantidad no limitada de adelantamientos que un proceso puede sufrir antes de acceder a su sección crítica. Luego, el algoritmo LH se investiga en profundidad mostrando que cumple todas las propiedades de exclusión mutua cuando opera con memoria atómica. Sin embargo, como este estudio demuestra, LH no está libre de interbloqueos cuando se utiliza con memoria no atómica. Finalmente, se propone una solución de exclusión mutua de última generación, que se basa en una versión simplificada de LH para procesos, que se utiliza como unidad de arbitraje en una organización de árbol de torneo (TT). Este estudio documenta que el algoritmo basado en TT de LH satisface todas las propiedades de exclusión mutua, con un adelantamiento lineal, tanto utilizando memoria atómica como no atómica.

Otros recursos que podrían interesarte

Temas Virtualpro