Datenlord | Анализ алгоритма Crossbeam Epoch для Rust Lock-Free Programming

Автор: Ши Цзичэн

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

Гвардия - это всего лишь самая внешняя оболочка

подобноПреамбулаКак уже упоминалось, люди обычно используют защиту только при взаимодействии с Crossbeam-epoch, а именно:

/// delete data
{
    let guard = epoch::pin();
    guard.defer(move || mem.release());
}

/// get data for reading
{
    let guard = epoch::pin();
    let value = map.get(&key, &guard);
    /// ... Use the value
}

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

что именно сделал Пин

Что именно делает epoch::pin(), объясняется в официальных комментариях к коду, то есть закрепляет текущий поток, чтобы поместить указатель данных на кучу в стеке. На самом деле, это объяснение только объясняет содержание вышеупомянутых данных чтения, а лежащие в их основе операции таковы:

Регистрирует текущий поток в глобальном коллекторе.Этот процесс регистрации выполняется только один раз для каждого потока.
Получите текущую глобальную эпоху и установите ее для текущего потока, указав, к какой эпохе принадлежит текущий поток в течение периода, когда контакт действителен.
Запишите, сколько раз текущий поток был закреплен. Когда количество раз достигнет определенного числа, попробуйте позволить глобальному сборщику продвинуть рост эпохи и собрать мусор.
Увеличивайте счетчик guard_count, чтобы отслеживать, сколько охранников было создано, а не уничтожено.

Так как pin() может вызываться повторно, два последовательных вызова epoch::pin() также разрешены. За исключением первого вызова, другие вызовы не будут иметь никакого эффекта, просто увеличьте счетчик guard_count. Конкретную реализацию см.internal.rsв файлеLocalструктураpinметод.

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

Эпоха продвижения

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

Все зарегистрированные потоки находятся в текущей эпохе, то есть ни один поток не находится в предыдущей эпохе.

Продвижение по эпохе не выполняется, если условие не выполняется. Конкретную реализацию см.internal.rsв файлеGlobalструктураtry_advanceметод.

механизм сбора мусора

Если все потоки будут регистрировать мусор для сбора с помощью глобального сборщика, возникнет огромная конкуренция: чем больше потоков и чем чаще выполняются операции, тем больше влияние на производительность. Чтобы решить конфликт, вызванный общей структурой данных, каждый поток будет поддерживать свою собственную очередь сборки мусора, длина очереди составляет 62 (связаны с магическим числом, предположением и строкой кэша ЦП). Когда очередь заполнится, поток равномерно переместит данные из локальной очереди в глобальный сборщик и поместит их в список мусора сборщика. Здесь стоит отметить, что в дополнение к функции сборки мусора существует также Число Эпох, сгенерированное мусором, которое используется для определения возможности переработки соответствующего мусора.

Есть две триггерные точки для сборки мусора, одна активная и одна пассивная. Активной точкой срабатывания является метод очистки Guard, и вызов этого метода приведет к тому, что глобальный сборщик попытается собрать мусор в списке мусора. Пассивная точка срабатывания — это метод булавки Guard, то есть сборка мусора запускается каждые 128 раз, когда вызывается булавка.

Мусор, отвечающий следующим условиям, может быть переработан:

(Глобальный Номер Эпохи) > ((Номер Эпохи Мусора) + 1), то есть Эпоха, соответствующая мусору, по крайней мере на два поколения раньше, чем текущая Эпоха.

Конкретную реализацию см.internal.rsв файлеGlobalструктураcollectметод.

внутренняя структура данных

Стоит упомянуть его внутреннюю структуру данных, что их две: Список и Очередь. List используется для управления зарегистрированными потоками, а Queue используется для управления мусором, ожидающим сбора. Общим моментом этих двух структур данных является то, что они управляются несколькими потоками одновременно.Для эффективной реализации crossbeam не использует Lock для защиты структуры данных, а реализует внутреннюю структуру данных без блокировок.

List

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

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

Конкретную реализацию см.list.rsдокумент.

Queue

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

А как насчет тех элементов, которые удалены из списка и очереди? Crossbeam использует метод начальной загрузки, то есть также ставится в очередь сборки мусора, ожидая последующей операции, которая вызовет сборку мусора.

Суммировать

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