|
Скалярные часы не являются строго непротиворечивыми и не позволяют зафиксировать параллелизм событий. События, которые могли бы происходить одновременно, могут получить различные отметки времени как будто они происходили в каком-то определенном порядке. Для некоторых задач, например, рассмотренных в п. 3.2.2, такое ограничение не является существенным. Однако, к примеру, при отладке распределенных программ (англ. distributed debugging) информация о том,
оказывают ли события потенциальное влияние друг на друга или нет, становится важной.
Параллелизм событий можно зафиксировать, если часовые отметки времени параллельных событий оказываются несравнимыми. Другими словами, выявление параллельных событий возможно только тогда, когда множество T допустимых значений логического времени оказывается упорядоченным частично, но не линейно. Чтобы понять, из каких элементов может состоять такое множество, предположим, что в каждом процессе работают логические локальные часы, увеличивающие свои показания на единицу перед наступлением каждого события. Тогда для стороннего наблюдателя, которому одномоментно доступна вся картина происходящего, ход выполнения распределенной системы будет определяться совокупностью показаний локальных часов всех процессов. Подходящей структурой данных для представления такого глобального времени будет являться N-мерный вектор, в котором i-й компонент содержит текущее значение локального времени процесса Pi. Пример изменения глобального векторного времени V с точки зрения стороннего наблюдателя приведен на рис. 3.5.
Рис. 3.5. Пример изменения глобального векторного времени.
Процессам же текущее значение глобального времени недоступно. Каждый процесс может лишь сформировать свое собственное представление о ходе выполнения процессов распределенной системы через поступающие ему сообщения. Для этого каждый процесс Pi должен локально поддерживать работу с вектором Vi[1..N]. В компоненте Vi[i] этого вектора хранятся показания логических локальных часов процесса Pi,
измеряющих ход его собственного выполнения. Логические глобальные часы, используемые для записи информации о ходе выполнения других процессов, представлены остальными компонентами вектора Vi, а именно, компонент Vi[j] содержит последние сведения, полученные процессом Pi о локальном времени процесса Pj. Другими словами, если Vi[j] = x, то процесс Pi "знает" о том, что локальное время процесса Pj достигло значения x. Стоит отметить, что к настоящему моменту локальные часы процесса Pj могли уйти вперед, т.е. текущее локальное время процесса Pj может превышать значение x, однако, процесс Pi не получал об этом никакой информации через направляемые ему сообщения. Весь вектор Vi можно рассматривать как локальное представление процесса Pi о глобальном векторном времени, отражающем ход выполнения всех процессов в распределенной системе.
Таким образом, областью значений часовой функции Θ является множество N-мерных векторов неотрицательных целых чисел, где N – количество процессов в распределенной системе. Поэтому такие часы называют векторными часами. Отметка времени события ei, происходящего в процессе Pi, определяется всеми компонентами вектора Vi на момент наступления ei. Такую отметку часто называют векторной отметкой времени события ei и обозначают через V(ei).
Для сравнения двух векторных отметок времени V(ei) и V(ej') событий ei и ej' введем следующие отношения:
V(ei) = V(ej') k: V(ei)[k] = V(ej')[k];
V(ei) ≤ V(ej') k: V(ei)[k] ≤ V(ej')[k];
V(ei) < V(ej') V(ei) ≤ V(ej') и k: V(ei)[k] < V(ej')[k].
Очевидно, что введенное выше отношение < определяет частичный порядок на множестве векторных отметок времени для N ≥ 2. Например, вектора V(ei) = [2, 3, 0] и V(ej') = [0, 4, 1] являются несравнимыми. Для обозначения этого факта будем использовать запись V(ei) || V(ej'):
V(ei) || V(ej') ¬(V(ei) < V(ej')) ˄ ¬(V(ej') < V(ei)).
Для выполнения условия непротиворечивости логических часов каждый процесс Pi использует следующие правила продвижения своего векторного времени.
Do'stlaringiz bilan baham: |
