• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта
Бакалавриат 2020/2021

Теория и практика многопоточной синхронизации

Лучший по критерию «Полезность курса для Вашей будущей карьеры»
Лучший по критерию «Полезность курса для расширения кругозора и разностороннего развития»
Лучший по критерию «Новизна полученных знаний»
Направление: 01.03.02. Прикладная математика и информатика
Когда читается: 3-й курс, 3, 4 модуль
Формат изучения: без онлайн-курса
Язык: русский
Кредиты: 6

Программа дисциплины

Аннотация

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

Цель освоения дисциплины

  • Изучить основные выразительные средства асинхронного программирования (файберы, futures/promises, корутины)
  • Сориентировать студента в подходах, которые применяются для работы с concurrency/асинхронностью в современных ЯП (C++, Golang, Rust, Java, Kotlin)
  • Изучить инженерную сторону конкурентности: механика исполнения потоков, механика корутин, реализация моделей памяти, когерентность кэшей процессора и т.п.
  • Познакомить студента с техниками тестирования и верификации конкурентных программ (sanitizers, fault injection, model checking)
  • Научить студента проводить формальные рассуждения о корректности синхронизации с помощью гарантий моделей памяти.
Планируемые результаты обучения

Планируемые результаты обучения

  • Студент владеет современными инструментами тестирования и верификации многопоточного кода, может доказывать корректность программ с помощью моделей памяти.
  • Студент владеет базовыми инструментами синхронизации потоков, как блокирующими (мьютексы/спинлоки/кондвары), так и неблокирующими (lock-free)
  • Студент понимает низкоуровневую механику конкурентного исполнения
  • Студент умеет писать современный конкурентный код с помощью файберов, futures/promises, корутин
Содержание учебной дисциплины

