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

Някои машинни инструкции са присъщо атомарни - например четенето и записването на правилно подравнени стойности на размера на думата на собствения процесор е атомарно на много архитектури.

Това означава, че хардуерните прекъсвания, други процесори и хипернишки не могат да прекъснат четенето или съхраняването и четенето или записването на частична стойност на едно и също място.

По-сложни неща, като четене и писане заедно атомно, могат да бъдат постигнати чрез изрични команди на атомна машина, напр. ЗАКЛЮЧВАНЕ на CMPXCHG на x86.

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

Някои интелигентни паралелни алгоритми могат да бъдат изградени само чрез четене и запис на указатели, напр. в свързани списъци, споделени между един читател и писател, или с усилие, множество читатели и писатели.

Atomic идва от гръцкото ἄτομος (atomos), което означава „неделим“. (Внимание: не говоря гръцки, така че може би наистина е нещо друго, но повечето англоговорящи, цитиращи етимологии, го тълкуват по този начин. :-)

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

Като пример... да кажем, че искате да зададете променлива на нещо, но само ако не е било зададено преди. Може да сте склонни да направите това:

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

Но какво ще стане, ако това се изпълнява паралелно? Възможно е програмата да извлече foo, да го види като нула, междувременно идва нишка 2 и прави същото и задава стойността на нещо. Обратно в оригиналната нишка, кодът все още смята, че foo е нула и променливата се присвоява два пъти.

За случаи като този процесорът предоставя някои инструкции, които могат да направят сравнението и условното присвояване като атомарна единица. Следователно, тестване и настройка, сравняване и размяна и свързано с натоварване/условно съхраняване. Можете да ги използвате за внедряване на заключвания (вашата ОС и вашата C библиотека са направили това.) Или можете да напишете еднократни алгоритми, които разчитат на примитивите, за да направят нещо. (Тук има страхотни неща за правене, но повечето обикновени смъртни избягват това от страх да не сбъркат.)

По-долу са някои от моите бележки за Atomicity, които могат да ви помогнат да разберете значението. Бележките са от източниците, изброени в края, и препоръчвам да прочетете някои от тях, ако имате нужда от по-подробно обяснение, а не от точкови точки, каквито имам аз. Моля, посочете грешки, за да мога да ги коригирам.

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

• От гръцки означава "неделим на по-малки части"
• Една „атомна“ операция винаги се наблюдава дали е извършена или не е извършена, но никога не е наполовина извършена.
• Една атомарна операция трябва да се извърши изцяло или да не се изпълнява изобщо.
• В сценарии с много нишки, променлива преминава от немутирана към мутирала директно, без „половина мутирали“ стойности

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

• Помислете за следните цели числа, използвани от различни нишки:

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

• В горния пример две нишки използват X, Y и Z

• Всяко четене и запис са атомарни
• The threads will race :
  • If thread 1 wins, then Z = 2
  • Ако нишка 2 спечели, тогава Z=1
  • Z определено ще бъде една от тези две стойности

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

• Помислете за изразите за увеличаване/намаляване:

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

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

  1. Read i
  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;
       }
   }

• #P10#

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

• #P11#

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

• В .NET, когато копирате тип стойност, CLR не извиква конструктор - той премества байтовете една атомна операция наведнъж

• Поради това операциите в двете нишки вече са четири атомарни операции
• Ако няма наложена безопасност на нишката, данните могат да бъдат повредени
• #P13#

  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 : The memory bus is at least as wide as the type being read or written
  • 2 : Процесорът чете и записва тези типове в една транзакция на шина, което прави невъзможно другите нишки да ги видят в полузавършено състояние

• При x86 и X64 няма гаранция, че четенията и записите, по-големи от осем байта, са атомни

• Доставчиците на процесори дефинират атомарните операции за всеки процесор в Ръководство за разработчици на софтуер
• В еднопроцесорни / едноядрени системи е възможно да се използват стандартни техники за заключване, за да се предотврати прекъсването на инструкциите на процесора, но това може да е неефективно
• Деактивирането на прекъсвания е друго по-ефективно решение, ако е възможно
• В многопроцесорни / многоядрени системи все още е възможно да се използват ключалки, но само използването на една инструкция или деактивирането на прекъсвания не гарантира атомен достъп
• Атомарността може да бъде постигната, като се гарантира, че използваните инструкции потвърждават сигнала „LOCK“ на шината, за да се предотврати достъп на други процесори в системата до паметта по същото време

Езикови разлики

C#

• C# гарантира, че операциите върху всеки вграден тип стойност, който заема до 4 байта, са атомарни
• Операциите върху типове стойности, които отнемат повече от четири байта (double, long и т.н.), не са гарантирани, че са атомарни
• The CLI guarantees that reads and writes of variables of value type that are the size (or smaller) of the processor's natural pointer size are atomic
  • Ex - running C# on a 64-bit OS in a 64-bit version of the CLR performs reads and writes of 64-bit doubles and long integers atomically
• Creating atomic operations :
  • .NET provodes the Interlocked Class as part of the System.Threading namespace
  • Взаимосвързаният клас предоставя атомарни операции като увеличаване, сравнение, обмен и т.н.

using System.Threading;             

int unsafeCount;                          
int safeCount;                           

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

C++

• C++ стандартът не гарантира атомарно поведение
• Всички C / C++ операции се предполагат като неатомни, освен ако не е посочено друго от компилатора или доставчика на хардуер - включително 32-битово присвояване на цели числа
• Creating atomic operations :
  • The C++ 11 concurrency library includes the - Atomic Operations Library ()
  • Библиотеката Atomic предоставя атомни типове като шаблонен клас, който да използвате с всеки тип, който искате
  • Операциите върху атомарни типове са атомарни и следователно безопасни за нишки

struct AtomicCounter
{

   std::atomic< int> value;   

   void increment(){                                    
       ++value;                                
   }           

   void decrement(){                                         
       --value;                                                 
   }

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

}

Java

• Java гарантира, че операциите върху всеки вграден тип стойност, който заема до 4 байта, са атомарни
• Гарантирано е също така, че присвояванията на volatile longs и doubles са атомарни
• Java предоставя малък инструментариум от класове, които поддържат програмиране с нишка без заключване на единични променливи чрез java.util.concurrent.atomic
• This provides atomic lock-free operations based on low-level atomic hardware primitives such as compare-and-swap (CAS) - also called compare and set :
  • CAS form - boolean compareAndSet(expectedValue, updateValue );
    • This method atomically sets a variable to the updateValue if it currently holds the expectedValue - reporting true on success

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

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

Проблемът е добре илюстриран с пример. Да приемем, че имате две програми, които искат да създадат файл, но само ако файлът вече не съществува. Всяка от двете програми може да създаде файла по всяко време.

Ако го направите (ще използвам C, тъй като това е във вашия пример):

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

не можете да сте сигурни, че другата програма не е създала файла между вашия отворен за четене и вашия отворен за запис.

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

Атомичността може да бъде гарантирана само от ОС. ОС използва основните функции на процесора, за да постигне това.

Така че създаването на ваша собствена функция testandset е невъзможно. (Въпреки че не съм сигурен дали може да се използва вграден asm фрагмент и да се използва директно мнемониката testandset (Възможно е, че това изявление може да се направи само с привилегии на OS))

РЕДАКТИРАНЕ: Според коментарите под тази публикация е възможно да направите своя собствена функция „bittestandset“, като използвате директно ASM директива (на intel x86). Не е ясно обаче дали тези трикове работят и на други процесори.

Поддържам тезата си: ако искате да правите атмосферни неща, използвайте функциите на ОС и не го правете сами