Compreendendo std :: atomic :: compare_exchange_weak () em C ++ 11

bool compare_exchange_weak (T& expected, T val, ..);

compare_exchange_weak()é uma das primitivas de troca de comparação fornecidas em C ++ 11. É fraco no sentido de que retorna falso mesmo se o valor do objeto for igual a expected. Isso ocorre devido a falhas espúrias em algumas plataformas onde uma sequência de instruções (em vez de uma como no x86) é usada para implementá-la. Em tais plataformas, troca de contexto, recarregamento do mesmo endereço (ou linha de cache) por outro thread, etc, pode causar falha no primitivo. É spuriousporque não é o valor do objeto (diferente de expected) que falha na operação. Em vez disso, são problemas de tempo.

Mas o que me intriga é o que é dito no padrão C ++ 11 (ISO / IEC 14882),

29.6.5. Uma consequência da falha espúria é que quase todos os usos de comparação e troca fraca serão em um loop.

Por que ele precisa estar em um loop em quase todos os usos ? Isso significa que devemos fazer um loop quando ele falhar por causa de falhas espúrias? Se for esse o caso, por que nos incomodamos em usar compare_exchange_weak()e escrever o loop nós mesmos? Podemos apenas usar o compare_exchange_strong()que acho que deve nos livrar de falhas espúrias. Quais são os casos de uso comuns de compare_exchange_weak()?

Outra questão relacionada. Em seu livro "C ++ Concurrency In Action", Anthony diz:

//Because compare_exchange_weak() can fail spuriously, it must typically
//be used in a loop:

bool expected=false;
extern atomic<bool> b; // set somewhere else
while(!b.compare_exchange_weak(expected,true) && !expected);

//In this case, you keep looping as long as expected is still false,
//indicating that the compare_exchange_weak() call failed spuriously.

Por que !expectedexiste na condição de loop? Ele existe para evitar que todos os tópicos morram de fome e não façam nenhum progresso por algum tempo?

Editar: (uma última pergunta)

Em plataformas em que não existe uma única instrução CAS de hardware, as versões fraca e forte são implementadas usando LL / SC (como ARM, PowerPC, etc). Então, há alguma diferença entre os dois loops a seguir? Por que, se houver? (Para mim, eles deveriam ter um desempenho semelhante.)

// use LL/SC (or CAS on x86) and ignore/loop on spurious failures
while (!compare_exchange_weak(..))
{ .. }

// use LL/SC (or CAS on x86) and ignore/loop on spurious failures
while (!compare_exchange_strong(..)) 
{ .. }

Eu vim com esta última pergunta que vocês mencionaram que talvez haja uma diferença de desempenho dentro de um loop. Também é mencionado pelo padrão C ++ 11 (ISO / IEC 14882):

Quando uma comparação e troca está em loop, a versão fraca renderá melhor desempenho em algumas plataformas.

Mas, conforme analisado acima, duas versões em um loop devem apresentar desempenho igual / semelhante. Qual é a coisa que eu sinto falta?

Por que fazer troca em um loop?

Normalmente, você deseja que seu trabalho seja concluído antes de seguir em frente, portanto, você o coloca compare_exchange_weakem um loop para que ele tente trocar até ter sucesso (ou seja, retornar true).

Observe que também compare_exchange_strongé freqüentemente usado em um loop. Ele não falha devido a falha espúria, mas falha devido a gravações simultâneas.

Por que usar em weakvez de strong?

Muito fácil: falhas espúrias não acontecem com frequência, portanto, não é um grande impacto no desempenho. Em contraste, tolerar tal falha permite uma implementação muito mais eficiente da weakversão (em comparação com strong) em algumas plataformas: strongdeve sempre verificar se há falha espúria e mascará-la. Isto é caro.

Portanto, weaké usado porque é muito mais rápido do que strongem algumas plataformas

Quando você deve usar weake quando strong?

Os estados de referência dão dicas de quando usar weake quando usar strong:

