Sincronização e Ausência de Condições de Corrida de Dados
Os mecanismos de sincronização coordenam threads concorrentes para que os dados compartilhados sejam acessados com segurança, e a ausência de condições de corrida de dados é a propriedade que torna os programas concorrentes previsíveis.
Definition
Sincronização é a coordenação de atividades concorrentes para impor ordenação ou exclusão mútua em recursos compartilhados, e a ausência de condições de corrida de dados é a propriedade de que nenhuma dupla de threads acessa a mesma localização de memória concorrentemente com pelo menos uma escrita sem sincronização interveniente.
Scope
Este tópico abrange os mecanismos e propriedades que tornam correto o acesso concorrente a estados compartilhados: exclusão mútua, bloqueios (locks), semáforos e monitores, variáveis de condição, algoritmos sem bloqueio (lock-free) e sem espera (wait-free), memória transacional, a relação "happens-before" e a detecção de condições de corrida de dados. Aborda o "deadlock", a atomicidade e a disciplina necessária para manter os programas livres de condições de corrida de dados.
Core questions
- Como a exclusão mútua é alcançada e quais são seus perigos (deadlock, inanição)?
- O que distingue a sincronização baseada em bloqueio da sincronização sem bloqueio?
- Como a relação "happens-before" define as condições de corrida de dados?
- Como as condições de corrida de dados podem ser detectadas automaticamente?
Key theories
- Exclusão mútua
- A solução de Dijkstra para o problema de controle concorrente estabeleceu a exclusão mútua como o requisito fundamental de sincronização, garantindo que as seções críticas não sejam executadas simultaneamente.
- Memória transacional
- Herlihy e Moss propuseram a memória transacional, na qual grupos de operações de memória são executados atomicamente, oferecendo uma alternativa composível ao bloqueio de granularidade fina para a construção de estruturas de dados concorrentes.
- Happens-before e detecção dinâmica de corrida
- Com base na relação "happens-before" de Lamport, o detector Eraser mostrou como encontrar condições de corrida de dados dinamicamente, verificando uma disciplina de bloqueio, exemplificando a detecção automatizada de corrida.
Clinical relevance
A sincronização correta é essencial para softwares concorrentes e paralelos confiáveis; as condições de corrida de dados causam alguns dos bugs mais elusivos na prática. Detectores de corrida, memória transacional e padrões de sincronização disciplinados são ferramentas centrais para a construção de sistemas multithread confiáveis.
History
A solução de exclusão mútua de Dijkstra de 1965 e seus subsequentes semáforos fundaram a sincronização, seguidos pelos monitores de Hoare e Brinch Hansen. A relação "happens-before" de Lamport de 1978 fundamenta as definições modernas de corrida; Herlihy e Moss introduziram a memória transacional em 1993, e detectores dinâmicos de corrida como o Eraser (1997) e, posteriormente, ferramentas "happens-before" tornaram-se padrão para depuração de concorrência.
Debates
- Bloqueios versus abordagens sem bloqueio e transacionais
- Os projetistas debatem a sincronização tradicional baseada em bloqueio, que é simples, mas propensa a "deadlock" e má composição, contra algoritmos sem bloqueio e memória transacional, que melhoram a composibilidade e as garantias de progresso ao custo de complexidade ou sobrecarga.
Key figures
- Edsger Dijkstra
- Leslie Lamport
- Maurice Herlihy
- C. A. R. Hoare
- Stefan Savage
Related topics
Seminal works
- dijkstra1965
- herlihy1993
- savage1997
- lamport1978
Frequently asked questions
- O que é uma condição de corrida de dados?
- Uma condição de corrida de dados ocorre quando duas threads acessam a mesma localização de memória concorrentemente, pelo menos um acesso é uma escrita, e os acessos não são ordenados por sincronização, levando a um comportamento indefinido ou imprevisível na maioria dos modelos de memória.
- Qual a diferença entre sincronização baseada em bloqueio e sincronização sem bloqueio?
- A sincronização baseada em bloqueio usa exclusão mútua para que apenas uma thread entre em uma seção crítica por vez, enquanto a sincronização sem bloqueio usa operações atômicas para garantir que alguma thread sempre progrida sem manter bloqueios, evitando "deadlock".