Федеральное государственное бюджетное образовательное
учреждение высшего образования 
Московский государственный университет имени М.В. Ломоносова
Факультет вычислительной математики и кибернетики

УТВЕРЖДАЮ
декан факультета вычислительной математики и кибернетики
______________/И.А. Соколов /
«___» ________________20___г.

РАБОЧАЯ ПРОГРАММА ДИСЦИПЛИНЫ
Наименование дисциплины:
Распределенные системы
Уровень высшего образования:
бакалавриат
Направление подготовки / специальность:
01.03.02 «Прикладная математика и информатика» (3++)
Направленность (профиль):
Системное программирование и компьютерные науки
Форма обучения:
очная

Москва 2023

Рабочая программа дисциплины (модуля) разработана в соответствии с самостоятельно установленным МГУ образовательным стандартом (ОС МГУ) для реализуемых основных профессиональных образовательных программ высшего образования по направлению подготовки 01.03.02, 01.04.02 "Прикладная математика и информатика" программы бакалавриата  Утвержден приказом МГУ от 30 августа 2019 года № 1041 (в редакции приказов МГУ от 11 сентября 2019 года № 1109, от 10 июня 2021 года № 609, от 7 октября 2021 года № 1048, от 21 декабря 2021 года № 1404, от 2 ноября 2022 года № 1299)

1. Дисциплина относится к вариативной части ОПОП ВО.

2. Входные требования для освоения дисциплины (модуля): учащиеся должны владеть знаниями по операционным системам, введению в сети ЭВМ и суперкомпьютерам и параллельной обработке данных в объеме, соответствующем программе второго и третьего года обучения основных образовательных программ бакалавриата по укрупненным группам направлений и специальностей 01.00.00 «Математика и механика», 02.00.00 «Компьютерные и информационные науки».

3. Результаты обучения по дисциплине (модулю), соотнесенные с требуемыми компетенциями выпускников.

Компетенции выпускников, частично формируемые при реализации дисциплины (модуля):

•	ОПК-3.Б Способность решать задачи в области прикладной математики и информатики с использованием современных информационных технологий, учитывая основные требования информационной безопасности
•	ПК-4.Б Способность применять в профессиональной деятельности современные средства разработки программного обеспечения и методы параллельной обработки данных, реализовывать отдельные этапы разработки системного и прикладного программного обеспечения, систем обработки и анализа данных, сетевых технологий 

Планируемые результаты обучения по дисциплине (модулю):

Знать:
1.	проблемы создания распределенных операционных систем - операционных систем, которые позволяют рассматривать совокупность независимых компьютеров как единый очень мощный компьютер, использование которого не намного сложнее, чем использование персональной ЭВМ.
2.	основные принципы построения РОС (прозрачность, гибкость, надежность, эффективность, масштабируемость).
3.	особенности технологий MPI и OpenMP для разработки программного обеспечения для распределенных систем и мультипроцессоров.

Уметь:
1.	использовать различные механизмы и алгоритмы для синхронизации процессов/нитей при доступе к разделяемой памяти, к общей файловой системе.
2.	реализовать коллективные MPI-операции рассылки/сбора данных при помощи сообщений точка-точка.

Владеть:
1.	техникой оценки времени работы различных алгоритмов (выбора координатора, прохождения критических секций, надежных и неделимых широковещательных рассылок сообщений, фиксации консистентного и строго консистентного множества контрольных точек), используемых в распределенных системах, при заданных параметрах - количестве ЭВМ и характеристиках сети (времени старта и времени передачи байта).
2.	техникой оценки времени выполнения операции модификации/чтения переменной из распределенной разделяемой памяти (DSM) для заданной модели консистентности памяти и при заданных параметрах сети (времени старта и времени передачи байта).

4. Формат обучения: лекции проводятся в традиционной манере с использованием компьютера и мультимедийного проектора для демонстрации слайдов.

5. Объем дисциплины (модуля) составляет 3 з.е., в том числе 36 академических часов, отведенных на контактную работу обучающихся с преподавателем, 72 академических часа на самостоятельную работу обучающихся. 

