Введение в линеаризуемость и свободную от блокировок структуру данных Сегодняшнее занятие будет посвящено концепциям линеаризуемости и двум фундаментальным структурам данных в программировании без блокировок. Мы рассмотрим их на слайдах, рассматривая детали их реализации.
Стек Трейбера: Объяснены операции Push и Pop-доступа Первая обсуждаемая структура - это стек Treiber's stack, простой стек на основе связанных списков с атомарными операциями для перемещения элементов. Операция перемещения включает в себя создание нового узла, присвоение ему значения, а затем попытку замены верхнего указателя до тех пор, пока она не завершится успешно. Аналогично, pop считывает верхний элемент; если он не пуст, он пытается обновить верхний указатель атомарно.
"Корректность" В сценариях вытеснения потоков Важным аспектом параллельных алгоритмов является обеспечение корректности, даже если потоки неожиданно выгружаются или задерживаются. Например, проверка пустого стека может привести к ложноотрицательным результатам из—за того, что другие потоки добавляют элементы в периоды ожидания - такое поведение должно учитываться при проектировании.
Диаграммы "Частичного порядка", Иллюстрирующие Поведение атомарных счетчиков Атомарные счетчики представляют собой еще один пример, когда несколько потоков увеличивают значения одновременно, не пропуская ни одного приращения, несмотря на перекрывающееся время выполнения — концепция, иллюстрируемая диаграммами частичного порядка, показывающими взаимодействие потоков с течением времени.
Блокирование вызовов в многопоточных структурах данных В многопоточных структурах данных блокирующие вызовы необходимы для обеспечения завершения операций перед выходом из функции. Этот подход вводит концепцию объединяющего потока, который объединяет задачи из других потоков и выполняет их последовательно.
Эффективность резьбы комбайнера Объединяющий поток иногда может обеспечить более высокую производительность, чем методы грубой синхронизации, за счет эффективного управления выполнением задач без частого переключения контекста или конфликтов между несколькими потоками.
Универсальный класс для агрегирования задач Универсальный класс может агрегировать любую структуру данных, используя примитивы синхронизации, чтобы гарантировать, что одновременно активен только один объединитель. Задачи регистрируются в этом фреймворке и выполняются либо самим объединителем, либо в ожидании, пока это сделает другой поток.
Метод оптимизации "аннигиляции" Оптимизация "Уничтожение" позволяет перестраивать операции в списке публикаций, например отменять противоположные действия (например, нажатие, за которым следует pop) без изменения фактического состояния стека. Это сокращает ненужную работу и повышает эффективность.
Стратегия оптимизации "пакетной вставки" Другая оптимизация заключается в пакетной вставке, при которой несколько элементов вставляются вместе, если это поддерживается API базовой структуры данных. Это минимизирует накладные расходы по сравнению с отдельными вставками, выполняемыми по отдельности.