A correção em um programa simultânea é significativamente mais complexa do que em um programa seqüencial devido às dimensões adicionadas do tempo, intercalação e recursos compartilhados. Um programa simultâneo é considerado correto se satisfazer sua especificação *, independentemente da programação de seus threads ou processos simultâneos *. Isso significa que o programa produz a saída esperada e exibe o comportamento desejado sob todas as viagens possíveis de execução.
Vários aspectos contribuem para a definição de correção em um programa simultâneo:
*
Segurança: O programa nunca entra em um estado inválido. Isso inclui evitar problemas como:
*
Races de dados: Vários encadeamentos acessando e modificando o mesmo local de memória compartilhada sem sincronização adequada, levando a resultados imprevisíveis.
*
impasse: Dois ou mais threads são bloqueados indefinidamente, aguardando a liberação de recursos.
*
Livelocks: Os threads estão mudando continuamente o estado em resposta um ao outro, mas nenhum faz progresso.
*
fome: Um ou mais threads têm acesso perpetuamente negado a um recurso compartilhado.
*
Condições de corrida: O resultado depende da ordem imprevisível em que os threads executam.
*
LIVRE: O programa eventualmente faz progresso e termina, se for necessário. Isso inclui garantir que:
* Os threads eventualmente adquirem os recursos necessários.
* O programa acaba chegando a um estado de término.
*
funcionalidade: O programa produz a saída correta e atinge seu objetivo pretendido. Isso é semelhante aos programas seqüenciais, mas complicado pela natureza simultânea da execução. O resultado final deve ser consistente em todos os cenários de execução possíveis.
Portanto, provar a correção de um programa simultâneo normalmente envolve demonstrar que:
1.
Todas as intercaladas possíveis de execuções de threads levam a um estado final válido. Isso é incrivelmente desafiador e muitas vezes impraticável para fazer exaustivamente.
2.
O programa está livre de violações de segurança (impasse, corridas de dados, etc.). Isso geralmente é abordado através do design cuidadoso e do uso de mecanismos de sincronização (mutexes, semáforos, monitores etc.).
3.
O programa satisfaz suas propriedades de lutividade. Isso significa demonstrar que o programa acabará concluindo suas tarefas e não ficará preso em um loop ou impasse infinito.
Em resumo, a correção na programação simultânea significa garantir um comportamento previsível e confiável em todos os possíveis cronogramas de execução. Isso requer atenção meticulosa à sincronização, gerenciamento de recursos e técnicas rigorosas de testes e verificação. Os métodos formais podem ser empregados para verificação rigorosa, mas geralmente são caros computacionalmente e aplicáveis apenas a programas menores. Portanto, geralmente é necessária uma combinação de design cuidadoso, teste e verificação potencialmente formal para garantir a correção de um programa simultâneo.
