El algoritmo de Peterson

El algoritmo de Peterson (o solución de Peterson ) es un algoritmo de programación concurrente para exclusión mutua que permite que dos o más procesos compartan un recurso de uso único sin conflicto, utilizando únicamente memoria compartida para la comunicación . Fue formulado por Gary L. Peterson en 1981. ^{[ 1 ]} El algoritmo original de Peterson funcionaba solo con dos procesos; puede generalizarse para más de dos. ^{[ 2 ]}

El algoritmo

El algoritmo utiliza dos variables: flagy turn. Un flag[n]valor de trueindica que el proceso nquiere entrar en la sección crítica . Se concede la entrada a la sección crítica al proceso P0 si P1 no quiere entrar en su sección crítica o si P1 ha dado prioridad a P0 estableciendo turnen 0.

El algoritmo satisface los tres criterios esenciales para resolver el problema de la sección crítica. La condición while funciona incluso con preemption. ^{[ 1 ]}

Los tres criterios son la exclusión mutua , el progreso y la espera limitada. ^{[ 3 ]}

Dado que turnpuede tomar uno de dos valores, puede reemplazarse por un solo bit, lo que significa que el algoritmo requiere solo tres bits de memoria. ^{[ 4 ]}^{: 22}

Exclusión mutua

P0 y P1 nunca pueden estar en la sección crítica al mismo tiempo. Si P0 está en su sección crítica, entonces flag[0]es verdadero. Además, o bien flag[1]es false(lo que significa que P1 ha salido de su sección crítica), o bien turnes 0(lo que significa que P1 está intentando entrar en la sección crítica, pero esperando pacientemente), o bien P1 está en la etiqueta P1_gate(intentando entrar en su sección crítica, después de establecer flag[1]en truepero antes de establecer turnen 0y esperando activamente). Por lo tanto, si ambos procesos están en sus secciones críticas, concluimos que el estado debe satisfacer flag[0]y flag[1]y turn = 0y turn = 1. Ningún estado puede satisfacer tanto turn = 0como turn = 1, por lo que no puede haber un estado donde ambos procesos estén en sus secciones críticas. (Esto relata un argumento que se formaliza rigurosamente en Schneider 1997. ^{[ 5 ]} )

Progreso

El progreso se define de la siguiente manera: si ningún proceso se está ejecutando en su sección crítica y algunos procesos desean entrar en sus secciones críticas, entonces solo aquellos procesos que no se estén ejecutando en sus secciones restantes pueden participar en la decisión sobre qué proceso entrará en su sección crítica a continuación. Nótese que, para un proceso o hilo, las secciones restantes son partes del código que no están relacionadas con la sección crítica. Esta selección no puede posponerse indefinidamente. ^{[ 3 ]} Un proceso no puede volver a entrar inmediatamente en la sección crítica si el otro proceso ha establecido su bandera para indicar que desea entrar en su sección crítica.

Espera atada

La espera limitada, o derivación limitada , significa que el número de veces que un proceso es derivado por otro proceso después de que ha indicado su deseo de entrar en la sección crítica está limitado por una función del número de procesos en el sistema. ^{[ 3 ]}^{[ 4 ]}^{: 11} En el algoritmo de Peterson, un proceso nunca esperará más de un turno para entrar en la sección crítica.

Algoritmo de filtrado: algoritmo de Peterson para más de dos procesos.

El algoritmo de filtro generaliza el algoritmo de Peterson a $N > 2$ procesos. ^{[ 6 ]} En lugar de una bandera booleana, requiere una variable entera por proceso, almacenada en un registro atómico de un solo escritor/múltiples lectores (SWMR) , y $N - 1$ variables adicionales en registros similares. Los registros se pueden representar en pseudocódigo como matrices :

nivel: matriz de N enteros last_to_enter: matriz de N − 1 enteros

Las variables de nivel toman valores hasta $N - 1$ , cada uno representando una "sala de espera" distinta antes de la sección crítica. ^{[ 6 ]} Los procesos avanzan de una sala a la siguiente, terminando en la sala $N - 1$ , que es la sección crítica. Específicamente, para adquirir un bloqueo, el proceso $i$ ejecuta ^{[ 4 ]}^{: 22}

i ← ProcessNo para ℓ de 0 a N − 1 exclusivo nivel[i] ← ℓ último_en_entrar[ℓ] ← i mientras last_to_enter[ℓ] = i y exista k ≠ i, tal que level[k] ≥ ℓ espere

Para liberar el bloqueo al salir de la sección crítica, el proceso $i$ establece level[i] en −1.

Que este algoritmo logra la exclusión mutua se puede demostrar de la siguiente manera. El proceso $i$ sale del bucle interno cuando no hay ningún proceso con un nivel superior a level[i] , por lo que la siguiente sala de espera está libre; o bien, cuando i ≠ last_to_enter[ℓ] , otro proceso se unió a su sala de espera. En el nivel cero, incluso si los $N$ procesos entraran a la sala de espera cero al mismo tiempo, no más de $N$ $-$ $1$ pasarán a la siguiente sala, siendo el último en entrar. De manera similar, en el siguiente nivel, $N$ $-$ $2$ pasarán, etc. , hasta que en el nivel final, solo se permite que un proceso salga de la sala de espera y entre en la sección crítica, lo que da lugar a la exclusión mutua. ^[⁴^]^:^22–24

