Por que C/C++ não possui um sinalizador atômico test_and_clear?

Conselhos práticos: use atomic<bool>ou atomic<unsigned char>em vez de atomic_flagcódigo normal se seu conjunto limitado de operações tornar seu código menos eficiente. A menos que você se preocupe em estar livre de bloqueios em máquinas muito primitivas, onde atomic<bool>e atomic<int>podem não estar livres de bloqueios. (Ou talvez use C++20 std::atomic_unsigned_lock_free.)

TAS (Test And Set) é uma das operações RMW atômicas primitivas bem conhecidas na ciência da computação que pode ser um alicerce para exclusão mútua (bloqueio). Em alguns hardwares antigos (como o Motorola 68000), é o único RMW atômico.

Não existem máquinas onde o único RMW atômico seja um teste e limpeza. (A memória com inicialização zero é a norma, portanto, um spinlock ou mutex no armazenamento estático começará no estado desbloqueado se 0 significar desbloqueado e o TAS assumir o bloqueio. Você precisa de um RMW atômico ao adquirir um spinlock, mas não ao liberar.)

O TAS também pode ser implementado de forma eficiente em termos de troca atômica, também conhecida como swap, que algum outro hardware antigo fornece como seu único RMW atômico. ( local = foo.exchange(true)e teste o resultado.)

Mas nem o TAS nem o exchange funcionam como blocos de construção para RMWs atômicos arbitrários e livres de bloqueio,fetch_xor como ou CAS ( Compare-and-Swap, por exemplo compare_exchange_weak/strong). Uma máquina com apenas TAS ou uma forma de emulá-lo não pode fornecer lock-free std::atomic<bool>, mas pode fornecer lock-free std::atomic_flag.

( LL/SC ou CAS são blocos de construção para RMWs arbitrários sem bloqueio em uma única variável. Todas (?) As máquinas modernas que suportam vários núcleos têm pelo menos um deles e, às vezes, também suporte direto para algumas das operações inteiras comuns como fetch_add, fetch_or, exchange, etc., como em x86-64 e ARMv8.1. E, claro, garantias de atomicidade para operações de carga pura e armazenamento puro, portanto, .load()podem ser feitas como uma carga real, não como um RMW que falharia na memória somente leitura e ter discórdia entre os leitores.)

Hipoteticamente, em uma CPU com apenas test-can-clear, você ainda pode implementar atomic_flagcom o estado C++ falsetendo uma representação de objeto diferente de zero; antes do C++ 20, não era necessário que a inicialização estática a tornasse false . Mas se uma CPU tiver TAS e "TAC" (ou exchange que possa fazer as duas coisas), mas não tiver funcionalidade suficiente para implementar lock-free atomic<bool>, você não poderá tirar vantagem total disso via atomic_flag.

atomic_flagé necessário que seja livre de bloqueios, diferente de qualquer outro arquivo atomic<T>. Ele existe para expor um conjunto mínimo de funcionalidades livres de bloqueio que podem ser implementadas em uma ampla gama de hardware que é capaz de implementar ISO C++ 11 (incluindo std::mutexo bloqueio para não livre de bloqueio std::atomic<T>).

Algumas coisas que evita exigir:

• Acesso somente leitura (antes de C++20 .test())
  Alguns hardwares podem ter detecção de corrida onde podem falhar na leitura e gravação simultâneas. (A mesma condição que seria um comportamento indefinido em C++ em variáveis ​​não atômicas.) Presumivelmente, esse hardware teria instruções especiais que podem ser simultâneas, que podem incluir apenas gravações e RMWs.

• Acesso somente gravação diferente de .clear().
  A escrita truepode ser feita .test_and_set()ignorando o valor de retorno. Mas isso não é eficiente. Ainda é um RMW atômico e, portanto, continua uma sequência de lançamento e precisa ver o "valor mais recente" na ordem de modificação para que seja linearizável, portanto, não é trivial para os compiladores otimizá-lo para apenas um armazenamento se o valor de retorno não for usado.
  IDK qual pode ser o motivo do hardware para não fornecer uma .set()API. Se o hardware subjacente não permitir armazenamentos simples de valores diferentes de 0(ou qualquer que seja o padrão de bits real clear), a implementação sempre poderá usar uma instrução TAS e ignorar o resultado. Ser mais forte não é um problema.

  Portanto, este pode ser apenas o caso de manter a API mínima, porque isso não importa; a maior parte do código deve ser usada apenas atomic<bool>porque também é livre de bloqueios nas plataformas reais para as quais a maioria das pessoas está programando.

