Атомарные операции

Атомарность означает неделимость операции. Это значит, что ни один поток не может увидеть промежуточное состояние операции, она либо выполняется, либо нет. Рассмотрим пример простой операции инкрементирования значения, описанный в работе [8]:

1 int x = 0;

2 ++x;

Даже такой простой код нужно синхронизировать в многопоточной среде. Если посмотреть ассемблерный код второй строки, то мы увидим, что она состоит из трех операций:

1 mov eax, dword ptr [x]; загрузка текущего значения из памяти в регистр eax

2 add eax, 1; инкрементирование значения регистра eax

3 mov dword ptr [x], eax; запись значения регистра eax обратно в память

Модификация встроенных C++ типов не является атомарной, то есть если два потока одновременно попытаются модифицировать переменную x, мы вполне можем получить ситуацию, где значение x станет 1 после двух инкрементов. Пример показан в таблице 1.1.

Таблица 1.1

Пример неверной модификации переменной х двумя потоками

Поток 1	Поток 2
исходно: x = 0
прочитать x	прочитать x
инкрементировать x	инкрементировать x
записать x
	записать x

Ситуации подобные этой, в которых финальный результат зависит от очередности выполнения, называется data race. Можно исправить этот код и сделать его потокобезопасным добавив блокировку перед инкрементом и разблокировку после него, тем самым обеспечивая атомарность операции инкрементирования, но существует другой способ.

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

В связи с этим, кроме атомарных операций чтения и записи, в число атомарных примитивов также должна входить такая операция, как сравнение с обменом или compare-and-swap (CAS), также известная, как compare exchange, или пара операций загрузка с пометкой/попытка записи или load linked/store conditional (LL/SC). Суть операции сравнение с обменом заключается в том, что она атомарно сравнивает значение одного объекта с другим и при удачном сравнении заменяет значение объекта.CAS принимает три аргумента: адрес области памяти, ожидаемое значение по этому адресу и вновь записываемое значение. Если и только если область памяти содержит ожидаемое значение, по этому адресу записывается новое значение. Операцией возвращается булево значение, определяющее произошла ли перезапись значения или нет. Иными словами, CAS(address, expected, new) атомарно выполняет следующую операцию (в псевдокоде):

Суть пары операций загрузка с пометкой/попытка записи аналогична сути операции CAS: LL атомарно сравнивает значение одного объекта с другим и при удачном сравнении SCзаменяет значение объекта.LL принимает один аргумент: адрес области памяти и возвращает ее содержимое. SC принимает два аргумента: адрес области памяти и новое значение. Если ни один другой поток не перезаписывал область памяти по адресу после того, как данный поток считал ее значение с помощью LL, только тогда по этому адресу записывается новое значение. Операция возвращает булево значение, определяющее произошла ли перезапись значения. Дополнительная инструкция validate (VL) принимает один аргумент: адрес области памяти, и возвращает булево значение, определяющее, происходила ли перезапись области памяти со стороны других потоков с того момента времени, как данный поток выполнил LL.

Большинство современных широко распространенных процессорных архитектур поддерживает либо CAS, либо пару LL/SC на выровненных однословных операндах. В некоторых 32-разрядных системах эти операции доступны и для двухсловных операндов (то есть доступна поддержка 64-разрядных инструкций), но на 64-битных архитектурах поддержки операций над двухсловными операндами нет (то есть 128-битные инструкции не поддерживаются). Пара LL/SC обычно используется в RISC-архитектурах (DEC Alpha, MIPS, PowerPC, ARM), тогда как на архитектурах x86 используется CAS в различных ее вариациях.

CAS легко выразить через пару LL/SC следующим образом:

Более подробное описание операций можно найти в работах [2,4].

Дата добавления: 2015-11-14