- - - - CENAPAD-MGCO

A seguir: Algoritmo de Lamport - Acima: O Algoritmo de Lamport: Anterior: O Algoritmo de Lamport:

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;