Сравнение с обменом
Сравнение с обменом (англ. compare and set, compare and swap, CAS) — атомарная инструкция, сравнивающая значение в памяти с одним из аргументов, и в случае успеха записывающая второй аргумент в память. Поддерживается в семействах процессоров x86, Itanium, Sparc и других.
Содержание
Назначение
/* Псевдокод работы инструкции, возвращающей булево значение в синтаксисе языка C */
int cas(int* addr, int old, int new)
{
if(*addr != old)
return 0;
*addr = new;
return 1;
}Как и другие атомарные инструкции, она предназначена для синхронизации между параллельными агентами (на разных процессорах или на одном, но без возможности монопольного захвата). Основное применение сравнения с обменом — реализация спинлоков и неблокирующих алгоритмов.
Подход атомарных инструкций противостоит подходу с «условной записью» (англ. load-link/store-conditional).
Инструкция для сравнения с обменом в процессорах x86 называется CMPXCHG и выполняется следующим образом:
1. Процессор читает область памяти, указанную в команде первым операндом, не снимая по завершении чтения блокировку шины.
2. Процессор сравнивает прочтённое значение со значением в аккумуляторе (регистр AL, AX, EAX или RAX). Флагу ZF присваивается значение в зависимости от результата сравнения (1 — если значение в памяти равно значению в аккумуляторе, 0 — если они отличаются).
3. Если значение в памяти было равно значению в аккумуляторе, процессор записывает значение из второго операнда в область памяти, указанную первым операндом. (Особенность реализации x86: запись происходит всегда, но если сравнение на шаге 2 показало неравенство, в аккумулятор записывается то значение, что было прочтено из памяти на шаге 1.) По завершении записи, блокировка шины снимается.
Далее программист обязан закодировать проверку флага ZF для выяснения, выполнилась операция успешно или к моменту её начала значение в памяти было заменено другим агентом.
Для SPARC, инструкции для данной операции называются CASA и CASXA.
Зачем это нужно
Казалось бы, на однопроцессорной машине можно отключить прерывания и тогда состояние памяти точно ничего не изменит. Но тут есть две проблемы. Первая проблема — отключение прерываний процедура сравнительно дорогостоящая. Вторая проблема — если отключить прерывания, а поток войдет в бесконечный цикл, то программу нельзя будет завершить без перезагрузки компьютера. Поэтому Linux требует высоких прав доступа для кода с этой инструкцией, что может доставить немало неудобств пользователям программы.
На многопроцессорной же машине отключение прерываний вообще не поможет, так как в ситуации:
1-й процессор проверил, что память не заблокирована 2-й процессор проверил, что память не заблокирована 1-й процессор заблокировал память 2-й процессор заблокировал память 1-й процессор изменил память 2-й процессор изменил память 1-й процессор разблокировал память 2-й процессор разблокировал память
изменения 1-го процессора будут потеряны, а программа будет думать, что все нормально.
Пример использования
У нас есть n процессоров, каждый из которых иногда хочет получить доступ к какому-то общему ресурсу. Например, к устройству или общему участку памяти.
До начала основной работы назначим им уникальные номера от 0 до n-1.
Выберем ячейку памяти, которая будет указывать, какой процессор сейчас использует ресурс. Значение −1 будет указывать, что ресурс никем не занят. Поместим в неё −1.
При основной работе каждый процессор должен проверить, что в ячейке находится −1, и если это так, то записать в неё свой номер. Если же ячейка занята — процессор обязан ждать, пока она не освободится (мы договорились, что он будет ждать, и не будем писать программы, которые не выполняют это требование).
То есть программа может выглядеть следующим образом:
; блокировка m_wait: mov eax, -1 mov ecx, 5 ; номер нашего процессора 5 cmpxchg 105BA9D2, ecx ; адрес ячейки 105BA9D2 jnz m_wait ; если ресурс заблокирован ; работа с общим ресурсом ... ; снятие блокировки ...
Использование в языках C/C++
Инструкции атомарного сравнения с обменом не входили в стандарты языков C/C++, поэтому они либо реализуются через ассемблер, либо через нестандартные расширения языка. В стандарте C++11 введена библиотека атомарных операций, в которой есть сравнение с обменом.[1] Также существует несколько библиотек с реализациями C/C++ интерфейсов к подобным инструкциям, например: Intel TBB, boost.atomic, Open Portable Atomics, Glib.
Через ассемблерную вставку
Команду cmpxchg напрямую можно закодировать с помощью следующей ассемблерной вставки компилятора GCC (GCC Inline Assembly):
uint32_t *ptr;
uint32_t ret_val,old_val,new_val;
asm volatile("lock\n\tcmpxchgl %1,%2"
: "=a"(ret_val)
: "r"(new_val),"m"(*ptr),"0"(old_val)
: "memory"
);либо для x86 64:
uint64_t *ptr;
uint64_t ret_val,old_val,new_val;
asm volatile("lock\n\tcmpxchgq %1,%2"
:"=a"(ret_val)
:"r"(new_val),"m"(*ptr),"0"(old_val)
:"memory"
);Следует обратить особое внимание на то, что используется asm volatile (а не просто asm), инструктирующая оптимизирующий компилятор о том, что у данной ассемблерной вставки есть побочные эффекты, и она должна находиться в том месте цикла, где находится по коду. Также обязательным является указание «memory» в clobbering list.
Через встроенные функции
GCC и некоторые другие компиляторы поддерживают builtin — расширения для реализации этой инструкции:
TYPE __sync_val_compare_and_swap(TYPE *ptr, TYPE oldval, TYPE newval);
Данное расширение может быть реализовано не для всех поддерживаемых gcc архитектур либо не во всех версиях gcc.[2]
Подобные функции с другим именем существуют в компиляторах для ОС Windows и Mac OS X: InterlockedCompareExchange(), OSAtomicCompareAndSwapPtrBarrier().
Безблокировочные алгоритмы с детектированием коллизий
На практике мало кто догадывается о том, что существование подобной инструкции открывает огромные горизонты в повышении производительности кода за счет возможности ухода вообще от блокировок как таковых.
Рассмотрим такой участок псевдокода:
читаем значение переменной; производим некоторую обработку; записываем новое значение переменной;
Наиболее обычным способом сделать данный код многопоточным является введение синхронизирующих примитивов (mutexы, спинлоки, и т. д.) следующим образом:
производим блокировку; читаем значение переменной; производим некоторую обработку; записываем новое значение переменной; отпускаем блокировку;
Однако, зачастую применим более элегантный метод:
читаем значение переменной; производим некоторую обработку; производим cmpxchg новое значение переменной в предположении что значение все еще равно старому; если значение было изменено другим потоком-повторяем обработку;
Реальный пример безблокировочного алгоритма и производительность
Рассмотрим классический пример структуры данных — связный список.
struct ll_node{
int key; // некоторый ключ
int val; // некоторое значение
struct ll_node *next; // указатель на следующий
};Функция вставки в связанный список узла new_node после указанного узла node выглядит следующим образом:
void ll_insert_after(struct ll_node *node,struct ll_node *new_node)
{
new_node->next=node->next;
node->next=new_node; // (!!!) - обратим внимание на данную строку
}Очевидно, код будет работать корректно только в предположении, что значение node->next не было изменено другим потоком к моменту работы строки, отмеченной «(!!!)», в противном случае мы рискуем потерять изменения остальных потоков, породив узлы, не относящиеся к списку (Утечка памяти).
Существует 3 основных способа борьбы с этим:
1) Закрыть весь связный список Мьютексом. С точки зрения производительности, это самый худший способ. Во-первых, со связным списком в данный момент времени будет работать только один поток, что само по себе сводит на нет все плюсы многопоточности. Во вторых, на практике ситуация обстоит намного хуже, чем можно было бы предположить: более-менее интенсивная одновременная работа с таким связным списком будет порождать огромное (тысячи, десятки тысяч, а в отдельных, особо интенсивных случаях даже миллионы) переключений контекста, что само по себе способно убить производительность не только самого приложения, но и системы в целом (эффект «просаживания производительности» квадратично возрастает от числа вычислительных ядер).
2) Более интеллектуальный способ. Заменить Mutex на Спинлок. Несколько холостых циклов ожидания занятости обходятся намного «дешевле», чем системный вызов и порожденное им переключение контекста. Дает реальный эффект на SMP-системах, однако на одноядерных системах порождает «редкий, но меткий» убой производительности за счет длительного простоя.
3) Алгоритм без блокировки. Перепишем функцию вставки следующим образом: сделаем предположение о неизменности значения node->next явным. Его мы в явном виде и будем проверять с помощью команды cmpxchg:
void ll_insert_after(struct ll_node *node,struct ll_node *new_node)
{
struct ll_node *old_val=node->next; // запоминаем старое значение
while(1){
new_node->next=old_val;
old_val=cmpxchg(&node->next,old_val,new_node);
if(old_val==new_node)
break; // Другие потоки не меняли node->next. Успех операции, выход.
// Иначе повторим попытку
}
}«Ядром» безблокировочной логики данной функции служит команда CMPXCHG. Она атомарно проверяет, что содержимое ячейки памяти &node->next все еще содержит значение old_val, и если это так (а вероятность этого лучшего случая крайне высока), записывает значение указателя new_node и выходит из цикла. В случае коллизии совместного доступа мы получаем обновленное значение old_val и выходим на новую итерацию цикла.
В случае рассматриваемого выше связного списка вероятность коллизии крайне мала. Формально она равна Pкол=(n/N)*pфунк , где N — к-во записей в списке, n — к-во одновременных потоков, pфунк — отношение времени, которое каждый поток проводит внутри функции вставки, к общему времени работы потока.
Команды CMPXCHG8B, CMPXCHG16B
Главным недостатком, сдерживающим применение команды cmpxchg в безблокировочных алгоритмах состоит в том, что команда заменяет всего лишь одно значение. В случае когда это только значение указателя или целочисленная переменная этого достаточно. Однако очень часто требуется атомарно условно заменить две связанные переменные. Например: указатель на буфер и его длина, указатель на начало и конец данных и т. д. Для этих целей в процессорах Intel введены команды CMPXCHG (32-bit), CMPXCHG8B (64-bit) и CMPXCHG16B (x86 64). Кстати, требование поддержки процессором команды CMPXCHG16B появилось в ОС MS Windows версии 8.1 x64.
В процессорах SPARC эти функции выполняют команды CASA и CASXA.
Напишите отзыв о статье "Сравнение с обменом"
Примечания
- ↑ [en.cppreference.com/w/cpp/atomic/atomic_compare_exchange std::atomic_compare_exchange_weak, std::atomic_compare_exchange_strong, std::atomic_compare_exchange_weak_explicit, std::atomic_compare_exchange_strong_explicit - cppreference.com]. en.cppreference.com. Проверено 10 ноября 2015.
- ↑ [gcc.gnu.org/onlinedocs/gcc-4.1.1/gcc/Atomic-Builtins.html 5.44 Built-in functions for atomic memory access], "Not all operations are supported by all target processors. ... type __sync_val_compare_and_swap (type *ptr, type oldval type newval, ...)"
См. также
Ссылки
- [developer.intel.com/products/processor/manuals/index.htm Intel 64 and IA-32 architectures software developer’s manuals]
- [faydoc.tripod.com/cpu/cmpxchg.htm Отдельная страница по команде CMPXCHG]
- [docs.sun.com/app/docs/doc/816-1681/6m83631ls?a=view SPARC assembly language reference manual]
 |
