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

Question

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

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

TestAndSet

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

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

Answer 1

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

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

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

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

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

Answer 2

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

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

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

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

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

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

Answer 3

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

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

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

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

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

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

Answer 4

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

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

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

Пример 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 атомарных операций, и сами по себе не являются атомарными
• Две попытки увеличить 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 предоставляет блокированный класс как часть System.Threading namespace
  • Класс блокировки обеспечивает элементарные операции, такие как приращение, сравнение, обмен и т. Д.

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

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

Answer 5

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

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

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

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