Атомная Инструкция

Что вы подразумеваете под атомными инструкциями?

Как следующее становится Атомным?

TestAndSet

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

С точки зрения программного обеспечения, если кто-то не хочет использовать неблокирующие примитивы синхронизации, как можно обеспечить атомарность инструкции? это возможно только на оборудовании или может быть использована какая-то оптимизация директивы на уровне сборки?

Источник

5 ответов

Решение

Некоторые машинные инструкции являются по сути атомарными - например, чтение и запись правильно выровненных значений размера слова собственного процессора является атомарным на многих архитектурах.

Это означает, что аппаратные прерывания, другие процессоры и гиперпотоки не могут прерывать чтение или сохранение и чтение или запись частичного значения в то же место.

Более сложные вещи, такие как атомарное чтение и запись вместе, могут быть достигнуты с помощью явных атомарных машинных инструкций, например, LOCK CMPXCHG на x86.

Блокировка и другие высокоуровневые конструкции построены на этих элементарных примитивах, которые обычно защищают только одно слово процессора.

Некоторые умные параллельные алгоритмы могут быть построены, используя только чтение и запись указателей, например, в связанных списках, совместно используемых одним читателем и писателем, или с усилием, несколькими читателями и писателями.

Источник

Ниже приведены некоторые из моих заметок об атомарности, которые могут помочь вам понять смысл. Примечания взяты из источников, перечисленных в конце, и я рекомендую прочитать некоторые из них, если вам нужно более подробное объяснение, а не точечные маркеры, как у меня. Пожалуйста, укажите на любые ошибки, чтобы я мог их исправить.

Определение:

  • От греческого значения "не делится на более мелкие части"
  • "Атомная" операция всегда выполняется или не выполняется, но никогда не выполняется наполовину.
  • Атомная операция должна выполняться полностью или не выполняться вообще.
  • В многопоточных сценариях переменная переходит от немутированного к мутированному напрямую, без значений "наполовину мутированных"

Пример 1: атомарные операции

  • Рассмотрим следующие целые числа, используемые разными потоками:

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

 Z = X;  //Thread 1

 X = Y;  //Thread 2

  • В приведенном выше примере два потока используют X, Y и Z

  • Каждое чтение и запись являются атомарными
  • Потоки будут гоняться:
    • Если победит нить 1, то Z = 2
    • Если победит нить 2, то Z = 1
    • Z определенно будет одним из этих двух значений

Пример 2: Неатомарные операции: ++/- Операции

  • Рассмотрим выражения увеличения / уменьшения:

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

  • Операции переводятся на:

    1. Читать я
    2. Увеличить / уменьшить значение чтения
    3. Напишите новое значение обратно мне
  • Каждая из этих операций состоит из трех атомарных операций, а не сами по себе
  • Две попытки увеличить i в отдельных потоках могут чередоваться так, что один из приращений будет потерян

Пример 3 - Неатомарные операции: значения больше, чем 4 байта

  • Рассмотрим следующую неизменную структуру:
  struct MyLong
   {
       public readonly int low;
       public readonly int high;

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

  • Мы создаем поля с конкретными значениями типа MyLong:

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

  • Мы изменяем наши поля в отдельных потоках без безопасности потока:

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

  • В.NET при копировании типа значения CLR не вызывает конструктор - он перемещает байты по одной атомарной операции за раз

  • Из-за этого операции в двух потоках теперь являются четырьмя атомарными операциями.
  • Если не обеспечена безопасность потоков, данные могут быть повреждены.

  • Рассмотрим следующий порядок выполнения операций:

    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

  • Чтение и запись значений, превышающих 32 бита в нескольких потоках в 32-битной операционной системе, без добавления какой-либо блокировки, чтобы сделать атомарную операцию, может привести к повреждению данных, как указано выше.

Процессор Операции

  • На всех современных процессорах можно предположить, что чтение и запись естественно выровненных собственных типов являются атомарными, если:

    • 1: шина памяти, по крайней мере, такая же широкая, как и тип читаемого или записываемого
    • 2: ЦП читает и записывает эти типы в одной транзакции шины, что не позволяет другим потокам видеть их в полузаполненном состоянии

  • На x86 и X64 нет гарантии, что чтение и запись больше восьми байтов являются атомарными

  • Поставщики процессоров определяют элементарные операции для каждого процессора в Руководстве разработчика программного обеспечения.
  • В одноядерных / одноядерных системах можно использовать стандартные методы блокировки для предотвращения прерывания инструкций процессора, но это может быть неэффективно
  • Отключение прерываний - еще одно более эффективное решение, если это возможно
  • В многопроцессорных / многоядерных системах все еще можно использовать блокировки, но простое использование одной команды или отключение прерываний не гарантирует атомарный доступ
  • Атомность может быть достигнута, гарантируя, что используемые инструкции устанавливают сигнал "LOCK" на шине, чтобы предотвратить одновременный доступ к памяти других процессоров в системе

Языковые различия

C#

  • C# гарантирует, что операции с любым встроенным типом значения, занимающим до 4 байтов, являются атомарными
  • Операции над типами значений, которые занимают более четырех байтов (двойной, длинный и т. Д.), Не гарантируются как атомарные
  • CLI гарантирует, что чтение и запись переменных типа значения, которые имеют размер (или меньше) естественного размера указателя процессора, являются атомарными
    • Например - запуск C# в 64-разрядной ОС в 64-разрядной версии CLR выполняет чтение и запись 64-разрядных двойных и длинных целых чисел атомарно
  • Создание атомарных операций:
    • .NET предоставляет Interlocked Class как часть пространства имен System.Threading
    • Класс Interlocked обеспечивает элементарные операции, такие как увеличение, сравнение, обмен и т. Д. 
using System.Threading;             

int unsafeCount;                          
int safeCount;                           

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

C++

  • Стандарт C++ не гарантирует атомарного поведения
  • Все операции C / C++ считаются неатомарными, если иное не указано компилятором или поставщиком оборудования, включая 32-разрядное целочисленное присваивание
  • Создание атомарных операций:
    • Библиотека параллелизма C++ 11 включает в себя - Atomic Operations Library ()
    • Библиотека Atomic предоставляет атомарные типы в качестве класса шаблона для использования с любым типом, который вы хотите
    • Операции над атомарными типами являются атомарными и, следовательно, потокобезопасными

struct AtomicCounter
{

   std::atomic< int> value;   

   void increment(){                                    
       ++value;                                
   }           

   void decrement(){                                         
       --value;                                                 
   }

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

}

Джава

  • Java гарантирует, что операции с любым встроенным типом значения, занимающим до 4 байтов, являются атомарными
  • Назначения к волатильным длинным и двойным также гарантированно будут атомарными
  • Java предоставляет небольшой набор классов, которые поддерживают поточно-ориентированное программирование без блокировок для отдельных переменных с помощью java.util.concurrent.atomic
  • Это обеспечивает операции без атомарной блокировки на основе низкоуровневых элементарных аппаратных примитивов, таких как сравнение и замена (CAS) - также называемых сравнением и установкой:
    • CAS форма - логическое сравнение AndSet(Ожидаемое значение, значение обновления);
      • Этот метод атомарно устанавливает переменную в updateValue, если он в настоящее время содержит ожидаемое значение - сообщая об истине в случае успеха
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();
     }
}

