Параллельное программирование — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(→‎19 билет. Упорядочивание сообщений. Определения, иерархия порядков. Алгоритм для синхронного порядка)
(→‎30 билет. Raft. Алгоритм, его свойства.)
(не показано 47 промежуточных версий 9 участников)
Строка 1: Строка 1:
 
[[Категория: Параллельное программирование]]
 
[[Категория: Параллельное программирование]]
 
=Программирование параллельных и распределенных систем=
 
=Программирование параллельных и распределенных систем=
 +
*[[Базовые определения и формализм]]
 +
*[[Алгоритмы взаимного исключения]]
 +
*[[Стек Трайбера]]
 +
*[[Формализм распределённых систем]]
 +
 
==6 семестр==
 
==6 семестр==
 
===Введение. Масштабируемость распределенных и параллельных систем, закон Амдала. Отличия распределенных систем от систем с разделяемой памятью===
 
===Введение. Масштабируемость распределенных и параллельных систем, закон Амдала. Отличия распределенных систем от систем с разделяемой памятью===
Строка 14: Строка 19:
 
===3-4 билеты. Часы с прямой зависимостью (и их свойства) и матричные часы===
 
===3-4 билеты. Часы с прямой зависимостью (и их свойства) и матричные часы===
 
*[[Параллельное программирование: Часы с прямой зависимостью|Часы с прямой зависимостью]]
 
*[[Параллельное программирование: Часы с прямой зависимостью|Часы с прямой зависимостью]]
−
*[[Параллельное программирование: Матричные часы|Матричные часы]]
+
*[[Параллельное программирование: Матричные часы|Матричные часы]] (билет весной 2019 года убран)
  
 
===5-7 билеты. Взаимное исключение в распределенной системе. Централизованный, алгоритм Лампорта, алгоритм Рикарта и Агравалы===
 
===5-7 билеты. Взаимное исключение в распределенной системе. Централизованный, алгоритм Лампорта, алгоритм Рикарта и Агравалы===
Строка 41: Строка 46:
  
 
===15 билет. Диффундирующие вычисления. Останов. Алгоритм Дейкстры и Шолтена===
 
===15 билет. Диффундирующие вычисления. Останов. Алгоритм Дейкстры и Шолтена===
−
TODO
+
* [[Диффундирующие вычисления]]
−
 
+
* [[Алгоритм Дейкстры и Шолтена]]
−
Алгоритм Дейкстры и Шолтена в английской википедии<ref>http://en.wikipedia.org/wiki/Dijkstra-Scholten_algorithm</ref>.
 
  
 
===16 билет. Локально-стабильные предикаты, согласованные интервалы, барьерная синхронизация (3 алгоритма). Применение для определения взаимной блокировки===
 
===16 билет. Локально-стабильные предикаты, согласованные интервалы, барьерная синхронизация (3 алгоритма). Применение для определения взаимной блокировки===
−
TODO
 
  
 
*[[Локально стабильный предикат]]
 
*[[Локально стабильный предикат]]
 
*[[Согласованный интервал]]
 
*[[Согласованный интервал]]
 
*[[Барьерная синхронизация (3 алгоритма)]]
 
*[[Барьерная синхронизация (3 алгоритма)]]
−
* Применение для определения дедлока.
+
*[[Определение взаимной блокировки]]
−
Каждый процесс <tex>P_i</tex> поддерживает свою часть графа ожидания (ребра, которые из него исходят), а также флажок changed, который равен true, если его часть графа поменялась с последнего  сообщения координатору. Координатор периодически опрашивает процессы, получая их графы. Процесс отвечает новым графом, если есть изменение, а иначе шлет notChanged. Координатор собирает весь граф ожидания. Если в нем есть цикл, он отправляет процессам запрос на изменение. Если все процессы в цикле ответили notChanged, дедлок найден.
 
−
 
 
−
Рассмотрим два среза:
 
−
* когда взаимно блокирующие процессы прислали координатору свои графы;
 
−
* когда они прислали ему notChanged.
 
