- PVSM.RU - https://www.pvsm.ru -

Atomic operations

Стало интересно, как же именно достигается атомарность операций. Кому интересно — добро пожаловать под кат.

Атомарные операции [1] — операции, выполняющиеся как единое целое либо не выполняющиеся вовсе. Т. е. это операция, во время исполнения которой данные, читаемые/изменяемые этой операцией не могут быть изменены другой операцией. Есть специальные ассемблерные команды, которые указывают процессору, что операция будет атомарной. Есть несколько типов команд, с помощью которых можно добиться атомарности: load-link and store-conditional (LL/SC [2]), compare-and-swap (CAS [3]) и другие.

1. LL/SC

Примеры команд LL/SC:
ldl_l/stl_c и ldq_l/stq_c (Alpha), lwarx/stwcx (PowerPC), ll/sc (MIPS), and ldrex/strex (ARM version 6 and above).
Команды даны парами, т. к. первая захватывает lock, вторая отпускает. Вместе они гарантируют, что все команды между ними работают с одной версией данных. Для примера возьмем пару lwarx/stwcx (PowerPC):

void atomic_incr(int * operand, int incr)
{
    asm volatile (
        "loop:nt" /* repeat until this succeeds */
        "lwarx  6,0,%0nt" /* reserve the operand */
        "add    6,6,%1nt" /* add incr to it */
        "stwcx. 6,0,%0nt" /* put the sum back, and release it */
        "bne- loop" /* start-over on failure */
        :
        : "r" (operand), "r" (incr)
        : "r6"
     );
}

Код взят отсюда. [4]
В 6-ой регистр загружаются данные из операнда и он(операнд) резервируется. Потом в 6-ом регистре получаем сумму операнда и incr. В конце выгружаем из регистра полученную сумму в операнд и отпускаем его. Если в промежуток между резервированием и освобождением операнда его значение будет изменено где-то еще помимо текущей операции(даже если было присвоено тоже самое значение, которое уже хранилось в операнде), то мы получим ошибку. Это проверяет 5-я строка, запускающая операцию снова в случае ошибки.

Ассемблерные параметры gcc

Пример:
: "=r" (val), "=m" (*mem)
: «0» (val), «m» (*mem)
: «memory», «cc»);
Первая строка — выходные параметры.
"=r" (val) — %0 является константой или операндом. gcc должен использовать любой регистр для %0.
"=m" (*mem) — %1 является переменной в памяти, которую gcc должен использовать для записи результата (mem — указатель на эту переменную).
Вторая строка — входные параметры.
«0» (val) — 0 означает, что должен использоваться такой же регистр, что и в выходных параметрах и в него должно быть загружено значение из переменной.
«m» (*mem) — «m» означает то же, что и "=m", только отсутствие знака "=" говорит, что происходит чтение.
Третья строка — что будет изменено инструкциями.
«memory» — будет изменена память.
«cc» — «condition code register». Это означает, что будут изменены флаги процессора.
Подробнее можно прочитать здесь [5].
2. CAS

Принцип работы простой — смотрим, какое значение хранится в операнде. Если оно то, какое мы ожидаем, то меняем его на новое.
Алгоритм:

int compare_and_swap (int* reg, int oldval, int newval) 
{
  int old_reg_val = *reg;
  if (old_reg_val == oldval) 
     *reg = newval;
  return old_reg_val;
}

Расширение CAS — Double Compare And Swap (CAS2 [6]). Даются указатели на две независимые переменные вместо одной, соответственно, два ожидаемых значения и два новых значения для каждой переменной соответственно. Пример:

/* double-compare-and-swap: atomically sets the two-word data at address @mem
 *                          to the two-word value of @new if value at @mem
 *                          equals @old
 *   @mem: pointer to value
 *   @old: old value 
 *   @new: new value
 *
 *   returns: 0 on failure, non-zero on success */
static inline 
char DWCAS(volatile DWORD *mem, DWORD old, DWORD new)
{
	char r = 0;
	unsigned long old_h = old >> SHIFT, old_l = old;
	unsigned long new_h = new >> SHIFT, new_l = new;
	__asm__ __volatile__("lock; " CMPXCHGxB " (%6);"
		     "setz %7; "
		     : "=a" (old_l),
		       "=d" (old_h)
		     : "0" (old_l),
		       "1" (old_h),
		       "b" (new_l),
		       "c" (new_h),
		       "r" (mem),
		       "m" (r)
		     : "cc", "memory");
	return r;
}

