Algoritmos De Sincronizacion

ALGORITMOS DE SINCRONIZACION

LAMPORT

Lamport señaló que la sincronización de relojes no tiene que ser absoluta. Si 2 procesos no interactúan no es necesario que sus relojes estén sincronizados.

Generalmente lo importante no es que los procesos estén de acuerdo en la hora, pero sí importa que coincidan en el orden en que ocurren los eventos. Y es aquí donde aparece el concepto de reloj lógico. Un reloj lógico de Lamport es un contador software que se incrementa monótonamente, cuyos valores no necesitan tener ninguna relación particular con ningún reloj físico.

Para sincronizar los relojes lógicos, Lamport definió la relación ocurre antes de (happens-before):

• Sí “a” y “b” son eventos en el mismo proceso y “a” ocurre antes de “b”, entonces “a –> b” es verdadero.

• “Ocurre antes de” es una relación transitiva: Si “a –> b” y “b –> c”, entonces “a –> c”.

• Si dos eventos “x” e “y” están en procesos diferentes que no intercambian mensajes, entonces “x –> y” no es verdadero, pero tampoco lo es “y –> x”:

• Se dice que son eventos concurrentes.

Necesitamos una forma de medir el tiempo tal que a cada evento “a”, le podamos asociar un valor del tiempo “C(a)” en el que todos los procesos estén de acuerdo:

Se debe cumplir que:

• Sí “a –> b” entonces “C(a) < C (b)”.

• El tiempo del reloj, “C”, siempre debe ir hacia adelante (creciente), y nunca hacia atrás (decreciente).

RICART Y AGRAWALA

Desarrollado en 1981, se basa en que todo proceso que quiera acceder a la

Sección crítica obtenga antes el beneplácito del resto de los procesos. Requiere

Establecer un orden total en los eventos, lo que se consigue con marcas de

Tiempo y asignando un orden predeterminado para procesos con la misma

Marca (por ejemplo, a partir del identificador del proceso).

Petición de entrar a la sección crítica:

• El solicitante envía a todos los procesos un mensaje con su nombre, la sección crítica y una marca del tiempo.

• Un receptor:

 Si no está en la sección crítica, envía un mensaje de confirmación al solicitante.

 Si está en la sección crítica, no responde (o deniega) y encola la petición.

 Si está esperando a entrar a la sección crítica, compara la marca de tiempo del solicitante con la de su propia petición. Si la del solicitante es anterior, le envía la confirmación; si no, no responde (o deniega) y encola su petición.

• Para poder entrar a la sección crítica, un proceso tiene que recibir confirmaciones de todos los procesos.

Petición de salir de la sección crítica:

• Un proceso envía

...