Правило 2: в каждое передаваемое сообщение добавляется значение матричного времени Mi процесса-отправителя Pi на момент отправки этого сообщения. Когда процесс Pj получает сообщение от процесса Pi с отметкой времени Mmsg, он выполняет следующие шаги:
обновляет показания своих векторных часов в строке Mj[j, .] согласно векторному времени процесса Pi, полученному в строке Mmsg[i, .]:
1 ≤ k ≤ N: Mj[j, k] = max(Mj[j, k], Mmsg[i, k]); остальные элементы матрицы Mj обновляются по правилу:
1 ≤ k, l ≤ N: Mj[k, l] = max(Mj[k, l], Mmsg[k, l]).
исполняет Правило 1;
доставляет сообщение и приступает к его обработке. Элементы матрицы Mi[k, l] инициализируется нулем, 1 ≤ k, l ≤ N.
2
2
2
Пример работы алгоритма матричных часов для d = 1 приведен на рис. 3.10. Рассмотрим матричную отметку времени для события e 6 процесса P2. Событие e15 является последним событием в процессе P1, которое предшествует e26 согласно отношению причинно-следственного порядка. Поэтому M(e26)[2,1] = M(e 6)[1,1] = 5. Аналогично, M(e 6)[2,3] =
1
2
M(e26)[3,3] = 4. По сведениям процесса P2 последним событием процесса P1, о котором "знает" процесс P3, является событие e 2. Поэтому M(e 6)[3,1] = 2.
Аналогично, e 4 – последнее событие в P , о котором "знает" P по
3 3 1
сведениям P2, т.е. M(e26)[1,3] = 4.
Рис. 3.10. Пример работы алгоритма матричных часов.
3.5.1 Основные свойства
По определению строка Mi[i, .] обладает всеми свойствами векторных часов. Кроме этого, если для матричного времени процесса Pi верно неравенство mink (Mi[k, l]) ≥ t, то по сведениям процесса Pi каждый из процессов Pk "знает" о том, что локальное время процесса Pl достигло значения t или превышает его. Например, исходя из матричной отметки
времени события e 6 на рис. 3.10 процессу P известно, что все процессы в
2 2
системе обладают информацией о том, что ход выполнения процесса P1
достиг события e 2. Из данного неравенства процесс P может сделать
1 i
вывод, что всем другим процессам в системе известно о том, что процесс Pl уже не будет передавать информацию с отметкой своего логического локального времени меньшей, либо равной t. Во многих приложениях это означает, что процессам больше не нужно хранить какие-либо данные, полученные ранее от процесса Pl, и они могут без проблем удалять устаревшую информацию (англ. obsolete information).
Если значение прироста локальных логических часов всегда равно единице (d = 1), то элемент матрицы Mi[k, l] будет содержать в себе число событий, выполненных в процессе Pl и известных процессу Pk настолько, насколько об этом "знает" процесс Pi.
Do'stlaringiz bilan baham: |