O C ++ 11 introduziu um modelo de memória padronizado. O que isso significa? E como isso afetará a programação C ++?

O C ++ 11 introduziu um modelo de memória padronizado, mas o que exatamente isso significa? E como isso afetará a programação C ++?

Este artigo (de Gavin Clarke, que cita Herb Sutter ) diz que,

O modelo de memória significa que o código C ++ agora tem uma biblioteca padronizada para chamar, independentemente de quem criou o compilador e em qual plataforma está executando. Existe uma maneira padrão de controlar como diferentes threads conversam com a memória do processador.

"Quando você está falando sobre dividir [código] entre diferentes núcleos que estão no padrão, estamos falando sobre o modelo de memória. Vamos otimizá-lo sem quebrar as seguintes suposições que as pessoas farão no código", disse Sutter .

Bem, eu posso memorizar este e outros parágrafos semelhantes disponíveis on-line (como eu tenho meu próprio modelo de memória desde o nascimento: P) e posso até postar como resposta a perguntas de outras pessoas, mas, para ser sincero, não entendo exatamente isto.

Os programadores C ++ costumavam desenvolver aplicativos multithread antes, então, como isso importa se são threads POSIX, Windows ou C ++ 11? Quais são os benefícios? Eu quero entender os detalhes de baixo nível.

Também sinto que o modelo de memória C ++ 11 está de alguma forma relacionado ao suporte a multiencadeamento do C ++ 11, como geralmente vejo esses dois juntos. Se for, como exatamente? Por que eles deveriam estar relacionados?

Como não sei como funcionam os componentes internos do multi-threading e o modelo de memória em geral, ajude-me a entender esses conceitos. :-)

Primeiro, você precisa aprender a pensar como um advogado de idiomas.

A especificação C ++ não faz referência a nenhum compilador, sistema operacional ou CPU específico. Faz referência a uma máquina abstrata que é uma generalização de sistemas reais. No mundo do advogado de idiomas, o trabalho do programador é escrever código para a máquina abstrata; o trabalho do compilador é atualizar esse código em uma máquina de concreto. Ao codificar rigidamente as especificações, você pode ter certeza de que seu código será compilado e executado sem modificação em qualquer sistema com um compilador C ++ compatível, seja hoje ou daqui a 50 anos.

A máquina abstrata na especificação C ++ 98 / C ++ 03 é fundamentalmente de thread único. Portanto, não é possível escrever código C ++ multiencadeado que seja "totalmente portátil" com relação às especificações. A especificação nem diz nada sobre a atomicidade de cargas e armazenamentos de memória ou a ordem em que cargas e armazenamentos podem ocorrer, independentemente de coisas como mutexes.

Obviamente, você pode escrever código multithread na prática para sistemas concretos específicos - como pthreads ou Windows. Mas não existe uma maneira padrão de escrever código multiencadeado para C ++ 98 / C ++ 03.

A máquina abstrata no C ++ 11 é multiencadeada por design. Ele também possui um modelo de memória bem definido ; isto é, diz o que o compilador pode ou não fazer quando se trata de acessar a memória.

Considere o seguinte exemplo, em que um par de variáveis ​​globais é acessado simultaneamente por dois threads:

           Global
           int x, y;

Thread 1            Thread 2
x = 17;             cout << y << " ";
y = 37;             cout << x << endl;

O que o Thread 2 pode gerar?

No C ++ 98 / C ++ 03, esse nem é um comportamento indefinido; a pergunta em si não tem sentido porque o padrão não contempla nada chamado "fio".

No C ++ 11, o resultado é Comportamento indefinido, porque cargas e armazenamentos não precisam ser atômicos em geral. O que pode não parecer uma grande melhoria ... E por si só, não é.

Mas com o C ++ 11, você pode escrever o seguinte:

           Global
           atomic<int> x, y;

Thread 1                 Thread 2
x.store(17);             cout << y.load() << " ";
y.store(37);             cout << x.load() << endl;

Agora as coisas ficam muito mais interessantes. Primeiro de tudo, o comportamento aqui é definido . O segmento 2 agora pode ser impresso 0 0(se for executado antes do segmento 1), 37 17(se for executado após o segmento 1) ou 0 17(se for executado após o segmento 1 atribuir x, mas antes atribuir y).