−
Эти срезы не обязательно согласованны, но они барьерно-синхронизированы (из-за сообщений координатору и обратно), а значит образуют согласованный интервал. Поэтому между ними есть согласованный срез <tex>G</tex>, а так как состояние процессов в цикле не менялось на всем интервале, и в первом срезе предикат выполнен, для <tex>G</tex> он также выполнен.
 
−
 
 
−
===17-18 билеты. Упорядочивание сообщений. Определения, иерархия порядков. Алгоритм для FIFO. Алгоритм для причинно-согласованного порядка ===
 
−
TODO
 
−
 
 
−
Порядок сообщений:
 
−
# асинхронный (нет порядка)
 
−
# FIFO (сообщения доходят получателю в том порядке, в котором они были ему отправлены в смысле одного потока)
 
−
# причинно-следственный (если одно сообщение было отправлено раньше другого, то оно будет доставлено раньше другого (в системе целиком, а не в смысле одного потока, как в FIFO)
 
−
# синхронный (можно выстроить ребра передачи сообщений без пересечений)
 
−
 
 
−
Алгоритм FIFO основан на нумерации сообщений.<br>
 
−
Псевдокод алгоритма для причинно-согласованного порядка. Вместе с сообщением отправляем матрицу M: M[i, j] &mdash; количество сообщений, отправленных процессом i процессу j.
 
−
  '''var'''
 
−
      M:array[l..N, 1..N] of integer initially 0;
 
−
  To send a message to <tex>P_j</tex>:
 
−
      M [i,j] := M[i,j] + 1;
 
−
      send M as part of the message;
 
−
  To receive a message with matrix W from Pj:
 
−
      '''enabled if''' W[j,i] = M [j,i] + 1 <tex>\land</tex> <tex> \forall k \neq j</tex> <tex>M[k, i] \geqslant W[k, i]</tex>
 
−
      M := max(M, W)
 
−
 
 
−
===19 билет. Упорядочивание сообщений. Определения, иерархия порядков. Алгоритм для синхронного порядка===
 
  
−
Алгоритм для синхронного порядка основан на иерархии процессов.
+
===17-19 билеты. Упорядочивание сообщений. Определения, иерархия порядков. Алгоритм для FIFO. Алгоритм для причинно-согласованного порядка. Алгоритм для синхронного порядка ===
−
Упорядочим процессы по номеру, назовем сообщение ''большим'', если номер отправителя больше номера получателя, и ''малым'' иначе.
+
* [[Иерархия порядков сообщений]]
−
Процесс может быть в ''активном'' или ''пассивном состоянии''. Изначально все активны.
+
* [[Алгоритм для FIFO порядка]]
−
Процесс может отправить большое сообщение, только если он активен. После отправки он становится пассивным и не может ни отправлять, ни принимать сообщения, пока не получит от получателя ack.
+
* [[Алгоритм для причинно-согласованного порядка]]
−
Чтобы отправить сообщение большему процессу <tex>P_j</tex>, процесс <tex>P_i</tex> должен получить разрешение от <tex>P_j</tex>. <tex>P_j</tex> может разрешить только в активном состоянии. Разрешив, он становится пассивным и остается в этом состоянии, пока не получает сообщение, которое разрешил.
+
* [[Алгоритм для синхронного порядка]]
  
 
===20-21 билеты. Общий порядок (total order). Алгоритмы Лампорта и Скина===
 
===20-21 билеты. Общий порядок (total order). Алгоритмы Лампорта и Скина===
−
TODO? (CHECK)
+
*[[Общий порядок сообщений]]
−
 
 
−
*[[Total order]]
 
 
*[[Алгоритм Лампорта]]
 
*[[Алгоритм Лампорта]]
 
*[[Алгоритм Скина]]
 
*[[Алгоритм Скина]]
−
 
−
===?? билет. Выбор лидера. Алгоритм Чанди-Робертса, и алгоритм Хирчберга-Синклера===
 
−
 
−
'''Алгоритм Чанди-Робертса''' (Chang and Roberts) выбора лидера <ref>http://en.wikipedia.org/wiki/Chang_and_Roberts_algorithm</ref>.
 
−
 
−
Пусть процессы находятся в кольце.
 
−
Посылаем свой номер налево по кольцу.
 
−
При получении номера справа посылаем налево максимум из своего номера и полученного справа.
 
