Наши партнеры

Книги по Linux (с отзывами читателей)

Библиотека сайта rus-linux.net

На главную -> MyLDP -> Тематический каталог -> Аппаратное обеспечение

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

Оригинал: Memory, part 6: More things programmers can do
Автор: Ulrich Drepper
Дата публикации: October 31, 2007
Перевод: М.Ульянов
Дата перевода: февраль 2010 г.

6.4.2 Оптимизация работы с атомарными операциями

В ситуации, когда несколько потоков параллельно работают с одной и той же областью памяти, процессоры сами не предпринимают никаких действий и, соответственно, не гарантируют никаких определенных результатов. Это обдуманное и взвешенное решение, принятое с целью избежания затрат, лишних в 99,999% всех случаев. Например, пусть область памяти имеет статус ‘S’ и два потока параллельно пытаются увеличить значение, хранящееся в этой области, на единицу. Исполнительный конвейер не станет ждать, пока кэш-строка получит статус ‘E’, прежде чем считать старое значение. Вместо этого он сразу считывает текущее значение из кэша и, как только кэш-строка получает статус ‘E’, записывает новое значение обратно. Но результат может обмануть ожидания, если операции чтения кэша произойдут в двух потоках одновременно - тогда одно из увеличений будет потеряно.

Для предотвращения таких ситуаций в процессорах предусмотрены так называемые атомарные (неделимые) операции. Эти операции, например, никогда не станут считывать старое значение до тех пор, пока не станет ясно, что увеличение возможно осуществить как атомарное. Помимо ожидания остальных ядер и процессоров, некоторые процессоры даже предупреждают другие устройства материнской платы о таких операциях. Всё это замедляет работу с ними.

Наборы доступных атомарных операций различаются у разных производителей процессоров. Ранние процессоры RISC - где ‘R’ означает reduced, "сокращенный" (о наборе команд) - имели очень мало таких команд, иногда вообще лишь атомарные битовые set и test. {HP Parisc до сих пор только их и поддерживает...}. А на другом конце спектра у нас архитектуры x86 и x86-64 со множеством атомарных инструкций. Основные из них можно разделить на четыре класса:

Bit Test: Эти операции атомарно устанавливают либо сбрасывают бит и возвращают его предыдущее состояние.
Load Lock/Store Conditional (LL/SC) {Иногда предпочитают использовать ⌠linked■ вместо ⌠lock■, это не суть важно.}: Тут у нас сразу пара операций: специальная инструкция загрузки (считывания) используется для начала транзакции, а инструкция сохранения (записи) завершает ее, причем успешное завершение возможно только если во время выполнения не произошло никаких изменений в целевой области. Программа может повторять попытки при необходимости, в зависимости от результата операции сохранения.
Compare-and-Swap (CAS): Троичная (тернарная) операция "Сравнение и замена" записывает значение (переданное как первый параметр) по адресу (второй параметр), только если текущее значение, хранящееся по этому адресу, равно третьему параметру.
Атомарные арифметические операции: Доступны исключительно на архитектурах x86 и x86-64, которые могут осуществлять арифметические и логические операции над памятью. Эти процессоры поддерживают также и неатомарные версии данных операций, чем не могут похвастаться архитектуры RISC. Поэтому неудивительно, что они так мало распространены.

Любая архитектура может поддерживать либо LL/SC, либо CAS - третьего не дано. Оба подхода по сути эквивалентны, и в равной степени одинаково позволяют реализовывать атомарные арифметические операции. Однако в наши дни чаще предпочитают CAS. Используя эту инструкцию, можно косвенно реализовать все остальные операции. Например, атомарное сложение:

  int curval;
  int newval;
  do {
    curval = var;
    newval = curval + addend;
  } while (CAS(&var, curval, newval));

Значение, возвращенное CAS, показывает, успешно завершилась операция или нет. Если нет (возвращено ненулевое значение), цикл запускается по новой, выполняется сложение и снова проверяется результат вызова CAS. И так до успешного финала. Стоит отметить, что адрес области памяти необходимо вычислять с помощью двух отдельных инструкций. {Операционный код CAS на x86 и x86-64 может пропустить загрузку значения во второй и последующих итерациях, но на той платформе мы вообще сможем всю операцию атомарного сложения записать проще, с использованием лишь одной инструкции.} В случае использования LL/SC код почти не отличается:

  int curval;
  int newval;
  do {
    curval = LL(var);
    newval = curval + addend;
  } while (SC(var, newval));

Здесь мы используем специальную инструкцию загрузки (LL), и при этом нам не нужно передавать в SC текущее значение в памяти, поскольку процессор сам следит, изменялось ли оно во время выполнения программы.

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

    for (i = 0; i < N; ++i)
      __sync_add_and_fetch(&var,1);
1. Произвести сложение и вернуть результат ("сложение с обменом")
    for (i = 0; i < N; ++i)
      __sync_fetch_and_add(&var,1);
2. Произвести сложение и вернуть старое значение ("сложение со считыванием")
    for (i = 0; i < N; ++i) {
      long v, n;
      do {
        v = var;
        n = v + 1;
      } while (!__sync_bool_compare_and_swap(&var, v, n));
    }
3. Атомарная замена новым значением (с использованием CAS)
Рисунок 6.12: Циклический атомарный инкремент

