Подсчет ссылок атомарными переменными в C/C++ и GCC

Автор: Alexander Sandler, оригинал статьи (27 мая 2009)

Введение

Допустим, у нас есть структура данных, которая управляет объектами и мы хотели бы работать с ней и объектами из двух или более потоков. Для достижения максимальной производительности мы должны различать механизм, использующийся для защиты самой структуры данных и механизм, использующийся для защиты актуальных объектов.

Зачем нужен подсчет ссылок?

Чтобы объяснить, почему эти два механизма обеспечивают наилучшую производительность и чем могут быть полезны атомарные переменные, рассмотрим следующую ситуацию.

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

Очевидно, что два потока должны работать с каким-то механизмом взаимного исключения (mutual exclusion — прим. пер.). Допустим, мы защищаем всю структуру данных одним мьютексом. В этом случае потоку манипулятора приходится удерживать мьютекс заблокированным до тех пор, пока он не найдет объект и не обработает его. Это значит, что у потока стирателя не будет доступа к структуре данных до тех пор, пока поток манипулятора не завершит свою работу. Если все, что делает поток манипулятора — это поиск записей и их обработка, то поток стирателя просто не сможет получить доступ к структуре данных.

В зависимости от обстоятельств, это может стать незаметным уничтожением для системы. И как уже было сказано, единственным способом решения этой проблемы является разделение между механизмами защищающими структуру данных и защищающими актуальные объекты.

Если мы поступим таким образом, поток манипулятора заблокирует мьютекс только при поиске объекта. Как только он получит объект, он сможет освободить мьютекс, защищающий структуру данных и позволяя потоку стирателя сделать свою работу.
Но теперь, как мы можем быть уверены, что поток стирателя не удалит тот же объект, что изменяется первым потоком?

Можно было бы использовать другой мьютекс, защищающий содержимое актуального объекта. Но тут появляется важный вопрос, который мы должны себе задать. Сколько мьютексов потребуется для защиты содержимого объекта?

Если мы используем один мьютекс для всех объектов, то мы сталкиваемся с тем же затором, который только что избежали. С другой стороны, если мы используем мьютекс на каждый объект, то сталкиваемся с несколько иной проблемой.

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

В действительности, есть несколько вещей, которые мы можем сделать. Один из них — применение подсчета ссылок на объекты. Однако, мы должны защитить сам счетчик ссылок. К счастью, благодаря атомарным переменным, нам не нужно использовать мьютекс для защиты счетчика.

О том, как мы будем использовать атомарные переменные для подсчета ссылок на объекты

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

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

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

А если его счетчик ссылок больше, чем один? В этом случае мы должны ждать, пока счетчик ссылок потоков не станет нулевым. Но, как это сделать?

Ответить на этот вопрос может быть весьма сложно. Обычно я рассматриваю один из двух подходов. Наивный подход или подход, который я называю подходом RCU (Read-copy update – прим. пер.).

Наивный подход

Наивный подход выглядит следующим образом. Мы создаем список объектов, которые хотим удалить. Каждый раз, когда активируется поток стирателя, он проходит по списку и удаляет все объекты, чей счетчик ссылок равен нулю.

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

Подход RCU

RCU — это другой механизм синхронизации. В основном он используется в ядре Linux. Можете прочитать о нем здесь. Я называю это подходом RCU, потому что у него есть некоторое сходство с тем, как работает механизм синхронизации RCU.

Идея исходит из предположения, что потоку манипулятора требуется некоторое время на работу с объектом. То есть, в основном, манипулятор продолжает использовать объект в течение определенного времени. После этого периода времени, объект должен перестать быть используемым и у потока стирателя должна быть возможность его удаления.

Допустим, что потоку манипулятора в основном требуется одна минута для выполнения своих манипуляций. Здесь я специально преувеличиваю. Когда поток стирателя попытается удалить объект, все что он должен сделать — это захватить мьютекс или spinlock, защищающий структуру данных, содержащую объекты, и удалить объект из этой структуры данных.

Далее, он должен получить текущее время и сохранить его в объекте. У объекта должны быть методы, позволяющие вспомнить время собственного удаления. Затем поток стирателя добавит его в конец списка удаленных объектов. Это особый список, который содержит все объекты, которые мы хотим удалить — так же, как и в наивном подходе.

Обратите внимание, что добавление объектов в конец списка делает их отсортированными по времени их удаления. Более ранние в списке те объекты, у которых раньше время удаления.

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

Чтобы показать, как это работает, посмотрите на рисунок выше. Допустим, сейчас 15:35:12. Это больше, чем одна минута после того, как мы удалили первый объект. Поэтому, как только стиратель активируется и проверит список, он сразу увидит, что первый объект в списке был удален больше минуты назад. Пришло время удалить объект из списка и проверить следующий.

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

Так что, вместо того, чтобы проходить через весь список, как мы это делали в наивном подходе, мы можем использовать временные метки (timestamps — прим.пер.) для создания отсортированного списка объектов и проверять только несколько объектов в начале списка. В зависимости от обстоятельств, это сэкономит массу времени.

Когда появились атомарные переменные?

Начиная с версии 4.1.2, у gcc есть встроенная поддержка атомарных переменных. Они работают на большинстве архитектур, но перед их использованием, пожалуйста, проверьте, что ваша архитектура их поддерживает.

Существует набор функций, оперирующих атомарными переменными.

type __sync_fetch_and_add (type *ptr, type value);
type __sync_fetch_and_sub (type *ptr, type value);
type __sync_fetch_and_or (type *ptr, type value);
type __sync_fetch_and_and (type *ptr, type value);
type __sync_fetch_and_xor (type *ptr, type value);
type __sync_fetch_and_nand (type *ptr, type value);

type __sync_add_and_fetch (type *ptr, type value);
type __sync_sub_and_fetch (type *ptr, type value);
type __sync_or_and_fetch (type *ptr, type value);
type __sync_and_and_fetch (type *ptr, type value);
type __sync_xor_and_fetch (type *ptr, type value);
type __sync_nand_and_fetch (type *ptr, type value);

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

Каждая из этих функций оперирует переменной определенного типа. Типом может быть как char, short, int, long, long long, так и их беззнаковые эквиваленты.

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

Наконец, есть мой хороший пример по использованию атомарных переменных в статье простой многопоточный тип доступа к данным и атомарные переменные.

Заключение

Надеюсь, что статья окажется интересной. Для дополнительных вопросов, пожалуйста, пишите на e-mail (указан в оригинале — прим. пер.).

Примечание переводчика

В дополнение к ссылке автора на документ по RCU стоит отметить проект Userspace RCU, реализующий RCU для userspace.

Автор: kpeo