−
Если полученный справа номер является нашим номером, то заканчиваем работу.
 
−
 
−
'''Алгоритм Хирчберга-Синклера''' <ref>http://en.wikipedia.org/wiki/HS_algorithm</ref> <ref>http://web.cs.gc.cuny.edu/~vmitsou/presentation.pdf слайды 16-18</ref>.
 
  
 
===22 билет. Иерархия ошибок в распределенных системах. Отказ узла в асинхронной системе - невозможность консенсуса (доказательство Фишера-Линча-Патерсона)===
 
===22 билет. Иерархия ошибок в распределенных системах. Отказ узла в асинхронной системе - невозможность консенсуса (доказательство Фишера-Линча-Патерсона)===
−
TODO
 
−
 
−
#Отказ одного или нескольких узлов (crash)
 
−
#Отказ одного или нескольких каналов (link failure)
 
−
#Ненадежная доставка сообщений (omission)
 
−
#Византийская ошибка (byzantine failure) (сломавшийся процесс может слать любой мусор)
 
−
 
−
Теорема FLP (Фишер-Линч-Патерсон):
 
−
 
−
Для асинхронной системы N потоков с хотя бы одним сбойным потоком нельзя построить решение задачи консенсуса.
 
−
 
−
Разрешением утверждения, которое постулируется в теореме выше, могут стать следующие изменения:
 
−
* Сделать сеть синхронной (ограничить время доставки сообщений)
 
−
* Сделать алгоритм недетерминированным (случайным)
 
−
* Ослабить требования при которых в алгоритме обязан быть прогресс (т.е. он обязан завершаться)
 
  
−
Инфо: http://bailonga.es/tpmtp/lecture09.pdf + презентация Р.Елизарова
+
* [[Иерархия ошибок в распределённых системах]]
 +
* [[Асинхронные и синхронные распределённые системы]]
 +
* [[Консенсус в распределённой системе]]
 +
* [[Теорема Фишера-Линча-Патерсона (FLP)]]
  
 
===23 билет. Консенсус в распределенных системах. Применение консенсуса: выбор лидера, terminating reliable broadcast===
 
===23 билет. Консенсус в распределенных системах. Применение консенсуса: выбор лидера, terminating reliable broadcast===
−
TODO
+
* [[Иерархия ошибок в распределённых системах]]
−
 
+
* [[Асинхронные и синхронные распределённые системы]]
−
Результат FLP о невозможности консенсуса верен даже если, процессу разрешено делать операцию «атомарной передачи» сообщения сразу несколько процессам, ибо нет гарантии что все процессы обработают его. Если есть гарантия получения сообщения всеми процессами (или ни одним), то такая операция называется Terminating Reliable Broadcast (TRB). Имея TRB можно тривиально на его основе написать алгоритм консенсуса.
+
* [[Консенсус в распределённой системе]]
−
 
+
* [[Переформулировки консенсуса в распределённой системе]]
−
Применение консенсуса:
 
−
 
 
−
1) Выбор лидера
 
−
 
 
−
* Каждый процесс предлагает себя. Консенсус определяет лидера для последующего распределенного алгоритма
 
−
 
 
−
2) Terminating Reliable Broadcast
 
−
 
 
−
* Надо прийти к консенсусу о том, надо ли обрабатывать полученное сообщение
 
−
* Таким образом, задача TRB эквивалентна задаче консенсуса
 
  
 
===24 билет. Синхронные системы. Алгоритм для консенсуса в случае отказа заданного числа узлов===
 
===24 билет. Синхронные системы. Алгоритм для консенсуса в случае отказа заданного числа узлов===
−
TODO
 
  
−
Пусть в системе имеется ''n'' узлов.
+
* [[Иерархия ошибок в распределённых системах]]
−
Пусть из них максимум ''f'' не работают.
+
* [[Асинхронные и синхронные распределённые системы]]
−
Тогда можно решить задачу консенсуса:
+
* [[Консенсус в распределённой системе]]
−
 
+
* [[Консенсус в синхронных системах]]
−
*Каждый узел посылает каждому свое число;
 
−
*Процессы запоминают пришедшие числа;
 
−
*Новые для себя числа процессы рассылают дальше;
 
