Редактирование: Параллельное программирование

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 50: Строка 50:
  
 
===16 билет. Локально-стабильные предикаты, согласованные интервалы, барьерная синхронизация (3 алгоритма). Применение для определения взаимной блокировки===
 
===16 билет. Локально-стабильные предикаты, согласованные интервалы, барьерная синхронизация (3 алгоритма). Применение для определения взаимной блокировки===
 +
TODO
  
 
*[[Локально стабильный предикат]]
 
*[[Локально стабильный предикат]]
 
*[[Согласованный интервал]]
 
*[[Согласованный интервал]]
 
*[[Барьерная синхронизация (3 алгоритма)]]
 
*[[Барьерная синхронизация (3 алгоритма)]]
*[[Определение взаимной блокировки]]
+
* Применение для определения дедлока.
 +
Каждый процесс <tex>P_i</tex> поддерживает свою часть графа ожидания (ребра, которые из него исходят), а также флажок changed, который равен true, если его часть графа поменялась с последнего  сообщения координатору. Координатор периодически опрашивает процессы, получая их графы. Процесс отвечает новым графом, если есть изменение, а иначе шлет notChanged. Координатор собирает весь граф ожидания. Если в нем есть цикл, он отправляет процессам запрос на изменение. Если все процессы в цикле ответили notChanged, дедлок найден.
 +
 
 +
Рассмотрим два среза:
 +
* когда взаимно блокирующие процессы прислали координатору свои графы;
 +
* когда они прислали ему notChanged.
 +
Эти срезы не обязательно согласованны, но они барьерно-синхронизированы (из-за сообщений координатору и обратно), а значит образуют согласованный интервал. Поэтому между ними есть согласованный срез <tex>G</tex>, а так как состояние процессов в цикле не менялось на всем интервале, и в первом срезе предикат выполнен, для <tex>G</tex> он также выполнен.
  
 
===17-19 билеты. Упорядочивание сообщений. Определения, иерархия порядков. Алгоритм для FIFO. Алгоритм для причинно-согласованного порядка. Алгоритм для синхронного порядка ===
 
===17-19 билеты. Упорядочивание сообщений. Определения, иерархия порядков. Алгоритм для FIFO. Алгоритм для причинно-согласованного порядка. Алгоритм для синхронного порядка ===
Строка 63: Строка 70:
  
 
===20-21 билеты. Общий порядок (total order). Алгоритмы Лампорта и Скина===
 
===20-21 билеты. Общий порядок (total order). Алгоритмы Лампорта и Скина===
 +
TODO? (CHECK)
 +
 
*[[Общий порядок сообщений]]
 
*[[Общий порядок сообщений]]
 
*[[Алгоритм Лампорта]]
 
*[[Алгоритм Лампорта]]
Строка 103: Строка 112:
 
* [[Алгоритм Бен-Ора]]
 
* [[Алгоритм Бен-Ора]]
  
=== 28-29 билеты. Paxos. Алгоритм, его свойства. Общие принципы. Основные модификации.===
+
=== 28 билет. Paxos. Алгоритм, его свойства.===
* [[Консенсус в распределённой системе]]
+
=== 29 билет. Paxos. Общие принципы. Основные модификации.===
* [[Replicated State Machine]]
+
=== 30 билет. Транзакции в распределенных системах. 2 Phase Locking===
* [[Paxos]]
+
=== 31 билет. Транзакции в распределенных системах. 2 Phase Commit.===
 +
=== 32 билет. СAP теорема (концепции, подходы, без доказательства)===
 +
=== 33 билет. Gossip. СRDT и дельта-CRDT (концепции, примеры алгоритмов, см. работу с семинара)===
 +
CRDT (Conflict-Free Replicated Data Type) &mdash; объект, который можно реплицировать на много узлов и обновлять параллельно без координации между узлами.
 +
 
 +
'''Репликация на основе состояния'''
 +
 
 +
Получив обновление от клиента, реплика сперва обновляет локальное состояние, затем отправляет это состояние другой реплике. Та применяет функцию merge, чтобы объединить свое состояние с полученным и отправляет его еще одной реплике, и т. д..
  
=== 30 билет. Raft. Алгоритм, его свойства.===
+
Достаточные условия согласованности:
* [[Консенсус в распределённой системе]]
 
* [[Replicated State Machine]]
 
* [[Raft]]
 
  
=== 31 билет. Транзакции в распределенных системах. 2 Phase Locking===
+
1. Множество возможных состояний образует полурешетку, т.е. частично упорядоченное множество с операцией наименьшей верхней грани, причем merge реализует эту операцию;
* [[Транзакции в распределённых системах]]
 
* [[2 Phase Locking]]
 
  
=== 32 билет. Транзакции в распределенных системах. 2 Phase Commit.===
+
2. Обновления возрастают.
* [[Транзакции в распределённых системах]]
 
* [[2 Phase Commit]]
 
  
=== 33 билет. СAP теорема (концепции, подходы, без доказательства)===
+
'''Репликация на основе операций'''
* [[CAP теорема]]
 
  
=== 34 билет. Gossip. СRDT и дельта-CRDT (концепции, примеры алгоритмов, см. работу с семинара)===
+
Реплика посылает не все состояние, а только обновление всем репликам. Согласованность можно гарантировать, если обновления коммутативны. Кроме того, требуется чтобы каждая операция была доставлена ровно один раз.
* [[Gossip-протоколы]]
 
* [[CRDT]]
 
  
=== 35 билет. Самостабилизирующиеся алгоритмы. Идея. Алгоритмы взаимного исключения и поиска остовного дерева ===
+
todo дельта-CRDT
* [[Иерархия ошибок в распределённых системах]]
 
* [[Самостабилизирующиеся алгоритмы]]
 
  
 
==Ссылки==
 
==Ссылки==
 
<references/>
 
<references/>

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)