Векторные часы — различия между версиями
(Новая страница: «'''Логическими векторными часами''' называется функция из множества событий (прием/посылка …») |
|||
| Строка 7: | Строка 7: | ||
Значением вышеупомянутой функции на событии является значение переменной, принадлежащей тому же потоку, что и событие. Стоит заметить, что векторное время уникально для каждого события. | Значением вышеупомянутой функции на событии является значение переменной, принадлежащей тому же потоку, что и событие. Стоит заметить, что векторное время уникально для каждого события. | ||
| − | Оказывается, что если в распределенной системе ввести частичный порядок предшествования на событиях, то имеет место следующее утверждение:<br> | + | Оказывается, что если в распределенной системе ввести [[Параллельное программирование: Частичный порядок|частичный порядок предшествования на событиях]], то имеет место следующее утверждение:<br> |
''a'' предшествует ''b'', тогда и только тогда, когда логическое время векторных часов события ''a'' меньше логического времени события ''b'' (при этом вектор ''x'' меньше вектора ''y'', если для каждой компоненты выполяется <tex>x_i \le y_i</tex> и <tex>\exists j: x_j < y_j</tex>). | ''a'' предшествует ''b'', тогда и только тогда, когда логическое время векторных часов события ''a'' меньше логического времени события ''b'' (при этом вектор ''x'' меньше вектора ''y'', если для каждой компоненты выполяется <tex>x_i \le y_i</tex> и <tex>\exists j: x_j < y_j</tex>). | ||
| − | Важным свойством векторных часов в распределенных системах с введенным частичным порядком предшествования оказывается то, что при сравнении векторов времени двух событий достаточно сравнивать только компоненты процессов, которым эти события принадлежат. | + | Важным свойством векторных часов в распределенных системах с введенным [[Параллельное программирование: Частичный порядок|частичным порядком предшествования]] оказывается то, что при сравнении векторов времени двух событий достаточно сравнивать только компоненты процессов, которым эти события принадлежат. |
Версия 14:10, 26 июня 2010
Логическими векторными часами называется функция из множества событий (прием/посылка сообщений) в вектор из целых чисел.
- Каждый поток имеет целочисленный n-мерный вектор (n – количество потоков), проинициализированный нулями.
- Перед посылкой/принятием сообщения, поток инкрементит свою компоненту вектора.
- При посылке сообщения к сообщению отправляющий поток добавляет свой вектор, а при приеме сообщения поток присваивает своей переменной покомпонентный максимум из полученного значения и значения собственной переменной.
Значением вышеупомянутой функции на событии является значение переменной, принадлежащей тому же потоку, что и событие. Стоит заметить, что векторное время уникально для каждого события.
Оказывается, что если в распределенной системе ввести частичный порядок предшествования на событиях, то имеет место следующее утверждение:
a предшествует b, тогда и только тогда, когда логическое время векторных часов события a меньше логического времени события b (при этом вектор x меньше вектора y, если для каждой компоненты выполяется и ).
Важным свойством векторных часов в распределенных системах с введенным частичным порядком предшествования оказывается то, что при сравнении векторов времени двух событий достаточно сравнивать только компоненты процессов, которым эти события принадлежат.
