O que impede uma condição de corrida em uma fechadura?

24

Entendo o básico sobre o que são corridas de dados e como bloqueios / mutexes / semáforos ajudam a evitá-las. Mas o que acontece se você tiver uma "condição de corrida" na própria fechadura? Por exemplo, dois threads diferentes, talvez no mesmo aplicativo, mas executando em processadores diferentes, tentam adquirir um bloqueio exatamente ao mesmo tempo .

O que acontece depois? O que é feito para evitar isso? É impossível, ou simplesmente improvável? Ou é uma condição real de corrida esperando para acontecer?

Gavin Howard
fonte
Esta pergunta foi feita antes no SO: stackoverflow.com/questions/980521/…
Doc Brown
e uma pergunta relacionada aqui no P.SE: programmers.stackexchange.com/questions/228827/…
ratchet freak
Você adquire um bloqueio para adquiri-lo;) (em outras palavras, se o seu bloqueio tem uma condição de corrida, ele não é implementado corretamente - um bloqueio é praticamente definido para ser uma construção que implementa exclusão mútua)
Tangrs
Você perdeu um ponto importante em como os bloqueios funcionam. Eles são construídos de tal forma que não é possível ter uma corrida em uma fechadura, caso contrário, são completamente inúteis.
Zane

Respostas:

36

É impossível, ou simplesmente improvável?

Impossível. Ele pode ser implementado de diferentes maneiras, por exemplo, através do Compare-and-swap, onde o hardware garante execução sequencial. Pode ficar um pouco complicado na presença de múltiplos núcleos ou até vários soquetes e precisa de um protocolo complicado entre os núcleos, mas tudo isso é resolvido.

maaartinus
fonte
3
Obrigado ... Deus ... é tratado em hardware ... (ou, pelo menos, um nível mais baixo do que tocar.)
corsiKa
2
@gdhoward Não acredito ... essa resposta levou menos de 5 minutos e é a terceira mais votada das minhas quatro centenas de respostas (principalmente SO). E também provavelmente o mais curto.
Maaartinus
1
@maaartinus - Curto e doce às vezes faz.
Bobson
17

Estude o conceito de operações atômicas de "Teste e Configuração".

Essencialmente, a operação não pode ser dividida - não é possível fazer duas coisas exatamente ao mesmo tempo. Ele verificará um valor, configurará se estiver claro e retornará o valor como estava no teste. Em uma operação de bloqueio, o resultado será sempre "lock == TRUE" após um teste e ajuste, a única diferença é que ele foi definido ou não no início.

No nível do microcódigo em um processador de núcleo único, esta é uma instrução indivisível e fácil de implementar. Com processadores múltiplos e multicore, fica mais difícil, mas como programadores não precisamos nos preocupar com isso, pois ele foi projetado para funcionar por pessoas realmente inteligentes que fazem o silício. Essencialmente, eles fazem a mesma coisa - fazem uma instrução atômica que é uma versão sofisticada do teste e configuração

mattnz
fonte
2
Basicamente, se o hardware não for intrinsecamente seqüencial em algum nível, ele terá um mecanismo que permite romper vínculos que, de outra forma, poderiam ocorrer.
Bill Michell
@ BillMichell, eu deveria ter pensado nisso. Na verdade, eu fiz; Só não sabia se minha suposição estava correta.
Gavin Howard
2

Basta colocar o código para entrar na seção crítica, especialmente projetado para que uma condição de corrida não viole a exclusão mútua.

Na maioria das vezes, são usados ​​loops atômicos de comparação e configuração que são executados no nível do hardware

while(!CompareAndSet(&lock, false, true));//busy loop won't continue until THIS thread has set the lock to true
//critical section
CompareAndSet(&lock, true, false);

Na ausência disso, existem soluções de software bem estudadas para permitir a exclusão mútua.

catraca arrepiante
fonte
1

Não é possível que dois (ou mais) threads adquiram bloqueio ao mesmo tempo. Existem alguns tipos de métodos de sincronização, por exemplo:

Espera ativa - bloqueio de rotação

Pseudo-código:

1. while ( xchg(lock, 1) == 1); - entry protocole

XCHG é um exemplo de operação atômica (existe na arquitetura x86) que primeiro define novo valor para uma variável "lock" e depois retorna o valor antigo. Atômico significa que não pode ser interrompido - no exemplo acima, entre definir novo valor e retornar antigo. Resultado atômico - determinístico, não importa o quê.

2. Your code
3. lock = 0; - exit protocol

Quando o bloqueio é igual a 0, outro thread pode entrar na seção crítica - enquanto o loop termina.

Suspensão de encadeamento - por exemplo, contagem de semáforo

Existe dois operação atômica .Wait()e .Signal()e temos inteiro variável vamos chamá-lo int currentValue.

Wait():
if (currentValue > 0) currentValue -= 1;
else suspend current thread;

Signal():
If there exists thread suspended by semaphore wake up one of them
Else currentValue += 1;

Agora, resolver o problema crítico da seção é realmente fácil:

Pseudo-código:

mySemaphore.Wait();
do some operations - critical section
mySemaphore.Signal();

Geralmente, a API do encadeamento de programação deve permitir que você especifique o máximo de encadeamentos simultâneos na seção crítica de semáforo. Obviamente, existem mais tipos de sincronização em sistemas multithread (mutex, monitores, semáforo binário etc.), mas eles se baseiam nas idéias acima. Alguém poderia argumentar que os métodos que usam a suspensão de encadeamento devem ser preferidos à espera ativa (para que a CPU não seja desperdiçada) - nem sempre é a verdade. Quando o encadeamento está sendo suspenso, ocorre uma operação cara chamada troca de contexto. No entanto, é razoável quando o tempo de espera é curto (número de threads ~ número de núcleos).

fex
fonte