• Armazenamento de um valor variável: você sempre pode if(x) flag.TAS(); else flag.clear(), mas a API não fornece isso.

• Alternar um valor existente: o único RMW (TAS) disponível armazena um novo valor que não depende do que já estava lá. Isso permite a implementação em termos de instruções como ARM swp(Swap) , que é anterior ao suporte LL/SC no ARM. Bem como em termos do próprio TAS.

  Presumivelmente, este é um dos fatores que torna o TAS e a troca mais fáceis de implementar em hardware: uma leitura + gravação poderia talvez acontecer no mesmo ciclo, ao contrário de operações em que o valor a ser escrito deve ser calculado a partir do resultado da carga, então ganho. não estará pronto até pelo menos um ciclo depois.

Se alguma operação suportada por atomic<bool>precisar de um mutex (por falta de CAS ou LL/SC), todas as operações deverão respeitar o mutex. (Exceto cargas puras, se o rasgo e a ordenação da memória não forem um problema, por exemplo, para cargas relaxadas de um byte ou bool, ou atomic int em alguns sistemas, mas esse é um caso de canto para sistemas obsoletos com os quais os compiladores modernos provavelmente não se preocupam. .) Então atomic<bool>::is_always_lock_freetem que ser false.

C++ 20 adicionados std::atomic_signed_lock_freee std::atomic_unsigned_lock_freetipos inteiros que são garantidos sem bloqueio (e são "mais eficientes" para espera/notificação). Eles são opcionais em implementações independentes (não hospedadas em um sistema operacional), mas acho que isso exclui implementações hospedadas em C++ 20 em 386 ou 68000; você precisaria de 486 ou 68020 ou posterior. Acho que o C++20 decidiu adicionar coisas úteis que as pessoas desejam, mesmo que isso signifique que algum hardware retro não possa implementar o C++20. O C++ moderno tem feito escolhas como essa em outras áreas, como exigir que números inteiros assinados sejam complemento de dois, descartando a escolha de implementação de complemento ou sinal/magnitude.

No ISO C, o material thread/mutex/atomics é opcional, ao contrário do ISO C++, então o C moderno ainda pode ser implementado em hardware antigo, deixando de fora completamente a biblioteca de suporte a threads.

ISAs apenas com TAS ou Swap

• 68000 Instrução TAS 68000 / http://www.easy68k.com/paulrsm/doc/dpbm68k3.htm
  68020 e posteriores têm CAS (e até CAS2 em 68020/030/040 , uma operação em dois locais de memória separados, embora isso tenha se mostrado muito difícil de suportar de forma eficiente, por isso foi eliminado de CPUs posteriores).

• ARMv5 (apenas swptrocar)

