Newtonpedia EN
Inicio › Informática › Algoritmo de la panadería de Lamport
Informática · 1973

Algoritmo de la panadería de Lamport

Un procedimiento de turnos que permite a varios hilos de ejecución de un programa usar un recurso compartido de uno en uno, sin que se pisen.

Año
1973
Protagonistas
Leslie Lamport
Sección
Informática

Historia

El algoritmo de la panadería de Lamport resuelve un problema básico de la informática: cuando varios hilos de ejecución (secuencias de instrucciones que avanzan a la vez dentro de un mismo programa) necesitan escribir o leer la misma zona de memoria, pueden corromper los datos. Para evitarlo, hace falta que solo uno entre en su sección crítica, el fragmento de código que accede al recurso compartido, mientras los demás esperan. Este fenómeno se llama exclusión mutua.

Antes de este algoritmo ya existían soluciones para la exclusión mutua, pero en general dependían de instrucciones especiales del procesador o del sistema operativo, como los cerrojos o las operaciones atómicas. Leslie Lamport, científico en computación conocido por sus trabajos sobre la corrección formal de sistemas concurrentes, buscó una solución más simple y con garantías demostrables. Su idea partió de una comparación cotidiana: la forma en que las panaderías atienden a los clientes por orden de llegada, mediante un número de turno.

El funcionamiento es así. Cada hilo que quiere entrar en la sección crítica calcula su número como el máximo de los números actuales de los demás, más uno. Después comprueba que su número es el más bajo de todos. Si dos hilos obtienen el mismo número, se desempata por el identificador: gana el de número más bajo. Al salir de la sección crítica, el hilo pone su número a cero, lo que indica que ya no está interesado en entrar. Para evitar que dos hilos calculen su número a la vez y se lleven un valor duplicado sin darse cuenta, el algoritmo usa una segunda variable que marca a los hilos que están eligiendo turno. Así, nadie compara con un vecino que aún no ha terminado de calcular.

La publicación original de Lamport, en 1974, tuvo una particularidad: el algoritmo no necesita operaciones atómicas de bajo nivel, es decir, instrucciones indivisibles del hardware. Solo requiere que las escrituras sobre una misma celda sean correctas, mientras que las lecturas simultáneas pueden devolver valores arbitrarios que el algoritmo sabe tolerar. Esto lo hace útil para implementar exclusión mutua en memorias sin mecanismos de sincronización, por ejemplo en un disco compartido entre dos ordenadores. La contrapartida es que cada hilo debe esperar activamente, consultando repetidamente las variables de los demás, lo que consume tiempo de procesador en sistemas con muchos hilos.

Con el tiempo, el algoritmo se convirtió en un modelo de referencia para enseñar la exclusión mutua y el razonamiento sobre concurrencia. Sus ideas aparecen en la formalización de protocolos y en la verificación de sistemas distribuidos. Sin embargo, los lenguajes y procesadores modernos no garantizan el modelo de memoria que supone el algoritmo, de modo que una implementación real suele necesitar barreras de memoria que impidan reordenar instrucciones. En la práctica, los sistemas actuales usan primitivas de hardware más eficientes, pero la lógica de los turnos sigue presente en la formación de programadores y en el diseño de sistemas donde varias partes deben coordinarse sin un árbitro central.

Cronología

  • 1973Leslie Lamport concibe el algoritmo, que resuelve la exclusión mutua entre N procesos o hilos.
  • 1974Se publica la formulación original, con la idea de los números de turno y el desempate por identificador.

Curiosidades y anécdotas

Inspiración cotidiana

El nombre procede de las panaderías y tiendas donde cada cliente recoge un boleto numerado para ser atendido por orden de llegada.

Sin operaciones atómicas

A diferencia de muchos métodos, no depende de instrucciones indivisibles del hardware, lo que permite usarlo en memorias muy sencillas.

Protagonistas

Otros hitos de informática