UFMG - Pós-graduação em Ciência da Computação - Programação Paralela

A seguir: Algoritmo de Lamport - Acima: Relógios Lógicos e Timestamps Anterior: Relógios Lógicos e Timestamps

Algoritmo de Lamport (1978)

• o meio de comunicação conserva a ordem de envio na entrega das mensagens;
• cada sítio possui uma fila de requisições;
• inicialmente o sítio possui o recurso crítico;
• todas as filas de requisições possuem a mensagem <T_-1:0, request> onde T_-1 é menor que o valor inicial de qualquer relógio lógico;
• O algoritmo é definido pelas seguintes regras:

  1.

  Requisição: o sítio i manda a mensagem <T_i:i, request> para todos os outros sítios, e também coloca esta mensagem em sua fila de requisições;

  2.

  Recepção de <T_j:j, request>: a requisição é colocada na fila, e uma mensagem <T_i:i, ack> é enviada ao sítio j;

  3.

  Liberação: o sítio i remove toda mensagem <T_i:i, request> de sua própria fila de requisições, e manda <T_i:i, release> para todos os outros sítios;

  4.

  Recepção de <T_j:j, release>: o sítio i remove toda mensagem <T_j:j, request> de sua fila de requisições;

  5.

  Início de seção crítica: o sítio i pode começar a utilizar o recurso quando:

  (a)

  a requisição mais prioritária em sua fila é da forma <T_i:i, request>, e

  (b)

  o sítio i já recebeu mensagens com prioridade menor que (T_i,i) de todos os outros sítios;