Изменения

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

Кворум

2043 байта добавлено, 19:37, 2 июня 2019
Пример
[[Категория: Параллельное программирование]]
{{Определение|definition='''Кворум''' - множество наборов это семейство $Q$ подмножеств множества процессов такое$2^\mathbb P$ причем:* $Q$ замкнуто относительно взятия надмножества, т.е. если $Q \ni A \subseteq B$, что каждые то $B \in Q$* Любые два элемента (т.е подмножества относительно множества процессов) этого семейства имеют непустое пересечение. }}Кворум позволяет решить проблему отсутствия взаимного исключения в CS: выбираем кворум $Q$, а дальше каждая вершина должна получить разрешение на вход в критическую секцию у кворума.Фишка в том, что каждая вершина может выбрать свой собственный кворум.Например, при оптимизации задержки можно послать запрос всем, а войти в секцию, как только получили подтверждение от хоть какого-нибудь семейства из кворума. Тонкость: если каждая вершина просто разрешает войти в критическую секцию первому приславшему запрос,то получаем deadlock из-за проблем с порядком сообщений при broadcast (например, если у нас кворум — это два выделенных координатора).Так что нам нужно требовать total order multicast, например, [[Алгоритм Скина|алгоритмом Скина]] (дальше в билетах, тут на него просто ссылаемся). == Пример ==Рассмотрим 5 процессов — P1, P2, P3, P4, P5.  Кворумом для них будет следующее семейство: {[P1, P2, P3], [P3, P4, P5]}. Кстати, такое семейство тоже будет кворумом: {[P1, P2, P3, P4, P5]}.
Кворум замкнут по надмножеству.
Кворум позволяет решить проблему критической секции - нужно лишь спросить Еще примеры: централизованный алгоритм (кворум — все процессы кворума. Пример: подмножества, содержащие лидера), [[Кворум простого большинства|кворум простого большинства]], [[Кворум рушащейся стенки|"рушащаяся" стенка]].
292
правки

Навигация