Логические часы Лампорта и векторные часы. Их свойства

By Денис Чащин  

Описание

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

Определения

Частичный порядок, это когда:

  1. Посылка предшествует получению этого-же сообщения,
  2. События в одном потоке упорядочены.

Логические часы — это функция c(e):\forall{e,f\in{E}:e\right{}f \Rightarrow{} c(e)<c(f)}, тоесть если событие e произошло до f, то c(e) имеет значение меньше, чем c(f)

Алгоритмы

Логические часы Лампорта:

  1. Процесс хранит у себя целое число
  2. Перед посылкой увеличивает число на 1
  3. При приеме присваивается своей переменной времени max+1

Логическое время получается уникальным только в рамках своего потока. Если a\right{b}, тоc(a)<c(b). Обратное неверно.

Векторные часы:

Функция V_c:E\right{}V, для которой

\forall{e,f\in{E}} e\right{f}\Rightarrow{V_c(e)<V_c(f)}

(где E — множество событий, а V — вектор)

  1. Каждый поток имеет n — мерный вектор
  2. Перед посылкой увеличивает свою компоненты
  3. При приеме присваиваем покомпонентный максимум

Значением функции времени является значение из того-же потока, что и событие. Для каждого события векторное время уникально. Если a\right{b} то для векторов a и b выполнено a\le{b}. (Это значит, что для компонент векторов a_i и b_i a_i\le{b_i} и \exists{j:a_j<b_j}).

Часы с прямой зависимостью

Говорят, что процесс e находится в прямой зависимости от процесса f, если они связаны не более чем одной передачей сообщения.

  1. Каждый процесс хранит вектор
  2. Перед посылкой/приемом увеличивает свою компоненту
  3. При приеме присваиваем максимум принимаемой и отсылаемой
Отличие от векторных:
  1. При посылке посылаем только свою компоненту
  2. При приеме максимум только по принятной и своей компонентой

a\right{}b \Leftrightarrow{} a<b (a.v[a.p]\le{}b.v[a.p])

Матричные часы (обобщенные векторные)

  1. Каждый процесс хранит матрицу
  2. При передаче передается вся матрица
  3. При приеме каждый элемент матрицы берется как максимальный из принятой и сушествующей
  4. Каждый элемент собственного вектора выбирается как максимум из соответствующих элементов других векторов

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

 
Предыдущая статья из серии «О параллельном программировании»


Post a Comment

Your email is never shared. Required fields are marked *

*
*