Код взят отсюда. [7]
Команда «lock;» означает, что шина доступа к памяти может быть использована только следующей за ней командой.
Но эта группа команд более «слабая», чем LL/SC, т. к. возможна ситуация:
начальные условия: compare_and_swap( reg, 5, 7 ) и *reg = 5;
1) int old_reg_val = *reg; (old_reg_val = 5)
2) другая операция делает *reg = 42; funny_stuff; *reg = 5;
3) if (old_reg_val == oldval) — утверждение верно, хотя произошло два изменения значения переменной. Т. е. произошло изменение, но наша операция об этом не знает. Эта ситуация называется ABA problem [8].
Есть много методов обхода этой проблемы. Мне показался интересным метод с использованием Double-Word Compare-And-Swap (часто путается с Double Compare And Swap). В передаваемом слове содержится указатель на память с требуемым значением и ABA номер, который изменяется с каждой операцией (увидел это в одном из патентов [9]).

3. Простые атомарные операции.

Обычно это сложение или инкрементация.
Примеры команд: addl(i386), xaddl(x86).
Вот реализация атомарного сложения из википедии [10]:

void atomic_add(int * operand, int incr)
{
    asm volatile (
        "lock; xaddl %1, (%0)n" // add incr to operand
        : // no output
        : "r" (operand), "r" (incr)
    );
}

На некоторых архитектурах команда «lock;» не нужна. Пример — инкрементирование на Итаниуме (взят отсюда [4]):

void atomic_oneup(int * operand)
{
    uint64_t res; // this MUST be 64 bits
    asm volatile (
        "fetchadd4.rel %0=%1,%2"
        : "=r" (res)
        : "m" (*operand), "i" (1)
        : "memory"
    );
}

Кстати, инкремент, декремент, +=, -= в С++ атомарные (по крайней мере на х86 и х86_64).

int a =0;
++a;

компилируется в

c7 45 fc 00 00 00 00 	movl   $0x0,-0x4(%rbp)
83 45 fc 01          	addl   $0x1,-0x4(%rbp)

Для декремента будет subl.

Заключение

Q: Это известно каждому школьнику! Зачем об этом писать?
A: Мне было интересно, как же оно работает. Представлял только, что там есть какие-то lock'и. Надеюсь, это было интересно еще кому-то.

Q: В статье куча ошибок и неточностей.
A: Пишите, с радостью исправлю.

Q: Что? Уже заключение? Где сама статья? Где MSI [11], Cache Coherence [12] и %еще_куча_умных_слов%?
A: Я не копал глубоко. Надеюсь, об этом напишут люди, которые знают эти темы.

Автор: Ramires

Источник [13]


Сайт-источник PVSM.RU: https://www.pvsm.ru

Путь до страницы источника: https://www.pvsm.ru/programmirovanie/18737

Ссылки в тексте:

[1] Атомарные операции: http://ru.wikipedia.org/wiki/%D0%90%D1%82%D0%BE%D0%BC%D0%B0%D1%80%D0%BD%D0%B0%D1%8F_%D0%BE%D0%BF%D0%B5%D1%80%D0%B0%D1%86%D0%B8%D1%8F

[2] LL/SC: http://en.wikipedia.org/wiki/Load-Link/Store-Conditional

[3] CAS: http://en.wikipedia.org/wiki/Compare_and_swap

[4] отсюда.: http://www.memoryhole.net/kyle/2007/05/atomic_incrementing.html

[5] здесь: http://www.ibiblio.org/gferg/ldp/GCC-Inline-Assembly-HOWTO.html

[6] CAS2: http://en.wikipedia.org/wiki/Double_compare-and-swap

[7] отсюда.: http://julien.benoist.name/lockfree/atomic-queue/atomic.h

[8] ABA problem: http://en.wikipedia.org/wiki/ABA_problem

[9] патентов: http://www.google.com/patents/US20080228784

[10] википедии: http://en.wikipedia.org/wiki/Fetch-and-add

[11] MSI: https://en.wikipedia.org/wiki/MSI_protocol

[12] Cache Coherence: https://en.wikipedia.org/wiki/Coherence_protocol

[13] Источник: http://habrahabr.ru/post/157163/