6. Содержание дисциплины (модуля), структурированное по темам (разделам) с указанием отведенного на них количества академических часов и виды учебных занятий.
Наименование и краткое содержание разделов и тем дисциплины (модуля),

Форма промежуточной аттестации по дисциплине (модулю)	Всего
(часы)	В том числе	
		Контактная работа 
(работа во взаимодействии с преподавателем)
Виды контактной работы, часы	Самостоятельная работа обучающегося,
 часы 
	
		Занятия лекционного типа*	Занятия семинарского типа*	Всего		
1.	Введение в параллельные и распределенные системы	8	4	0	4	4	
2.	Операционные системы многопроцессорных ЭВМ с общей памятью	12	6	0	6	6	
3.	Коммуникации в распределенных системах	12	6	0	6	6	
4.	Синхронизация в распределенных системах  	12	6	0	6	6	
5.	Распределенные и параллельные файловые системы	8	4	0	4	4	
6.	Распределенная разделяемая память (DSM)	12	6	0	6	6	
7.	Обеспечение надежности	8	4	0	4	4	
Промежуточная аттестация: устный экзамен	36	0	0	0	36	
Итого	108	36	0	36	72	

7. Фонд оценочных средств (ФОС) для оценивания результатов обучения по дисциплине (модулю)

7.1. Типовые контрольные задания или иные материалы для проведения текущего контроля успеваемости.

Текущий контроль успеваемости не предусмотрен рабочей программой.

7.2. Типовые контрольные задания или иные материалы для проведения промежуточной аттестации.

Вопросы к экзамену.
Какие аппаратные механизмы необходимы для организации мультипрограммного режима? Как обеспечить мультипрограммный режим без этих механизмов? Как обеспечить, если отсутствует только один из этих механизмов?
2.	Имеется механизм двоичных семафоров. Опираясь на него, реализуйте P-операцию и V-операцию для общего (считающего) семафора. Активное ожидание освобождения семафора не допускается.
3.	Имеется команда TSL и команда объявления прерывания указанному процессору. Опираясь на них, реализуйте на мультипроцессоре P-операцию и V-операцию для двоичного семафора. Активное ожидание освобождения семафора не допускается.
4.	Имеется механизм двоичных семафоров. Опираясь на него, реализуйте операторы POST(имя переменной-события) и WAIT(имя переменной-события). Активное ожидание события не допускается. Оцените, во сколько раз нижеприведенный алгоритм  метода последовательной верхней релаксации можно выполнить быстрее, чем последовательный, если число процессоров мультипроцессора = N, время выполнения одного оператора присваивания (A[i][j]=....) равно 1, временами выполнения остальных операторов можно пренебречь.
float  A[ L1 ][ L2 ];
semaphore  s[ L1 ][ L2 ];  /*  массив двоичных семафоров с нулевым начальным значением */
for ( j = 0; j < L2; j++)   { post( s[ 0 ][ j ]) }
parfor ( i = 1; i < L1-1; i++)
 	for ( j = 1; j < L2-1; j++) 
	{	wait( s[ i-1 ][ j ]);
		A[ i ][ j ] = (A[ i-1 ][ j ] + A[ i+1][ j ] + A[ i ][ j-1 ] + A[ i ][ j+1 ]) / 4;
		post( s[ i ][ j ]);
	}
