Синхронизация часов: различия между версиями

Простейшим вариантом синхронизации часов является внешняя синхронизация, при которой у одного из процессоров, называемого источником, имеются часы без дрейфа, и задачей всех процессоров является поддержка как можно более точной оценки текущего показания часов источника. Эта формулировка соответствует ньютоновской модели, в которой процессоры находятся в четко определенной системе временных координат, а часы источника отсчитывают стандартное время. Говоря формально, при внешней синхронизации каждый процессор v имеет две выходные переменные Av и Ѵв; оценка v времени источника в заданном состоянии равна LTv + Av, где LTv – текущее локальное время в v. От алгоритма требуется, чтобы разница между временем источника и его оценкой была не более Ѵв (заметим, что Av, как и Ѵв, может динамически меняться в процессе выполнения). О производительности алгоритма судят по значению переменных Ѵв: чем они меньше, тем лучше.

Определение 1. Пусть f$ – представление выполнения системы, а H – спецификация реального времени для f$. Граф синхронизации, порожденный f$ и H, является ориентированным взвешенным графом Грц = (V;E;w), где V – множество событий в /}, и для каждой упорядоченной пары событий p q в /}, такой, что H(p; q) < 1, существует ориентированное ребро (p; q) 2 E.

Естественное понятие расстояния от события p до события q в графе синхронизации Г, обозначаемое drip, Ф> определяется длиной кратчайшего взвешенного пути от p до q, или бесконечностью, если q недостижимо из p. Поскольку веса могут быть отрицательными, необходимо доказать, что понятие точно определено: действительно, было показано, что если Грн получен из выполнения с представлением f$, удовлетворяющего спецификации реального времени H, то Грн не содержит ориентированных циклов с отрицательным весом.

Теорема 1. Пусть a – выполнение с представлением f$. Тогда a удовлетворяет спецификации реального времени H тогда и только тогда, когда RT(p) - RT(q) < dr(p, q) + LT(p) - LT(q) для любых двух событий p и q в Грн.

Теорема 2. Пусть Грн = (V, E, w) – граф синхронизации, полученный из представления f$, удовлетворяющего спецификации реального времени H. Тогда для любого заданного события p0 2 V и для любого конечного числа N > 0 существуют исполнения ao и a\ с представлением f$, удовлетворяющие спецификации H, такие, что выполняются следующие присваивания реального времени.

С алгоритмической точки зрения важным недостатком результатов теорем 1 и 2 является то, что они зависят от представления выполнения, которое может неограниченно расти. Так ли оно необходимо? Последний общий результат в работе [10] отвечает на этот вопрос утвердительно. В частности, было показано, что в некотором варианте вычислительной модели ветвящейся программы пространственная сложность любого алгоритма синхронизации, работающего с произвольными спецификациями реального времени, не может быть ограничена функцией от размера системы. Результат доказывается путем рассмотрения нескольких сценариев на простой системе из четырех процессоров на одной линии.

Теорема 1 сразу же дает алгоритм синхронизации часов: каждый процессор поддерживает известное ему представление (representation) части графа синхронизации. Это можно сделать с помощью протокола полной информации: этот граф отправляется в каждом исходящем сообщении, и всякий раз, когда приходит сообщение, граф расширяется, чтобы включить новую информацию из графа в пришедшем сообщении. Согласно Теореме 2, полученный таким образом граф синхронизации представляет в любой момент времени всю доступную информацию, необходимую для оптимальной синхронизации. Для примера рассмотрим внешнюю синхронизацию. Непосредственно из определений следует, что все события, связанные с часами без дрейфа (например, события в узле-источнике), находятся на расстоянии 0 друг от друга в графе синхронизации и поэтому могут рассматриваться при вычислении расстояния как один узел s. Теперь, предполагая, что часы источника действительно показывают реальное время, легко увидеть, что для любого события p,

Одной из центральных проблем при синхронизации часов являются ошибочные выполнения, при которых нарушается спецификация реального времени. Графы синхронизации выявляют любую обнаруживаемую ошибку: представления, не имеющие выполнения, соответствующего спецификации реального времени, приводят к графам синхронизации с отрицательными циклами. Однако желательно преодолеть такие ошибки – например, удалив из графа синхронизации некоторые ребра, чтобы разорвать все циклы с отрицательным весом. Естественной целью в этом случае является удаление наименьшего числа ребер. Эта задача является APX-трудной, поскольку она обобщает задачу о множестве обратных дуг. К сожалению, нетривиальные приближенные алгоритмы для ее решения неизвестны.