O que ele não pode imprimir é 37 0porque o modo padrão para cargas / armazenamentos atômicos no C ++ 11 é impor consistência sequencial . Isso significa apenas que todas as cargas e armazenamentos devem ser "como se" eles tivessem acontecido na ordem em que você os gravou em cada encadeamento, enquanto as operações entre encadeamentos podem ser intercaladas da maneira que o sistema desejar. Portanto, o comportamento padrão dos átomos fornece atomicidade e pedidos para cargas e armazenamentos.

Agora, em uma CPU moderna, garantir a consistência sequencial pode ser caro. Em particular, é provável que o compilador emita barreiras de memória completas entre todos os acessos aqui. Mas se o seu algoritmo puder tolerar cargas e armazenamentos fora de ordem; isto é, se requer atomicidade, mas não ordenação; ou seja, se ele pode tolerar 37 0como saída deste programa, você pode escrever o seguinte:

           Global
           atomic<int> x, y;

Thread 1                            Thread 2
x.store(17,memory_order_relaxed);   cout << y.load(memory_order_relaxed) << " ";
y.store(37,memory_order_relaxed);   cout << x.load(memory_order_relaxed) << endl;

Quanto mais moderna a CPU, maior a probabilidade de ela ser mais rápida que o exemplo anterior.

Por fim, se você precisar apenas manter cargas e armazenamentos específicos em ordem, pode escrever:

           Global
           atomic<int> x, y;

Thread 1                            Thread 2
x.store(17,memory_order_release);   cout << y.load(memory_order_acquire) << " ";
y.store(37,memory_order_release);   cout << x.load(memory_order_acquire) << endl;

Isso nos leva de volta às cargas e lojas encomendadas - portanto, 37 0não é mais uma saída possível -, mas o faz com uma sobrecarga mínima. (Neste exemplo trivial, o resultado é o mesmo que a consistência sequencial completa; em um programa maior, não seria.)

Obviamente, se as únicas saídas que você deseja ver forem 0 0or 37 17, você pode apenas envolver um mutex em torno do código original. Mas se você leu até aqui, aposto que já sabe como isso funciona, e essa resposta já é mais longa do que eu pretendia :-).

Então, linha de fundo. Os mutexes são ótimos e o C ++ 11 os padroniza. Mas, às vezes, por razões de desempenho, você deseja primitivas de nível inferior (por exemplo, o padrão de bloqueio clássico verificado duas vezes ). O novo padrão fornece dispositivos de alto nível, como mutexes e variáveis ​​de condição, e também dispositivos de baixo nível, como tipos atômicos e os vários tipos de barreira à memória. Portanto, agora você pode escrever rotinas simultâneas sofisticadas e de alto desempenho, inteiramente dentro do idioma especificado pelo padrão, e pode ter certeza de que seu código será compilado e executado inalterado nos sistemas de hoje e no de amanhã.

Embora seja franco, a menos que você seja um especialista e trabalhe em algum código sério de baixo nível, provavelmente deve seguir mutexes e variáveis ​​de condição. É isso que pretendo fazer.

Para mais informações, consulte esta postagem no blog .

Vou apenas dar a analogia com a qual entendo os modelos de consistência de memória (ou modelos de memória, para abreviar). É inspirado no artigo seminal de Leslie Lamport, "Tempo, relógios e a ordem dos eventos em um sistema distribuído" . A analogia é adequada e tem um significado fundamental, mas pode ser um exagero para muitas pessoas. No entanto, espero que ele forneça uma imagem mental (uma representação pictórica) que facilite o raciocínio sobre os modelos de consistência da memória.

Vamos ver os históricos de todas as localizações da memória em um diagrama de espaço-tempo no qual o eixo horizontal representa o espaço de endereço (ou seja, cada localização de memória é representada por um ponto nesse eixo) e o eixo vertical representa o tempo (veremos que, em geral, não existe uma noção universal de tempo). O histórico de valores mantidos por cada local de memória é, portanto, representado por uma coluna vertical nesse endereço de memória. Cada alteração de valor ocorre devido a um dos segmentos que escreve um novo valor para esse local. Por uma imagem de memória , queremos dizer a agregação / combinação de valores de todos os locais de memória observáveis em um momento específico por um encadeamento específico .