Quando uma comparação e troca está em loop, a versão fraca renderá melhor desempenho em algumas plataformas. Quando uma comparação e troca fraca exigiria um loop e um forte não, o forte é preferível.

Portanto, a resposta parece ser bastante simples de lembrar: se você tivesse que introduzir um loop apenas por causa de uma falha espúria, não o faça; usar strong. Se você tiver um loop de qualquer maneira, use weak.

Por que está !expectedno exemplo

Depende da situação e de sua semântica desejada, mas geralmente não é necessário para correção. Omiti-lo produziria uma semântica muito semelhante. Apenas em um caso em que outro thread pode redefinir o valor para false, a semântica pode se tornar um pouco diferente (mas não consigo encontrar um exemplo significativo onde você desejaria isso). Veja o comentário de Tony D. para uma explicação detalhada.

É simplesmente um atalho quando outro thread escreve true: Então, abortamos em vez de tentar escrever truenovamente.

Sobre sua última pergunta

Mas, conforme analisado acima, duas versões em um loop devem apresentar desempenho igual / semelhante. Qual é a coisa que eu sinto falta?

Da Wikipedia :

Implementações reais de LL / SC nem sempre têm sucesso se não houver atualizações simultâneas para o local de memória em questão. Quaisquer eventos excepcionais entre as duas operações, como uma troca de contexto, outro link de carregamento ou mesmo (em muitas plataformas) outro carregamento ou operação de armazenamento, farão com que a condição de armazenamento falhe espúriamente. Implementações mais antigas falharão se houver atualizações transmitidas pelo barramento de memória.

Portanto, LL / SC falhará espúriamente na troca de contexto, por exemplo. Agora, a versão forte traria seu "próprio pequeno loop" para detectar aquela falha espúria e mascará-la tentando novamente. Observe que este próprio loop também é mais complicado do que um loop CAS normal, uma vez que deve distinguir entre falha espúria (e mascará-la) e falha devido a acesso simultâneo (que resulta em um retorno com valor false). A versão fraca não possui um loop próprio.

Como você fornece um loop explícito em ambos os exemplos, simplesmente não é necessário ter o loop pequeno para a versão forte. Consequentemente, no exemplo com a strongversão, a verificação de falha é feita duas vezes; uma vez por compare_exchange_strong(o que é mais complicado, pois deve distinguir falha espúria e acessos simultâneos) e uma vez por seu loop. Esta verificação cara é desnecessária e o motivo weakserá mais rápido aqui.

Observe também que seu argumento (LL / SC) é apenas uma possibilidade de implementar isso. Existem mais plataformas que possuem até conjuntos de instruções diferentes. Além disso (e mais importante), observe que std::atomicdeve oferecer suporte a todas as operações para todos os tipos de dados possíveis , portanto, mesmo se você declarar uma estrutura de dez milhões de bytes, poderá usar compare_exchangenisso. Mesmo quando em uma CPU que tem CAS, você não pode fazer CAS dez milhões de bytes, então o compilador irá gerar outras instruções (provavelmente aquisição de bloqueio, seguida por uma comparação não atômica e troca, seguida por uma liberação de bloqueio). Agora, pense em quantas coisas podem acontecer durante a troca de dez milhões de bytes. Portanto, embora um erro espúrio possa ser muito raro para trocas de 8 bytes, ele pode ser mais comum neste caso.

Portanto, em poucas palavras, C ++ fornece duas semânticas, uma de "melhor esforço" ( weak) e uma "Eu farei isso com certeza, não importa quantas coisas ruins possam acontecer entre" uma ( strong). Como eles são implementados em vários tipos de dados e plataformas é um tópico totalmente diferente. Não vincule seu modelo mental à implementação em sua plataforma específica; a biblioteca padrão foi projetada para funcionar com mais arquiteturas do que você possa imaginar. A única conclusão geral que podemos tirar é que garantir o sucesso geralmente é mais difícil (e, portanto, pode exigir trabalho adicional) do que apenas tentar e deixar espaço para um possível fracasso.

