- •Национальный исследовательский ядерный университет «мифи»
- •Пояснительная записка к дипломному проекту на тему:
- •Глава 1. Обзор методов и средств многопоточного взаимодействия 7
- •Глава 2. Разработка структуры и алгоритмов взаимодействия 29
- •Глава 3. Реализация и тестирование разработанных структур и алгоритмов взаимодействия 53
- •Введение
- •Глава 1. Обзор методов и средств многопоточного взаимодействия
- •1.1. Блокирующая синхронизация
- •1.2. Неблокирующая синхронизация
- •1.2.1. Общие сведения
- •1.2.2. Принципы неблокирующих алгоритмов Узлы неизменяемого типа
- •Подмена указателей
- •Атомарные операции
- •Специальные методы управления памятью
- •1.2.3. Обзор специальных методов управления памятью Метод использования специальных тегов
- •Метод неблокирующего подсчета ссылок
- •Метод опасных указателей
- •1.2.4. Оценка эффективности методов
- •1.2.5. Типы алгоритмов для неблокирующей синхронизации
- •1.3. Выводы
- •Глава 2. Разработка структуры и алгоритмов взаимодействия
- •2.1. Требования к разрабатываемой структуре данных и обоснование выбранных методов реализации
- •2.2. Обзор существующих неблокирующих структур
- •2.3. Разработка структуры данных
- •2.4. Разработка алгоритмов
- •2.4.1. Алгоритм записи
- •2.4.2. Алгоритм чтения
- •Метод неблокирующего подсчёта ссылок
- •Метод опасных указателей
- •2.4.3. Алгоритм освобождения памяти
- •Метод неблокирующего подсчёта ссылок
- •Метод опасных указателей
- •2.4.4. Алгоритм добавления и удаления опасных указателей
- •Глава 3. Реализация и тестирование разработанных структур и алгоритмов взаимодействия
- •3.1. Особенности программной реализации
- •3.2. Тестирование разработанных алгоритмов
- •3.3. Тестирование разработанной структуры при многопоточном доступе
- •3.4. Сравнение структур по временным характеристикам
- •Заключение
- •Список литературы
1.2.3. Обзор специальных методов управления памятью Метод использования специальных тегов
Метод использования специальных тегов (счетчиков изменений) является самым ранним и наиболее простым неблокирующим методом повторного использования памяти узлов. Он требует, чтобы с каждым адресом памяти, который может быть использован в операции сравнения с ожидаемым значением, подверженной ABA-проблеме, был ассоциирован специальный тег. Увеличение значение тега в момент, когда происходит запись значения по соответствующему адресу, позволяет операциям сравнения (например, CAS) определить, было ли произведено изменение с момента последнего чтения значения тем же потоком. Таким образом, проблема ABA устраняется. Данный метод требует, чтобы тег имел достаточную разрядность для того, чтобы полный цикл инкрементации был невозможен за время выполнения любой единичной неблокирующей операции. Этот метод очень эффективен и позволяет немедленное освобождение памяти узлов или их повторное использование.
Однако его недостаток заключается в том, что для применения к произвольным указателям, как в случае с объектами динамического размера, он требует наличия инструкций двойной разрядности DCAS (Double-CAS, подробнее – в работе [3]), которые выполняют CAS для двух независимых областей памяти, что дает возможность выполнять атомарные операции как с указателем, так и с его ассоциированным тегом. Эти инструкции совсем не поддерживаются в 64-разрядных архитектурах и в большинстве 32-разрядных. Кроме того, семантика тегового поля должна сохраняться постоянно. Таким образом, если тег является частью динамической структуры узлов, повторное использование таких узлов затрудняется. Их память не может быть поделена или объединена, поскольку это может привести к изменению семантики теговых полей. Это значит, то коль скоро некая область памяти была использована для определенного типа узлов, она не может уже быть повторно использована для другого типа узлов, которые не сохраняют семантику теговых полей. Таким образом, данный метод является, по сути, аппаратным решением, в связи с чем от его дальнейшего рассмотрения приходится отказаться.
Метод неблокирующего подсчета ссылок
Метод неблокирующего подсчета ссылок, описанный в работе [1], требует включения в структуру динамического узла специального счетчика ссылок, отражающего текущее число ссылок на данный узел структуры и локальных переменных потоков, оперирующих данной структурой. Каждый раз, когда получается, либо удаляется новая ссылка на динамический узел, счетчик ссылок должен быть увеличен, либо уменьшен, используя инструкцию fetch-and-addилиcompare-and-swap. Только в том случае, если счетчик ссылок равен нулю, узел может быть повторно использован.
Как и в случае метода специальных тегов (счетчиков изменений), методу неблокирующего подсчёта ссылок требуется наличие операции DCAS для атомарного манипулирования одновременно указателями и счетчиками ссылок, которая не поддерживаются в 64-разрядных архитектурах и в большинстве 32-разрядных. Используя такую операцию можно гарантировать, что счетчик ссылок никогда не будет иметь значение, меньшее реального числа ссылок. Однако возможна реализация, в которой манипулирование указателями и, одновременно, независимо расположенными счетчиками ссылок одноадресной операцией CAS производится в неатомарном режиме, но в таком случае могут произойти следующие ситуации:
Если поток вначале увеличивает счётчик ссылок, а потом получает указатель, то может получиться, что в промежуток между этими двумя операциями другой поток уже изменил указатель. В результате первый поток получает уже другой указатель, а в памяти остается структура, которая не будет удалена, так как счётчик ссылок будет равен минимум единице.
Если поток вначале получает указатель, а потом увеличивает счётчик, то может получиться, что в промежуток времени между этими двумя операциями другой поток уже удалил структуру, указатель на которую получил первый поток. В результате первый поток получит ошибку при попытке увеличить указатель или увеличит какие-то неизвестные данные, что приведёт либо к ошибке, либо к тому, что потоки будут работать с некорректными данными.
В связи с этим необходимы дополнительные проверки корректности счётчиков и указателей.