Compartilhar via

Considerações sobre programação sem bloqueio para Xbox 360 e Microsoft Windows

  • Artigo

A programação sem bloqueio é uma maneira de compartilhar com segurança dados alterados entre vários threads sem o custo de adquirir e liberar bloqueios. Isso soa como uma solução milagrosa, mas a programação sem bloqueio é complexa e sutil e, às vezes, não oferece os benefícios que promete. A programação sem bloqueio é particularmente complexa no Xbox 360.

A programação sem bloqueio é uma técnica válida para a programação multi-threaded, mas não deve ser usada de maneira leviana. Antes de usá-lo, é preciso entender as complexidades e medir cuidadosamente para ter certeza de que ele está realmente proporcionando os ganhos esperados. Em muitos casos, há soluções mais simples e rápidas, como o compartilhamento de dados com menor frequência, que devem ser usadas em seu lugar.

Usar a programação sem bloqueio de forma correta e segura requer um conhecimento significativo do hardware e do compilador. Este artigo apresenta uma visão geral de alguns dos problemas a serem considerados ao tentar usar técnicas de programação sem bloqueio.

Programação com bloqueios

Ao escrever um código multi-threaded é comum ser necessário compartilhar dados entre threads. Se vários threads estiverem lendo e gravando simultaneamente as estruturas de dados compartilhadas, poderá ocorrer corrupção de memória. A maneira mais simples de resolver esse problema é usar bloqueios. Por exemplo, se ManipulateSharedData só deve ser executado por um thread por vez, um CRITICAL_SECTION pode ser usado para garantir isso, como no código a seguir:

// Initialize
CRITICAL_SECTION cs;
InitializeCriticalSection(&cs);

// Use
void ManipulateSharedData()
{
    EnterCriticalSection(&cs);
    // Manipulate stuff...
    LeaveCriticalSection(&cs);
}

// Destroy
DeleteCriticalSection(&cs);

Este código é bastante simples e direto, e é fácil dizer que está correto. No entanto, a programação com bloqueios vem com várias desvantagens potenciais. Por exemplo, se dois threads tentarem adquirir os mesmos dois bloqueios, mas os adquirirem em uma ordem diferente, você poderá obter um deadlock. Se um programa mantiver um bloqueio por muito tempo, devido a um design ruim ou porque o thread foi trocado por um thread de prioridade mais alta, outros threads poderão ser bloqueados por um longo tempo. Esse risco é particularmente grande no Xbox 360 porque os threads de software são atribuídos a um thread de hardware pelo desenvolvedor e o sistema operacional não os moverá para outro thread de hardware, mesmo que um esteja ocioso. O Xbox 360 também não tem proteção contra inversão de prioridade, em que um thread de alta prioridade gira em um loop enquanto espera que um thread de baixa prioridade libere um bloqueio. Por fim, se uma chamada de procedimento adiado ou uma rotina de serviço de interrupção tentar adquirir um bloqueio, você poderá obter um deadlock.

Apesar desses problemas, os primitivos de sincronização, como seções críticas, geralmente são a melhor maneira de coordenar vários threads. Se as primitivas de sincronização forem muito lentas, a melhor solução geralmente é usá-las com menor frequência. Entretanto, para aqueles que podem arcar com a complexidade adicional, outra opção é a programação sem bloqueio.

Programação sem bloqueio

A programação sem bloqueio, como o nome sugere, é uma família de técnicas que manipula com segurança dados compartilhados sem usar bloqueios. Existem algoritmos sem bloqueio disponíveis para passar mensagens, compartilhar listas, filas de dados e outras tarefas.

Ao fazer a programação sem bloqueio, há dois desafios com os quais você deve lidar: operações não atômicas e reordenação.

Operações não atômicas

Uma operação atômica é aquela que é indivisível, onde outros threads têm a garantia de nunca ver a operação enquanto ela estiver pela metade. As operações atômicas são importantes para a programação sem bloqueio, pois sem elas, outros threads podem ver valores semi-gravados ou em estado inconsistente.

Em todos os processadores modernos, você pode supor que as leituras e gravações de tipos nativos alinhados naturalmente são atômicas. Desde que o barramento de memória seja pelo menos tão largo quanto o tipo que está sendo lido ou gravado, a CPU lê e grava esses tipos em uma única transação de barramento, tornando impossível para outros threads vê-los em um estado incompleto. Em x86 e x64, não há garantia de que leituras e gravações maiores que oito bytes sejam atômicas. Isso significa que leituras e gravações de 16 bytes de registros de extensão SIMD (SSE) de streaming e operações de cadeia de caracteres podem não ser atômicas.

