Algoritmo de Peterson

Algoritmo de Peterson (o 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 solo -usar recursos sin conflicto, usando solo memoria compartida para la comunicación. Fue formulado por Gary L. Peterson en 1981. Si bien la formulación original de Peterson funcionó con solo dos procesos, el algoritmo se puede generalizar para más de dos.

El algoritmo

El algoritmo utiliza dos variables: flag y turn. Un valor flag[n] de true indica que el proceso n quiere entrar en la sección crítica. La entrada a la sección crítica se otorga para el proceso P0 si P1 no desea ingresar a su sección crítica o si P1 le ha dado prioridad a P0 configurando turn a 0.

bool bandera[2] = {}falso, falso};int turno;

P0: bandera[0] = verdadero;P0_gate: turno = 1; mientras ()bandera[1] == verdadero " turno == 1) {} // ocupado espera } // sección crítica ... // final de la sección crítica bandera[0] = falso;

P1: bandera[1] = verdadero;P1_gate: turno = 0; mientras ()bandera[0] == verdadero " turno == 0) {} // ocupado espera } // sección crítica ... // final de la sección crítica bandera[1] = falso;

El algoritmo satisface los tres criterios esenciales para resolver el problema de la sección crítica. La condición while funciona incluso con preferencia.

Los tres criterios son exclusión mutua, progreso y espera limitada.

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.

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, flag[1] es false (lo que significa que P1 ha dejado su sección crítica) o turn es 0 (lo que significa que P1 ahora está tratando de ingresar a la sección crítica, pero espera gentilmente), 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 configurar turn a 0 y espera ocupado). Entonces, si ambos procesos están en sus secciones críticas, concluimos que el estado debe satisfacer flag[0] y flag[1] y turn = 0 y giro = 1. Ningún estado puede satisfacer tanto turn = 0 como turn = 1, por lo que 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.)

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 decisión sobre qué proceso entrará en 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 puede posponerse indefinidamente. 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 haber 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. En el algoritmo de Peterson, un proceso nunca esperará más de un turno para ingresar a la sección crítica.

Filter algorithm: Peterson 's algorithm for more than two processes

El algoritmo de filtrado generaliza el algoritmo de Peterson a N > 2 procesos. 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: array de N enteros
last_to_enter: array de N − 1 enteros

Las variables level toman valores de hasta N − 1, cada una de las cuales representa un "sala de espera" antes de la sección crítica. Los procesos avanzan de una sala a la siguiente y terminan en la sala N − 1, que es la sección crítica. Específicamente, para adquirir un bloqueo, el proceso i ejecuta

i ← Proceso No
para l desde 0 a N - 1 exclusivanivel[i] ← l
← i
 mientras último_to_enter[l] = i y existe k ل i, tal que nivel[k] ≥ l
 Espera.

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

Que este algoritmo logra la exclusión mutua se puede demostrar de la siguiente manera. El proceso i sale del ciclo interno cuando no hay ningún proceso con un nivel superior al level[ i], por lo que la siguiente sala de espera está libre; o, cuando i ≠ last_to_enter[ℓ], entonces otro proceso se unió a su sala de espera. Entonces, en el nivel cero, incluso si todos los procesos N entraran en la sala de espera cero al mismo tiempo, no más de N − 1 pasará a la habitación siguiente, y la última será la última en entrar en la habitación. De manera similar, en el siguiente nivel, N − 2 procederá, etc., hasta que en el nivel final, solo un proceso puede salir de la espera habitación y entrar en la sección crítica, dando exclusión mutua.

A diferencia del algoritmo de Peterson de dos procesos, el algoritmo de filtro no garantiza una espera limitada.

Nota

Cuando se trabaja a nivel de hardware, normalmente no se necesita el algoritmo de Peterson para lograr el acceso atómico. Algunos procesadores tienen instrucciones especiales, como test-and-set o compare-and-swap, que, al bloquear el bus de memoria, pueden usarse 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 la ejecución (consulte el ordenamiento de la memoria para conocer los tipos de reordenamiento permitidos). Dichos procesadores invariablemente brindan 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 otros relacionados en los 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 Xbox 360).

La mayoría de estas CPU también tienen algún tipo de operación atómica garantizada, como XCHG en procesadores x86 y load-link/store-conditional en Alpha, MIPS, PowerPC y otras arquitecturas. Estas instrucciones están destinadas a proporcionar una manera de construir primitivos de sincronización de manera más eficiente que con enfoques de memoria compartida puros.