источники
http://www.evernote.com/shard/s10/sh/c2735e95-85ae-4d8c-a615-52aadc305335/99de177ac05dc8635fb42e4e6121f1d2

Источник

Атомное происходит от греческого ἄτομος (atomos), что означает "неделимый". (Предостережение: я не говорю по-гречески, так что, возможно, это действительно что-то другое, но большинство англоязычных, ссылаясь на этимологию, интерпретируют это так:-)

В вычислительной технике это означает, что операция, ну, в общем, происходит. Там нет никакого промежуточного состояния, которое видно до его завершения. Таким образом, если ваш ЦП прерывается на служебное оборудование (IRQ) или если другой ЦП читает ту же самую память, это не влияет на результат, и эти другие операции будут считать его завершенным или не запущенным.

В качестве примера... допустим, вы хотели установить переменную в что-то, но только если она не была установлена ​​ранее. Вы можете быть склонны сделать это:

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

Но что, если это будет выполняться параллельно? Может быть, что программа будет получать foo воспринимайте это как ноль, в то время как поток 2 приходит и делает то же самое и устанавливает значение в что-то. Вернувшись в исходную ветку, код все еще думает foo равен нулю, и переменная назначается дважды.

Для подобных случаев CPU предоставляет некоторые инструкции, которые могут выполнять сравнение и условное присвоение как элементарный объект. Следовательно, тестируйте и устанавливайте, сравнивайте и меняйте местами и привязывайте к нагрузке / сохраняйте условия. Вы можете использовать их для реализации блокировок (ваша ОС и ваша библиотека C сделали это.) Или вы можете написать одноразовые алгоритмы, которые полагаются на примитивы, чтобы что-то делать. (Здесь можно сделать что-то классное, но большинство простых смертных избегают этого, опасаясь ошибиться.)

Источник

Атомность является ключевым понятием, когда у вас есть любая форма параллельной обработки (включая различные приложения, взаимодействующие или совместно использующие данные), которая включает в себя общие ресурсы.

Проблема хорошо проиллюстрирована на примере. Допустим, у вас есть две программы, которые хотят создать файл, но только если файл еще не существует. Любая из двух программ может создать файл в любой момент времени.

Если вы это сделаете (я буду использовать C, потому что это то, что в вашем примере):

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

Вы не можете быть уверены, что другая программа не создала файл между открытием для чтения и открытием для записи.

Вы не можете сделать это самостоятельно, вам нужна помощь операционной системы, которая обычно предоставляет для этой цели примитивы синхронизации, или другой механизм, который гарантированно является атомарным (например, реляционная база данных, в которой операция блокировки является атомарной, или механизм более низкого уровня, такой как процессоры "тестируют и устанавливают" инструкции).

Источник

Атомность может быть гарантирована только ОС. ОС использует базовые функции процессора для достижения этой цели.

Поэтому создание собственной функции набора тестов невозможно. (Хотя я не уверен, что можно использовать встроенный фрагмент asm и использовать мнемонику testandset напрямую (возможно, это утверждение может быть сделано только с привилегиями ОС))

РЕДАКТИРОВАТЬ: Согласно комментариям ниже этого поста, возможно создание собственной функции 'bittestandset' с использованием директивы ASM напрямую (на Intel x86). Однако, если эти приемы также работают на других процессорах, неясно.

Я придерживаюсь своей точки зрения: если вы хотите заниматься амбициозными вещами, используйте функции ОС и не делайте это сами

Источник
Другие вопросы по тегам