Leituras e gravações de tipos que não são alinhados naturalmente como por exemplo, escrever DWORDs que cruzam limites de quatro bytes, não possuem garantia de serem atômicas. A CPU pode ter que fazer essas leituras e gravações como várias transações de barramento, permitindo que outro thread modifique ou veja os dados no meio da leitura ou gravação.

As operações compostas, como a sequência de leitura, modificação e gravação que ocorre quando você incrementa uma variável compartilhada, não são atômicas. No Xbox 360, essas operações são implementadas como múltiplas instruções (lwz, addi e stw) e o thread pode ser trocado no meio da sequência. Em x86 e x64, há uma única instrução (inc) que pode ser usada para incrementar uma variável na memória. Se você usar essa instrução, o incremento de uma variável será atômico em sistemas com um único processador, mas ainda não será atômico em sistemas com vários processadores. Para tornar a inc atômica em sistemas multiprocessadores baseados em x86 e x64, é necessário usar o prefixo lock, que impede que outro processador faça sua própria sequência de leitura, modificação e gravação entre a leitura e a gravação da instrução inc.

O código a seguir mostra alguns exemplos:

// This write is not atomic because it is not natively aligned.
DWORD* pData = (DWORD*)(pChar + 1);
*pData = 0;

// This is not atomic because it is three separate operations.
++g_globalCounter;

// This write is atomic.
g_alignedGlobal = 0;

// This read is atomic.
DWORD local = g_alignedGlobal;

Garantia de atomicidade

Você pode ter certeza de que está usando operações atômicas pela seguinte combinação:

  • Operações naturalmente atômicas
  • Bloqueios para encapsular operações compostas
  • Funções do sistema operacional que implementam versões atômicas de populares operações compostas

O incremento de uma variável não é uma operação atômica e o incremento pode levar à corrupção de dados se for executado em vários threads.

// This will be atomic.
g_globalCounter = 0;

// This is not atomic and gives undefined behavior
// if executed on multiple threads
++g_globalCounter;

O Win32 vem com uma família de funções que oferecem versões atômicas de leitura, modificação e gravação de várias operações comuns. Estas são as funções da família InterlockedXxx. Se todas as modificações da variável compartilhada usarem essas funções, as modificações serão thread‑safe.

// Incrementing our variable in a safe lockless way.
InterlockedIncrement(&g_globalCounter);

Reordenação

Um problema mais sutil é a reordenação. Leituras e gravações nem sempre acontecem na ordem em que você as escreveu em seu código, e isso pode levar a problemas bem confusos. Em muitos algoritmos multi-threaded, um thread grava alguns dados e, em seguida, grava em um sinalizador que informa a outros threads que os dados estão prontos. Isso é conhecido como lançamento de gravação. Se as gravações forem reordenadas, outros threads poderão ver que o sinalizador está definido antes de poderem ver os dados que foram gravados.

De forma similar, em muitos casos, um thread lê a partir de um sinalizador e, em seguida, lê alguns dados compartilhados se o sinalizador indicar que o thread adquiriu acesso aos dados compartilhados. Isso é conhecido como leitura e aquisição. Se as leituras forem reordenadas, os dados poderão ser lidos do armazenamento compartilhado antes do sinalizador, podendo os valores vistos não estarem atualizados.

A reordenação de leituras e gravações pode ser feita pelo compilador e pelo processador. Compiladores e processadores têm feito essa reordenação há anos, mas em máquinas com um único processador, isso não era um problema. Isso ocorre porque o rearranjo de leituras e gravações da CPU é invisível em máquinas com um único processador (para código de driver que não seja de dispositivo e que não faça parte de um driver de dispositivo), e o rearranjo de leituras e gravações do compilador tem menos probabilidade de causar problemas em máquinas com um único processador.

Se o compilador ou a CPU reorganizar as gravações exibidas no código a seguir, outro thread poderá ver que o sinalizador ativo está definido e ainda ver os valores antigos de x ou y. Um rearranjo semelhante pode acontecer durante a leitura.

Neste código, um thread adiciona uma nova entrada à matriz de sprite:

// Create a new sprite by writing its position into an empty
// entry and then setting the 'alive' flag. If 'alive' is
// written before x or y then errors may occur.
g_sprites[nextSprite].x = x;
g_sprites[nextSprite].y = y;
g_sprites[nextSprite].alive = true;

Neste próximo bloco de código, outro thread lê a partir da matriz de sprite:

// Draw all sprites. If the reads of x and y are moved ahead of
// the read of 'alive' then errors may occur.
for( int i = 0; i < numSprites; ++i )
{
    if( g_sprites[nextSprite].alive )
    {
        DrawSprite( g_sprites[nextSprite].x,
                g_sprites[nextSprite].y );
    }
}

Para poder tornar esse sistema de sprite seguro, precisamos evitar a reordenação de leituras e gravações do compilador e da CPU.

Reconhecimento do rearranjo de gravações da CPU