5.	Имеется механизм двоичных семафоров. Опираясь на него, реализуйте задачу читателей и писателей (алгоритмы предоставления прав доступа процессам-читателям и процессам-писателям):
Процесс-писатель должен получать исключительный (монопольный) доступ к базе данных (других писателей или каких-либо читателей быть не должно). Произвольное число процессов-читателей может работать одновременно, но любой читатель может получить доступ только при отсутствии работающих писателей. 
Запросы на доступ должны удовлетворяться "справедливо" - в порядке их поступления (можно исходить из "справедливости" удовлетворения запросов на двоичные семафоры).
6.	Какие модели консистентности памяти удовлетворяют алгоритму Деккера (алгоритм без каких-либо изменений будет работать правильно), а какие нет? Объясните ответ.
7	Какие модели консистентности памяти удовлетворяют алгоритму Петерсона (алгоритм без каких-либо изменений будет работать правильно), а какие нет? Объясните ответ.
8.	В транспьютерной матрице размером 4*4, в каждом узле которой находится один процесс, необходимо выполнить операцию передачи сообщения длиной N байт всем процессам от одного (MPI_BCAST) - процесса с координатами (0,0). Сколько времени потребуется для этого, если все процессы выдали ее одновременно. Время старта равно 100, время передачи байта равно 1 (Ts=100,Tb=1). Процессорные операции, включая чтение из памяти и запись в память, считаются бесконечно быстрыми. 
9.	В транспьютерной матрице размером 4*4, в каждом узле которой находится один процесс, необходимо выполнить операцию сбора данных (длиной один байт) от всех процессов  для одного (MPI_GATHER) - процесса с координатами (0,0). Сколько времени потребуется для этого, если все процессы выдали ее одновременно. Время старта равно 100, время передачи байта равно 1 (Ts=100,Tb=1). Процессорные операции, включая чтение из памяти и запись в память, считаются бесконечно быстрыми.
10.	В транспьютерной матрице размером 4*4, в каждом узле которой находится один процесс, необходимо выполнить операцию рассылки данных (длиной один байт) всем процессам от одного (MPI_SCATTER) - процесса с координатами (0,0). Сколько времени потребуется для этого, если все процессы выдали ее одновременно. Время старта равно 100, время передачи байта равно 1 (Ts=100,Tb=1). Процессорные операции, включая чтение из памяти и запись в память, считаются бесконечно быстрыми.
11.	В транспьютерной матрице размером 4*4, в каждом узле которой находится один процесс, необходимо выполнить операцию нахождения максимума среди 16 чисел (каждый процесс имеет свое число). Сколько времени потребуется для получения всеми максимального числа, если все процессы выдали эту операцию редукции одновременно. А сколько времени потребуется для нахождения максимума среди 64 чисел в матрице 8*8? Время старта равно 100, время передачи байта равно 1 (Ts=100,Tb=1). Процессорные операции, включая чтение из памяти и запись в память, считаются бесконечно быстрыми.
12.	В транспьютерной матрице размером 4*4, в каждом узле которой находится один процесс, необходимо переслать очень длинное сообщение (длиной L байт) из узла с координатами (0,0) в узел с координатами (3,3). Сколько времени потребуется для этого, если передача сообщений точка-точка выполняется в буферизуемом режиме MPI? А сколько времени потребуется при использовании синхронного режима и режима готовности? Время старта равно 100, время передачи байта равно 1 (Ts=100,Tb=1). Процессорные операции, включая чтение из памяти и запись в память, считаются бесконечно быстрыми.
13.	В транспьютерной матрице размером 4*4, в каждом узле которой находится один процесс, необходимо переслать сообщение длиной L байт из узла с координатами (0,0) в узел с координатами (3,3). Сколько времени потребуется для этого при использовании а) неблокирующих и б) блокирующих операций MPI? Время старта равно 100, время передачи байта равно 1 (Ts=100,Tb=1). Процессорные операции, включая чтение из памяти и запись в память, считаются бесконечно быстрыми.
14.	Все 16 процессов, находящихся на разных ЭВМ сети с шинной организацией (без аппаратных возможностей широковещания), одновременно выдали запрос на вход в критическую секцию. Сколько времени потребуется для прохождения всеми критических секций, если используется древовидный маркерный алгоритм (маркером владеет нулевой процесс). Время старта (время "разгона" после получения доступа к шине для передачи сообщения) равно 100, время передачи байта равно 1 (Ts=100,Tb=1). Доступ к шине ЭВМ получают последовательно в порядке выдачи запроса на передачу (при одновременных запросах - в порядке номеров ЭВМ). Процессорные операции, включая чтение из памяти и запись в память, считаются бесконечно быстрыми.  
15.	Все 16 процессов, находящихся на разных ЭВМ сети с шинной организацией (без аппаратных возможностей широковещания), одновременно выдали запрос на вход в критическую секцию. Сколько времени потребуется для прохождения всеми критических секций, если используется децентрализованный алгоритм с временными метками. Время старта (время "разгона" после получения доступа к шине для передачи сообщения) равно 100, время передачи байта равно 1 (Ts=100,Tb=1). Доступ к шине ЭВМ получают последовательно в порядке выдачи запроса на передачу (при одновременных запросах - в порядке номеров ЭВМ). Процессорные операции, включая чтение из памяти и запись в память, считаются бесконечно быстрыми.
16.	Все 16 процессов, находящихся на разных ЭВМ сети с шинной организацией (без аппаратных возможностей широковещания), одновременно выдали запрос на вход в критическую секцию. Сколько времени потребуется для прохождения всеми критических секций, если используется широковещательный маркерный алгоритм (маркером владеет нулевой процесс).  Время старта равно 100, время передачи байта равно 1 (Ts=100,Tb=1). Процессорные операции, включая чтение из памяти и запись в память, считаются бесконечно быстрыми.
17.	15 процессов, находящихся в узлах транспьютерной матрицы размером 4*4, одновременно выдали запрос на вход в критическую секцию. Сколько времени потребуется для прохождения всеми критических секций, если используется централизованный алгоритм (координатор расположен в узле 0,0)? Время старта равно 100, время передачи байта равно 1 (Ts=100,Tb=1). Процессорные операции, включая чтение из памяти и запись в память, считаются бесконечно быстрыми.
18.	Сколько времени потребует выбор координатора среди 16 процессов, находящихся на разных ЭВМ сети с шинной организацией (без аппаратных возможностей широковещания),  если используется алгоритм "задиры"? "Задира" расположен в узле с координатами (0,0) и имеет уникальный номер 0. Время старта (время "разгона" после получения доступа к шине для передачи сообщения) равно 100, время передачи байта равно 1 (Ts=100,Tb=1). Доступ к шине ЭВМ получают последовательно в порядке выдачи запроса на передачу (при одновременных запросах - в порядке номеров ЭВМ). Процессорные операции, включая чтение из памяти и запись в память, считаются бесконечно быстрыми.
19.	Сколько времени потребует выбор координатора среди 16 процессов, находящихся в узлах транспьютерной матрицы размером 4*4, если используется круговой алгоритм? Время старта равно 100, время передачи байта равно 1 (Ts=100,Tb=1). Процессорные операции, включая чтение из памяти и запись в память считаются бесконечно быстрыми.
20.	Какие принципиальные решения приходится принимать при обеспечении файлового сервиса?
21.	Интерфейс сервера директорий.
22.	Семантика разделения файлов.
23.	Серверы с состоянием и без состояния. Достоинства и недостатки.
24.	Алгоритмы обеспечения консистентности кэшей в распределенных файловых системах.
25.	Способы организации размножения файлов и коррекции копий.
26.	Последовательная консистентность памяти и алгоритм ее  реализации  в DSM с полным размножением. Сколько времени потребует модификация 10 различных переменных 10-ю процессами (каждый процесс модифицирует одну переменную), находящимися на разных ЭВМ сети с шинной организацией (без аппаратных возможностей широковещания) и одновременно выдавшими запрос на модификацию. Время старта (время "разгона" после получения доступа к шине для передачи сообщения) равно 100, время передачи байта равно 1 (Ts=100,Tb=1). Доступ к шине ЭВМ получают последовательно в порядке выдачи запроса на передачу (при одновременных запросах - в порядке номеров ЭВМ). Процессорные операции, включая чтение из памяти и запись в память, считаются бесконечно быстрыми.
27.	Причинная консистентность памяти и алгоритм ее реализации в DSM с полным размножением при условии, что никаких сведений от компилятора о причинной зависимости операций записи не имеется. Сколько времени потребует модификация 10 различных переменных, если все 10 процессов (каждый процесс модифицирует одну переменную), находящихся на разных ЭВМ сети с шинной организацией (без аппаратных возможностей широковещания), одновременно выдали запрос на модификацию  своей переменной. Время старта (время "разгона" после получения доступа к шине для передачи сообщения) равно 100, время передачи байта равно 1 (Ts=100,Tb=1). Доступ к шине ЭВМ получают последовательно в порядке выдачи запроса  на передачу (при одновременных запросах - в порядке номеров ЭВМ). Процессорные операции, включая чтение из памяти и запись в память, считаются бесконечно быстрыми. 
28.	Процессорная консистентность памяти и алгоритм ее реализации в DSM с полным размножением. Сколько времени потребует модификация 10 различных переменных, если все 10 процессов (каждый процесс модифицирует одну переменную), находящихся на разных ЭВМ сети с шинной организацией (без аппаратных возможностей широковещания), одновременно выдали запрос на модификацию своей переменной. Время старта (время "разгона" после получения доступа к шине для передачи сообщения) равно 100, время передачи байта равно 1 (Ts=100,Tb=1). Доступ к шине ЭВМ получают последовательно в порядке выдачи запроса  на передачу (при одновременных запросах - в порядке номеров ЭВМ). Процессорные операции, включая чтение из памяти и запись в память, считаются бесконечно быстрыми. 
29.	PRAM консистентность памяти и алгоритм ее реализации в DSM с полным размножением. Сколько времени потребует 3-кратная модификация 10 различных переменных, если все 10 процессов (каждый процесс 3 раза модифицирует одну переменную), находящихся на разных ЭВМ сети с шинной организацией (без аппаратных возможностей широковещания), одновременно выдали запрос на модификацию. Время старта (время "разгона" после получения доступа к шине для передачи сообщения) равно 100, время передачи байта равно 1 (Ts=100,Tb=1). Доступ к шине ЭВМ получают последовательно в порядке выдачи запроса  на передачу (при одновременных запросах - в порядке номеров ЭВМ). Процессорные операции, включая чтение из памяти и запись в память, считаются бесконечно быстрыми. 
30.	Слабая консистентность памяти и алгоритм ее реализации в DSM с полным размножением. Сколько времени потребует модификация одним процессом 10 обычных переменных, а затем 3-х различных синхронизационных переменных, если DSM реализована на 10 ЭВМ сети с шинной организацией (с аппаратными возможностями широковещания). Время старта (время "разгона" после получения доступа к шине для передачи сообщения) равно 100, время передачи байта равно 1 (Ts=100,Tb=1). Доступ к шине ЭВМ получают последовательно в порядке выдачи запроса  на передачу (при одновременных запросах - в порядке номеров ЭВМ). Процессорные операции, включая чтение из памяти и запись в память, считаются бесконечно быстрыми. 
31.	Консистентность памяти по выходу и алгоритм ее реализации в DSM с полным размножением. Сколько времени потребует трехкратное выполнение каждым процессом критической секции, в которой модифицируются 10 переменных,  если DSM реализована на 10 ЭВМ сети с шинной организацией (с аппаратными возможностями широковещания). Время старта (время "разгона" после получения доступа к шине для передачи сообщения) равно 100, время передачи байта равно 1 (Ts=100,Tb=1). Доступ к шине ЭВМ получают последовательно в порядке выдачи запроса  на передачу (при одновременных запросах - в порядке номеров ЭВМ). Процессорные операции, включая чтение из памяти и запись в память, считаются бесконечно быстрыми. 
32.	Консистентность памяти по входу и алгоритм ее реализации в DSM с полным размножением. Сколько времени потребует трехкратное выполнение критической секции и модификация в ней 10 переменных каждым процессом, если DSM реализована на 10 ЭВМ сети с шинной организацией (с аппаратными возможностями широковещания). Время старта (время "разгона" после получения доступа к шине для передачи сообщения) равно 100, время передачи байта равно 1 (Ts=100,Tb=1). Доступ к шине ЭВМ получают последовательно в порядке выдачи запроса  на передачу (при одновременных запросах - в порядке номеров ЭВМ). Процессорные операции, включая чтение из памяти и запись в память считаются бесконечно быстрыми.