• SparcV8 (mencionado por https://llvm.org/docs/Atomics.html#atomics-and-codegen )

• 80386: cmpxchgera oficialmente novo no Pentium, embora 486 tivesse um opcode diferente não documentado para ele .
  (Veja também uma questão de retrocomputação 486 SMP para alguma menção a alguns dos primeiros sistemas x86 SMP.)

  80386 tem xchg(que é um RMW atômico mesmo sem lockprefixo quando usado com um operando de memória, quer você queira ou não), e lock bts/ btr/ btcpara testar e configurar, testar e redefinir (limpar) ou testar e -complementar (inverter) um pouco sem perturbar os bits circundantes.

  Ele também tem lock add, lock or/ lock andetc. ( fetch_or/ fetch_and sem um valor de retorno, além de definir FLAGS a partir do resultado para que você possa ramificar o resultado sendo totalmente zero ou tendo seu MSB definido. Ou a paridade do byte baixo.) lock xaddera novo em 486 ( fetch_addincluindo o valor de retorno) Se você usar o valor de retorno de fetch_or, os compiladores terão que implementá-lo usando um lock cmpxchgloop de nova tentativa.

  Mas nada disso é cmpxchgou é suficiente para imitá-lo.

Exclusão mútua sem RMWs atômicos?

Tecnicamente, a exclusão mútua é possível sem um RMW atômico por meio do algoritmo de Peterson com apenas seq_cstcarregamentos e armazenamentos, mas isso requer um array com uma entrada para cada thread possível, e C++ permite iniciar novos threads depois que objetos mutex já existirem e estiverem em uso. Então isso não é realmente viável. O algoritmo de padaria de Lamport tem o mesmo requisito para uma matriz com size = NUM_THREADS.

C11 e C++11 não estavam interessados ​​em tentar oferecer suporte a threads em CPUs antigas, onde o multiprocessamento é uma tarefa difícil, então eles foram em frente e exigiram atomic_flagsuporte a RMWs sem bloqueio.

Em uma máquina uniprocessada, uma maneira de implementar qualquer RMW atômico é apenas desabilitar/reativar interrupções ao seu redor. De certa forma, isso ainda é livre de bloqueios: ele não pode criar um impasse entre uma interrupção ou manipulador de sinal e o thread principal como um spinlock ou mutex real poderia. Isso exigiria uma chamada de sistema em uma implementação hospedada.

Ou, em máquinas uniprocessadas onde as interrupções só podem acontecer nos limites das instruções, faça isso com uma única instrução. por exemplo, x86 add [mem], eaxé atômico. interrompe e, portanto, muda de contexto no mesmo núcleo, mas não em um sistema multi-core, a menos que você também use o lockprefixo. ( Incrementar um int é efetivamente atômico em casos específicos? ).

Portanto, alguns CISCs com instruções RMW de destino de memória podem usá-las para operações que precisam apenas ser de atomicidade. outros threads (ou manipuladores de interrupção) que só poderiam ser executados no mesmo núcleo (porque este é um sistema uniprocessador ou porque nos preocupamos apenas com manipuladores de interrupção/sinal). Mesmo que as instruções não tenham nenhuma garantia especial de RMW. gravadores simultâneos como DMA ou outros dispositivos de E/S de barramento mestre. Ou outros núcleos, se existirem.

Alguns ISAs como o m68k podem salvar o progresso parcial da execução de uma instrução e retomar após uma interrupção, anulando isso. Mas o x86 não é assim; interrupções são processadas apenas nos limites das instruções. (Consulte O x86 CMPXCHG é atômico, em caso afirmativo, por que ele precisa de LOCK? )

Relacionado:

• Como o atomic_flag é implementado? - para x86, os compiladores atuais usam xchgporque é um pouco mais eficiente que lock bts. clear(memory_order_release)ou mais fraco é muito mais eficiente do que lock btrusar simples movsem mfenceou xchg.

• As operações atômicas requerem suporte de hardware?

• Por que apenas std::atomic_flag é garantido como livre de bloqueios?

• Instrução TAS 68000 - exemplo de asm para um spinlock

• http://www.easy68k.com/paulrsm/doc/dpbm68k3.htm discute o design por trás do TAS

• O incremento de um int é efetivamente atômico em casos específicos? - como as microarquiteturas modernas com cache lidam com RMWs atômicos sem bloquear todo o barramento de memória, de modo que núcleos separados possam executar RMWs atômicos em locais de memória separados ao mesmo tempo.

atomic_flagé de fato o único tipo que é garantido como livre de bloqueio e, portanto, projetado para ser o suporte mínimo que deve estar presente em uma arquitetura para implementar atômica. Em geral, em chipsets minimalistas como são, por exemplo, para dispositivos embarcados, pode haver apenas uma instrução específica que permite definir uma palavra de memória para um valor específico e acessar atomicamente o valor anterior dessa palavra. Isso geralmente não é simétrico e os valores de clear e set não são necessariamente 0 e 1.

Com essas propriedades atomic_flagpodemos então usar para implementar um spinlock, que pode ser a única estrutura de bloqueio de baixo nível possível em arquiteturas onde não temos um sistema operacional.

O artigo n2145 foi apresentado std::atomic_flagcom a seguinte descrição:

A proposta inclui um tipo de flag atômico muito simples, fornecendo duas operações, test-and-set-acquire e clear-release. Este tipo é o tipo mínimo implementado em hardware necessário para estar em conformidade com este padrão. Os demais tipos podem ser emulados com o sinalizador atômico, embora com propriedades abaixo do ideal. Poucos programadores deveriam usar esse tipo.

Como o conjunto mínimo de instruções atômicas é de teste e configuração e claro, ele std::atomic_flagpossui apenas essas duas funções. Mesmo que não haja hardware com um conjunto de instruções tão restrito no momento, ele poderá aparecer no futuro e será capaz de executar código C++ com std::atomic_flag.

Acho que Nicol Bolas acertou em cheio, provavelmente tem a ver com o fato de que atomic_flag é garantido sem bloqueio, enquanto um atomic bool não.

Provavelmente é uma limitação de implementação por causa disso.