Citação de "Uma cartilha sobre consistência de memória e coerência de cache"

O modelo de memória intuitivo (e mais restritivo) é a consistência sequencial (SC), na qual uma execução multithread deve parecer uma intercalação das execuções sequenciais de cada encadeamento constituinte, como se os encadeamentos fossem multiplexados no tempo em um processador de núcleo único.

Essa ordem de memória global pode variar de uma execução do programa para outra e pode não ser conhecida antecipadamente. A característica do SC é o conjunto de fatias horizontais no diagrama espaço-endereço-tempo que representa planos de simultaneidade (ou seja, imagens de memória). Em um determinado plano, todos os seus eventos (ou valores de memória) são simultâneos. Existe uma noção de tempo absoluto , na qual todos os threads concordam com quais valores de memória são simultâneos. No SC, a cada instante, há apenas uma imagem de memória compartilhada por todos os threads. Ou seja, a cada instante, todos os processadores concordam com a imagem da memória (ou seja, o conteúdo agregado da memória). Isso não significa apenas que todos os threads visualizam a mesma sequência de valores para todos os locais de memória, mas também que todos os processadores observam o mesmocombinações de valores de todas as variáveis. É o mesmo que dizer que todas as operações de memória (em todos os locais de memória) são observadas na mesma ordem total por todos os threads.

Nos modelos de memória relaxada, cada thread dividirá o espaço do endereço e o tempo do seu próprio jeito, a única restrição é que as fatias de cada thread não se cruzarão porque todos os threads devem concordar com o histórico de cada local de memória individual (é claro , fatias de diferentes segmentos podem e vão se cruzar). Não existe uma maneira universal de dividi-lo (nenhuma foliação privilegiada do espaço do endereço-tempo). As fatias não precisam ser planas (ou lineares). Eles podem ser curvos e é isso que pode fazer um thread ler valores gravados por outro thread fora da ordem em que foram gravados. Histórias de diferentes locais de memória podem deslizar (ou se esticar) arbitrariamente em relação um ao outro quando visualizados por qualquer thread específico. Cada encadeamento terá um senso diferente de quais eventos (ou, equivalentemente, valores de memória) são simultâneos. O conjunto de eventos (ou valores de memória) que são simultâneos a um encadeamento não são simultâneos a outro. Assim, em um modelo de memória relaxada, todos os threads ainda observam o mesmo histórico (isto é, sequência de valores) para cada local de memória. Mas eles podem observar imagens de memória diferentes (ou seja, combinações de valores de todos os locais de memória). Mesmo que dois locais de memória diferentes sejam gravados pelo mesmo encadeamento em seqüência, os dois valores recém-gravados podem ser observados em ordem diferente por outros encadeamentos.

[Imagem da Wikipedia]

Os leitores familiarizados com a Teoria Especial da Relatividade de Einstein perceberão o que estou fazendo alusão. Traduzindo as palavras de Minkowski para o domínio dos modelos de memória: espaço de endereço e tempo são sombras do espaço de endereço-tempo. Nesse caso, cada observador (ou seja, thread) projetará sombras de eventos (ou seja, armazenamentos / cargas de memória) em sua própria linha do mundo (ou seja, seu eixo de tempo) e em seu próprio plano de simultaneidade (seu eixo de espaço de endereço) . Os encadeamentos no modelo de memória C ++ 11 correspondem a observadores que estão se movendo um em relação ao outro em uma relatividade especial. A consistência sequencial corresponde ao espaço-tempo da Galiléia (ou seja, todos os observadores concordam com uma ordem absoluta de eventos e um senso global de simultaneidade).

A semelhança entre modelos de memória e relatividade especial deriva do fato de que ambos definem um conjunto de eventos parcialmente ordenados, geralmente chamado de conjunto causal. Alguns eventos (ou seja, armazenamentos de memória) podem afetar (mas não são afetados por) outros eventos. Um encadeamento C ++ 11 (ou observador em física) não passa de uma cadeia (ou seja, um conjunto totalmente ordenado) de eventos (por exemplo, carregamentos e armazenamentos de memória em endereços possivelmente diferentes).