Algumas CPUs reorganizam as gravações para ficarem visíveis externamente para outros processadores ou dispositivos em uma ordem não relacionada ao programa. Essa reorganização nunca é visível para o código não driver de thread único, mas pode causar problemas no código multi-threaded.

Xbox 360

Embora a CPU do Xbox 360 não reordene as instruções, ela reorganiza as operações de gravação, que são concluídas após as próprias instruções. Essa reorganização de gravações é permitida especificamente pelo modelo de memória PowerPC.

As gravações no Xbox 360 não vão diretamente para o cache L2. Em vez disso, para melhorar a largura de banda de gravação do cache L2, eles passam por filas de armazenamento e, em seguida, para buffers de coleta de armazenamento. Os buffers de coleta de armazenamento permitem que blocos de 64 bytes sejam gravados no cache L2 em uma operação. Existem oito buffers de coleta de armazenamento, que permitem a gravação eficiente em várias áreas diferentes da memória.

Os buffers de coleta de armazenamento são geralmente gravados no cache L2 na ordem FIFO (primeiro a entrar e primeiro a sair). No entanto, se a linha de cache de destino de uma gravação não estiver no cache L2, ela poderá ser atrasada enquanto a linha de cache é obtida da memória.

Mesmo quando os buffers de armazenamento e coleta são gravados no cache L2 em ordem FIFO de forma estrita, isso não garante que as gravações individuais serão gravadas no cache L2 em ordem. Por exemplo, imagine que a CPU grava no local 0x1000, depois no local 0x2000 e depois no local 0x1004. A primeira gravação aloca um buffer de coleta de armazenamento e o coloca na frente da fila. A segunda gravação aloca outro buffer de coleta de armazenamento e o coloca em seguida na fila. A terceira gravação adiciona seus dados ao primeiro buffer de coleta de armazenamento, que permanece na frente da fila. Assim, a terceira gravação acaba indo para o cache L2 antes da segunda gravação.

A reordenação provocada por buffers de coleta de armazenamento é fundamentalmente imprevisível, especialmente porque ambos os threads em um núcleo compartilham os buffers de coleta de armazenamento, tornando a alocação e o esvaziamento dos buffers de coleta de armazenamento altamente variáveis.

Este é um exemplo de como as gravações podem ser reordenadas. Pode haver outras possibilidades.

x86 e x64

Embora as CPUs x86 e x64 reordenem as instruções, elas geralmente não reordenam as operações de gravação em relação a outras gravações. Existem algumas exceções para a memória combinada de gravação. Além disso, as operações de cadeia de caracteres (MOVS e STOS) e as gravações SSE de 16 bytes podem ser reordenadas internamente, mas, por outro lado, as gravações não são reordenadas em relação umas às outras.

O reconhecimento do rearranjo de leituras da CPU

Algumas CPUs reorganizam as leituras para que elas venham efetivamente do armazenamento compartilhado em uma ordem diferente da do programa. Esse rearranjo nunca é visível para o código não driver de thread único, mas pode gerar problemas no código multi-threaded.

Xbox 360

Os erros de cache podem fazer com que algumas leituras atrasem, o que de fato faz com que as leituras venham da memória compartilhada fora de ordem, e o tempo desses erros de cache é fundamentalmente imprevisível. A busca prévia e a previsão de ramificação também podem fazer com que os dados venham da memória compartilhada fora de ordem. Estes são apenas alguns exemplos de como as leituras podem ser reordenadas. Pode haver outras possibilidades. Esse rearranjo de leituras é especificamente permitido pelo modelo de memória do PowerPC.

x86 e x64

Embora as CPUs x86 e x64 reordenem as instruções, elas geralmente não reordenam as operações de leitura em relação a outras leituras. As operações de cadeias de caracteres (MOVS e STOS) e as leituras SSE de 16 bytes podem ser reordenadas internamente, mas, por outro lado, as leituras não são reordenadas em relação umas às outras.

Outros reordenamentos

Embora as CPUs x86 e x64 não reordenem as gravações em relação a outras gravações ou reordenem as leituras em relação a outras leituras, elas podem reordenar as leituras em relação às gravações. Em especial, se um programa gravar em um local e depois ler em um local diferente, os dados lidos poderão vir da memória compartilhada antes que os dados gravados cheguem lá. Essa reordenação pode quebrar alguns algoritmos, como os algoritmos de exclusão mútua de Dekker. No algoritmo de Dekker, cada thread define um sinalizador para indicar que deseja entrar na região crítica e, em seguida, verifica o sinalizador do outro thread para ver se ele está na região crítica ou tentando entrar nela. O código inicial está a seguir.

volatile bool f0 = false;
volatile bool f1 = false;

