Глобальное состояние (информатика) ⇐ Васина Википедия

[wiki_en]

'''Глобальное состояние''' распределенной вычислительной|распределенной системы представляет собой совокупность всех локальных состояний процесса (вычисления)|процесса и содержимого всех каналов связи|каналов связи в конкретный момент. Поскольку в распределенных системах отсутствует общая память и глобальные часы, ни один процесс не может одновременно отслеживать все локальные состояния и передаваемые сообщения.

Наивная совокупность локальных состояний, собранных последовательно, без координации, создает глобальное состояние, которое может не соответствовать ни одному состоянию, через которое система фактически прошла. Сообщение, отправленное до того, как будет записано состояние одного процесса, но полученное после того, как состояние другого процесса, может оказаться исчезнувшим или продублированным, создавая логически невозможный снимок.

Глобальное состояние является «согласованным», если оно соответствует состоянию, через которое могло пройти возможное выполнение системы: формально ни одно сообщение не записывается как полученное, если оно также не записывается как отправленное. Это понятие, введенное К. Мани Чанди и Лесли Лэмпортом в 1985 году, также выражается как «последовательный разрез» истории выполнения системы. Ченди и Лэмпорт доказали, что любое непротиворечивое глобальное состояние достижимо из начального состояния системы, а фактическое текущее состояние достижимо из любого записанного непротиворечивого глобального состояния.

Согласованные глобальные состояния лежат в основе обнаружения взаимоблокировок, обнаружения завершения, распределенной сборки мусора (информатика) | сбор мусора, контрольных точек для обеспечения отказоустойчивости и распределенной отладки. Их достаточно для оценки «стабильных предикатов», свойств, которые когда-то были истинными, остаются истинными, не требуя приостановки работы системы.

== Модель системы ==

Модель, принятая Ченди и Лэмпортом, состоит из фиксированного набора
Каждый процесс выполняет последовательность событий трех типов: событие «отправки» на исходящем канале, событие «получения» на входящем канале или «внутреннее» событие, которое изменяет локальное состояние без обмена данными. «Локальное состояние»
Отношение событий «произошло до», введенное Лэмпортом в 1978 году, обеспечивает частичный порядок: событие
== Глобальное состояние ==

'''Глобальное состояние''' системы представляет собой кортеж

:GS = (s_1, s_2, \ldots, s_n,\ M_{12}, M_{13}, \ldots, M_{n(n-1)})

состоящий из местного государства
Как математический объект, глобальное состояние не обязательно должно соответствовать какому-либо моменту, который одновременно можно было наблюдать с одной точки зрения. Локальные состояния двух процессов могут быть записаны в разное реальное время, и сообщения, передаваемые в течение этого интервала, не могут появляться в локальном состоянии ни одного процесса.

'''Пример.''' Рассмотрим три процесса.
== Согласованное глобальное состояние ==

=== Условие согласованности ===

«История выполнения» системы представляет собой набор всех событий, частично упорядоченных отношением «произошло до». '''разрез'''
Разрез является «согласованным», если для каждого события приема в прошлом
=== Почему наивный сбор не работает ===