Por que ele precisa estar em um loop em quase todos os usos ?

Porque se você não fizer um loop e falhar espúriamente, seu programa não fez nada de útil - você não atualizou o objeto atômico e não sabe qual é o seu valor atual (Correção: veja o comentário abaixo de Cameron). Se a chamada não faz nada de útil, qual é o sentido de fazer isso?

Isso significa que devemos fazer um loop quando ele falhar por causa de falhas espúrias?

Sim.

Se for esse o caso, por que nos incomodamos em usar compare_exchange_weak()e escrever o loop nós mesmos? Podemos apenas usar compare_exchange_strong () que acho que deve eliminar as falhas espúrias para nós. Quais são os casos de uso comuns de compare_exchange_weak ()?

Em algumas arquiteturas compare_exchange_weaké mais eficiente, e falhas espúrias devem ser bastante incomuns, então pode ser possível escrever algoritmos mais eficientes usando a forma fraca e um loop.

Em geral, é provavelmente melhor usar a versão forte em vez disso, se seu algoritmo não precisar fazer um loop, já que você não precisa se preocupar com falhas espúrias. Se for necessário fazer um loop de qualquer maneira, mesmo para a versão forte (e muitos algoritmos precisam fazer o loop de qualquer maneira), usar a forma fraca pode ser mais eficiente em algumas plataformas.

Por que !expectedexiste na condição de loop?

O valor pode ter sido definido truepor outro encadeamento, então você não quer ficar repetindo tentando defini-lo.

Editar:

Mas, conforme analisado acima, duas versões em um loop devem apresentar desempenho igual / semelhante. Qual é a coisa que eu sinto falta?

Certamente, é óbvio que em plataformas onde a falha espúria é possível, a implementação de compare_exchange_strongtem que ser mais complicada para verificar se há falha espúria e tentar novamente.

A forma fraca apenas retorna em caso de falha espúria, não tenta novamente.

Estou tentando responder isso sozinho, depois de passar por vários recursos online (por exemplo, este e este ), o C ++ 11 Standard, bem como as respostas fornecidas aqui.

As questões relacionadas são mescladas (por exemplo, " por que! Esperado? " É mesclado com "por que colocar compare_exchange_weak () em um loop? ") E as respostas são fornecidas de acordo.

Por que compare_exchange_weak () tem que estar em um loop em quase todos os usos?

Padrão Típico A

Você precisa obter uma atualização atômica com base no valor da variável atômica. Uma falha indica que a variável não foi atualizada com nosso valor desejado e queremos tentar novamente. Observe que não nos importamos se ele falhará devido a gravação simultânea ou falha espúria. Mas nos preocupamos que sejamos nós que fazemos essa mudança.

expected = current.load();
do desired = function(expected);
while (!current.compare_exchange_weak(expected, desired));

Um exemplo do mundo real é para vários threads adicionarem um elemento a uma lista vinculada individualmente simultaneamente. Cada thread carrega primeiro o ponteiro do cabeçalho, aloca um novo nó e anexa o cabeçalho a este novo nó. Finalmente, ele tenta trocar o novo nó com a cabeça.

Outro exemplo é implementar mutex usando std::atomic<bool>. No máximo um segmento pode entrar na região crítica de cada vez, consoante o primeiro fio de definir currentpara truee sair do ciclo.

Padrão Típico B

Este é realmente o padrão mencionado no livro de Anthony. Ao contrário do padrão A, você deseja que a variável atômica seja atualizada uma vez, mas não se importa com quem o faz. Desde que não esteja atualizado, você tenta novamente. Isso normalmente é usado com variáveis ​​booleanas. Por exemplo, você precisa implementar um gatilho para que uma máquina de estado siga em frente. Qual thread puxa o gatilho é independente.

