- PVSM.RU - https://www.pvsm.ru -
Стало интересно, как же именно достигается атомарность операций. Кому интересно — добро пожаловать под кат.
Атомарные операции [1] — операции, выполняющиеся как единое целое либо не выполняющиеся вовсе. Т. е. это операция, во время исполнения которой данные, читаемые/изменяемые этой операцией не могут быть изменены другой операцией. Есть специальные ассемблерные команды, которые указывают процессору, что операция будет атомарной. Есть несколько типов команд, с помощью которых можно добиться атомарности: load-link and store-conditional (LL/SC [2]), compare-and-swap (CAS [3]) и другие.
Примеры команд 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-я строка, запускающая операцию снова в случае ошибки.
Принцип работы простой — смотрим, какое значение хранится в операнде. Если оно то, какое мы ожидаем, то меняем его на новое.
Алгоритм:
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]).
Обычно это сложение или инкрементация.
Примеры команд: 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/
Нажмите здесь для печати.