Na relatividade, alguma ordem é restaurada para o quadro aparentemente caótico de eventos parcialmente ordenados, uma vez que a única ordem temporal com a qual todos os observadores concordam é a ordem entre eventos "semelhantes ao tempo" (ou seja, aqueles eventos que são, em princípio, conectáveis ​​por qualquer partícula que fica mais lenta). que a velocidade da luz no vácuo). Somente os eventos relacionados ao horário são invariáveis. Tempo em Física, Craig Callender .

No modelo de memória C ++ 11, um mecanismo semelhante (o modelo de consistência adquirir-liberar) é usado para estabelecer essas relações de causalidade local .

Para fornecer uma definição de consistência da memória e uma motivação para abandonar o SC, citarei "Uma cartilha sobre consistência de memória e coerência de cache"

Para uma máquina de memória compartilhada, o modelo de consistência de memória define o comportamento arquiteturalmente visível de seu sistema de memória. O critério de correção para um único processador particiona o comportamento entre " um resultado correto " e " muitas alternativas incorretas ". Isso ocorre porque a arquitetura do processador exige que a execução de um encadeamento transforme um determinado estado de entrada em um único estado de saída bem definido, mesmo em um núcleo fora de ordem. Os modelos de consistência de memória compartilhada, no entanto, dizem respeito às cargas e armazenamentos de vários encadeamentos e geralmente permitem muitas execuções corretasenquanto não permite muitos (mais) incorretos. A possibilidade de várias execuções corretas deve-se ao ISA, que permite que vários threads sejam executados simultaneamente, geralmente com muitas intercalações legais possíveis de instruções de diferentes threads.

Modelos de consistência de memória relaxada ou fraca são motivados pelo fato de que a maioria dos pedidos de memória em modelos fortes é desnecessária. Se um thread atualiza dez itens de dados e, em seguida, um sinalizador de sincronização, os programadores geralmente não se importam se os itens de dados são atualizados em ordem um com o outro, mas apenas com todos os itens de dados antes da atualização do sinalizador (geralmente implementado usando as instruções FENCE ) Modelos relaxados procuram capturar essa maior flexibilidade de pedidos e preservar apenas os pedidos que os programadores “ exigem”Para obter maior desempenho e correção do SC. Por exemplo, em certas arquiteturas, os buffers de gravação FIFO são usados ​​por cada núcleo para manter os resultados dos armazenamentos confirmados (aposentados) antes de gravar os resultados nos caches. Essa otimização aprimora o desempenho, mas viola o SC. O buffer de gravação oculta a latência de manutenção de uma falta de armazenamento. Como as lojas são comuns, poder evitar o empate na maioria delas é um benefício importante. Para um processador de núcleo único, um buffer de gravação pode ser invisível da arquitetura, garantindo que uma carga para endereçar A retorne o valor do armazenamento mais recente para A, mesmo que um ou mais armazenamentos em A estejam no buffer de gravação. Isso geralmente é feito ignorando o valor da loja mais recente para A e transferindo a carga de A, onde "mais recente" é determinado pela ordem do programa, ou paralisando uma carga de A se um armazenamento para A estiver no buffer de gravação. Quando vários núcleos são usados, cada um terá seu próprio buffer de gravação ignorado. Sem buffers de gravação, o hardware é SC, mas com buffers de gravação, não é, tornando os buffers de gravação arquitetonicamente visíveis em um processador multicore.

A reordenação de loja pode ocorrer se um núcleo tiver um buffer de gravação não FIFO que permita que as lojas partam em uma ordem diferente da ordem em que foram inseridas. Isso pode ocorrer se a primeira loja falhar no cache enquanto a segunda ocorre ou se a segunda loja puder se unir a uma loja anterior (ou seja, antes da primeira loja). A reordenação de carga também pode ocorrer em núcleos agendados dinamicamente que executam instruções fora da ordem do programa. Isso pode se comportar da mesma maneira que reordenar lojas em outro núcleo (você pode criar um exemplo de intercalação entre dois threads?). Reordenar um carregamento anterior com um armazenamento posterior (um reordenamento de armazenamento de carga) pode causar muitos comportamentos incorretos, como carregar um valor após liberar o bloqueio que o protege (se o armazenamento for a operação de desbloqueio).

Como a coerência do cache e a consistência da memória às vezes são confusas, é instrutivo também ter esta citação:

