Dado um programa que consiste em variáveis e instruções que modificam essas variáveis e uma primitiva de sincronização (um monitor, mutex, sincronização de java ou bloqueio de C #), é possível provar que esse programa é seguro para threads?
Existe mesmo um modelo formal para descrever coisas como segurança de linha ou condições de corrida?
Respostas:
É difícil provar que um programa é "seguro para threads". É possível, no entanto, definir concreta e formalmente o termo "corrida de dados". E é possível determinar se um rastreamento de execução de uma execução específica de um programa tem ou não uma corrida de dados no tempo proporcional ao tamanho do rastreamento. Esse tipo de análise remonta ao menos a 1988: Barton P. Miller, Jong-Deok Choi, "Um mecanismo para depuração eficiente de programas paralelos", Conf. em Prog. Lang. Dsgn. e Impl. (PLDI-1988): 135-144 .
Dado o rastreio de uma execução, primeiro definimos uma ordem parcial acontece antes da ocorrência entre os eventos no rastreamento. Dados dois eventos e b que ocorrem no mesmo segmento, em seguida, a < b ou b < a . (Os eventos no mesmo encadeamento formam uma ordem total dada pela semântica sequencial da linguagem de programação.) Eventos de sincronização (podem ser adquiridos e liberados por mutex, por exemplo), fornecem um encadeamento adicional que acontece antes da ordem parcial. (Se o segmento S libera um mutex e o segmento T adquire esse mutex, dizemos que o lançamento ocorre antes da aquisição.)uma b a < b b < a S T
Então dado dois acessos de dados (lê ou escreve variáveis que são não sincronização variáveis) e b , que são para o mesmo local de memória, mas por diferentes threads e onde quer um ou b é uma operação de gravação dizemos que há uma data- corrida entre um e b se nem um < b nem b < a .uma b uma b uma b a <b b < a
O padrão C ++ 11 é um bom exemplo. (A seção relevante é 1.10 nas especificações de rascunho disponíveis on-line.) O C ++ 11 distingue entre objetos de sincronização (mutexes e variáveis declaradas com um
atomic<>tipo) e todos os outros dados. A especificação do C ++ 11 diz que o programador pode raciocinar sobre os acessos aos dados em um rastreamento de um programa multithread como se fosse sequencialmente consistente se os acessos aos dados forem livres de corrida de dados.A ferramenta Helgrind (parte da Valgrind) realiza esse tipo de detecção baseada em dados baseada em fatos anteriores a várias ferramentas comerciais (por exemplo, Intel Inspector XE.) objeto. Eu acho que essa técnica de usar relógios vetoriais para detecção de corrida de dados foi pioneira por Michiel Ronsse; Koen De Bosschere: "RecPlay: um sistema prático de gravação / repetição totalmente integrado", ACM Trans. Comput. Syst. 17 (2): 133-152, 1999 .
fonte
Do lado prático, existe um sistema de verificação VCC que pode ser usado para provar formalmente a segurança dos programas C em thread.
Esta é uma citação do site:
fonte
Essa é uma área muito difícil de garantir a correção do programa quanto a excluir as condições de corrida, uma espécie de "calcanhar de aquiles" do processamento paralelo. A melhor abordagem para a correção do programa é geralmente evitar primitivas de baixo nível e trabalhar com padrões de design de nível superior (por exemplo, de bibliotecas) que garantam a sincronização do encadeamento. Há um modelo de CSP, que comunica processos sequenciais por Hoare, que possui algumas provas de correção, uma vez que os desenvolvedores se limitam à "estrutura". Tem alguma semelhança conceitual e originação / sobreposição cronológica para "tubos e filtros" unix, embora ainda não tenham encontrado um vínculo direto entre os dois.
Duas outras estruturas que tentam melhorar a correção da paralelização por meio de padrões de design e que possuem a maioria dos algoritmos / padrões conhecidos / padrões de design para esse fim:
fonte