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] 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 concibió Lamport (la solución de Lamport utilizó n variables de comunicación factoriales frente a las 5 de Szymański).
El algoritmo
El algoritmo se basa en una sala de espera con una puerta de entrada y salida. [1] Inicialmente, la puerta de entrada está abierta y la puerta de salida está cerrada. Todos los procesos que solicitan el ingreso a la sección crítica aproximadamente al mismo tiempo ingresan a la sala de espera; el último de ellos cierra la puerta de entrada y abre la puerta de salida. Luego, los procesos ingresan a la sección crítica uno por 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 puede entrar el siguiente lote de procesos.
La aplicación consiste en que cada proceso de tener un indicador variable que está escrito por ese proceso y leída por todos los demás (esta propiedad de un solo escritor es deseable para una eficiente caché de uso). El estado de la puerta de entrada se calcula leyendo las banderas de todos los procesos. El pseudocódigo se proporciona a continuación:
# Entrada protocolo bandera [ auto ] ← 1 # de pie fuera de la sala de espera await ( todo flag [ 1. . N ] ∈ { 0 , 1 , 2 }) # Espere a puerta abierta bandera [ auto ] ← 3 # coloca en el umbral si cualquier bandera [ 1 .. N ] = 1 : # Otro proceso está esperando para ingresar bandera [ self ] ← 2 # Esperando que otros procesos entren en espera ( cualquier bandera [ 1 .. N ] = 4 ) # Espere a que un proceso entre y cierre la puertaflag [ self ] ← 4 # La puerta está cerrada aguardar ( todos los flag [ 1 .. self - 1 ] ∈ { 0 , 1 }) # Esperar a que todos los de ID inferior terminen el protocolo de salida# Sección crítica # ...# Protocolo de salida en espera ( todos marcan [ self + 1 .. N ] ∈ { 0 , 1 , 4 }) # Asegúrese de que todos en la sala de espera # se hayan dado cuenta de que la puerta debe estar cerrada flag [ self ] ← 0 # Salir . Vuelva a abrir la puerta si todavía no hay nadie en la sala de espera
Tenga en cuenta que el orden de las pruebas "todos" y "cualquiera" debe ser uniforme. Además, las pruebas "cualquiera" deben ser satisfechas por un hilo que no sea self. Por ejemplo, si la prueba es cualquier marca [1..N] = 1 y solo marca [self] = 1, entonces se dice que la prueba falló / devolvió 0. A pesar de la explicación intuitiva, el algoritmo no fue fácil de probar. correcto , sin embargo, debido a sus propiedades favorables, era deseable una prueba de corrección y se han presentado múltiples pruebas. [2] [5]
Referencias
- ↑ a b Szymański, Bolesław K. (1988). "Una solución simple al problema de programación concurrente de Lamport con espera lineal". Actas de la 2da conferencia internacional sobre supercomputación - ICS '88 . ICS '88: Actas de la 2ª Conferencia Internacional de Supercomputación . St. Malo, Francia: ACM. págs. 621–626. doi : 10.1145 / 55364.55425 . ISBN 978-0-89791-272-3. S2CID 18612278 .
- ^ a b Maná, Zohar ; Pnueli, Amir (1990). "Un ejercicio de verificación de programas multiproceso". La belleza es nuestro negocio: Un saludo de cumpleaños a Edsger W. Dijkstra . Springer Verlag. págs. 289-301. ISBN 978-0-387-97299-2.
- ^ Szymański, Bolesław (1990). "Revisión de la exclusión mutua" (PDF) . Quinta Conferencia de Jerusalén sobre Tecnología de la Información . Jerusalén, Israel: 110-117.
- ^ Lamport, Leslie (1986). "El problema de la exclusión mutua: parte II: declaración y soluciones". Revista de la ACM . 33 (2): 327–348. CiteSeerX 10.1.1.32.9808 . doi : 10.1145 / 5383.5385 . S2CID 7387839 .
- ^ de Roever, Willem-Paul; de Boer, Frank; Hannemann, Ulrich; Hooman, Jozef; Lakhnech, Yassine; Poel, Mannes; Zwiers, Job (noviembre de 2002). Verificación de concurrencia . Número 54 en Cambridge Tracts in Theoretical Computer Science. Prensa de la Universidad de Cambridge. doi : 10.2277 / 0521806089 (inactivo el 31 de mayo de 2021). ISBN 978-0-521-80608-4.Mantenimiento de CS1: DOI inactivo a partir de mayo de 2021 ( enlace )