Эту статью следует викифицировать. Пожалуйста, оформите её согласно правилам оформления статей.
|
<imagemap>: неверное или отсутствующее изображение |
Для улучшения этой статьи желательно?:
|
Отрывок, характеризующий Сравнение с обменом
– …И вот, братец ты мой, – продолжал Платон с улыбкой на худом, бледном лице и с особенным, радостным блеском в глазах, – вот, братец ты мой…Пьер знал эту историю давно, Каратаев раз шесть ему одному рассказывал эту историю, и всегда с особенным, радостным чувством. Но как ни хорошо знал Пьер эту историю, он теперь прислушался к ней, как к чему то новому, и тот тихий восторг, который, рассказывая, видимо, испытывал Каратаев, сообщился и Пьеру. История эта была о старом купце, благообразно и богобоязненно жившем с семьей и поехавшем однажды с товарищем, богатым купцом, к Макарью.
Остановившись на постоялом дворе, оба купца заснули, и на другой день товарищ купца был найден зарезанным и ограбленным. Окровавленный нож найден был под подушкой старого купца. Купца судили, наказали кнутом и, выдернув ноздри, – как следует по порядку, говорил Каратаев, – сослали в каторгу.
– И вот, братец ты мой (на этом месте Пьер застал рассказ Каратаева), проходит тому делу годов десять или больше того. Живет старичок на каторге. Как следовает, покоряется, худого не делает. Только у бога смерти просит. – Хорошо. И соберись они, ночным делом, каторжные то, так же вот как мы с тобой, и старичок с ними. И зашел разговор, кто за что страдает, в чем богу виноват. Стали сказывать, тот душу загубил, тот две, тот поджег, тот беглый, так ни за что. Стали старичка спрашивать: ты за что, мол, дедушка, страдаешь? Я, братцы мои миленькие, говорит, за свои да за людские грехи страдаю. А я ни душ не губил, ни чужого не брал, акромя что нищую братию оделял. Я, братцы мои миленькие, купец; и богатство большое имел. Так и так, говорит. И рассказал им, значит, как все дело было, по порядку. Я, говорит, о себе не тужу. Меня, значит, бог сыскал. Одно, говорит, мне свою старуху и деток жаль. И так то заплакал старичок. Случись в их компании тот самый человек, значит, что купца убил. Где, говорит, дедушка, было? Когда, в каком месяце? все расспросил. Заболело у него сердце. Подходит таким манером к старичку – хлоп в ноги. За меня ты, говорит, старичок, пропадаешь. Правда истинная; безвинно напрасно, говорит, ребятушки, человек этот мучится. Я, говорит, то самое дело сделал и нож тебе под голова сонному подложил. Прости, говорит, дедушка, меня ты ради Христа.
Каратаев замолчал, радостно улыбаясь, глядя на огонь, и поправил поленья.
– Старичок и говорит: бог, мол, тебя простит, а мы все, говорит, богу грешны, я за свои грехи страдаю. Сам заплакал горючьми слезьми. Что же думаешь, соколик, – все светлее и светлее сияя восторженной улыбкой, говорил Каратаев, как будто в том, что он имел теперь рассказать, заключалась главная прелесть и все значение рассказа, – что же думаешь, соколик, объявился этот убийца самый по начальству. Я, говорит, шесть душ загубил (большой злодей был), но всего мне жальче старичка этого. Пускай же он на меня не плачется. Объявился: списали, послали бумагу, как следовает. Место дальнее, пока суд да дело, пока все бумаги списали как должно, по начальствам, значит. До царя доходило. Пока что, пришел царский указ: выпустить купца, дать ему награждения, сколько там присудили. Пришла бумага, стали старичка разыскивать. Где такой старичок безвинно напрасно страдал? От царя бумага вышла. Стали искать. – Нижняя челюсть Каратаева дрогнула. – А его уж бог простил – помер. Так то, соколик, – закончил Каратаев и долго, молча улыбаясь, смотрел перед собой.
Не самый рассказ этот, но таинственный смысл его, та восторженная радость, которая сияла в лице Каратаева при этом рассказе, таинственное значение этой радости, это то смутно и радостно наполняло теперь душу Пьера.
– A vos places! [По местам!] – вдруг закричал голос.
Между пленными и конвойными произошло радостное смятение и ожидание чего то счастливого и торжественного. Со всех сторон послышались крики команды, и с левой стороны, рысью объезжая пленных, показались кавалеристы, хорошо одетые, на хороших лошадях. На всех лицах было выражение напряженности, которая бывает у людей при близости высших властей. Пленные сбились в кучу, их столкнули с дороги; конвойные построились.
– L'Empereur! L'Empereur! Le marechal! Le duc! [Император! Император! Маршал! Герцог!] – и только что проехали сытые конвойные, как прогремела карета цугом, на серых лошадях. Пьер мельком увидал спокойное, красивое, толстое и белое лицо человека в треугольной шляпе. Это был один из маршалов. Взгляд маршала обратился на крупную, заметную фигуру Пьера, и в том выражении, с которым маршал этот нахмурился и отвернул лицо, Пьеру показалось сострадание и желание скрыть его.
Генерал, который вел депо, с красным испуганным лицом, погоняя свою худую лошадь, скакал за каретой. Несколько офицеров сошлось вместе, солдаты окружили их. У всех были взволнованно напряженные лица.
– Qu'est ce qu'il a dit? Qu'est ce qu'il a dit?.. [Что он сказал? Что? Что?..] – слышал Пьер.
Во время проезда маршала пленные сбились в кучу, и Пьер увидал Каратаева, которого он не видал еще в нынешнее утро. Каратаев в своей шинельке сидел, прислонившись к березе. В лице его, кроме выражения вчерашнего радостного умиления при рассказе о безвинном страдании купца, светилось еще выражение тихой торжественности.
Каратаев смотрел на Пьера своими добрыми, круглыми глазами, подернутыми теперь слезою, и, видимо, подзывал его к себе, хотел сказать что то. Но Пьеру слишком страшно было за себя. Он сделал так, как будто не видал его взгляда, и поспешно отошел.
Когда пленные опять тронулись, Пьер оглянулся назад. Каратаев сидел на краю дороги, у березы; и два француза что то говорили над ним. Пьер не оглядывался больше. Он шел, прихрамывая, в гору.
Сзади, с того места, где сидел Каратаев, послышался выстрел. Пьер слышал явственно этот выстрел, но в то же мгновение, как он услыхал его, Пьер вспомнил, что он не кончил еще начатое перед проездом маршала вычисление о том, сколько переходов оставалось до Смоленска. И он стал считать. Два французские солдата, из которых один держал в руке снятое, дымящееся ружье, пробежали мимо Пьера. Они оба были бледны, и в выражении их лиц – один из них робко взглянул на Пьера – было что то похожее на то, что он видел в молодом солдате на казни. Пьер посмотрел на солдата и вспомнил о том, как этот солдат третьего дня сжег, высушивая на костре, свою рубаху и как смеялись над ним.
Собака завыла сзади, с того места, где сидел Каратаев. «Экая дура, о чем она воет?» – подумал Пьер.
Солдаты товарищи, шедшие рядом с Пьером, не оглядывались, так же как и он, на то место, с которого послышался выстрел и потом вой собаки; но строгое выражение лежало на всех лицах.
Депо, и пленные, и обоз маршала остановились в деревне Шамшеве. Все сбилось в кучу у костров. Пьер подошел к костру, поел жареного лошадиного мяса, лег спиной к огню и тотчас же заснул. Он спал опять тем же сном, каким он спал в Можайске после Бородина.
Опять события действительности соединялись с сновидениями, и опять кто то, сам ли он или кто другой, говорил ему мысли, и даже те же мысли, которые ему говорились в Можайске.
«Жизнь есть всё. Жизнь есть бог. Все перемещается и движется, и это движение есть бог. И пока есть жизнь, есть наслаждение самосознания божества. Любить жизнь, любить бога. Труднее и блаженнее всего любить эту жизнь в своих страданиях, в безвинности страданий».
«Каратаев» – вспомнилось Пьеру.
И вдруг Пьеру представился, как живой, давно забытый, кроткий старичок учитель, который в Швейцарии преподавал Пьеру географию. «Постой», – сказал старичок. И он показал Пьеру глобус. Глобус этот был живой, колеблющийся шар, не имеющий размеров. Вся поверхность шара состояла из капель, плотно сжатых между собой. И капли эти все двигались, перемещались и то сливались из нескольких в одну, то из одной разделялись на многие. Каждая капля стремилась разлиться, захватить наибольшее пространство, но другие, стремясь к тому же, сжимали ее, иногда уничтожали, иногда сливались с нею.
– Вот жизнь, – сказал старичок учитель.
«Как это просто и ясно, – подумал Пьер. – Как я мог не знать этого прежде».
– В середине бог, и каждая капля стремится расшириться, чтобы в наибольших размерах отражать его. И растет, сливается, и сжимается, и уничтожается на поверхности, уходит в глубину и опять всплывает. Вот он, Каратаев, вот разлился и исчез. – Vous avez compris, mon enfant, [Понимаешь ты.] – сказал учитель.
– Vous avez compris, sacre nom, [Понимаешь ты, черт тебя дери.] – закричал голос, и Пьер проснулся.
Он приподнялся и сел. У костра, присев на корточках, сидел француз, только что оттолкнувший русского солдата, и жарил надетое на шомпол мясо. Жилистые, засученные, обросшие волосами, красные руки с короткими пальцами ловко поворачивали шомпол. Коричневое мрачное лицо с насупленными бровями ясно виднелось в свете угольев.
– Ca lui est bien egal, – проворчал он, быстро обращаясь к солдату, стоявшему за ним. – …brigand. Va! [Ему все равно… разбойник, право!]
И солдат, вертя шомпол, мрачно взглянул на Пьера. Пьер отвернулся, вглядываясь в тени. Один русский солдат пленный, тот, которого оттолкнул француз, сидел у костра и трепал по чем то рукой. Вглядевшись ближе, Пьер узнал лиловую собачонку, которая, виляя хвостом, сидела подле солдата.
– А, пришла? – сказал Пьер. – А, Пла… – начал он и не договорил. В его воображении вдруг, одновременно, связываясь между собой, возникло воспоминание о взгляде, которым смотрел на него Платон, сидя под деревом, о выстреле, слышанном на том месте, о вое собаки, о преступных лицах двух французов, пробежавших мимо его, о снятом дымящемся ружье, об отсутствии Каратаева на этом привале, и он готов уже был понять, что Каратаев убит, но в то же самое мгновенье в его душе, взявшись бог знает откуда, возникло воспоминание о вечере, проведенном им с красавицей полькой, летом, на балконе своего киевского дома. И все таки не связав воспоминаний нынешнего дня и не сделав о них вывода, Пьер закрыл глаза, и картина летней природы смешалась с воспоминанием о купанье, о жидком колеблющемся шаре, и он опустился куда то в воду, так что вода сошлась над его головой.
Перед восходом солнца его разбудили громкие частые выстрелы и крики. Мимо Пьера пробежали французы.
– Les cosaques! [Казаки!] – прокричал один из них, и через минуту толпа русских лиц окружила Пьера.
Долго не мог понять Пьер того, что с ним было. Со всех сторон он слышал вопли радости товарищей.
– Братцы! Родимые мои, голубчики! – плача, кричали старые солдаты, обнимая казаков и гусар. Гусары и казаки окружали пленных и торопливо предлагали кто платья, кто сапоги, кто хлеба. Пьер рыдал, сидя посреди их, и не мог выговорить ни слова; он обнял первого подошедшего к нему солдата и, плача, целовал его.
