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

A seguir: Grafo de Precedências Acima: The Drinking Philosophers Problem[#!Drinking!#] Anterior: Introdução

Grafos de Conflitos e de Precedências

• Grafo de conflitos G:
  • nós: processos
  • não dirigido
  • aresta (u,v) existe se for possível um conflito entre u e v
• Grafo de precedências H:
  • é definido por uma função que sempre atribua precedências distintas a pares de processos em conflito
  • idêntico a G, mas dirigido
  • $u \rightarrow v$ em H se u tem precedência sobre v
• Profundidade de u em um grafo acíclico: maior número de arestas em uma rota que sai de um nó sem precedentes e vai até u
• Se H for acíclico, a profundidade sempre vai diferenciar de todos os concorrentes potenciais ($\equiv$ vizinhos em G)
• Se H for cíclico, nem todos os conflitos poderão ser resolvidos