void P0Acquire()
{
    // Indicate intention to enter critical region
    f0 = true;
    // Check for other thread in or entering critical region
    while (f1)
    {
        // Handle contention.
    }
    // critical region
    ...
}


void P1Acquire()
{
    // Indicate intention to enter critical region
    f1 = true;
    // Check for other thread in or entering critical region
    while (f0)
    {
        // Handle contention.
    }
    // critical region
    ...
}

O problema é que a leitura de f1 em P0Acquire pode ler do armazenamento compartilhado antes que a gravação em f0 chegue lá. Enquanto isso, a leitura de f0 em P1Acquire pode ser lida do armazenamento compartilhado antes que a gravação em f1 chegue ao armazenamento compartilhado. O efeito final é que ambos os threads definem seus sinalizadores como TRUE, e ambos os threads veem o sinalizador do outro thread como FALSE, de modo que ambos entram na região crítica. Portanto, embora os problemas com a reordenação em sistemas baseados em x86 e x64 sejam menos comuns do que no Xbox 360, eles ainda podem ocorrer. O algoritmo de Dekker não funcionará sem barreiras de memória de hardware em nenhuma dessas plataformas.

As CPUs x86 e x64 não reordenarão uma gravação antes de uma leitura anterior. As CPUs x86 e x64 só reordenam as leituras antes das gravações anteriores se forem direcionadas a locais diferentes.

As CPUs PowerPC podem reordenar as leituras antes das gravações e podem reordenar as gravações antes das leituras, desde que sejam para endereços diferentes.

Reordenação do resumo

A CPU do Xbox 360 reordena as operações de memória mais agressivamente do que as CPUs x86 e x64, como é mostrado na tabela a seguir. Para obter mais detalhes, consulte a documentação do processador.

Reordenação da atividade x86 e x64 Xbox 360
Leituras se movem à frente das leituras Não Sim
Gravações se movem à frente das gravações Não Sim
Gravações se movem antes das leituras Não Sim
As leituras se movem à frente das gravações Sim Sim

 

Barreiras de leitura e aquisição e barreiras de gravação e liberação

As principais construções usadas para evitar a reordenação de leituras e gravações são chamadas de barreiras de leitura e aquisição e gravação e liberação. Uma leitura e aquisição é uma leitura de um sinalizador ou outra variável para obter a propriedade de um recurso, juntamente com uma barreira contra a reordenação. Da mesma forma, uma versão de gravação é uma gravação de um sinalizador ou outra variável para revelar a propriedade de um recurso, juntamente com uma barreira contra a reordenação.

As definições formais, cortesia de Herb Sutter, são:

  • Uma leitura e aquisição é executada antes de todas as leituras e gravações pelo mesmo thread que o segue na ordem do programa.
  • Uma versão da gravação é executada depois de todas as leituras e gravações pelo mesmo thread que a precede na ordem do programa.

Quando seu código adquire a propriedade de alguma memória, seja adquirindo um bloqueio ou extraindo um item de uma lista vinculada compartilhada (sem um bloqueio), sempre há uma leitura envolvida testando um sinalizador ou ponteiro para ver se a propriedade da memória foi adquirida. Essa leitura pode fazer parte de uma operação InterlockedXxx, caso em que envolve uma leitura e uma gravação, mas é a leitura que indica se a propriedade foi obtida. Depois que a propriedade da memória é adquirida, os valores normalmente são lidos ou gravados nessa memória, e é muito importante que essas leituras e gravações sejam executadas após a aquisição da propriedade. Uma barreira de leitura e aquisição garante isso.

Quando a propriedade de alguma memória é liberada, seja liberando um bloqueio ou empurrando um item para uma lista vinculada compartilhada, sempre há uma gravação envolvida que notifica outros threads de que a memória agora está disponível para eles. Embora seu código tenha a propriedade da memória, ele provavelmente leu ou gravou nela, e é muito importante que essas leituras e gravações sejam executadas antes de liberar a propriedade. Uma barreira de gravação e liberação garante isso.

É mais simples pensar em barreiras de leitura/aquisição e de gravação/liberação como operações únicas. No entanto, às vezes eles precisam ser construídos a partir de duas partes: uma leitura ou gravação e uma barreira que não permite que leituras ou gravações se movam por ela. Nesse caso, colocar uma barreira é crítico. Para uma barreira de leitura/aquisição, a leitura do sinalizador vem primeiro, depois a barreira e, em seguida, as leituras e gravações dos dados compartilhados. Para uma barreira de gravação/liberação, as leituras e gravações dos dados compartilhados vêm primeiro, depois a barreira e, em seguida, a gravação do sinalizador.

