El algoritmo de exclusión mutua de Szymański es un algoritmo de exclusión mutua ideado por el científico informático Dr. Bolesław Szymański , que tiene muchas propiedades favorables, incluida la espera lineal, [1] [2] y cuya extensión [3] resolvió el problema abierto publicado por Leslie Lamport [4] sobre si existe un algoritmo con un número constante de bits de comunicación por proceso que satisfaga todos los requisitos razonables de equidad y tolerancia a fallas que Lamport concibió (la solución de Lamport usó n variables de comunicación factoriales frente a las 5 de Szymański).
El algoritmo está modelado sobre una sala de espera con una puerta de entrada y otra de salida. [1] Inicialmente, la puerta de entrada está abierta y la de salida está cerrada. Todos los procesos que solicitan la entrada a la sección crítica aproximadamente al mismo tiempo entran en la sala de espera; el último de ellos cierra la puerta de entrada y abre la de salida. A continuación, los procesos entran en la sección crítica uno a uno (o en grupos más grandes si la sección crítica lo permite). El último proceso en salir de la sección crítica cierra la puerta de salida y vuelve a abrir la puerta de entrada, por lo que el siguiente lote de procesos puede entrar.
La implementación consiste en que cada proceso tiene una variable de bandera que es escrita por ese proceso y leída por todos los demás (esta propiedad de escritor único es deseable para un uso eficiente de la memoria caché ).
La variable de bandera asume uno de los siguientes cinco valores/estados:
El estado de la puerta de entrada se calcula leyendo las banderas de todos los N procesos. El pseudocódigo se proporciona a continuación:
# Protocolo de entrada flag [ self ] ← 1 # De pie fuera de la sala de espera await ( all flag [ 1. . N ] ∈ { 0 , 1 , 2 }) # Esperando a que se abra la puerta flag [ self ] ← 3 # De pie en la puerta si hay alguna flag [ 1. . N ] = 1 : # Otro proceso está esperando para entrar flag [ self ] ← 2 # Esperando a que entren otros procesos await ( any flag [ 1. . N ] = 4 ) # Esperando a que entre un proceso y cierre la puertaflag [ self ] ← 4 # La puerta está cerrada await ( all flag [ 1. . self - 1 ] ∈ { 0 , 1 }) # Esperar a que todos con ID más bajo terminen de salir del protocolo# Sección crítica # ...# Salir del protocolo await ( all flag [ self + 1. . N ] ∈ { 0 , 1 , 4 }) # Asegurarse de que todos en la sala de espera se hayan # dado cuenta de que la puerta debe estar cerrada flag [ self ] ← 0 # Salir. Volver a abrir la puerta si todavía no hay nadie en la sala de esperaTenga en cuenta que el orden de las pruebas "all" y "any" debe ser uniforme. Además, las pruebas "any" deben ser satisfechas por un hilo distinto de self. Por ejemplo, si la prueba es any flag[1.. N ] = 1 y solo flag[self] = 1, entonces se dice que la prueba ha fallado/ha devuelto 0. A pesar de la explicación intuitiva, no fue fácil demostrar que el algoritmo fuera correcto , sin embargo, debido a sus propiedades favorables, era deseable una prueba de corrección y se han presentado múltiples pruebas. [2] [5]
{{cite book}}: Mantenimiento CS1: fecha y año ( enlace )