expected = false;
// !expected: if expected is set to true by another thread, it's done!
// Otherwise, it fails spuriously and we should try again.
while (!current.compare_exchange_weak(expected, true) && !expected);

Observe que geralmente não podemos usar esse padrão para implementar um mutex. Caso contrário, vários threads podem estar dentro da seção crítica ao mesmo tempo.

Dito isso, deve ser raro usar compare_exchange_weak()fora de um loop. Ao contrário, há casos em que a versão forte está em uso. Por exemplo,

bool criticalSection_tryEnter(lock)
{
  bool flag = false;
  return lock.compare_exchange_strong(flag, true);
}

compare_exchange_weak não é adequado aqui porque quando ele retorna devido a uma falha espúria, é provável que ninguém ocupe a seção crítica ainda.

Starving Thread?

Um ponto que vale a pena mencionar é que o que acontecerá se falhas espúrias continuarem a acontecer, deixando o segmento de fome? Teoricamente, isso poderia acontecer em plataformas quando compare_exchange_XXX()é implementado como uma sequência de instruções (por exemplo, LL / SC). O acesso frequente da mesma linha de cache entre LL e SC produzirá falhas espúrias contínuas. Um exemplo mais realista é devido a uma programação burra onde todos os threads simultâneos são intercalados da seguinte maneira.

Time
 |  thread 1 (LL)
 |  thread 2 (LL)
 |  thread 1 (compare, SC), fails spuriously due to thread 2's LL
 |  thread 1 (LL)
 |  thread 2 (compare, SC), fails spuriously due to thread 1's LL
 |  thread 2 (LL)
 v  ..

Isso pode acontecer?

Isso não acontecerá para sempre, felizmente, graças ao que o C ++ 11 requer:

As implementações devem garantir que as operações fracas de comparação e troca não retornem consistentemente falso, a menos que o objeto atômico tenha um valor diferente do esperado ou que haja modificações simultâneas no objeto atômico.

Por que nos incomodamos em usar compare_exchange_weak () e escrever o loop nós mesmos? Podemos apenas usar compare_exchange_strong ().

Depende.

Caso 1: quando ambos precisam ser usados ​​dentro de um loop. C ++ 11 diz:

Quando uma comparação e troca está em loop, a versão fraca renderá melhor desempenho em algumas plataformas.

No x86 (pelo menos atualmente. Talvez ele vá recorrer a um esquema semelhante ao LL / SC um dia para desempenho quando mais núcleos forem introduzidos), a versão fraca e a versão forte são essencialmente as mesmas porque ambas se resumem a uma única instrução cmpxchg. Em algumas outras plataformas onde compare_exchange_XXX()não é implementado atomicamente (aqui significando que nenhum primitivo de hardware existe), a versão fraca dentro do loop pode vencer a batalha porque a versão forte terá que lidar com as falhas espúrias e tentar novamente de acordo.

Mas,

raramente, podemos preferir compare_exchange_strong()até compare_exchange_weak()mesmo em um loop. Por exemplo, quando há muitas coisas a fazer entre o carregamento da variável atômica e a troca de um novo valor calculado (veja function()acima). Se a própria variável atômica não muda com frequência, não precisamos repetir o cálculo caro para cada falha espúria. Em vez disso, podemos esperar compare_exchange_strong()"absorver" tais falhas e apenas repetir o cálculo quando ele falhar devido a uma mudança de valor real.

Caso 2: Quando só compare_exchange_weak() precisa ser usado dentro de um loop. C ++ 11 também diz:

Quando uma comparação e troca fraca exigiria um loop e um forte não, o forte é preferível.

Esse é normalmente o caso quando você faz um loop apenas para eliminar falhas espúrias da versão fraca. Você tenta novamente até que a troca seja bem-sucedida ou falhe devido à gravação simultânea.

expected = false;
// !expected: if it fails spuriously, we should try again.
while (!current.compare_exchange_weak(expected, true) && !expected);

