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

A seguir: Exemplo: Inteiro Oscilante Acima: Aula 12 - Modelos Anterior: Aula 12 - Modelos

Equidade fraca e equidade forte

• Os problemas para a caracterização de propriedades de progresso podem ser contornados
  • tornando todas as computações infinitas, através da obrigatoriedade da existência de um comando guardado $\gamma_{skip} = (true, identity)$em todos os sistemas de transições.
  • $\gamma_{skip}$ sempre pode ser escolhido para prolongar uma computação finita, pois sua guarda sempre está habilitada
  • a ação de $\gamma_{skip}$ não altera o estado, pois é a função identidade
  • desta forma a toda computação finita corresponde uma computação infinita, que é o seu prolongamento por infinitos $\gamma_{skip}$.
• o progresso é forçado, excluindo computações infinitas que não satisfazem hipóteses de equidade sobre certos comandos guardados:
• Equidade fraca : para certos comandos, computações em que o comando permanece com sua guarda continuamente habilitada sem ser executado são excluídas
  • Exemplo: a hipótese de equidade fraca relativa ao comando $\gamma_{1} =$ (g = consumerState = thinking, a = consumerState = thinking) significa que não se admitem computações em que o processo consumidor se esqueça eternamente de tentar consumir
• Equidade forte : para certos comandos, computações que que o comando nunca é executado, apesar de ter a sua guarda habilitada e desabilitada intermitentemente, por um número infinito de vezes, são excluídas