Доступ к одим и тем же данным в нескольких потоках считается плохой практикой, но во многих случаях это неизбежно, и это не тот вопрос, который обсуждается здесь. Вопрос который здесь обсуждается, это как организовать такой доступ наиболее безопасным способом. Также тут не обсуждаются атомарные операции, которые тут упоминаются: разные компиляторы предлагают различные средства для таких операций.
В многопоточной среде при использовании объекта или структуры данных, один из главных вопросов, помимо прочего, это гарантия того, что объект к которому производится доступ все еще жив и память, выделенная для структуры не освобождена.
Это может быть сделано несколькими способами, но мы будем говорить только о двух из них: хэндлы (handles) и встроенные счётчики ссылок (intrusive reference counters).
Хэндлы — это небольшие структуры, которые содержат указатель на объект данных и вспомогательные данные, чтобы гарантировать, что объект еще жив. Как правило для работы с хэндлами пишутся две функции: lock_handle и unlock_handle (имена выбраны произвольно, чтобы показать функциональность). Lock_handle проверяет «живость» объекта, увеличивает атомарный счетчик ссылок и возвращает указатель на объект данных, если он ещё доступен. Если нет, то функция возвращает NULL, или с помощью другого способа даёт знать, что объект больше не доступен. Соответственно своему названию, unlock_handle атомарно уменьшает счетчик ссылок и как только он достигает значения 0, удаляет объект.
Встроенные счетчики ссылок — это атомарные числовые переменные внутри объекта данных, которые считают количество ссылок в программе на указанный объект данных. Как только счетчик ссылок достигает значения 0, объект удаляется.
Теперь давайте взглянем на преимущества и распространенные ошибки обеих стратегий и определим, какую из них лучше использовать в конкретных случаях. Сперва давайте разберемся с встроенными счетчиками ссылок.
Встроенные счетчики ссылок, как понятно из названия, должны быть встроены в структуру данных: это атомарное целое число. В простой структуре, назовем ее data_packet_s, подобная модификация может выглядеть так:
=>
Именно это является главным недостатком этого подхода: он нуждается в модификации структуры данных, поэтому использовать его можно только для таких структур, которые мы можем изменить. Мы не можем использовать его с произвольным типом данных или структурами, например, библиотечными.
Любопытно, но это же факт является и преимуществом. Преимущество состоит в том, что нам не нужны никакие дополнительные структуры и дополнительное выделение памяти для подобных структур.
Еще один недостаток, или, скорее, специфика этого подхода заключается в следующем: доступность объекта должна быть гарантирована, когда происходит приращение счетчика ссылок. Другими словами, мы не можем просто хранить указатель на объект и дожидаться момента, когда мы хотим получить к нему доступ, и затем просто увеличить счетчик ссылок и далее работать с объектом, поскольку между моментом когда мы сохранили указатель и моментом когда мы начинаем использовать объект он может быть уничтожен, при этом уничтожается и счётчик ссылок. Давайте продемонстрируем простой случай такого события, используя простой условный язык.
В указанном случае, чтобы обеспечить целостность объекта, придется увеличить количество ссылок в потоке 1 и передать полученную ссылку в собственность потоку 2 (уменьшать reference_count будет поток 2 после того как объект больше не нужен). Другими словами, эта схема может работать очень хорошо, если необходимо обработать объект в другом потоке, и забыть о нем. Это может быть продемонстрировано с помощью следующей иллюстрации:
Такая схема может быть использована любым количеством потоков при условии, что каждый поток, который увеличивает счетчик ссылок, уже владеет по крайней мере одним экземпляром-ссылкой (либо увеличил количество ссылок и не передал собственность, либо получил экземпляр-ссылку в собственность от другого потока). Таким образом, в последнем случае поток 1 может увеличить счетчик ссылок несколько раз (по одному для каждого потока) и лишь после этого он может запустить несколько потоков (столько, на сколько был увеличен счетчик ссылок.
Тут становится виден и второй недостаток: мы увеличивать и уменьшаем счетчик ссылок в разных потоках, что часто может приводить к различным ошибкам, начиная от утечек памяти когда ссылка не освобождается, заканчивая двойным освобождением ссылки и соответственно ложным освобождением объекта, что ведёт к его удалению во время того как он ещё используется в другом потоке или потоках.
Эта схема реализует так называемый «shared ownership», когда потоки совместно владеют объектом, и нить, уменьшающая счетчик ссылок до нуля, будет удалять объект.
И если вы хотите сохранить указатель на объект в одном из потоков, и использовать его при необходимости вы увидите, что память выделенная вашей программой будет расти с каждым хранящимся объектом, потому что поток никогда не освободит ссылку на объект, «живость» которого он хочет гарантировать.
Другая возможная ошибка в таком подходе это обращение к косвенно переданным объектам, то есть объектам, которые передаются по указателю, содержащемуся в одном из других, прямо или косвенно переданных объектов, которые ссылаются, но не владеют объектом. Все такие объекты должны быть известны, при этом должен быть обеспечен безопасный доступ ко всем подобным объектам, если они используются наряду с основным.
Итак, давайте просуммируем недостатки и преимущества встроенных счетчиков ссылок:
Недостатки:
Преимущества:
Хэндлы — это легкие структуры, которые передаются по значению, они ссылаются на объект, управляют ссылками и обеспечивают целостность объекта.
Очевидно, что хэндлы, которые ссылаются на один и тот же объект, будут иметь указатель на один счетчик ссылок. Как правило, это означает, что счетчик ссылок должен быть выделен на куче динамически. Простейшая структура хэндла, которая первой приходит на ум, может выглядеть так:
Где reference_count выделяется при создании первого хэндла на данный объект.
Первый недостаток такого подхода уже очевиден. Мы должны управлять еще одной дополнительной структурой, выделять еще одну область памяти для счетчика ссылок. Но это окупается, если вы хотите использовать подсчет ссылок со структурами, к которым вы не имеете доступа.
Типичное применение такого хэндла будет следующим:
Давайте посмотрим, что происходит, когда последняя ссылка на объект удалена. Прежде всего, мы, очевидно, хотим, чтобы удалился управляемый объект. Если объект является простым куском выделенной памяти, мы просто хотим, чтобы память, используемая объектом была освобождена. Но в большинстве случаев это не так. Как и в вышеупомянутом примере data_packet_s, где мы хотели бы освободить также и память data_buffer. Если мы используем хэндл для только одного типа объектов, это не создаёт большой проблемы. Но если мы хотим, чтобы хэндл мог обрабатывать разыличные типы, это привносит ещё один вопрос: как правильно удалить управляемый объект?
Мы можем добавить в хэндл ещё одно поле: указатель на функцию, которая будет использоваться для уничтожения/освобождения управляемого объекта. Теперь хэндл выглядит следующим образом:
Теперь release_handle не обязательно знать специфику объекта, чтобы удалить его, он просто будет использовать функцию, которую мы сохранили в хэндле, так что давайте вернёмся к тому, что происходит, когда последняя ссылка будет освобождена.
После этого мы хотели бы освободить память, которая содержит reference_count. Но не тут то было: сделать это будет ужасной ошибкой. Если другие хэндлы на этот же объект до сих пор хранятся в других потоках, после освобождения памяти они будут ссылаться на reference_count, который уже удален. А на следующей попытке получить доступ к объекту, мы будем иметь попытку обращения к освобожденной памяти.
Есть ли решение, которое позволило бы не допустить утечки памяти но при этом избежать обращений к освобождённой памяти счетчиков ссылок? Такой способ есть. Это пул объектов, который будут управлять освобожденными счетчиками. И вот тут-то и появляется проблема, найти которую может быть довольно непросто, и которая известна как «проблема ABA». Представьте себе, ситуацию, когда у вас есть хэндл на объект. Один из потоков удаляет объект. Затем конструируется другой объект, и для него создается управляющих хэндл. Что при этом произойдет?
Когда объект уничтожен, reference_count связанный с данным объектом (назовем его object1) освобождается обратно в пул объектов со значением 0. Пока что всё идёт по плану. Но когда выделяется другой хэндл для нового объекта (назовем его object2), то reference_count, который будет связан с этим объектом берется из пула объектов, при этом данный reference_count устанавливается в 1. Теперь представьте, что поток хранящий хэндл на object1 пытается получить указатель. Это удастся, потому что reference_count на который указывает данный хэндл уже не 0, хотя он и принадлежит теперь object2. Функция блокировки вернет неверный указатель, программа (если повезёт) потерпит крушение, или (если не повезёт) повредит содержимое памяти обращением к освобожденному участку.
Решение, разумеется, существует, иначе я бы не писал всё это.
Мы хотим сделать структуру handle_s настолько легкой, насколько это возможно, чтобы иметь возможность передать ее по значению, а не по указателю, так что сделаем следующее: создадим две структуры, одна из которых будет «слабым» хэндлом, то есть не ограничивать и не проверять объект, которым она управляет, а другой будет «сильным» хэндлом, т.е. таким, который будет иметь жесткую связь с конкретным управляемым объектом и вернет NULL, если «слабый» хэндл связанный с ним больше не ссылается на тот же объект.
Давайте определим их так:
Итак, как вы видите, теперь обе ручки имеют поле «version», и strong_handle_s уже не имеет указателя на объект, так как он теперь хранится в общем для объекта weak_handle_s.
Давайте посмотрим, как он защищает нас от проблемы ABA, показанной выше.
В strong_handle_s и weak_handle_s, которые ссылаются на один и тот же объект имеются поля «version», которые равны друг другу.
Всякий раз, когда ручка освобождается и weak_handle_s помещается обратно в пул объектов, мы будем увеличивать номер версии в weak_handle_s.
В следующий раз, если освобожденный в пул weak_handle_s переиспользуется для обработки другого объекта, он будет иметь номер версии, отличный от номера версии который был у объекта, который был освобожден. Теперь в функции lock_handle, сравнивая поля версии в обоих, «слабом» и «сильном» хэндле, мы можем сказать, ссылается ли weak_handle_s по-прежнему на тот объект, указатель которого мы пытаемся получить из strong_handle_s, и вернуть NULL, если это не так.
Так что, как мы видим, хэндлы приносят некоторые довольно сложные проблемы, но он также имеет и свои плюсы: хэндл может быть сохранен и забыт, пока нам не понадобится управляемый им объект; хэндл не является встроенным, что означает, что мы можем использовать его практически с любыми типами данных.
Кроме того, передача хэндла не обязательно означает передачу права собственности на объект, так что он может быть использован вместо указателя в качестве безопасной ссылки на объекты везде, где они не являются собственностью ссылающегося объекта (в структурах данных и т.д.).
Таким образом хэндлами сложнее управлять. Но и возможности их гораздо мощнее.
Недостатки:
Преимущества:
Встроенный счетчик ссылок реализует общие сильные ссылки (strong reference), которые должны удерживать счетчик ссылок, пока объект не будет гарантированно невостребован. Пока все ссылки не будут разлочены, объект не будет удален. Если ссылка разблокирована в потоке, который имел в собственности лишь одну ссылку, этот поток уже больше не сможет гарантированно безопасно получить еще одну ссылку.
Хэндл реализует общую слабую ссылку (weak reference). Если объект жив, функция lock_handle вернет указатель на запрашиваемый объект, и объект гарантированно не будет удален, пока хэндл не будет разлочен. Это безопасно для блокировки и разблокировки сколько угодно раз, так как хэндл является отдельным объектом, и гарантированно является валидным участком памяти. Соответствующие меры должны быть приняты, чтобы гарантировать, что разделяемая память счетчика ссылок не освобождается, когда объект достигает счетчика ссылок 0, и что повторно используемый счетчик ссылок не используется, чтобы проверить количество ссылок на уже освобожденные объекты.
В многопоточной среде при использовании объекта или структуры данных, один из главных вопросов, помимо прочего, это гарантия того, что объект к которому производится доступ все еще жив и память, выделенная для структуры не освобождена.
Это может быть сделано несколькими способами, но мы будем говорить только о двух из них: хэндлы (handles) и встроенные счётчики ссылок (intrusive reference counters).
Хэндлы — это небольшие структуры, которые содержат указатель на объект данных и вспомогательные данные, чтобы гарантировать, что объект еще жив. Как правило для работы с хэндлами пишутся две функции: lock_handle и unlock_handle (имена выбраны произвольно, чтобы показать функциональность). Lock_handle проверяет «живость» объекта, увеличивает атомарный счетчик ссылок и возвращает указатель на объект данных, если он ещё доступен. Если нет, то функция возвращает NULL, или с помощью другого способа даёт знать, что объект больше не доступен. Соответственно своему названию, unlock_handle атомарно уменьшает счетчик ссылок и как только он достигает значения 0, удаляет объект.
Встроенные счетчики ссылок — это атомарные числовые переменные внутри объекта данных, которые считают количество ссылок в программе на указанный объект данных. Как только счетчик ссылок достигает значения 0, объект удаляется.
Теперь давайте взглянем на преимущества и распространенные ошибки обеих стратегий и определим, какую из них лучше использовать в конкретных случаях. Сперва давайте разберемся с встроенными счетчиками ссылок.
Встроенные счетчики ссылок
Встроенные счетчики ссылок, как понятно из названия, должны быть встроены в структуру данных: это атомарное целое число. В простой структуре, назовем ее data_packet_s, подобная модификация может выглядеть так:
struct data_packet_s {
void *data_buffer;
size_t data_buffer_size;
};
=>
struct data_packet_s {
void *data_buffer;
size_t data_buffer_size;
volatile int reference_count;
};
Именно это является главным недостатком этого подхода: он нуждается в модификации структуры данных, поэтому использовать его можно только для таких структур, которые мы можем изменить. Мы не можем использовать его с произвольным типом данных или структурами, например, библиотечными.
Любопытно, но это же факт является и преимуществом. Преимущество состоит в том, что нам не нужны никакие дополнительные структуры и дополнительное выделение памяти для подобных структур.
Еще один недостаток, или, скорее, специфика этого подхода заключается в следующем: доступность объекта должна быть гарантирована, когда происходит приращение счетчика ссылок. Другими словами, мы не можем просто хранить указатель на объект и дожидаться момента, когда мы хотим получить к нему доступ, и затем просто увеличить счетчик ссылок и далее работать с объектом, поскольку между моментом когда мы сохранили указатель и моментом когда мы начинаем использовать объект он может быть уничтожен, при этом уничтожается и счётчик ссылок. Давайте продемонстрируем простой случай такого события, используя простой условный язык.
В указанном случае, чтобы обеспечить целостность объекта, придется увеличить количество ссылок в потоке 1 и передать полученную ссылку в собственность потоку 2 (уменьшать reference_count будет поток 2 после того как объект больше не нужен). Другими словами, эта схема может работать очень хорошо, если необходимо обработать объект в другом потоке, и забыть о нем. Это может быть продемонстрировано с помощью следующей иллюстрации:
Такая схема может быть использована любым количеством потоков при условии, что каждый поток, который увеличивает счетчик ссылок, уже владеет по крайней мере одним экземпляром-ссылкой (либо увеличил количество ссылок и не передал собственность, либо получил экземпляр-ссылку в собственность от другого потока). Таким образом, в последнем случае поток 1 может увеличить счетчик ссылок несколько раз (по одному для каждого потока) и лишь после этого он может запустить несколько потоков (столько, на сколько был увеличен счетчик ссылок.
Тут становится виден и второй недостаток: мы увеличивать и уменьшаем счетчик ссылок в разных потоках, что часто может приводить к различным ошибкам, начиная от утечек памяти когда ссылка не освобождается, заканчивая двойным освобождением ссылки и соответственно ложным освобождением объекта, что ведёт к его удалению во время того как он ещё используется в другом потоке или потоках.
Эта схема реализует так называемый «shared ownership», когда потоки совместно владеют объектом, и нить, уменьшающая счетчик ссылок до нуля, будет удалять объект.
И если вы хотите сохранить указатель на объект в одном из потоков, и использовать его при необходимости вы увидите, что память выделенная вашей программой будет расти с каждым хранящимся объектом, потому что поток никогда не освободит ссылку на объект, «живость» которого он хочет гарантировать.
Другая возможная ошибка в таком подходе это обращение к косвенно переданным объектам, то есть объектам, которые передаются по указателю, содержащемуся в одном из других, прямо или косвенно переданных объектов, которые ссылаются, но не владеют объектом. Все такие объекты должны быть известны, при этом должен быть обеспечен безопасный доступ ко всем подобным объектам, если они используются наряду с основным.
Итак, давайте просуммируем недостатки и преимущества встроенных счетчиков ссылок:
Недостатки:
- Встроенные счётчики требуют изменения структур данных
- Ссылка должна оставаться залоченной пока есть вероятность что объект будет использован
- Собственность ссылок передаётся между потоками
- Необходимо внимательное отношение к косвенно переданным объектам
Преимущества:
- Не требуются дополнительные структуры и операции с памятью
Хэндлы
Хэндлы — это легкие структуры, которые передаются по значению, они ссылаются на объект, управляют ссылками и обеспечивают целостность объекта.
Очевидно, что хэндлы, которые ссылаются на один и тот же объект, будут иметь указатель на один счетчик ссылок. Как правило, это означает, что счетчик ссылок должен быть выделен на куче динамически. Простейшая структура хэндла, которая первой приходит на ум, может выглядеть так:
struct handle_s {
volatile int *reference_count;
void *object;
};
Где reference_count выделяется при создании первого хэндла на данный объект.
Первый недостаток такого подхода уже очевиден. Мы должны управлять еще одной дополнительной структурой, выделять еще одну область памяти для счетчика ссылок. Но это окупается, если вы хотите использовать подсчет ссылок со структурами, к которым вы не имеете доступа.
Типичное применение такого хэндла будет следующим:
struct some_struct_s *object = lock_handle(hdata);
if(object) {
use(object);
release_handle(hdata);
};
Давайте посмотрим, что происходит, когда последняя ссылка на объект удалена. Прежде всего, мы, очевидно, хотим, чтобы удалился управляемый объект. Если объект является простым куском выделенной памяти, мы просто хотим, чтобы память, используемая объектом была освобождена. Но в большинстве случаев это не так. Как и в вышеупомянутом примере data_packet_s, где мы хотели бы освободить также и память data_buffer. Если мы используем хэндл для только одного типа объектов, это не создаёт большой проблемы. Но если мы хотим, чтобы хэндл мог обрабатывать разыличные типы, это привносит ещё один вопрос: как правильно удалить управляемый объект?
Мы можем добавить в хэндл ещё одно поле: указатель на функцию, которая будет использоваться для уничтожения/освобождения управляемого объекта. Теперь хэндл выглядит следующим образом:
struct handle_s {
volatile int *reference_count;
void *object;
void (*destroy_object)(void*);
};
Теперь release_handle не обязательно знать специфику объекта, чтобы удалить его, он просто будет использовать функцию, которую мы сохранили в хэндле, так что давайте вернёмся к тому, что происходит, когда последняя ссылка будет освобождена.
После этого мы хотели бы освободить память, которая содержит reference_count. Но не тут то было: сделать это будет ужасной ошибкой. Если другие хэндлы на этот же объект до сих пор хранятся в других потоках, после освобождения памяти они будут ссылаться на reference_count, который уже удален. А на следующей попытке получить доступ к объекту, мы будем иметь попытку обращения к освобожденной памяти.
Есть ли решение, которое позволило бы не допустить утечки памяти но при этом избежать обращений к освобождённой памяти счетчиков ссылок? Такой способ есть. Это пул объектов, который будут управлять освобожденными счетчиками. И вот тут-то и появляется проблема, найти которую может быть довольно непросто, и которая известна как «проблема ABA». Представьте себе, ситуацию, когда у вас есть хэндл на объект. Один из потоков удаляет объект. Затем конструируется другой объект, и для него создается управляющих хэндл. Что при этом произойдет?
Когда объект уничтожен, reference_count связанный с данным объектом (назовем его object1) освобождается обратно в пул объектов со значением 0. Пока что всё идёт по плану. Но когда выделяется другой хэндл для нового объекта (назовем его object2), то reference_count, который будет связан с этим объектом берется из пула объектов, при этом данный reference_count устанавливается в 1. Теперь представьте, что поток хранящий хэндл на object1 пытается получить указатель. Это удастся, потому что reference_count на который указывает данный хэндл уже не 0, хотя он и принадлежит теперь object2. Функция блокировки вернет неверный указатель, программа (если повезёт) потерпит крушение, или (если не повезёт) повредит содержимое памяти обращением к освобожденному участку.
Решение, разумеется, существует, иначе я бы не писал всё это.
Мы хотим сделать структуру handle_s настолько легкой, насколько это возможно, чтобы иметь возможность передать ее по значению, а не по указателю, так что сделаем следующее: создадим две структуры, одна из которых будет «слабым» хэндлом, то есть не ограничивать и не проверять объект, которым она управляет, а другой будет «сильным» хэндлом, т.е. таким, который будет иметь жесткую связь с конкретным управляемым объектом и вернет NULL, если «слабый» хэндл связанный с ним больше не ссылается на тот же объект.
Давайте определим их так:
struct weak_handle_s {
volatile int version;
volatile int reference_count;
void object;
void (*destroy_object)(void*);
};
struct strong_handle_s {
struct weak_handle_s *handle;
int version;
};
Итак, как вы видите, теперь обе ручки имеют поле «version», и strong_handle_s уже не имеет указателя на объект, так как он теперь хранится в общем для объекта weak_handle_s.
Давайте посмотрим, как он защищает нас от проблемы ABA, показанной выше.
В strong_handle_s и weak_handle_s, которые ссылаются на один и тот же объект имеются поля «version», которые равны друг другу.
Всякий раз, когда ручка освобождается и weak_handle_s помещается обратно в пул объектов, мы будем увеличивать номер версии в weak_handle_s.
В следующий раз, если освобожденный в пул weak_handle_s переиспользуется для обработки другого объекта, он будет иметь номер версии, отличный от номера версии который был у объекта, который был освобожден. Теперь в функции lock_handle, сравнивая поля версии в обоих, «слабом» и «сильном» хэндле, мы можем сказать, ссылается ли weak_handle_s по-прежнему на тот объект, указатель которого мы пытаемся получить из strong_handle_s, и вернуть NULL, если это не так.
Так что, как мы видим, хэндлы приносят некоторые довольно сложные проблемы, но он также имеет и свои плюсы: хэндл может быть сохранен и забыт, пока нам не понадобится управляемый им объект; хэндл не является встроенным, что означает, что мы можем использовать его практически с любыми типами данных.
Кроме того, передача хэндла не обязательно означает передачу права собственности на объект, так что он может быть использован вместо указателя в качестве безопасной ссылки на объекты везде, где они не являются собственностью ссылающегося объекта (в структурах данных и т.д.).
Таким образом хэндлами сложнее управлять. Но и возможности их гораздо мощнее.
Недостатки:
- Нуждается в дополнительной структуре и памяти.
- Занимает дополнительное время процессора
- Добавляет некоторые неочевидные проблемы
Преимущества:
- Позволяет сохранять хэндлы и иметь к ним доступ по мере необходимости.
- Не требует того, чтобы объект постоянно находился в собственности.
Выводы
Встроенный счетчик ссылок реализует общие сильные ссылки (strong reference), которые должны удерживать счетчик ссылок, пока объект не будет гарантированно невостребован. Пока все ссылки не будут разлочены, объект не будет удален. Если ссылка разблокирована в потоке, который имел в собственности лишь одну ссылку, этот поток уже больше не сможет гарантированно безопасно получить еще одну ссылку.
Хэндл реализует общую слабую ссылку (weak reference). Если объект жив, функция lock_handle вернет указатель на запрашиваемый объект, и объект гарантированно не будет удален, пока хэндл не будет разлочен. Это безопасно для блокировки и разблокировки сколько угодно раз, так как хэндл является отдельным объектом, и гарантированно является валидным участком памяти. Соответствующие меры должны быть приняты, чтобы гарантировать, что разделяемая память счетчика ссылок не освобождается, когда объект достигает счетчика ссылок 0, и что повторно используемый счетчик ссылок не используется, чтобы проверить количество ссылок на уже освобожденные объекты.