Diferentemente da consistência, a coerência do cache não é visível para o software nem é necessária. A coerência procura tornar os caches de um sistema de memória compartilhada tão funcionalmente invisíveis quanto os caches de um sistema de núcleo único. A coerência correta garante que um programador não possa determinar se e onde um sistema possui caches analisando os resultados de cargas e armazenamentos. Isso ocorre porque a coerência correta garante que os caches nunca permitam comportamentos funcionais novos ou diferentes (os programadores ainda podem inferir a estrutura provável do cache usando o tempoem formação). O principal objetivo dos protocolos de coerência de cache é manter o SWMR (single-writer-multiple-readers) invariável para todos os locais de memória. Uma distinção importante entre coerência e consistência é que a coerência é especificada em uma localização por memória , enquanto a consistência é especificada em relação a todos os locais da memória.

Continuando com nossa imagem mental, o invariante SWMR corresponde ao requisito físico de que haja no máximo uma partícula localizada em qualquer local, mas pode haver um número ilimitado de observadores em qualquer local.

_{Agora, essa é uma pergunta de vários anos, mas, sendo muito popular, vale a pena mencionar um recurso fantástico para aprender sobre o modelo de memória C ++ 11. Não vejo sentido em resumir sua palestra para fazer mais uma resposta completa, mas, como esse é o cara que realmente escreveu o padrão, acho que vale a pena assistir à palestra.}

Herb Sutter tem uma conversa de três horas sobre o modelo de memória C ++ 11 intitulado "Atomic <> Weapons", disponível no site do Channel9 - parte 1 e parte 2 . A palestra é bastante técnica e aborda os seguintes tópicos:

1. Otimizações, raças e o modelo de memória
2. Pedidos - O quê: Adquirir e liberar
3. Ordenação - Como: Mutexes, Atômicas e / ou Cercas
4. Outras restrições em compiladores e hardware
5. Geração e desempenho de código: x86 / x64, IA64, POWER, ARM
6. Atomics relaxado

A conversa não é elaborada sobre a API, mas sobre o raciocínio, o histórico, os bastidores e os bastidores (você sabia que semânticas relaxadas foram adicionadas ao padrão apenas porque o POWER e o ARM não suportam a carga sincronizada de maneira eficiente?).

Isso significa que o padrão agora define multiencadeamento e define o que acontece no contexto de vários encadeamentos. Obviamente, as pessoas usavam implementações variadas, mas é como perguntar por que deveríamos ter um std::stringquando todos nós poderíamos estar usando uma stringclasse feita em casa .

Quando você está falando sobre threads POSIX ou Windows, isso é uma ilusão, já que você está falando sobre threads x86, pois é uma função de hardware que é executada simultaneamente. O modelo de memória C ++ 0x oferece garantias, esteja você em x86, ARM, MIPS ou qualquer outra coisa que possa oferecer .

Para idiomas que não especificam um modelo de memória, você está escrevendo um código para o idioma e o modelo de memória especificado pela arquitetura do processador. O processador pode optar por reordenar os acessos à memória para desempenho. Portanto, se seu programa tiver corridas de dados (uma corrida de dados é quando é possível que vários núcleos / hiperencadeamentos acessem a mesma memória simultaneamente), seu programa não é multiplataforma devido à dependência do modelo de memória do processador. Você pode consultar os manuais de software da Intel ou AMD para descobrir como os processadores podem solicitar novamente o acesso à memória.

Muito importante, bloqueios (e semântica de simultaneidade com bloqueio) são normalmente implementados de uma forma multiplataforma ... Portanto, se você estiver usando bloqueios padrão em um programa multithread sem corridas de dados, não precisará se preocupar com modelos de memória multiplataforma .

Curiosamente, os compiladores da Microsoft para C ++ possuem semântica de aquisição / lançamento para volátil, que é uma extensão do C ++ para lidar com a falta de um modelo de memória no C ++ http://msdn.microsoft.com/en-us/library/12a04hfd(v=vs .80) .aspx . No entanto, como o Windows roda apenas em x86 / x64, isso não significa muito (os modelos de memória Intel e AMD tornam fácil e eficiente implementar a semântica de aquisição / lançamento em um idioma).

Se você usa mutexes para proteger todos os seus dados, não precisa se preocupar. Os mutexes sempre forneceram garantias suficientes de pedidos e visibilidade.

