Pergunta

O que você quer dizer por Atômica instruções?

Como faz o seguinte se tornar Atômica?

TestAndSet

int TestAndSet(int *x){
   register int temp = *x;
   *x = 1;
   return temp;
}

A partir de um software de perspectiva, se não quiser usar não-bloqueio primitivos de sincronização, como se pode garantir a Atomicidade de instrução?é possível apenas no Hardware, ou algum conjunto de nível de diretiva de otimização podem ser usadas?

Foi útil?

Solução

Algumas instruções da máquina são intrinsecamente atômicas - por exemplo, ler e escrever valores adequadamente alinhados do tamanho da palavra do processador nativo é atômico em muitas arquiteturas.

Isso significa que o hardware interrompe, outros processadores e hiper-threads não podem interromper a leitura ou armazenar e ler ou escrever um valor parcial no mesmo local.

Coisas mais complicadas, como ler e escrever em conjunto atomicamente, podem ser alcançadas por instruções explícitas da máquina atômica, por exemplo, bloqueio cmpxchg no x86.

O bloqueio e outras construções de alto nível são construídas sobre essas primitivas atômicas, que normalmente protegem apenas uma única palavra do processador.

Alguns algoritmos simultâneos inteligentes podem ser construídos usando apenas a leitura e a escrita de ponteiros, por exemplo, em listas vinculadas compartilhadas entre um único leitor e escritor, ou com esforço, vários leitores e escritores.

Outras dicas

Atomic vem do grego ἄτομος (Atomos), que significa "indivisível". (Advertência: Eu não falo grego, então talvez seja realmente outra coisa, mas a maioria dos falantes de inglês citando etimologias interpreta dessa maneira. :-)

Na computação, isso significa que a operação, bem, acontece. Não há nenhum estado intermediário que seja visível antes de concluir. Portanto, se a sua CPU for interrompida em serviço de hardware (IRQ) ou se outra CPU estiver lendo a mesma memória, ela não afeta o resultado e essas outras operações o observarão como concluídas ou não.

Como exemplo ... digamos que você queria definir uma variável para algo, mas apenas se ela não tivesse sido definida antes. Você pode estar inclinado a fazer isso:

if (foo == 0)
{
   foo = some_function();
}

Mas e se isso for executado em paralelo? Pode ser que o programa busque foo, veja como zero, enquanto isso, o Thread 2 aparece e faz a mesma coisa e define o valor para algo. De volta ao tópico original, o código ainda pensa foo é zero e a variável é atribuída duas vezes.

Para casos como esse, a CPU fornece algumas instruções que podem fazer a comparação e a atribuição condicional como uma entidade atômica. Portanto, teste e conjunto, comparação e troca e reticulados em carga/lojas-condicionais. Você pode usá-los para implementar bloqueios (seu sistema operacional e sua biblioteca C fez isso.) Ou você pode escrever algoritmos únicos que dependem dos primitivos para fazer algo. (Há coisas legais a serem feitas aqui, mas a maioria dos meros mortais evita isso por medo de errar.)

Atomicidade é um conceito -chave quando você tem qualquer forma de processamento paralelo (incluindo diferentes aplicativos que cooperam ou compartilham dados) que inclui recursos compartilhados.

O problema é bem ilustrado com um exemplo. Digamos que você tenha dois programas que desejam criar um arquivo, mas apenas se o arquivo ainda não existir. Qualquer um dos dois programas pode criar o arquivo a qualquer momento.

Se você o faz (eu usarei C, pois é o que está no seu exemplo):

 ...
 f = fopen ("SYNCFILE","r");
 if (f == NULL) {
   f = fopen ("SYNCFILE","w");
 }
 ...

Você não pode ter certeza de que o outro programa não criou o arquivo entre o seu Open for Read e o Open for Write.