ШКАЛА И КРИТЕРИИ ОЦЕНИВАНИЯ результатов обучения (РО) по дисциплине (модулю)  	
Оценка
РО и
соответствующие виды оценочных средств 	2	3	4	5	
Знания
Экзамен	Отсутствие знаний	Фрагментарные знания	Общие, но не структурированные знания	Сформированные систематические знания	
Умения
Экзамен 	Отсутствие умений	В целом успешное, но не систематическое умение	В целом успешное, но содержащее отдельные пробелы умение (допускает неточности непринципи-ального характера)	Успешное и систематическое умение	
Навыки 
(владения, опыт деятельности)
Экзамен	Отсутствие навыков (владений, опыта)	Наличие отдельных навыков (наличие фрагментарного опыта)	В целом, сформированные навыки (владения), но используемые не в активной форме	Сформированные навыки (владения), применяемые при решении задач	

Соответствие результатов обучения и компетенций, в развитии которых участвует дисциплина (модуль)	
Результаты обучения	Компетенция, с частичным формированием которой связано достижение результата обучения	
Знать:
1.	Проблемы создания распределенных операционных систем - операционных систем, которые позволяют рассматривать совокупность независимых компьютеров как единый очень мощный компьютер, использование которого не намного сложнее, чем использование персональной ЭВМ.
2.	Основные принципы построения РОС (прозрачность, гибкость, надежность, эффективность, масштабируемость).
3.	Особенности технологий MPI и OpenMP для разработки программного обеспечения для распределенных систем и мультипроцессоров.