Agora, se você usou atômicos ou algoritmos sem bloqueio, é necessário pensar no modelo de memória. O modelo de memória descreve precisamente quando os atômicos fornecem garantias de pedidos e visibilidade e fornecem cercas portáteis para garantias codificadas manualmente.

Anteriormente, os atômicos eram feitos usando intrínsecas do compilador ou alguma biblioteca de nível superior. As cercas teriam sido feitas usando instruções específicas da CPU (barreiras de memória).

As respostas acima abordam os aspectos mais fundamentais do modelo de memória C ++. Na prática, a maioria dos usos do std::atomic<>"apenas funciona", pelo menos até o programa otimizar demais (por exemplo, tentando relaxar muitas coisas).

Há um lugar onde os erros ainda são comuns: bloqueios de sequência . Há uma discussão excelente e fácil de ler sobre os desafios em https://www.hpl.hp.com/techreports/2012/HPL-2012-68.pdf . Os bloqueios de sequência são atraentes porque o leitor evita a gravação da palavra de bloqueio. O código a seguir é baseado na Figura 1 do relatório técnico acima e destaca os desafios ao implementar bloqueios de sequência em C ++:

atomic<uint64_t> seq; // seqlock representation
int data1, data2;     // this data will be protected by seq

T reader() {
    int r1, r2;
    unsigned seq0, seq1;
    while (true) {
        seq0 = seq;
        r1 = data1; // INCORRECT! Data Race!
        r2 = data2; // INCORRECT!
        seq1 = seq;

        // if the lock didn't change while I was reading, and
        // the lock wasn't held while I was reading, then my
        // reads should be valid
        if (seq0 == seq1 && !(seq0 & 1))
            break;
    }
    use(r1, r2);
}

void writer(int new_data1, int new_data2) {
    unsigned seq0 = seq;
    while (true) {
        if ((!(seq0 & 1)) && seq.compare_exchange_weak(seq0, seq0 + 1))
            break; // atomically moving the lock from even to odd is an acquire
    }
    data1 = new_data1;
    data2 = new_data2;
    seq = seq0 + 2; // release the lock by increasing its value to even
}

Tão pouco intuitivo quanto parece no começo, data1e data2precisa ser atomic<>. Se eles não forem atômicos, poderão ser lidos (in reader()) no exato momento em que foram escritos (in writer()). De acordo com o modelo de memória C ++, essa é uma corrida, mesmo que reader()nunca use os dados . Além disso, se eles não forem atômicos, o compilador poderá armazenar em cache a primeira leitura de cada valor em um registro. Obviamente, você não gostaria disso ... quer reler a cada iteração do whileloop reader().

Também não é suficiente criá-los atomic<>e acessá-los com memory_order_relaxed. A razão para isso é que as leituras de seq (in reader()) só adquirem semântica. Em termos simples, se X e Y são acessos à memória, X precede Y, X não é uma aquisição ou liberação e Y é uma aquisição, o compilador pode reordenar Y antes de X. Se Y foi a segunda leitura de seq, e X era uma leitura de dados, essa reordenação interromperia a implementação do bloqueio.

O artigo fornece algumas soluções. O que tem o melhor desempenho hoje é provavelmente aquele que usa um atomic_thread_fencecom memory_order_relaxed antes da segunda leitura do seqlock. No artigo, é a Figura 6. Não estou reproduzindo o código aqui, porque quem já leu até agora deve ler o artigo. É mais preciso e completo que este post.

A última questão é que pode não ser natural tornar as datavariáveis ​​atômicas. Se você não pode no seu código, precisa ter muito cuidado, porque transmitir de não atômico para atômico é legal apenas para tipos primitivos. O C ++ 20 deve ser adicionado atomic_ref<>, o que facilitará a solução desse problema.

Resumindo: mesmo que você entenda o modelo de memória C ++, tenha muito cuidado antes de rolar seus próprios bloqueios de sequência.

C e C ++ costumavam ser definidos por um rastreamento de execução de um programa bem formado.

Agora eles são meio definidos por um rastreio de execução de um programa e meio a posteriori por muitas ordens em objetos de sincronização.

Significando que essas definições de linguagem não fazem sentido, pois não há método lógico para misturar essas duas abordagens. Em particular, a destruição de um mutex ou variável atômica não está bem definida.