Não há como fazer isso por conta própria, você precisa de ajuda do sistema operacional, que geralmente fornece primitivas de sincronização para esse fim, ou outro mecanismo que é garantido para ser atômico (por exemplo, um banco de dados relacional em que a operação de bloqueio é atômica, ou um mecanismo de nível mais baixo, como os processadores "testam e definem as instruções).

Abaixo estão algumas das minhas notas na Atomicidade que podem ajudar você a entender o significado.As notas são de fontes listadas no final e eu recomendo a leitura de alguns deles, se você precisar de uma explicação mais completa, em vez de ponto-formulário de balas, como eu tenho.Por favor apontar os erros para que eu possa corrigi-los.

Definição :

  • Do grego que significa "não divisível em partes menores"
  • Um "atômico" a operação é sempre observado a ser feito ou não feito, mas nunca a meio caminho feito.
  • Uma operação atômica deve ser realizado inteiramente ou não realizadas em tudo.
  • Em multi-threaded cenários, uma variável que vai de unmutated para mutantes diretamente, sem a "meio caminho mutantes" valores

Exemplo 1 :Operações Atômicas

  • Considere os seguintes números inteiros usado por threads diferentes : 

     int X = 2;
 int Y = 1;
 int Z = 0;

 Z = X;  //Thread 1

 X = Y;  //Thread 2

  • No exemplo acima, dois threads fazer uso de X, Y e Z

  • Cada leitura e escrita são atômica
  • As linhas vão corrida :
    • Se o thread 1 wins e, em seguida, Z = 2
    • Se o thread 2 vitórias, então Z=1
    • Z vai definitivamente vai ser um desses dois valores

Exemplo 2 :Não-Operações Atômicas :++/-- Operações

  • Considere o incremento/decremento expressões :

    i++;  //increment
i--;  //decrement

  • As operações de traduzir para :

    1. Leitura i
    2. Aumentar/diminuir o valor da leitura
    3. Escreva o novo valor de volta para eu
  • As operações são compostos, cada um, de 3 de operações atômicas, e não são atômico-se
  • Duas tentativas de incremento eu em segmentos separados poderia se intercalam, de modo que um dos incrementos é perdida

Exemplo 3 - Não-Operações Atômicas :Valores superiores a 4 Bytes

  • Considere o seguinte imutável struct :
  struct MyLong
   {
       public readonly int low;
       public readonly int high;

       public MyLong(int low, int high)
       {
           this.low = low;
           this.high = high;
       }
   }

  • Podemos criar campos com valores específicos do tipo MyLong :

    MyLong X = new MyLong(0xAAAA, 0xAAAA);   
MyLong Y = new MyLong(0xBBBB, 0xBBBB);     
MyLong Z = new MyLong(0xCCCC, 0xCCCC);

  • Podemos modificar nossos campos em threads separados sem a segurança do thread :

    X = Y; //Thread 1                                  
Y = X; //Thread 2

  • Em .NET, quando a cópia de um tipo de valor, o CLR não chamar um construtor - ele move os bytes uma operação atômica de cada vez

  • Devido a isso, as operações em dois segmentos são agora quatro operações atômicas
  • Se não há thread de segurança imposta, os dados podem ser corrompidos

  • Considere a seguinte ordem de execução das operações de :

    X.low = Y.low;      //Thread 1 - X = 0xAAAABBBB            
Y.low = Z.low;      //Thread 2 - Y = 0xCCCCBBBB              
Y.high = Z.high;    //Thread 2 - Y = 0xCCCCCCCC             
X.high = Y.high;    //Thread 1 - X = 0xCCCCBBBB   <-- corrupt value for X

  • Leitura e escrita de valores superiores a 32-bits em vários segmentos em um sistema operacional de 32 bits, sem a adição de algum tipo de bloqueio para tornar a operação atômica é provável resultar em dados corrompidos como acima

As Operações Do Processador

  • Em todos os processadores modernos, pode-se assumir que lê e escreve de naturalmente alinhado tipos nativos são atômica desde que :

    • 1 :O barramento de memória é pelo menos tão grande como o tipo a ser lido ou escrito
    • 2 :A CPU lê e escreve esses tipos em um único barramento de transação, tornando impossível para outros segmentos para vê-los em um semi-estado concluído

  • No x86 e X64 não há nenhuma garantia de que lê e grava maior do que oito bytes são atômica

  • Os fabricantes de processadores definir as operações atômicas para cada processador em um Manual do Desenvolvedor de Software
  • Em processadores único / single-core e sistemas é possível utilizar o padrão de técnicas de bloqueio para impedir CPU instruções de ser interrompido, mas isso pode ser ineficiente
  • A desabilitação de interrupções é outra solução mais eficiente, se possível
  • No multiprocessador / sistemas com vários núcleos ainda é possível usar os bloqueios, mas apenas usando uma única instrução ou desabilitação de interrupções não garante atômica de acesso
  • Atomicidade pode ser alcançado, garantindo que as instruções utilizadas afirmar o 'LOCK' do sinal no barramento para evitar que outros processadores no sistema de acessar a memória ao mesmo tempo

Diferenças De Linguagem

C#

  • C# garante que as operações em qualquer built-in tipo de valor que ocupa 4 bytes são atômica
  • Operações sobre tipos de valor que tome mais de quatro bytes (duplo, long, etc.) não são garantidos para ser atômica
  • O CLI garante que lê e escreve de variáveis do tipo de valor que são o tamanho (ou menor) do que o processador natural do tamanho do ponteiro de são atômica
    • Ex - execução C# em um sistema operacional de 64 bits em uma versão de 64 bits do CLR executa leituras e gravações de 64 bits duplos e números inteiros longos atomicamente
  • A criação de operações atômicas :
    • .NET provodes a Classe Interlocked como parte do Sistema.Rosqueamento de espaço de nomes
    • A Classe Interlocked fornece operações atômicas, tais como o incremento, comparar, exchange, etc. 
using System.Threading;             

int unsafeCount;                          
int safeCount;                           

unsafeCount++;                              
Interlocked.Increment(ref safeCount);

C++

  • Padrão de C++ não garante atômica comportamento
  • Todos C / C++ operações são consideradas não-atômica, a menos que especificado de outra forma pelo compilador ou fornecedor de hardware - incluindo número inteiro de 32 bits atribuição
  • A criação de operações atômicas :
    • O C++ 11 de simultaneidade biblioteca inclui - Operações Atômicas (Biblioteca)
    • O Atomic biblioteca fornece tipos atômicos como uma classe de modelo para usar com qualquer tipo que quiser
    • Operações atômicas são os tipos de átomos e, portanto, thread-safe

estrutura AtomicCounter
{ 

   std::atomic< int> value;   

   void increment(){                                    
       ++value;                                
   }           

   void decrement(){                                         
       --value;                                                 
   }

   int get(){                                             
       return value.load();                                    
   }

}

Java

  • Java garante que as operações em qualquer built-in tipo de valor que ocupa 4 bytes são atômica
  • Atribuições voláteis longas e duplas também são garantidos para ser atômica
  • Java fornece um pequeno conjunto de classes que suportam sem bloqueio thread-safe de programação em um único variáveis através de java.util.simultâneas.atomic
  • Isso fornece atômica sem bloqueio de operações com base no baixo nível atômico hardware primitivos como comparar-e-swap (CAS) - também chamado de comparar e definir :
    • CAS formulário - boolean compareAndSet(expectedValue, updateValue );
      • Este método atomicamente define uma variável para o updateValue se realiza atualmente o expectedValue - relatório true em caso de sucesso
import java.util.concurrent.atomic.AtomicInteger;

public class Counter
{
     private AtomicInteger value= new AtomicInteger();

     public int increment(){
         return value.incrementAndGet();  
     }

     public int getValue(){
         return value.get();
     }
}

Fontes
http://www.evernote.com/shard/s10/sh/c2735e95-85ae-4d8c-a615-52aadc305335/99de177ac05dc8635fb42e4e6121f1d2

Atomicidade só pode ser garantida pelo sistema operacional. O sistema operacional usa os recursos do processador subjacente para conseguir isso.

Portanto, criar sua própria função de teste de teste é impossível. (Embora eu não tenha certeza se alguém poderia usar um snippet ASM embutido e usar o Mnemonic TestAndSet diretamente (pode ser que essa declaração só pode ser feita com os privilégios do sistema operacional))

EDIT: De acordo com os comentários abaixo deste post, é possível tornar possível sua própria função 'BitteStandSet' usando uma diretiva ASM (na Intel x86). No entanto, se esses truques também funcionarem em outros processadores não for claro.

Eu mantenho o meu ponto: se você quiser fazer coisas atmosféricas, use as funções do sistema operacional e não faça você mesmo

Licenciado em: CC-BY-SA com atribuição
Não afiliado a StackOverflow
scroll top