Взаимодействующие параллельные системы
2018/19 учебный год г., Математический, II курс4 семестр(ы)
Специальности:
- 09.03.04 - Программная инженерия.
Содержание лекционных занятий.
- Гл.0. Введение. Сущность взаимодействующих (параллельных) вычислений. Взаимодействие => синхронизация: взаимное исключение и условная синхронизация. Типы приложений: многопоточные системы, распределенные вычисления, синхронные параллельные вычисления.
- Гл.1. Программирование взаимодействующих параллельных вычислений. Парадигмы взаимодействующих параллельных вычислений. Итеративный параллелизм (умножение матриц), рекурсивный параллелизм (адаптивная квадратура), производитель–потребитель (конвейер), клиент–сервер, взаимодействующие равные. Программная нотация.
- Гл.2. Процессы, потоки и синхронизация. Процессы/потоки вычислений, «тяжелые» и «легковесные» процессы. Взаимосвязь между процессами: передача сообщений и разделяемая память. Состояния, действия, истории и свойства. Возможные истории и синхронизация. Свойства безопасности и живучести. Неделимые действия и операторы ожидания. Мелкомодульная и крупномодульная неделимость. Оператор await.
- Гл.3. Замки и барьеры. Задача критической секции. Ключевые свойства. Циклические замки (активная блокировка). Реализация оператора await. Решения со справедливой стратегией. Алгоритм «разрыв узла». Алгоритм «билета». Алгоритм «поликлиники». Синхронизация барьером: разделяемый счетчик, флаги и координаторы.
- Гл.4. Семафоры. Механизм синхронизации на примерах задач: "Об обедающих философах", "Читатели и писатели", "Управление ресурсами (выделение и распределение)".
Содержание лабораторных работ.
- Тема 1. Парадигмы взаимодействующих параллельных вычислений. Разработка и анализ параллельной версии известного алгоритма для демонстрации различных парадигм.
- Тема 2. Типовые задачи. Критическая секция (протоколы входа и выхода). Потребитель-производитель (синхронизация). Задача об обедающих философах (взаимная блокировка). Задача о читателях и писателях (исключительное использование ресурса). Задача о спящем парикмахере (принцип рандеву).
- Тема 3. Состояния, истории и свойства параллельных программ. Разбор задач "Поиск образца в файле (распараллеливание, парадигма производитель-потребитель)", "Поиск максимального элемента (синхронизация, принцип перепроверки)" и других [Andrews, гл. 2].
- Тема 4. Критическая секция. Разбор возможных механизмов синхронизации: циклические замки, алгоритм Деккера, инструкции DEC и INC, инструкции «test-test-set», семафоры.
Список литературы.
- Эндрюс Г.Р. Основы многопоточного, параллельного и распределенного программирования / Г.Р.Эндрюс. - Москва : Вильямс, 2003. - 512 с.
- Бэкон Д. Операционные системы: Параллельные и распределенные системы / Д. Бэкон, Т. Харрис. – Санкт-Петербург : Питер ; Киев: Изд. группа BHV, 2004. – 800 с.
- Федотов И. Е. Модели параллельного программирования / И.Е.Федотов. - Москва : СОЛОН-ПРЕСС, 2012. - 384 с. [Электронный ресурс]. http://biblioclub.ru/index.php?page=book&id=227018
