292
правки
Изменения
Нет описания правки
[[Категория: Параллельное программирование]]
{{Определение|id = vector_clock|definition = '''Векторные часы''' — это функция $VC(e) \colon E \to \mathbb R^n$ (из событий в вектор константного размера) такая, что для любых двух событий $e$ и $f$ следующие утверждения равносильны:* $e \to f$ ($e$ [[Частичный порядок|произошло-до]] $f$)* Каждый $VC(e) < VC(f)$ (все компоненты $VC(e)$ меньше всех компонент $VC(f)$)}} Алгоритм векторных часов можно построить из [[Логические часы Лампорта|логических часов Лампорта]], если попросить каждый процесс помнить счётчики всех процессов, а не только свой: * каждый поток имеет целочисленный $n$-мерный вектор ($n – $ — количество потоков), проинициализированный нулями.* Перед посылкой/принятием сообщения, поток увеличивает свою компоненту вектора.в случае внутреннего события счётчик текущего процесса увеличивается на 1;* При посылке перед отправкой сообщения внутренний счётчик, соответствующий текущему процессу, увеличивается на 1, и вектор целиком прикрепляется к сообщению отправляющий поток добавляет свой вектор, а ;* при приеме получении сообщения поток присваивает своей переменной счётчик текущего процесса увеличивается на 1, далее значения в текущем векторе выставляются в покомпонентный максимум из от текущего и полученного значения и значения собственной переменной.
Значением вышеупомянутой функции на событии является значение переменной, принадлежащей тому же потоку, что и событие. Стоит заметить, что векторное время уникально для каждого события.
Оказывается, что если в распределенной системе ввести [[Параллельное программирование: Частичный порядок|частичный порядок предшествования на событиях]], то имеет место следующее утверждение:<br>
''a'' предшествует ''b'', тогда и только тогда, когда логическое время векторных часов события ''a'' меньше логического времени события ''b'' (при этом вектор ''x'' меньше вектора ''y''покомпонентно с одной строгостью, т.е если для каждой компоненты выполяется <tex>x_i \le y_i</tex> и <tex>\exists j: x_j < y_j</tex>).
Важным свойством векторных часов в распределенных системах с введенным [[Параллельное программирование: Частичный порядок|частичным порядком предшествования]] оказывается то, что при сравнении векторов времени двух событий достаточно сравнивать только компоненты процессов, которым эти события принадлежат.