Если наблюдатель последовательно записывает локальные состояния (сначала запрашивая
Соответствующий разрез противоречив: получение
=== Теорема о достижимости ===

Ченди и Лэмпорт доказали, что любое согласованное глобальное состояние, записанное во время выполнения, достижимо из начального состояния этого выполнения, а фактическое состояние системы на момент завершения записи достижимо из записанного согласованного глобального состояния. Формально, если
Записанное состояние не обязательно должно совпадать с каким-либо состоянием, которое одновременно существовало во время выполнения, но оно представляет собой допустимое промежуточное состояние, через которое могло пройти возможное выполнение системы. Это свойство делает записанное состояние надежным для проверки свойств системы (например, наличия взаимоблокировки) без приостановки или приостановки выполнения.

== Стабильные предикаты ==

Предикат (логика)|предикат
По теореме достижимости, если устойчивый предикат
Нестабильные предикаты, которые могут стать ложными после того, как станут истинными, не могут быть надежно оценены на основе одного снимка. Обнаружение временных условий, например, находится ли конкретное сообщение в данный момент в пути, требует постоянного мониторинга или многочисленных наблюдений, выходящих за рамки методов, основанных на моментальных снимках.

== Запись глобального состояния ==

Для записи согласованного глобального состояния требуется скоординированный протокол, поскольку сообщения могут находиться в пути, когда собираются локальные состояния; нескоординированный набор может привести к противоречивому разрезу. Любой правильный протокол должен гарантировать, что набор записанных локальных состояний и содержимого каналов удовлетворяет условию согласованности.

Протокол на основе маркеров, разработанный Чанди и Лэмпортом (1985), действует следующим образом. Инициирующий процесс записывает свое собственное локальное состояние и отправляет специальное управляющее сообщение, «маркер», по каждому исходящему каналу перед отправкой любых дальнейших сообщений приложения по этим каналам. Когда процесс
Протокол на основе маркеров предполагает порядок каналов FIFO. Для систем с каналами, отличными от FIFO, алгоритм Лай-Янга (1987) использует «раскраску» сообщений, помечая каждое сообщение приложения как до или после снимка, чтобы избежать необходимости в явных маркерах. Алгоритм Маттерна (1989) использует векторные часы для определения того, какие сообщения к какому снимку принадлежат, что позволяет создавать несколько одновременных снимков без выделенных сообщений-маркеров. name="Matter1989" />

== Приложения ==

Согласованные глобальные состояния и поддерживаемое ими свойство стабильного предиката применялись в исследованиях и практике распределенных систем.

Распределенный тупик — это цикл процессов, каждый из которых ожидает ресурса, принадлежащего следующему; это стабильная собственность. Запись согласованного глобального состояния и проверка записанного графика ожидания циклов позволяет обнаружить взаимоблокировку без ложных срабатываний: если цикл существует в записанном состоянии, он существует в фактическом текущем состоянии благодаря стабильности. Завершение, отсутствие активных процессов и отсутствие сообщений в пути являются стабильными. Согласованный глобальный снимок, в котором все состояния процессов простаивают, а все состояния каналов пусты, подтверждает, что вычисление завершено. Объект без активных ссылок может быть собран; это свойство стабильно в объединенных состояниях кучи всех процессов. Сборщики мусора на основе моментальных снимков идентифицируют недоступные объекты, записывая согласованное глобальное состояние всех куч процессов.

Периодическая запись согласованных глобальных состояний создает точки восстановления, из которых выполнение может быть возобновлено после сбоя процесса, без повторного воспроизведения полного выполнения с самого начала. Теорема о достижимости гарантирует, что перезапуск из записанного согласованного состояния приведет к допустимому продолжению. Нарушения утверждений и инвариантные сбои являются стабильными, если они представлены как условия, которые после срабатывания не удаляются автоматически. Воспроизведение записанных согласованных глобальных состояний позволяет отладчику проверить, соблюдаются ли такие условия во время выполнения.

== Расширения ==

Последующая работа смягчила предположения исходной модели Чанди-Лэмпорта.

'''Каналы без FIFO'''. Исходный протокол требует, чтобы каналы доставляли сообщения по порядку. Лай и Янг (1987) расширили запись моментальных снимков на каналы, не относящиеся к FIFO, путем окраски сообщений: каждый процесс окрашивает все сообщения приложения, которые он отправляет после записи своего состояния, с помощью цвета после моментального снимка, что позволяет получателям без маркеров отличать сообщения до снимка от сообщений после снимка. Маттерн (1989) добился аналогичного результата, используя векторные часы, которые снабжают каждое сообщение меткой времени, достаточной для определения его связи с снимок без явной окраски или маркеров.

'''Системы со сбоями процессов.''' Если процесс дает сбой во время записи моментального снимка, его локальное состояние невозможно зафиксировать; сообщения, находящиеся в пути по каналам к или от отказавшего процесса, могут никогда не быть доставлены. Скоординированные протоколы контрольных точек и схемы регистрации сообщений расширяют возможности записи моментальных снимков для отказоустойчивых систем за счет объединения локальной записи состояния с журналированием отправленных и полученных сообщений, что позволяет выполнять восстановление даже в случае потери некоторых записанных состояний.

«Динамические наборы процессов». Существуют варианты систем, в которых процессы могут присоединяться к вычислениям или покидать их во время выполнения. Эти протоколы отслеживают членство в процессах как часть моментального снимка, записывая, какие процессы существовали на момент наблюдения каждого локального состояния.

== См. также ==

* Алгоритм Чанди – Лэмпорта
* Алгоритм создания снимков
* Векторные часы
* Временная метка Лампорта
* Случилось раньше
* Тупик
* Распределенные вычисления




Распределенные вычисления
Распределенные алгоритмы
Информатика
Параллелизм (информатика)

Подробнее: https://en.wikipedia.org/wiki/Global_st ... r_science)