4817
правок
Синхронизация часов: различия между версиями
Перейти к навигации
Перейти к поиску
→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 52: | Строка 52: | ||
Теорема 2. Пусть | '''Теорема 2. Пусть <math>\Gamma_{\beta H} = (V, E, w)</math> – граф синхронизации, полученный из ракурса <math>\beta</math>, удовлетворяющего спецификации реального времени <math>H</math>. Тогда для любого заданного события <math>p_0 \in V</math> и для любого конечного числа <math>N > 0</math> существуют исполнения <math>\alpha_0</math> и <math>\alpha_1</math> с ракурсом <math>\beta</math>, удовлетворяющие спецификации <math>H</math>, такие, что выполняются следующие присваивания реального времени.''' | ||
В | * В <math>\alpha_0</math> для всех <math>q \in V</math> с <math>d_{\Gamma} (q, p_0) < \infty</math> верно <math>RT_{\alpha_0}(q) = LT(q) + d_{\Gamma}(q, p_0)</math>, и для всех <math>q \in V</math> с <math>d_{\Gamma}(q, p_0) = \infty</math> верно <math>RT_{\alpha_0} > LT(q) + N.</math> | ||
* В <math>\alpha_1</math> для всех <math>q \in V</math> с <math>d_{\Gamma} (p_0, q) < \infty</math> верно <math>RT_{\alpha_1}(q) = LT(q) - d_{\Gamma}(p_0, q)</math>, и для всех <math>q \in V</math> с <math>d_{\Gamma}(p_0, q) = \infty</math> верно <math>RT_{\alpha_1} < LT(q) - N.</math> | |||
С алгоритмической точки зрения важным недостатком результатов теорем 1 и 2 является то, что они зависят от ракурса выполнения, которое может неограниченно расти. Так ли оно необходимо? Последний общий результат в работе [10] отвечает на этот вопрос утвердительно. В частности, было показано, что в некотором варианте вычислительной модели ветвящейся программы пространственная сложность любого алгоритма синхронизации, работающего с произвольными спецификациями реального времени, не может быть ограничена функцией от размера системы. Результат доказывается путем рассмотрения нескольких сценариев на простой системе из четырех процессоров на одной линии. | |||
С алгоритмической точки зрения важным недостатком результатов теорем 1 и 2 является то, что они зависят от ракурса выполнения, которое может неограниченно расти. Так ли оно необходимо? Последний общий результат в работе [10] отвечает на этот вопрос утвердительно. В частности, было показано, что в некотором варианте вычислительной модели ''ветвящейся программы'' пространственная сложность любого алгоритма синхронизации, работающего с произвольными спецификациями реального времени, не может быть ограничена функцией от размера системы. Результат доказывается путем рассмотрения нескольких сценариев на простой системе из четырех процессоров на одной линии. | |||