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

A seguir: Carvalho e Campos: mensagens Acima: Algoritmo de Carvalho e Anterior: Algoritmo de Carvalho e

Carvalho e Campos: grafo de precedências

Sejam c e d dois clientes, e seja a seu árbitro comum; O cliente c tem precedência sobre d se e somente se:

1.

d possui a permissão P_a, suja, ou

2.

P_a está em trânsito indo de d para a, e está suja, ou

3.

nenhuma das condições acima aplica-se a d ou a c, e Priority_a(c) > Priority_a(d).

Suponha que a permissão de a foi dada a c, e que foi pedida por um outro cliente d:

• se Priority_a(d) > Priority_a(c), o árbitro a sabe que d tem precedência sobre c, e pede sua permissão de volta usando uma mensagem StrongRequest;
• se Priority_a(d) < Priority_a(c), a relação de precedência entre c e d é determinada pelo estado (suja ou limpa) de P_a, e esta informação é local ao cliente c.