// Read that acquires the data.
if( g_flag )
{
    // Guarantee that the read of the flag executes before
    // all reads and writes that follow in program order.
    BarrierOfSomeSort();

    // Now we can read and write the shared data.
    int localVariable = sharedData.y;
    sharedData.x = 0;

    // Guarantee that the write to the flag executes after all
    // reads and writes that precede it in program order.
    BarrierOfSomeSort();
    
    // Write that releases the data.
    g_flag = false;
}

A única diferença entre uma leitura/aquisição e uma gravação/liberação é a localização da barreira de memória. Uma leitura/aquisição tem a barreira após a operação de bloqueio e uma versão de gravação tem a barreira antes. Em ambos os casos, a barreira está entre as referências à memória bloqueada e as referências ao bloqueio.

Para entender por que as barreiras são necessárias tanto na aquisição quanto na liberação de dados, é melhor (e mais preciso) pensar nessas barreiras como uma garantia da sincronização com a memória compartilhada, não com outros processadores. Se um processador usar uma versão de gravação para liberar uma estrutura de dados para a memória compartilhada e outro processador usar uma aquisição de leitura para obter acesso a essa estrutura de dados da memória compartilhada, o código funcionará corretamente. Se um dos processadores não usar a barreira apropriada, o compartilhamento de dados poderá falhar.

Usar a barreira certa para evitar a reordenação do compilador e da CPU para sua plataforma é fundamental.

Uma das vantagens de usar os primitivos de sincronização fornecidos pelo sistema operacional é que todos eles incluem as barreiras de memória apropriadas.

Impedimento da reordenação do compilador

O trabalho de um compilador é otimizar agressivamente seu código para melhorar o desempenho. Isso inclui reorganizar as instruções onde quer que seja útil e sem mudar o comportamento. Como o padrão C++ nunca menciona multithreading e como o compilador não sabe qual código precisa ser thread-safe, o compilador pressupõe que seu código é single-threaded ao decidir quais reorganizações ele pode fazer com segurança. Portanto, você precisa informar ao compilador quando ele não tem permissão para reordenar leituras e gravações.

Com o Visual C++, você pode evitar a reordenação do compilador usando a função intrínseca do compilador _ReadWriteBarrier. Quando você insere _ReadWriteBarrier em seu código, o compilador não moverá leituras e gravações entre ele.

#if _MSC_VER < 1400
    // With VC++ 2003 you need to declare _ReadWriteBarrier
    extern "C" void _ReadWriteBarrier();
#else
    // With VC++ 2005 you can get the declaration from intrin.h
#include <intrin.h>
#endif
// Tell the compiler that this is an intrinsic, not a function.
#pragma intrinsic(_ReadWriteBarrier)

// Create a new sprite by filling in a previously empty entry.
g_sprites[nextSprite].x = x;
g_sprites[nextSprite].y = y;
// Write-release, barrier followed by write.
// Guarantee that the compiler leaves the write to the flag
// after all reads and writes that precede it in program order.
_ReadWriteBarrier();
g_sprites[nextSprite].alive = true;

No código a seguir, outro thread lê a partir da matriz de sprite:

// Draw all sprites.
for( int i = 0; i < numSprites; ++i )
{

    // Read-acquire, read followed by barrier.
    if( g_sprites[nextSprite].alive )
    {
    
        // Guarantee that the compiler leaves the read of the flag
        // before all reads and writes that follow in program order.
        _ReadWriteBarrier();
        DrawSprite( g_sprites[nextSprite].x,
                g_sprites[nextSprite].y );
    }
}

É importante entender que _ReadWriteBarrier não insere instruções adicionais e não impede que a CPU reorganize leituras e gravações, apenas impede que o compilador as reorganize. Portanto, _ReadWriteBarrier é suficiente quando você implementa uma barreira de liberação de gravação em x86 e x64 (porque x86 e x64 não reordenam gravações e uma gravação normal é suficiente para liberar um bloqueio), mas na maioria dos outros casos, também é necessário impedir que a CPU reordene leituras e gravações.

Você também pode usar _ReadWriteBarrier ao gravar em memória combinada de gravação não armazenável em cache para evitar a reordenação de gravações. Nesse caso _ReadWriteBarrier ajuda a melhorar o desempenho, garantindo que as gravações ocorram na ordem linear preferida do processador.

Também é possível usar os intrínsecos _ReadBarrier e _WriteBarrier para um controle mais preciso da reordenação do compilador. O compilador não moverá leituras entre um _ReadBarrier e não moverá gravações entre um _WriteBarrier.

Impedimento da reordenação da CPU

A reordenação da CPU é mais sutil do que a reordenação do compilador. Você nunca consegue ver isso acontecer diretamente, você apenas vê bugs inexplicáveis. Para evitar a reordenação da CPU de leituras e gravações, você precisa usar instruções de barreira de memória em alguns processadores. O nome para todos os fins de uma instrução de barreira de memória, no Xbox 360 e no Windows, é MemoryBarrier. Essa macro é implementada de forma apropriada para cada plataforma.

