El algoritmo de Peterson (o la solución de Peterson ) es un algoritmo de programación concurrente para la exclusión mutua que permite que dos o más procesos compartan un recurso de un solo uso sin conflictos, utilizando solo la memoria compartida para la comunicación . Fue formulado por Gary L. Peterson en 1981. [1] Si bien la formulación original de Peterson funcionó con solo dos procesos, el algoritmo se puede generalizar para más de dos. [2]
El algoritmo
El algoritmo usa dos variables flag
y turn
. Un flag[n]
valor de true
indica que el proceso n
quiere ingresar a la sección crítica . La entrada a la sección crítica se concede para el proceso P0 si P1 no quiere entrar en su sección crítica o si P1 ha dado prioridad a P0 estableciendo turn
en 0
.
bool flag [ 2 ] = { falso , falso }; int turn ; | |
P0 : bandera [ 0 ] = verdadero ; P0_gate : turn = 1 ; while ( flag [ 1 ] == true && turn == 1 ) { // espera ocupada } // sección crítica ... // fin de la sección crítica flag [ 0 ] = false ; | P1 : bandera [ 1 ] = verdadero ; P1_gate : turn = 0 ; while ( flag [ 0 ] == true && turn == 0 ) { // espera ocupada } // sección crítica ... // fin de la sección crítica flag [ 1 ] = false ; |
Adecuación del algoritmo de los tres criterios esenciales para resolver el problema de la sección crítica, siempre que los cambios en las variables turn
, flag[0]
y flag[1]
propagar inmediatamente y de forma atómica. La condición while funciona incluso con preferencia. [1]
Los tres criterios son exclusión mutua, progreso y espera limitada. [3]
Dado que turn
puede tomar uno de dos valores, puede ser reemplazado 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 cierto. Además, flag[1]
es false
(lo que significa que P1 ha abandonado su sección crítica), o turn
está 0
(lo que significa que P1 recién ahora está tratando de ingresar a la sección crítica, pero amablemente esperando), o P1 está en la etiqueta P1_gate
(tratando de ingresar a su sección crítica, después de configurar flag[1]
a true
pero antes de establecer turn
a 0
y ocupado esperando). Entonces, si ambos procesos están en sus secciones críticas, entonces concluimos que el estado debe satisfacer flag[0]
y flag[1]
y turn = 0
y turn = 1
. Ningún estado puede satisfacer ambos turn = 0
y turn = 1
, por lo tanto , no puede haber ningún estado en el que ambos procesos se encuentren en sus secciones críticas. (Esto relata un argumento que se hace riguroso en. [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 ingresar a sus secciones críticas, entonces solo aquellos procesos que no se están ejecutando en sus secciones restantes pueden participar en la toma de la decisión sobre qué proceso ingresará. su sección crítica a continuación. Tenga en cuenta que para un proceso o subproceso, las secciones restantes son partes del código que no están relacionadas con la sección crítica. Esta selección no se puede posponer indefinidamente. [3] Un proceso no puede volver a ingresar inmediatamente a la sección crítica si el otro proceso ha establecido su bandera para decir que le gustaría ingresar a su sección crítica.
Espera limitada
Espera limitada o derivación limitada significa que la cantidad de veces que un proceso es omitido por otro proceso después de que ha indicado su deseo de ingresar a la sección crítica está limitada por una función de la cantidad de procesos en el sistema. [3] [4] : 11 En el algoritmo de Peterson, un proceso nunca esperará más de un turno para entrar a la sección crítica.
Algoritmo de filtro: 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 / lector múltiple (SWMR) y N −1 variables adicionales en registros similares. Los registros se pueden representar en pseudocódigo como matrices :
nivel: matriz de N enteroslast_to_enter: matriz de N − 1 enteros
Las variables de nivel toman valores hasta N- 1 , cada una representando una "sala de espera" distinta antes de la sección crítica. [6] Los procesos avanzan de una habitación a la siguiente, terminando en la habitación 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] ← ℓ last_to_enter [ℓ] ← i mientras que last_to_enter [ℓ] = i y existe k ≠ i, tal que el nivel [k] ≥ ℓ espera
Para liberar el bloqueo al salir de la sección crítica, el proceso i establece nivel [i] a -1.
Que este algoritmo logra la exclusión mutua se puede probar de la siguiente manera. El proceso i sale del bucle interno cuando no hay ningún proceso con un nivel superior a nivel [i] , por lo que la siguiente sala de espera es libre; o cuando i ≠ last_to_enter [ℓ] , por lo que otro proceso se unió a su sala de espera. En el nivel cero, entonces, incluso si todos los N procesos ingresaran a la sala de espera cero al mismo tiempo, no más de N −1 pasará a la siguiente sala, siendo el último el último en ingresar a la sala. De igual forma, en el siguiente nivel se procederá N −2 , etc. , hasta que en el último nivel, solo se permita a un proceso salir de la sala de espera y entrar en la sección crítica, dando mutua exclusión. [4] : 22-24
También se puede demostrar que el algoritmo está libre de inanición, lo que significa que todos los procesos que ingresan al bucle eventualmente lo abandonan (asumiendo que no permanecen en la sección crítica de manera indefinida). La demostración procede por inducción desde N −1 hacia abajo. Un proceso en N −1 está en la sección crítica y, por supuesto, saldrá de ella. En todos los niveles inferiores ℓ , es imposible que un proceso i espere eternamente, ya que otro proceso j entrará en la sala de espera, configurando last_to_enter [ℓ] ← j y "liberando" i ; o esto nunca sucede, pero entonces todos los procesos j que también están en las salas de espera deben estar en niveles más altos y por la hipótesis inductiva, eventualmente terminarán el ciclo y restablecerán sus niveles, de modo que para todo k ≠ i , nivel [k] <ℓ y i de nuevo sale del bucle. [4] : 24-25
La inanición libertad es de hecho la más alta liveness garantía de que el algoritmo da; a diferencia del algoritmo de Peterson de dos procesos, el algoritmo de filtro no garantiza una espera limitada. [4] : 25-26
Nota
Cuando se trabaja a nivel de hardware , el algoritmo de Peterson normalmente no es necesario para lograr el acceso atómico. Algunos procesadores tienen instrucciones especiales, como probar y configurar o comparar e intercambiar , que, al bloquear el bus de memoria, se pueden utilizar para proporcionar exclusión mutua en sistemas SMP .
La mayoría de las CPU modernas reordenan los accesos a la memoria para mejorar la eficiencia de ejecución (consulte el orden de la memoria para conocer los tipos de reordenación permitidos). Dichos procesadores invariablemente dan alguna forma de forzar el orden en un flujo de accesos a la memoria, generalmente a través de una instrucción de barrera de memoria . La implementación de los algoritmos de Peterson y relacionados en procesadores que reordenan los accesos a la memoria generalmente requiere el uso de tales operaciones para que funcionen correctamente y evitar que las operaciones secuenciales ocurran en un orden incorrecto. Tenga en cuenta que el reordenamiento de los accesos a la memoria puede ocurrir incluso en procesadores que no reordenan las instrucciones (como el procesador PowerPC en la Xbox 360 ). [ cita requerida ]
La mayoría de estas CPU también tienen algún tipo de operación atómica garantizada , como XCHG
en los procesadores x86 y condicional de carga / enlace de almacenamiento en Alpha , MIPS , PowerPC y otras arquitecturas. Estas instrucciones están destinadas a proporcionar una forma de construir primitivas de sincronización de manera más eficiente que lo que se puede hacer con enfoques de memoria compartida pura.
Ver también
Notas al pie
- ^ a b G. L. Peterson: "Mitos sobre el problema de exclusión mutua", Cartas de procesamiento de información 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).
- ^ a b c Silberschatz. Conceptos de sistemas operativos: séptima edición. John Wiley and Sons, 2005., páginas 194
- ↑ a b c d e f Raynal, Michel (2012). Programación concurrente: algoritmos, principios y fundamentos . Springer Science & Business Media. ISBN 3642320279.
- ^ FB Schneider. On Concurrent Programming, Sringer Verlag, 1997, páginas 185–196
- ^ a b Herlihy, Maurice ; Shavit, Nir (2012). El arte de la programación multiprocesador . Elsevier. pag. 28–31. ISBN 9780123977953.
enlaces externos
- https://elixir.bootlin.com/linux/latest/source/arch/arm/mach-tegra/sleep. S Implementación del algoritmo de Peterson