Лекция по очереди Майкла Скотта и алгоритму RCU

Введение

• Завершение темы с очередью Майкла Скотта.
• Лог-фри алгоритмы.
• Обзор структуры очереди.

Очередь Майкла Скотта

• Тип очереди: FIFO (First In, First Out).
• Методы: NQ (enqueue), DQ (dequeue).
• Структура: включает один элемент-сентинел, ссылки на голову (head) и хвост (tail).
• Элементы: содержат данные и ссылку на следующий элемент (next).

Добавление элементов в очередь (enqueue)

• Создание нового элемента.
• Перенаправление указателя хвоста на новый элемент.
• Проблемы: блокировка потоков при добавлении.
  • Если поток засыпает, другой поток не знает, был ли добавлен элемент.
  • Возможные ситуации с недоступными элементами.

Удаление элементов из очереди (dequeue)

• Проверка пустоты очереди.
• Если голова и хвост равны, список пуст.
• Получение данных из головы и обновление ссылки.

Алгоритм RCU (Read-Copy-Update)

• Цель: обеспечить высокую производительность для множества читателей и редких писателей.
• Потоки читателей работают параллельно, не блокируя друг друга.
• Писатели могут работать с некоторыми ограничениями (например, могут быть менее производительными).

Этапы работы

1. Удаление элементов: изменение ссылок не блокирует читающие потоки.
2. Грейс-период: время ожидания завершения операций читателей перед фактическим удалением данных.
3. Синхронизация: писатели ждут, пока все читатели завершат свои операции.

Код реализации в ядре

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

Заключение

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

Вопросы и обсуждения

• Как улучшить производительность в многопоточном окружении?
• Возможности использования RCU в других языках программирования (например, Java).