Владеть:
1.	Техникой оценки времени работы различных алгоритмов (выбора координатора, прохождения критических секций, надежных и неделимых широковещательных рассылок сообщений, фиксации консистентного и строго консистентного множества контрольных точек), используемых в распределенных системах, при заданных параметрах - количестве ЭВМ и характеристиках сети (времени старта и времени передачи байта).
2.	Техникой оценки времени выполнения операции модификации/чтения переменной из распределенной разделяемой памяти (DSM) для заданной модели консистентности памяти и при заданных параметрах сети (времени старта и времени передачи байта).

ОПК-3.Б	
Уметь:
1.	Использовать различные механизмы и алгоритмы для синхронизации процессов/нитей при доступе к разделяемой памяти, к общей файловой системе.
2.	Реализовать коллективные MPI-операции рассылки/сбора данных при помощи сообщений точка-точка.

ПК-4.Б	

8. Ресурсное обеспечение:

Основная литература:  
1.	Крюков В.А. Распределенные операционные системы. http://sp.cs.msu.su в разделе "Информация".
2.	Таненбаум Э., Стен М. ван. Распределенные системы. Принципы и парадигмы. – СПб.: Питер, 2003. (ISBN 5272000536, страниц: 877).
3.	Таненбаум Э. Современные операционные системы. 3-е изд. – СПб.: Питер, 2010. (ISBN 9785498073064, страниц: 1120).

Информационные справочные системы:

1. MPI: A Message-Passing Interface Standard. [HTML] (http://www.mpi-forum.org).
2. OpenMP Application Program Interface. Version 3.1. July 2011. [HTML] (http://www.openmp.org/mp-documents/OpenMP3.1.pdf).

Материально-техническое обеспечение: аудитория с партами, компьютером и мультимедийным проектором для демонстрации слайдов

9. Язык преподавания - русский.

10. Преподаватели:		профессор факультета ВМК МГУ В.А. Крюков, 
доцент факультета ВМК МГУ В.А. Бахтин.

11. Авторы программы:	профессор факультета ВМК МГУ В.А. Крюков, 
доцент факультета ВМК МГУ В.А. Бахтин.