No Xbox 360, MemoryBarrier é definido como lwsync (sincronização leve), também disponível por meio do intrínseco __lwsync, que é definido em ppcintrinsics.h. __lwsync também serve como uma barreira de memória do compilador, impedindo a reorganização de leituras e gravações pelo compilador.

A instrução lwsync é uma barreira de memória no Xbox 360 que sincroniza um núcleo de processador com o cache L2. Ele garante que todas as gravações antes do lwsync cheguem ao cache L2 antes de qualquer gravação que se seguir. Ele também garante que todas as leituras que seguem lwsync não obtenham dados mais antigos de L2 do que as leituras anteriores. O único tipo de reordenação que ele não impede é uma leitura que se move à frente de uma gravação para um endereço diferente. Assim, o lwsync impõe a ordenação de memória que corresponde à ordenação de memória padrão em processadores x86 e x64. Para obter a ordenação de memória completa, é necessária a instrução de sincronização mais cara (também conhecida como sincronização pesada), mas na maioria dos casos, isso não é necessário. As opções de reordenação de memória no Xbox 360 são mostradas na tabela a seguir.

Reordenação do Xbox 360 Nenhuma sincronização lwsync sync
Leituras se movem à frente das leituras Sim Não No
Gravações se movem à frente das gravações Sim Não No
Gravações se movem antes das leituras Sim Não No
As leituras se movem à frente das gravações Sim Sim No

 

O PowerPC também possui as instruções de sincronização isync e eieio (que são usadas para controlar a reordenação para memória inibida por cache). Essas instruções de sincronização não devem ser necessárias para fins normais de sincronização.

No Windows, MemoryBarrier é definido em Winnt.h e fornece uma instrução de barreira de memória diferente, dependendo se você está compilando para x86 ou x64. A instrução de barreira de memória serve como uma barreira completa, impedindo toda a reordenação de leituras e gravações através da barreira. Assim, o MemoryBarrier no Windows oferece uma garantia de reordenação mais forte do que no Xbox 360.

No Xbox 360 e em muitas outras CPUs, há uma maneira adicional de evitar a reordenação de leitura pela CPU. Se você ler um ponteiro e usá-lo para carregar outros dados, a CPU garantirá que as leituras do ponteiro não sejam mais antigas do que a leitura do ponteiro. Se o sinalizador de bloqueio for um ponteiro e se todas as leituras de dados compartilhados estiverem fora do ponteiro, o MemoryBarrier poderá ser omitido, para uma economia de desempenho modesta.

Data* localPointer = g_sharedPointer;
if( localPointer )
{
    // No import barrier is needed--all reads off of localPointer
    // are guaranteed to not be reordered past the read of
    // localPointer.
    int localVariable = localPointer->y;
    // A memory barrier is needed to stop the read of g_global
    // from being speculatively moved ahead of the read of
    // g_sharedPointer.
    int localVariable2 = g_global;
}

A instrução MemoryBarrier impede apenas a reordenação de leituras e gravações na memória armazenável em cache. Se você alocar memória como PAGE_NOCACHE ou PAGE_WRITECOMBINE, uma técnica comum para autores de driver de dispositivo e para desenvolvedores de jogos no Xbox 360, o MemoryBarrier não terá efeito sobre os acessos a essa memória. A maioria dos desenvolvedores não precisa de sincronização de memória não armazenável em cache. Isso está além do escopo deste artigo.

Funções interligadas e reordenação da CPU

Às vezes, a leitura ou gravação que adquire ou libera um recurso é feita usando uma das funções InterlockedXxx. No Windows, isso simplifica as coisas, porque nele, as funções InterlockedXxx são todas barreiras de memória completas. Eles efetivamente têm uma barreira de memória da CPU antes e depois deles, o que significa que eles são uma barreira completa de leitura/aquisição ou de gravação/liberação por si só.

No Xbox 360, as funções InterlockedXxx não contêm barreiras de memória da CPU. Eles impedem a reordenação do compilador de leituras e gravações, mas não a reordenação da CPU. Portanto, na maioria dos casos, ao usar as funções InterlockedXxx no Xbox 360, você deve precedê-las ou segui-las com um __lwsync, para torná-las uma barreira de leitura/aquisição ou gravação/liberação. Por conveniência e para facilitar a leitura, existem versões Acquire e Release de muitas das funções InterlockedXxx. Eles vêm com uma barreira de memória embutida. Por exemplo, InterlockedIncrementAcquire faz um incremento intertravado seguido por uma barreira de memória __lwsync para fornecer a funcionalidade completa de leitura/aquisição.

