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

Бакалавриат 2023/2024

Статус: Курс обязательный (Прикладная математика и информатика)

Направление: 01.03.02. Прикладная математика и информатика

Кто читает: Департамент больших данных и информационного поиска

Где читается: Факультет компьютерных наук

Когда читается: 3-й курс, 3, 4 модуль

Формат изучения: без онлайн-курса

Охват аудитории: для своего кампуса

Преподаватели: Липовский Роман Германович

Язык: русский

Кредиты: 6

Контактные часы: 80

Полная версия программы учебной дисциплины

Аннотация

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

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

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

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

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

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

Введение
Взаимное исключение
Механика потоков
Когерентность кэшей
Модели памяти
Futures/Promises
Non-blocking synchronization
Устройство планировщика
Корутины (Сопрограммы)
Сравнение современных подходов к concurrency в различных языках программирования: C++, Golang, Java, Kotlin, Rust.
Конкурентная сборка мусора | Сила атомарных операций, задача консенсуса и consensus number для атомарных операций, wait-free иерархия.

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

Домашние задания
В ходе семестра вам будет предложено X домашних заданий, в каждом задании будет несколько задач. Стоимости У каждой задачи будет своя стоимость в баллах. У каждого домашнего задания (и иногда – у отдельных задач) будет дедлайн, после которого стоимость задач снижается. Лимиты У каждого домашнего задания будет лимит в баллах. Иногда он будет равен сумме баллов за отдельные задачи, а иногда суммарная стоимость задач будет чуть выше, чтобы можно было добирать баллы после дедлайна. Дедлайны Стандартный дедлайн на домашнее задание – 2 недели. После дедлайна в течение недели стоимость задач линейно падает в два раза. После этого стоимость задачи не меняется. Домашние задания будут наслаиваться друг на друга, будьте к этому готовы и планируйте свое время. Не оставляйте решение домашнего задания на последние выходные перед дедлайном! Защита Чтобы задача была зачтена, мало написать код и пройти тесты, нужно защитить задачу. Формат защиты остается на усмотрение семинариста, но в самом общем виде процедуру можно описать так: семинарист атакует вас каверзными вопросами на понимание тонкостей задачи и решает, достаточно ли вашего понимания или нет. На защиту тоже устанавливается дедлайн. Сделано это для того, чтобы: Нагрузка на семинаристов и ассистентов распределялась равномерно в течение семестра Вы не успевали забывать решения собственных задач Базовая оценка В конце семестра баллы за все домашние задания суммируются, после чего результат нормируется в базовую оценку от 0 до 8 баллов. Точные правила округления будут известны во второй половине семестра, но можно сказать сразу, что выбить 8 баллов на этом этапе будет крайне сложно, для этого придется прорешивать почти все домашние задания. Обязательные задачи Некоторые домашние работы и отдельные задачи будут обязательными для получения зачета. Дедлайна на защиту для них не будет. Но помните, что если вы решите сдавать их в самом конце семестра, то семинарист может физически не успеть проверить их. В этот момент приоритет будет отдаваться студентам, которые претендуют на более высокие оценки. Пожалуйста, не откладывайте все на последний момент!
Домашние задания

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

2023/2024 учебный год 4 модуль
0.5 * Домашние задания + 0.5 * Домашние задания

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