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

В параллельной среде некоторые действия должны выполняться атомарно, то есть без какой-либо возможности прерывания. Эти операции должны быть неделимыми, какими в свое время считались атомы.

В качестве примера рассмотрим подсчет ссылок. Если вы хотите отказаться от своей доли в разделяемом ресурсе и узнать, владеет ли им кто-то еще, вы уменьшите счетчик этого разделяемого ресурса и проверите его на равенство нулю. Типичная последовательность действий может начинаться со следующего:

1. Процессор загружает текущее значение счетчика (скажем, 2) в один из своих регистров.
2. Процессор уменьшает это значение в своем регистре; теперь оно равно 1.
3. Процессор записывает новое значение (1) обратно в память.
4. Процессор решает, что поскольку значение равно 1, разделяемый объект используется каким-то другим процессом, поэтому не освобождает объект.

В однопроцессорных системах этот сценарий не вызывает особого беспокойства (за исключением некоторых случаев). Но в симметричных мультипроцессорных системах картина совершенно иная: а что будет, если окажется, что другой процессор выполняет ту же работу и в то же время? Наихудший случай выглядит примерно так:

1. Процессор А загружает текущее число (2) в один из своих регистров.
2. Процессор В загружает текущее число (2) в один из своих регистров.
3. Процессор А уменьшает значение в своем регистре; теперь оно равно 1.
4. Процессор В уменьшает значение в своем регистре; теперь оно равно 1.
5. Процессор А записывает новое значение (1) обратно в память.
6. Процессор В записывает новое значение (1) обратно в память.
7. Процессор А решает, что поскольку значение равно 1, этот разделяемый объект используется каким-то другим процессом, поэтому не освобождает его.
8. Процессор В решает, что поскольку значение равно 1, этот разделяемый объект использует какой-то другой процесс, поэтому не освобождает его.

Число ссылок в памяти теперь должно быть равно 0, но вместо этого, оно равно 1. Оба процесса удалили свои ссылки на разделяемый объект, но ни один из них его не освободил.

Это интересный отказ, поскольку каждый процессор выполнил именно то, что требовалось, и все равно возник неправильный результат. Проблема, безусловно, состоит в том, что процессоры не координировали свои действия, поэтому правая рука не знала, что делает левая.

А если мы попытаемся решить эту проблему в программном обеспечения? Рассмотрим все действия с точки зрения любого из процессоров, скажем, процессора А. Чтобы сообщить процессору В, что он должен оставить нетронутым число ссылок, поскольку вы хотите его уменьшить, вы должны как-то изменить некоторую информацию, доступную процессору В, то есть обновить данные в каком-то месте разделяемой памяти. Например, можно зарезервировать для этой цели какое-то место в разделяемой памяти и договориться, что в нем будет записана 1, если любой из процессоров собирается уменьшить число ссылок, и 0 — в ином случае. Это соглашение может выполняться примерно так:

1. Процессор А загружает обусловленное значение из специального места в памяти в один из своих регистров.
2. Процессор А проверяет это значение в своем регистре и обнаруживает, что оно равно 0. (Если нет, он осуществляет последующие попытки, повторяя их до тех пор, пока в регистре не появится 0.)
3. Процессор А записывает 1 обратно в специальное место в памяти.
4. Процессор А обращается к защищенному числу ссылок.
5. Процессор А записывает 0 обратно в специальное место в памяти.

Да... Это выглядит неприятно знакомым. Ничто не может предотвратить такого развития событий:

1. Процессор А загружает значение из специального места в памяти в один из своих регистров.
2. Процессор В загружает значение из специального места в памяти в один из своих регистров.
3. Процессор А проверяет значение в одном из своих регистров и обнаруживает, что оно равно 0.
4. Процессор В проверяет значение в одном из своих регистров и обнаруживает, что оно равно 0.
5. Процессор А записывает 1 обратно в специальное место в памяти.
6. Процессор В записывает 1 обратно в специальное место в памяти.
7. Процессор А обращается к защищенному числу ссылок.
8. Процессор В обращается к защищенному числу ссылок.
9. Процессор А записывает 0 обратно в специальное место в памяти.
10. Процессор В записывает 0 обратно в специальное место в памяти.