É recomendável que você use as versões Acquire e Release das funções InterlockedXxx (a maioria das quais também está disponível no Windows, sem prejudicar o desempenho) para tornar sua intenção mais óbvia e facilitar a colocação das instruções de barreira de memória no local correto. Qualquer uso de InterlockedXxx no Xbox 360 sem uma barreira de memória deve ser examinada com muito cuidado, pois geralmente é um bug.

Este exemplo demonstra como um thread pode passar tarefas ou outros dados para outro thread usando as versões Acquire e Release das funções InterlockedXxxSList. As funções InterlockedXxxSList são uma família de funções para manter uma lista vinculada simples, compartilhada e sem bloqueio. Observe que as variantes de aquisição e liberação dessas funções não estão disponíveis no Windows, mas as versões regulares dessas funções são uma barreira de memória completa no Windows.

// Declarations for the Task class go here.

// Add a new task to the list using lockless programming.
void AddTask( DWORD ID, DWORD data )
{
    Task* newItem = new Task( ID, data );
    InterlockedPushEntrySListRelease( g_taskList, newItem );
}

// Remove a task from the list, using lockless programming.
// This will return NULL if there are no items in the list.
Task* GetTask()
{
    Task* result = (Task*)
        InterlockedPopEntrySListAcquire( g_taskList );
    return result;
}

Variáveis voláteis e reordenação

O padrão C++ diz que as leituras de variáveis voláteis não podem ser armazenadas em cache, as gravações voláteis não podem ser atrasadas e as leituras e gravações voláteis não podem ser movidas umas sobre as outras. Isso é suficiente para se comunicar com dispositivos de hardware, que é a finalidade da palavra chave volatile no padrão C++.

No entanto, as garantias do padrão não são suficientes para o uso de voláteis para multithreading. O padrão C++ não impede que o compilador reordene leituras e gravações não voláteis em relação a leituras e gravações voláteis e não diz nada sobre como impedir a reordenação da CPU.

O Visual C++ 2005 vai além do C++ padrão para definir uma semântica multithreading favorável ao para acesso a variáveis voláteis. A partir do Visual C++ 2005, as leituras de variáveis voláteis são definidas para ter semântica de leitura/aquisição e as gravações em variáveis voláteis são definidas para ter semântica de gravação/liberação. Isso significa que o compilador não reorganizará as leituras e gravações que passarem por eles e, no Windows, garantirá que a CPU também não o faça.

É importante entender que essas novas garantias se aplicam apenas ao Visual C++ 2005 e versões futuras do Visual C++. Os compiladores de outros fornecedores geralmente implementam semânticas diferentes, sem as garantias extras do Visual C++ 2005. Além disso, no Xbox 360, o compilador não insere nenhuma instrução para impedir que a CPU reordene leituras e gravações.

Exemplo de um pipe de dados sem bloqueio

Um pipe é uma construção que permite que um ou mais threads gravem dados que são lidos por outros threads. Uma versão sem trava de um pipe pode ser uma maneira elegante e eficiente de passar o trabalho de thread para thread. O SDK do DirectX fornece LockFreePipe, um pipe sem bloqueio de leitor e gravador único que está disponível em DXUTLockFreePipe.h. O mesmo LockFreePipe está disponível no SDK do Xbox 360 em AtgLockFreePipe.h.

O LockFreePipe pode ser usado quando dois threads têm uma relação produtor/consumidor. O thread produtor pode gravar dados no pipe para que o thread do consumidor processe em uma data posterior, sem nunca bloquear. Se o pipe for preenchido, as gravações falharão e o thread produtor terá que tentar novamente mais tarde, mas isso só acontecerá se o thread produtor estiver à frente. Se o pipe esvaziar, as leituras falharão e o thread consumidor terá que tentar novamente mais tarde, mas isso só acontecerá se não houver trabalho para o thread consumidor fazer. Se os dois threads estiverem bem equilibrados e o pipe for grande o suficiente, permitirá que eles passem dados sem problemas, sem atrasos ou bloqueios.

Desempenho do Xbox 360

O desempenho das instruções e funções de sincronização no Xbox 360 varia de acordo com o outro código que estiver sendo executado. A aquisição de bloqueios levará muito mais tempo se outro thread possuir o bloqueio no momento. O InterlockedIncrement e as operações de seção crítica levarão muito mais tempo se outros threads estiverem gravando na mesma linha de cache. O conteúdo das filas de armazenamento também pode afetar o desempenho. Portanto, todos esses números são apenas aproximações, geradas a partir de testes muito simples:

  • lwsync foi medido como levando de 33 a 48 ciclos.
  • InterlockedIncrement foi medido como levando de 225‑260 ciclos.
  • A aquisição ou liberação de uma seção crítica foi medida como levando cerca de 345 ciclos.
  • A aquisição ou liberação de um mutex foi medida como levando cerca de 2350 ciclos.

Desempenho do Windows