На x86 и x86-64 после интерпретации во всех трех случаях получится разный код, в то время как на других архитектурах он будет идентичен. В скорости выполнения разница огромна. Следующая таблица демонстрирует, сколько времени заняло выполнение одного миллиона инкрементов четырьмя параллельными потоками. В коде использовались встроенные примитивы gcc (__sync_*).

1. Сложение с обменом 2. Сложение со считыванием 3. CAS

0.23s 0.21s 0.73s

1. Сложение с обменом	2. Сложение со считыванием	3. CAS
0.23s	0.21s	0.73s

Сравнив первые два числа, видим, что они близки: сложение со считыванием старого значения лишь чуть-чуть быстрее. Но важно здесь то, что мы видим в третьем, выделенном поле - время, затраченное на выполнение с использованием CAS. Оно гораздо больше. Тому есть несколько причин: 1. В коде присутствуют две отдельные операции по работе с памятью; 2. Сама по себе операция CAS более сложна и даже содержит условный переход; 3. Вся операция сложения находится во вложенном цикле на случай, если произойдут две параллельные попытки доступа и CAS вернет ошибку.

Читатель может спросить: "А зачем вообще использовать CAS, если код получается сложнее и длиннее?". Ответ - вся сложность обычно спрятана. Выше упоминалось, что CAS сейчас присутствует во всех интересных архитектурах, по сути служит инструментом унификации. И поэтому люди считают разумным реализовывать все атомарные операции именно через CAS. Это упрощает программы. Но как показывают цифры, это далеко не оптимально с точки зрения производительности. Решения, построенные на CAS, крайне неэффективно обращаются с памятью. Далее показаны алгоритмы выполнения всего лишь двух потоков, каждого на своем отдельном процессоре ("П"):

Поток #1 Поток #2 Статус кэша var

v = var
‘E’ на П1

n = v + 1
v = var
‘S’ на П1+2

CAS(var)
n = v + 1
‘E’ на П1

CAS(var)
‘E’ на П2

Поток #1	Поток #2	Статус кэша `var`
`v = var`		‘E’ на П1
`n = v + 1`	`v = var`	‘S’ на П1+2
CAS(`var`)	`n = v + 1`	‘E’ на П1
	CAS(`var`)	‘E’ на П2

Видим, что даже за такой небольшой период статус строки кэша меняется минимум три раза, два из которых - в результате запросов RFO. К тому же, CAS во втором потоке выдаст ошибку, и потоку придется повторить операцию с начала. А пока она будет выполняться, снова может произойти та же ситуация.

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

Всё это значит, что крайне важно работать на таком уровне абстракции, на котором можно использовать преимущества атомарных арифметических и логических операций. Не стоит повсюду использовать CAS в качестве механизма унификации.

Для большинства процессоров атомарные операции сами по себе всегда атомарны, неделимы. В случае, когда в атомарности нет необходимости, для ее избежания программисту придется изворачиваться, искать "окольные пути". Соответственно, это значит - больше кода, условные и безусловные переходы к прямому выполнению.

С x86 и x86-64 ситуация иная. Одни и те же инструкции можно использовать и как атомарные, и как "обычные". Чтобы сделать их атомарными, используется специальный префикс: lock. Такой подход позволяет не использовать атомарность, когда в ней нет необходимости - и таким образом избежать связанных с ней затрат. Это очень полезно при, например, написании кода общего пользования в библиотеке, ведь такой код всегда должен обеспечивать потоковую безопасность. Причем во время написания кода можно еще не знать, потребуется это или нет, а выбор будет делаться уже при работе программы. Трюк заключается в том, чтобы перепрыгнуть префикс lock, когда нужно, и прием этот реализуем для всех инструкций, с которыми процессоры x86 и x86-64 позволяют использовать данный префикс.

      cmpl $0, multiple_threads
      je   1f
      lock
  1:  add  $1, some_var

Если этот ассемблерный код кажется непонятным, не волнуйтесь. Все просто. Первая инструкция проверяет, равна ли переменная нулю. В данном случае ненулевое значение будет означать, что запущено более одного потока. При нулевом значении вторая инструкция осуществляет переход к метке 1. Иначе просто выполняется следующая инструкция. Вот и весь трюк. Если перехода не было, инструкция add выполняется с префиксом lock. Иначе - без него.

Добавление относительно дорогой (в смысле ресурсов) операции вроде условного перехода (дорогим он становится в случае, когда предсказание переходов дает сбой) может показаться непродуктивным шагом. И несомненно, иногда это так: если большую часть времени идет работа в несколько потоков, то производительность действительно упадет, особенно в случае частых ошибок механизма предсказания переходов. Но если ситуация противоположна и чаще всего выполняется только один поток, такой код будет выполняться значительно быстрее. Альтернативой конструкции if-then-else в обоих случаях может послужить дополнительный безусловный переход. Учитывая, что затраты ресурсов на атомарную операцию соизмеримы с затратами на 200 циклов, можно сказать, что использование такого трюка (или блока if-then-else) часто оправдывает себя, и этот прием стоит иметь в виду. К сожалению, его использование означает невозможность применения примитивов __sync_*, предоставляемых gcc.

Замечания и предложения по переводу принимаются по адресу michael@right-net.ru. М.Ульянов.

Оглавление

Вперед