−
*Каждый процесс выбирает минимально известное ему число.
 
  
 
===25 билет. Синхронные системы. Проблема византийских генералов. Алгоритм для N >= 4, f = 1. Объяснить идею обобщения для f > 1===
 
===25 билет. Синхронные системы. Проблема византийских генералов. Алгоритм для N >= 4, f = 1. Объяснить идею обобщения для f > 1===
 +
* [[Асинхронные и синхронные распределённые системы]]
 +
* [[Проблема византийских генералов]]
 +
* [[Алгоритм Лампорта-Шостака-Пиза]] для решения проблемы
  
−
'''Задача двух генералов''' — мысленный эксперимент, призванный проиллюстрировать проблему синхронизации состояния двух систем по ненадежному каналу связи. ([https://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%B4%D0%B2%D1%83%D1%85_%D0%B3%D0%B5%D0%BD%D0%B5%D1%80%D0%B0%D0%BB%D0%BE%D0%B2 Википедия])
+
===26 билет. Синхронные системы. Проблема византийских генералов. Невозможность решения при N = 3, f = 1===
 +
* [[Асинхронные и синхронные распределённые системы]]
 +
* [[Проблема византийских генералов]]
 +
* [[Невозможность византийского консенсуса]] при N=3, f=1.
  
−
Два процесса в случае ненадежного канала не могут достичь [[консенсус|консенсуса]].
+
=== 27 билет. Недетерминированные алгоритмы консенсуса. Алгоритм Бен-Ора. ===
−
 
+
* [[Иерархия ошибок в распределённых системах]]
−
Consider the last such message that was successfully delivered. If that last message had not been successfully delivered, then one general at least (presumably the receiver) would decide not to attack. From the viewpoint of the sender of that last message, however, the sequence of messages sent and delivered is exactly the same as it would have been, had that message been delivered.
+
* [[Асинхронные и синхронные распределённые системы]]
 +
* [[Консенсус в распределённой системе]]
 +
* [[Алгоритм Бен-Ора]]
  
−
Для недетерминнированного - аналогично. Посмотрим на "успешную" последовательность.
+
=== 28-29 билеты. Paxos. Алгоритм, его свойства. Общие принципы. Основные модификации.===
−
И отменим успешность последнего сообщения. Для 1-ого все ок, для 2-ого все испортилось.
+
* [[Консенсус в распределённой системе]]
 +
* [[Replicated State Machine]]
 +
* [[Paxos]]
  
−
===26 билет. Синхронные системы. Проблема византийских генералов. Невозможность решения при N = 3, f = 1===
+
=== 30 билет. Raft. Алгоритм, его свойства.===
 +
* [[Консенсус в распределённой системе]]
 +
* [[Replicated State Machine]]
 +
* [[Raft]]
  
−
'''Задача византийских генералов''' — мысленный эксперимент, призванный проиллюстрировать проблему синхронизации состояния систем в случае, когда коммуникации считаются надёжными, а процессоры — нет. (Вики)
+
=== 31 билет. Транзакции в распределенных системах. 2 Phase Locking===
 +
* [[Транзакции в распределённых системах]]
 +
* [[2 Phase Locking]]
  
−
Проблема византийских генералов формулируется так: имеется ''n'' генералов из которых ''f'' являются предателями. Как прийти к консенсусу честным генералам?
+
=== 32 билет. Транзакции в распределенных системах. 2 Phase Commit.===
 +
* [[Транзакции в распределённых системах]]
 +
* [[2 Phase Commit]]
  
−
Известно, что при ''n'' > 3''f'' задача решаема, а иначе нет.
+
=== 33 билет. СAP теорема (концепции, подходы, без доказательства)===
 +
* [[CAP теорема]]
  
−
*Каждый рассылает каждому свое число;
+
=== 34 билет. Gossip. СRDT и дельта-CRDT (концепции, примеры алгоритмов, см. работу с семинара)===
−
*Каждый рассылает каждому собранные значения;
+
* [[Gossip-протоколы]]
−
*В полученных векторах каждый проводит голосование.
+
* [[CRDT]]
  
−
Можно доказать, например, что при ''n'' = 3, ''f'' = 1 консенсус невозможен.
+
=== 35 билет. Самостабилизирующиеся алгоритмы. Идея. Алгоритмы взаимного исключения и поиска остовного дерева ===
−
 
+
* [[Иерархия ошибок в распределённых системах]]
−
Данный вопрос достаточно хорошо описан в английской версии.
+
* [[Самостабилизирующиеся алгоритмы]]
−
 
 
−
=== 27 билет. Недетерминированные алгоритмы консенсуса. Алгоритм Бен-Ора. ===
 
−
=== 28 билет. Paxos. Алгоритм, его свойства.===
 
−
=== 29 билет. Paxos. Общие принципы. Основные модификации.===
 
−
=== 30 билет. Транзакции в распределенных системах. 2 Phase Locking===
 
−
=== 31 билет. Транзакции в распределенных системах. 2 Phase Commit.===
 
−
=== 32 билет. СAP теорема (концепции, подходы, без доказательства)===
 
−
=== 33 билет. Gossip. СRDT и дельта-CRDT (концепции, примеры алгоритмов, см. работу с семинара)===
 
  
 
==Ссылки==
 
==Ссылки==
 
<references/>
 
<references/>

Версия 09:06, 4 июня 2019

Содержание

Программирование параллельных и распределенных систем

6 семестр

Введение. Масштабируемость распределенных и параллельных систем, закон Амдала. Отличия распределенных систем от систем с разделяемой памятью

1-2 билеты. Логические часы Лампорта и векторные часы, их свойства

3-4 билеты. Часы с прямой зависимостью (и их свойства) и матричные часы

5-7 билеты. Взаимное исключение в распределенной системе. Централизованный, алгоритм Лампорта, алгоритм Рикарта и Агравалы

8-10 билеты. Взаимное исключение в распределенной системе. Алгоритм обедающих философов, на основе токена, на основе кворума (простое большинство, рушащиеся стены)

11-12 билеты. Согласованное глобальное состояние (согласованный срез). Алгоритм Чанди-Лампорта. Запоминание сообщений на стороне отправителя и получателя

13-14 билеты. Глобальные свойства. Стабильные и нестабильные предикаты. Слабый конъюнктивный предикат. Централизованный и распределенный алгоритмы

15 билет. Диффундирующие вычисления. Останов. Алгоритм Дейкстры и Шолтена

16 билет. Локально-стабильные предикаты, согласованные интервалы, барьерная синхронизация (3 алгоритма). Применение для определения взаимной блокировки

17-19 билеты. Упорядочивание сообщений. Определения, иерархия порядков. Алгоритм для FIFO. Алгоритм для причинно-согласованного порядка. Алгоритм для синхронного порядка

20-21 билеты. Общий порядок (total order). Алгоритмы Лампорта и Скина

22 билет. Иерархия ошибок в распределенных системах. Отказ узла в асинхронной системе - невозможность консенсуса (доказательство Фишера-Линча-Патерсона)

23 билет. Консенсус в распределенных системах. Применение консенсуса: выбор лидера, terminating reliable broadcast

24 билет. Синхронные системы. Алгоритм для консенсуса в случае отказа заданного числа узлов

25 билет. Синхронные системы. Проблема византийских генералов. Алгоритм для N >= 4, f = 1. Объяснить идею обобщения для f > 1

26 билет. Синхронные системы. Проблема византийских генералов. Невозможность решения при N = 3, f = 1

27 билет. Недетерминированные алгоритмы консенсуса. Алгоритм Бен-Ора.

28-29 билеты. Paxos. Алгоритм, его свойства. Общие принципы. Основные модификации.

30 билет. Raft. Алгоритм, его свойства.

31 билет. Транзакции в распределенных системах. 2 Phase Locking

32 билет. Транзакции в распределенных системах. 2 Phase Commit.

33 билет. СAP теорема (концепции, подходы, без доказательства)

34 билет. Gossip. СRDT и дельта-CRDT (концепции, примеры алгоритмов, см. работу с семинара)

35 билет. Самостабилизирующиеся алгоритмы. Идея. Алгоритмы взаимного исключения и поиска остовного дерева

Ссылки

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Параллельное_программирование&oldid=71614»