O desempenho das instruções e funções de sincronização no Windows varia muito, dependendo do tipo e da configuração do processador e do outro código que estiver em execução. Os sistemas multi-core e multi-socket geralmente levam mais tempo para executar instruções de sincronização, e a aquisição de bloqueios leva muito mais tempo se outro thread atualmente possui o bloqueio.

No entanto, mesmo algumas medições geradas a partir de testes muito simples são úteis:

  • O MemoryBarrier foi medido como levando de 20 a 90 ciclos.
  • InterlockedIncrement foi medido como levando de 36‑90 ciclos.
  • A aquisição ou liberação de uma seção crítica foi medida como levando cerca de 40 a 100 ciclos.
  • A aquisição ou liberação de um mutex foi medida como levando cerca de 750‑2500 ciclos.

Esses testes foram feitos no Windows XP em vários processadores diferentes. Os tempos curtos estavam em uma máquina de processador único e os tempos mais longos estavam em uma máquina de vários processadores.

Embora adquirir e liberar bloqueios seja mais caro do que usar a programação sem bloqueio, é ainda melhor compartilhar dados com menos frequência, evitando assim o custo por completo.

Pensamentos de desempenho

A aquisição ou liberação de uma seção crítica consiste em uma barreira de memória, uma operação InterlockedXxx e algumas verificações extras para lidar com a recursão e voltar para um mutex, se necessário. Você deve ter cuidado ao implementar sua própria seção crítica, porque girar em um loop esperando que um bloqueio seja liberado sem voltar para um mutex, pode desperdiçar um desempenho considerável. Para seções críticas que são fortemente contestadas, mas não mantidas por muito tempo, você deve considerar o uso de InitializeCriticalSectionAndSpinCount para que o sistema operacional gire por um tempo aguardando que a seção crítica esteja disponível, em vez de adiar imediatamente para um mutex se a seção crítica for de propriedade quando você tentar adquiri-la. Para identificar seções críticas que podem se beneficiar de uma contagem de rotação, é necessário medir a duração da espera típica por um bloqueio específico.

Se um heap compartilhado for usado para alocações de memória, que é o comportamento padrão, toda alocação e liberação de memória irá envolver a aquisição de um bloqueio. À medida que o número de threads e o número de alocações aumentam, o desempenho diminui e eventualmente começa a diminuir. O uso de heaps por thread ou a redução do número de alocações pode evitar esse gargalo de bloqueio.

Se um thread estiver gerando dados e outro thread estiver consumindo dados, eles podem acabar compartilhando dados com frequência. Isso pode acontecer se um thread estiver carregando recursos e outro thread estiver renderizando a cena. Se o thread de renderização fizer referência aos dados compartilhados em cada chamada do desenho, a sobrecarga de bloqueio será alta. Um desempenho muito melhor pode ser obtido se cada thread tiver estruturas de dados privadas que são sincronizadas uma vez por quadro ou menos.

Não há garantia de que os algoritmos sem bloqueio sejam mais rápidos do que os algoritmos que usam bloqueios. Você deve verificar se os bloqueios estão realmente causando problemas antes de tentar evitá-los e deve medir se o código sem bloqueio realmente melhora o desempenho.

Resumo das diferenças de plataforma

  • As funções InterlockedXxx impedem a reordenação de gravação/liberação da CPU no Windows, mas não no Xbox 360.
  • A leitura e a gravação de variáveis voláteis usando o Visual Studio C++ 2005 impedem a reordenação de gravação/liberação da CPU no Windows, mas no Xbox 360, ela impede apenas a reordenação de leitura/aquisição do compilador.
  • As gravações são reordenadas no Xbox 360, mas não em x86 ou x64.
  • As leituras são reordenadas no Xbox 360, mas no x86 ou x64 elas são reordenadas apenas em relação às gravações e somente se as leituras e gravações forem direcionadas a locais diferentes.

Recomendações

  • Use bloqueios quando possível, pois são mais fáceis de usar corretamente.
  • Evite bloquear com muita frequência, para que os custos de bloqueio não se tornem significativos.
  • Evite segurar bloqueios por muito tempo, a fim de evitar paradas longas.
  • Use a programação sem bloqueio quando apropriado, mas certifique-se de que os ganhos justifiquem a complexidade.
  • Use programação sem bloqueio ou bloqueios de rotação em situações em que outros bloqueios são proibidos, como ao compartilhar dados entre chamadas de procedimento adiado e código normal.
  • Use apenas algoritmos de programação lockless padrão que tenham sido comprovadamente corretos.
  • Ao fazer a programação sem bloqueio, certifique-se de usar variáveis de sinalizador voláteis e instruções de barreira de memória conforme necessário.
  • Ao usar o InterlockedXxx no Xbox 360, use as variantes Acquire e Release.

Referências