Na melhor das hipóteses, está reinventando as rodas e tendo o mesmo desempenho que compare_exchange_strong(). Pior? Essa abordagem falha em aproveitar todas as vantagens das máquinas que fornecem comparação e troca não espúrias em hardware .

Por último, se você fizer um loop para outras coisas (por exemplo, consulte "Padrão Típico A" acima), então há uma boa chance de que compare_exchange_strong()também seja colocado em um loop, o que nos leva de volta ao caso anterior.

Tudo bem, então preciso de uma função que execute o deslocamento atômico para a esquerda. Meu processador não tem uma operação nativa para isso e a biblioteca padrão não tem uma função para isso, então parece que estou escrevendo minha própria. Aqui vai:

void atomicLeftShift(std::atomic<int>* var, int shiftBy)
{
    do {
        int oldVal = std::atomic_load(var);
        int newVal = oldVal << shiftBy;
    } while(!std::compare_exchange_weak(oldVal, newVal));
}

Agora, há dois motivos pelos quais esse loop pode ser executado mais de uma vez.

1. Alguém mudou a variável enquanto eu fazia meu turno à esquerda. Os resultados do meu cálculo não devem ser aplicados à variável atômica, porque isso apagaria efetivamente a escrita de outra pessoa.
2. Minha CPU arrotou e o fraco CAS falhou espúriamente.

Sinceramente, não me importa qual. A mudança para a esquerda é rápida o suficiente para que eu possa simplesmente fazer de novo, mesmo que a falha seja espúria.

O que é menos rápido, entretanto, é o código extra que o CAS forte precisa para envolver o CAS fraco para ser forte. Esse código não faz muito quando o CAS fraco é bem-sucedido ... mas quando falha, o CAS forte precisa fazer algum trabalho de detetive para determinar se foi o Caso 1 ou o Caso 2. Esse trabalho de detetive assume a forma de um segundo loop, efetivamente dentro do meu próprio loop. Dois loops aninhados. Imagine seu professor de algoritmos olhando para você agora.

E como mencionei anteriormente, não me importo com o resultado desse trabalho de detetive! De qualquer forma, vou refazer o CAS. Portanto, usar um CAS forte não me ganha exatamente nada e me perde uma pequena, mas mensurável quantidade de eficiência.

Em outras palavras, o CAS fraco é usado para implementar operações de atualização atômica. O CAS forte é usado quando você se preocupa com o resultado do CAS.

Acho que a maioria das respostas acima aborda "falha espúria" como algum tipo de problema, compensação de desempenho VS correção.

Pode ser visto que a versão fraca é mais rápida na maioria das vezes, mas em caso de falha espúria, torna-se mais lenta. E a versão forte é uma versão que não tem possibilidade de falha espúria, mas quase sempre é mais lenta.

Para mim, a principal diferença é como essas duas versões lidam com o problema ABA:

a versão fraca terá sucesso somente se ninguém tiver tocado na linha do cache entre carregar e armazenar, então ela detectará 100% o problema ABA.

a versão forte falhará apenas se a comparação falhar, portanto, não detectará o problema ABA sem medidas extras.

Portanto, em teoria, se você usar a versão fraca em uma arquitetura de ordem fraca, não precisará do mecanismo de detecção ABA e a implementação será muito mais simples, dando melhor desempenho.

Mas, no x86 (arquitetura ordenada forte), a versão fraca e a versão forte são as mesmas, e ambas sofrem de problema ABA.

Portanto, se você escrever um algoritmo de plataforma cruzada completamente, precisará resolver o problema ABA de qualquer maneira, portanto, não há benefício de desempenho em usar a versão fraca, mas há uma penalidade de desempenho por lidar com falhas espúrias.

Em conclusão - por motivos de portabilidade e desempenho, a versão forte é sempre uma opção melhor ou igual.

A versão fraca só pode ser uma opção melhor se permitir que você ignore completamente as contramedidas ABA ou se seu algoritmo não se importar com ABA.