ALGORITMO DE LAMPORT

Lamport desarrolló una solución que es particularmente aplicable a los sistemas de procesamiento distribuido.

El algoritmo usa un sistema de "toma de boleto", como el usado en las panaderías muy concurridas, y ha sido apodado el algoritmo de la panadería de Lamport. Nos centraremos únicamente en los aspectos del algoritmo relacionados con un entorno centralizado. Al entrar en la tienda cada cliente recibe un número, y se atiende primero al que tenga el número menor. Por desgracia, el algoritmo de la panadería no puede garantizar que dos procesos (clientes) no reciban el mismo número.

En el caso de un empate, primero se atiende el proceso con el nombre menor. Es decir, si Pi y Pj reciben el mismo número y si i < j, entonces primero se servirá a Pi. Como los nombres de procesos son únicos y ordenados, nuestro algoritmo es completamente determinista.

Las estructuras de datos comunes son: var boleto: array[1..nprocs] of integer; eleccion: array[1..nprocs] of boolean; Al principio, a estas estructuras se les asigna un valor inicial 0 y false, respectivamente. Por conveniencia, definimos la siguiente notación: n (a,b) < (c,d) si (a < c) o si (a = c) y b < d condición que determina si el proceso b con el boleto a es favorecido o no para entrar a la sección crítica con respecto al proceso d con el boleto c. (en el programa bakery esta condición se implementa por medio de la función favorecido). n max(a1 , ... , an) es un número, k, tal que k > ai para i=1, ...,n (esto se implementa en el programa mediante la función max) A continuación se muestra un listado del programa para resolver el mismo problema de exclusión mutua (conteo de líneas) mediante el algoritmo de la panadería de Lamport. program bakery;

(* Exclusión mutua con el algoritmo de la panadería de Lamport*)

const
nprocs = 5;
var
boleto: array[1..nprocs] of integer;
eleccion: array[1..nprocs] of boolean;
lp: integer;
nolineas: integer;
process type Entrada(esteproc: integer);
var
otroproc, lp: integer;
function max: integer;
var
i, largo: integer;
begin
largo := 0;
for i := 1 to nprocs do
if boleto[i] > largo then
largo := boleto[i];
max := largo + 1
end; (* max *)
function favorecido(i, j: integer): boolean;
begin
if (boleto[i] = 0) or (boleto[i] > boleto[j]) then
favorecido := false
else
if boleto[i] < boleto[j] then
favorecido := true
else
favorecido := (i < j)
end;(* favorecido *)
begin
for lp := 1 to 20 do
begin
eleccion[esteproc] := true;
boleto[esteproc] := max;
eleccion[esteproc] := false;
for otroproc := 1 to nprocs do
begin
while eleccion[otroproc] do
null;
while favorecido(otroproc, esteproc) do
null;
end;
nolineas := nolineas + 1;
boleto[esteproc] := 0
end
end;(* Entrada *)
var
turnos: array[1..nprocs] of Entrada;
begin
nolineas := 0;
for lp := 1 to nprocs do
begin
boleto[lp] := 0;
eleccion[lp] := false;
end;
cobegin
for lp := 1 to nprocs do
turnos[lp](lp)
coend;
writeln('Total de Líneas: ',nolineas:4)
end.

Resultado de la corrida del programa: Total de Líneas: 100