Содержание учебной дисциплины

  • Введение
    Concurrency и параллелизм, и отношения между ними, контексты возникновения concurrency: процессоры, операционные системы, сетевые сервисы, базы данных, распределенные системы.
  • Взаимное исключение
    Задача взаимного исключения, мотивирующие примеры. Гарантии взаимного исключения: deadlock freedom (safety), starvation freedom (liveness). Проблемы со взаимными блокировками: deadlock, livelock. Работа с блокировками в коде, RAII. Peterson lock - простейший протокол для двух потоков, масштабирование на произвольное число потоков. Атомарные RMW-операции и спинлоки: 1) операция exchange и TaS-спинлок 2) операция fetch_add и ticket lock. Реализация ожидания: инструкция pause, системный вызов sched_yield, системный вызов futex. Применение мьютексов и спинлоков.
  • Механика потоков
    Поток управления (control flow), циклы и вызов функций, call/ret, стек вызовов. Файберы - кооперативные потоки в пространстве пользователя. Базовый API: Spawn, Yield, семантика. Кооперативность и I/O. Нативные потоки как виртуальные ядра процессора. Составные части файбера: исполняемая функция, стек вызовов, контекст исполнения. Процедура переключения контекста. Очередь на запуск и планировщик, переключение между файберами через планировщик, цикл планировщика. Процедура переключения контекста с точки зрения ассемблера и с точки зрения файбера/планировщика. Механика переключения контекста. Кооперативность и callee-saved регистры. Сохранение регистров на стек. Завершение потока, трамплин. Намеренно за скобками - многопоточность, устройство планировщика.
  • Когерентность кэшей
    Работа процессора с памятью, кэши, иерархия памяти, паттерны доступа, numbers everyone should know. Задача синхронизации кэшей, протоколы когерентности MSI, MESI. Стоимость синхронизации с точки зрения протокола когерентности.
  • Модели памяти
    Мотивация: store buffering в процессорах, наблюдаемые программой реордеринги. Вопросы, на которые отвечает модель памяти. Примеры определения моделей памяти в разных языках программирования. Подходы к формальному описанию моделей памяти: операционный, трансформационный, декларативный. Декларативный подход, исполнение как граф с частичными порядками, примеры. Последовательная согласованность. Барьеры памяти. Локальность реордерингов / барьеров и глобальные гарантии порядка. Компромисс: последовательная согласованность для программ без гонок. Поиск достаточных гарантий для видимости последовательной согласованности. Разделение всех обращений / переменных на атомики и не-атомики. Последовательная согласованность для атомиков. Упорядочивание обращений к не-атомикам через атомики. Наблюдаемый порядок и причинность. Happens-before, program order и synchronizes-with, видимость через happens-before, определение data race. Видимость глобального порядка обращений к памяти. Оптимизации, допустимые в SC-DRF, локальность оптимизаций. Реализация модели памяти, схемы компиляции. Слабые (weak) модели памяти. Упорядочивание release/acquire и его стоимость на разных архитектурах. Упорядочивание relaxed и его гарантии. Паттерны применения слабых моделей памяти. Проблемы разработки моделей памяти: 1) Различные варианты Happens-Before в C++ MM. 2) Нерешенная проблема слабых моделей памяти С++ – OoTA. Поиск data races в исполнениях, алгоритм работы thread sanitizer-а.
  • Futures/Promises
    Асинхронные операции, future/promise как простой канал для возврата асинхронного результата. Возврат значения из задачи в пуле потоков с помощью фьючи. Блокирующее ожидание. Result<T>. Источники фьюч: RPC, запросы к базе данных. Проблема блокирующего API. Задача последовательной композиции асинхронных функций и ограниченное число нативных потоков. Future - как абстракция будущего результата, который можно передать в следующий вызов до завершения предыдущего, Then. Реализация Then через подписку на завершение, операция Subscribe. Гонка между Set и Subscribe, недетерминизм при запуске коллбэка, последствия для промышленного кода. Абстракция экзекутора и привязка экзекутора к фьюче. Комбинаторы: Any, FirstOf, Quorum. Декомпозиция на декларативный язык композиции (комбинаторы) и среду исполнения. Конкурентные активности как графы, описываемые комбинаторами фьюч, и исполняемые без блокирующего ожидания рантаймом.
  • Non-blocking synchronization
    Прогресс операций в случае паузы потока, идея неблокирующей синхронизации, гарантии lock-freedom и wait-freedom. Параллель между гарантиями прогресса блокирующей и неблокирующей синхронизации, гарантии планировщика. Предположение об аллокаторе памяти. Невозможность использовать блокировки. Основной инструмент – операция Сompare-And-Set (CAS). Структуры данных: 1) Trieber lock-free stack. Применения lock-free стека в промышленных задачах. Операция Push, CAS loop. Операция Pop и проблема управления памятью. 2) Michael/Scott lock-free очередь, техника helping. Управление памятью в lock-free структурах данных: Языки с автоматической сборкой мусора. Невозможность использования shared_ptr при конкуренции копирования / перезаписи. Переиспользование узлов и сценарий A-B-A. Пример сложного lock-free бага в аллокаторе памяти. Более сложные техники управления памятью: hazard pointers, deferred reference counting (atomic_shared_ptr).
  • Устройство планировщика
    Лекции про файберы / фьючи - как выражать конкурентные активности в коде. Лекция про планировщик - как их эффективно исполнять. Неэффективность простого пула потоков для исполнения файберов. Промышленный пример – планировщик горутин в языке Golang. О бщая идея дизайна – шардирование состояния планировщика, локальная очередь на каждый поток-носитель горутин, проблема балансировки нагрузки. Системные вызовы, сущности G, M, P. Разделение обязанностей: М отвечает за исполнение, P – за состояние (очередь задач, кэш аллокатора). Работа планировщика с двух сторон: 1) планирование горутины на запуск: yield / старт новой горутины / пробуждение ждущей горутины 2) выбор очередной горутины при освобождении потока. Локальная очередь как циклический буфер, переполнение локальной очереди и выгрузка задач в глобальную очередь. Запуск очередной задачи – извлечение из локальной очереди. Сценарий голодания, периодический polling глобальной очереди. Work stealing, lock-free реализация. Проблема ABA? Fifo и Lifo планирование – честность и производительность, мотивация для Lifo – каналы. Lifo-слот перед циклической Fifo-очередью. Вытеснение в точках обращения к рантайму.
  • Корутины (Сопрограммы)
    Обзор выразительных средств для описания конкурирующих активностей: коллбэки, futures/promises и асинхронные пайплайны, файберы. Общая механика исполнения – экзекуторы и таски. Сравнение эффективности. Неоптимальность файберов - преаллокация стека фиксированного размера. Понятие stackless coroutine, реализация на уровне компилятора: трансформация функции в автомат. Точки остановки корутины - точки ожидания IO. Маркировка точек остановки для компилятора, оператор co_await. Мета-алгоритм co_await: awaiter, await_suspend / await_resume / await_ready. Примеры awaiter-ов: для сокетов asio, для future из folly, для запуска задачи в пуле потоков. Запуск корутины и возвращаемое значение, два взгляда. Управляющий компонент корутины – promise. Блокировка всего стека вызовов в файбере и блокировка одного вызова в корутине. Синие и красные функции, What colour is your function, синтаксическое заражение. Граница между корутиной и не-корутиной, возврат фьючи и неоптимальность такого дизайна. Ортогональность корутин как языковой фичи и среды исполнения. Неявная механика – мета-алгоритм, awaiter-ы, прикладной код. Критика Coroutines TS, Core coroutines.
  • Сравнение современных подходов к concurrency в различных языках программирования: C++, Golang, Java, Kotlin, Rust.
  • Конкурентная сборка мусора | Сила атомарных операций, задача консенсуса и consensus number для атомарных операций, wait-free иерархия.
Элементы контроля

Элементы контроля

  • неблокирующий Домашние задания
  • неблокирующий Домашние задания
Промежуточная аттестация

Промежуточная аттестация

  • Промежуточная аттестация (4 модуль)
    0.5 * Домашние задания + 0.5 * Домашние задания
Список литературы

Список литературы

Рекомендуемая основная литература

  • Shalev, O., & Shavit, N. (2006). Split-Ordered Lists: Lock-Free Extensible Hash Tables. Journal of the ACM, 53(3), 397–405.

Рекомендуемая дополнительная литература

  • Paul E. Mckenney. (2010). Memory Barriers: a Hardware View for Software Hackers. Http://Www.Rdrop.Com/Users/Paulmck/Scalability/Paper/Whymb.2010.06.14a.Pdf.