Но, может, для защиты специального места в памяти, которое должно защищать первоначальное место в памяти, можно использовать еще одно специальное место в памяти...

Мы должны признать свое поражение. Такой подход позволяет только перевести проблему на другой уровень, но не решить ее. В конечном итоге, атомарность операций нельзя гарантировать только за счет одного программного обеспечения, без конкретной помощи со стороны аппаратных средств.

Па платформе х86 именно такую помощь предоставляет команда lock. (Точнее, lock — это скорее префикс, а не отдельная команда, но для наших целей эта разница не имеет значения.) Команда lock блокирует шину памяти (по меньшей мере, для указанного адреса назначения) на время выполнения следующей команды. Поскольку платформа х86 позволяет уменьшать значение прямо в памяти, без необходимости его явного предварительного чтения в регистр, мы имеем все необходимое для реализации атомарного уменьшения: нам достаточно заблокировать шину памяти, а затем немедленно выполнить команду decl с этим адресом в памяти.

Функция atomic_dec (строка 10241) выполняет именно это для платформы х86. Версия макрокоманды LOCK, которая определена директивой #define в строке 10192 для симметричной мультипроцессорной системы, развертывается в команду lock. (Версия для однопроцессорной системы, которая определена директивой #define двумя строками ниже, просто пуста, поскольку единственный процессор не нуждается в защите от других процессоров, и блокировка шины памяти будет напрасной тратой времени.) Теперь можно применять перед встроенным ассемблерным кодом макрокоманду LOCK и блокировать следующую команду для версий ядра симметричной мультипроцессорной системы. Если процессор В вызовет функцию atomic_dec в то время, как блокировка процессора А находится в действии, процессор В автоматически перейдет в состояние ожидания до тех пор, пока процессор А не удалит блокировку. Это успех!

Да, почти. Первоначальная проблема еще не совсем решена. Задача состояла не только в атомарном уменьшении числа ссылок, но также и в определении того, равно ли результирующее значение 0. Теперь мы может выполнять атомарное уменьшение, но что, если другой процессор успеет проскочить между этим уменьшением и проверкой результата?

К счастью, решение этой части проблемы не требует специализированной помощи процессора. Будучи заблокированной или нет, команда decl в архитектуре х86 всегда устанавливает флажок Zero процессора, если результат равен 0, и этот флажок является собственной принадлежностью процессора, поэтому никакой другой процессор не может повлиять на него между частью операций, связанной с уменьшением, и частью операций, связанной с проверкой. В соответствии с этим, в функции atomic_dec_and_test (строка 10249) выполняется блокированное уменьшение, как и раньше, а затем устанавливается значение локальной переменной с на основании значения флажка Zero процессора. Эта функция возвращает ненулевое (истинное) значение, если результат после уменьшения стал равен 0.

Функции atomic_dec, atomic_dec_and_test, а также другие функции, которые определены в том же файле, оперируют с объектами типа atomic_t (строка 10205). Объект atomic_t, как и макрокоманда LOCK, имеет разные определения для однопроцессорной системы и симметричной мультипроцессорной системы, и здесь разница состоит в том, что в случае симметричной мультипроцессорной системы введен спецификатор типа volatile, который указывает транслятору gcc, чтобы он не делал некоторых предположений относительно отмеченной переменной (например, не предполагал, что ее можно безопасно хранить в регистре).

Кстати, есть сведения, что все макрокоманды __atomic_fool_gcc, которые разбросаны по этому коду, больше не нужны; они применялись для обхода ошибки в выработке объектного кода в ранних версиях gcc.