A diferencia del algoritmo de Peterson de dos procesos, el algoritmo de filtro no garantiza un tiempo de espera limitado. ^{[ 4 ]}^{: 25–26}

Problemas modernos

En las máquinas modernas, el algoritmo de Peterson (como se muestra aquí) no proporciona exclusión mutua. Declaraciones y/o instrucciones adicionales pueden hacer que funcione (aunque diferentes métodos que utilizan las características del lenguaje y/o nuevas instrucciones de máquina pueden lograr la exclusión mutua de manera más eficiente). Las computadoras se han vuelto mucho más complejas desde 1981; ya no ejecutan instrucciones de forma sincronizada. La mayoría de los compiladores cambian el orden de las operaciones de manera que produzcan los mismos resultados más rápido, pero no consideran la interacción de operaciones concurrentes que acceden a los mismos datos. Las CPU reordenan las instrucciones dentro de sus tuberías de ejecución. Las CPU preleen el contenido de la memoria, almacenan en caché el contenido de la memoria y retrasan y combinan escrituras. Múltiples núcleos de CPU pueden acceder a la misma memoria con verdadera concurrencia. Múltiples CPU pueden tener cachés separadas que pueden retrasar la sincronización. Cualquiera de estos puede romper el algoritmo de Peterson. ^{[ 7 ]} Para permitir una exclusión mutua utilizable en este nuevo entorno, se han agregado instrucciones de máquina, como barrera de memoria y operaciones atómicas de lectura y modificación. Estas instrucciones permiten que las cosas se "pongan al día" cuando sea necesario. Los lenguajes de programación han agregado características que invocan estas instrucciones. En varios lenguajes de programación, declarar una variable como volatile produce código ejecutable que accede a la variable con mayor precaución.

El algoritmo de Peterson no suele ser necesario para garantizar el acceso atómico. En procesadores y sistemas operativos anteriores, bastaba con deshabilitar las interrupciones justo antes de una sección crítica y volver a habilitarlas una vez finalizada. La mayoría de los procesadores modernos cuentan con instrucciones especiales que permiten construir primitivas de sincronización de forma más eficiente que con los enfoques de memoria compartida pura. Estas instrucciones, al bloquear el bus de memoria , pueden utilizarse para garantizar la atomicidad y proporcionar exclusión mutua en sistemas de multiprocesamiento simétricos . Algunos ejemplos son las instrucciones `test-and-set` y XCHG` compare-and-swap` en CMPXCHGprocesadores x86, y ` load-link/store-conditional` en arquitecturas Alpha , MIPS , PowerPC y otras.

La mayoría de las CPU modernas reordenan los accesos a memoria para mejorar la eficiencia de ejecución (consulte la sección sobre ordenamiento de memoria para conocer los tipos de reordenamiento permitidos). Estos procesadores invariablemente proporcionan algún método para forzar el ordenamiento en una secuencia de accesos a memoria, generalmente mediante una instrucción de barrera de memoria . La implementación de los algoritmos de Peterson y similares en procesadores que reordenan los accesos a memoria generalmente requiere el uso de dichas operaciones para funcionar correctamente y evitar que las operaciones secuenciales se ejecuten en un orden incorrecto. El reordenamiento de los accesos a memoria puede ocurrir incluso en procesadores que no reordenan las instrucciones (como el procesador PowerPC de la Xbox 360 ).

Véase también

Notas a pie de página

1 2 G. L. Peterson: "Mitos sobre el problema de la exclusión mutua", Information Processing Letters 12(3) 1981, 115–116
↑ Como se comenta en Operating Systems Review , enero de 1990 ("Prueba de un algoritmo de exclusión mutua", M. Hofri).
1 2 3 Silberschatz. Conceptos de sistemas operativos: Séptima edición. John Wiley and Sons, 2005, página 194.
1 2 3 4 5 Raynal, Michel (2012). Programación concurrente: algoritmos, principios y fundamentos . Springer Science & Business Media. ISBN 978-3642320279.
↑ FB Schneider, Sobre programación concurrente , Springer Verlag, 1997, páginas 185–196.
1 2 Herlihy, Maurice ; Shavit, Nir (2012). El arte de la programación multiprocesador . Elsevier. págs. 28–31 . ISBN 9780123977953.
↑ El algoritmo de los años 80 para evitar condiciones de carrera (y por qué falló) .

Enlaces externos

https://elixir.bootlin.com/linux/v5.6.19/source/arch/arm/mach-tegra/sleep-tegra20.S#L120 Ejemplo del algoritmo de Peterson que se utilizaba anteriormente en el kernel de Linux ( eliminado en la versión 5.7).