2.7.3.2. Исчисление реального времени

Исчисление реального времени (RTC – Real -time calculus) [42] базируется на описании интенсивности входящих событий. Это описание также включает отклонения от этой интенсивности. С этой целью временные характеристики последовательности событий представляются кортежем кривых (графиков) поступления: ^u(Δ), ^l(Δ) ∈ IR ≥ 0,Δ ∈ IR ≥ 0.

Эти кривые представляют максимальное соответственно минимальное число событий поступающих внутри интервала времени Δ. Существуют наибольшее ^u(Δ) и наименьшее ^l(Δ) число событий поступающих в интервале (t, t +Δ) для всех t ≥ 0. На рис. 95 показан ряд возможных поступлений событий для некоторых возможных моделей поступления.

Рис. 95 Кривые поступления: периодический поток (слева),

периодический поток с джиттером J (справа)

Например, в случае периодического потока событий с периодом p существует максимум простого события происходящего на интервале времени (0, p). Аналогично существует верхняя граница двух событий внутри временного интервала (p,2p). Теперь рассмотрим нижнюю границу для интервала (0, p). Возможно не существует единичного события в этом интервале. Следовательно, граница равна 0. Так для Δ=0.5p будет существовать минимум 0 и максимум одно входное событие. В случае периодического потока события с джиттером J эти кривые сдвигаются на эту величину. Верхняя граница смещается влево, нижняя граница смещается вправо. Предполагается, что джиттер не накапливается. Верхнее подчеркивание в обозначении символизирует входящее событие.

Полезная вычислительная и коммуникационная пропускная способность может быть описана функциями обслуживания:

β^u(Δ),β^l(Δ) ∈ IR ≥ 0,Δ ∈ IR ≥ 0.

Эти функции позволяют моделировать ситуации, в которых изменяется полезная пропускная способность. На рис. 96 показана коммуникационная пропускная способность TDMA шины (time division multiple access – множественный доступ с временным разделением). Распределение выполняется периодически с периодом p. Арбитр выделяет шину на время s (окно). Во время этого окна шина достигает ширины полосы в b единиц.

Рис. 96. Функции обслуживания для TDMA шины

Верхняя граница достигается, если шина выделяется точно во время, когда начинается отсчет. Количество переданных данных тогда увеличивается линейно. Нижняя граница достигается, если шина была только что освобождена, когда начался отсчет Δ. Затем необходимо ждать p−s единиц времени пока шина не будет выделена снова.

Требуются отдельные методы для определения и β потоков (внешних) событий поступающих в систему, чтобы они могли быть использованы для моделирования. Эти вычисления не являются частью RTC. В противоположность границы для событий, генерируемых внутри системы, получаются с помощью исчисления.

До сих пор не было информации об объеме работы требуемой для каждого входящего события. Этот объем работы представляется отдельными функциями γ ^u(e), γ ^l(e) ∈ IR≥0 для каждой последовательности e входящих событий. Эта информация может быть получена из границ времени выполнения кода для обработки каждого из событий. На рис. 97 приведен пример таких функций. Этот пример базируется на предположении, что для обработки одиночного события требуется от трех до четырех единиц времени.

1 2 3 e

Рис. 97. Характеристика объема работы

Соответственно объем работы для одиночного события варьируется между 3 и 4 единицами времени, объем работы для двух событий варьируется между 6 и 8 единицами времени и т.д. Пунктирные линии не являются частью функции, т.к. она определена только для целого числа событий. Объем работы получающийся из входного потока событий теперь может быть легко вычислен. Верхняя и нижняя границы характеризуются функциями:

α ^u(Δ) = γ ^u(^u(Δ)) (1)

α ^l(Δ) = γ ^l(^l(Δ)) (2)

Должно быть достаточной вычислительная или коммуникационная пропускная способность для обработки этого объема. Число событий, которое может быть обработано с полезной вычислительной пропускной способностью может быть вычислено как

^u(Δ) = (γ ^l)⁻¹(β ^u(Δ)) (3)

^l(Δ) = (γ ^u)⁻¹(β ^l(Δ)) (4)

Равенства 3 и 4 используют обратные функции γ ^u ( (γ ^u)⁻¹) и γ ^l ( (γ ^l)⁻¹) для конвертирования границ полезной пропускной способности (измеряется действительными значениями времени) в границы, измеряемые в терминах числа событий которые могут быть обработаны.

Основываясь на этой информации, можно получить свойства выходных потоков событий из входных потоков событий. Предположим, что входной поток характеризуется границами [^l , ^u]. Затем вычисляем характеристики выходных потоков как, например соответствующие границам

[^l’, ^u’] исходящего потока событий и оставшейся пропускной способности полезной для других задач. Эту оставшуюся пропускную способность получают преобразованием кривых обслуживания [^l , ^u] в кривые обслуживания [^l’,^u’] (рис. 98). Эта оставшаяся пропускная способность может быть использована для низкоприоритетных задач для выполнения на том же процессоре.

Рис. 98. Преобразование потока событий и пропускной способности

компонентами реального времени

Исходящие потоки и оставшаяся пропускная способность ограничиваются следующими функциями:

^u’ = [(^u⊗^u) ^l ]∧ ^u (5)

^l’ = [(^{l u})⊗ ^l ]∧ ^l (6)

^u’ = (^u−^l) ∅0 (7)

^l’ = (^l −^u)0 (8)

Операции, используемые в этих равенствах, определяются следующим образом:

( f∅g)(t) = inf 0≤u≤t{ f (t −u)+g(u)} (9)

( fg)(t) = sup 0≤u≤t{ f (t −u)+g(u)} (10)

( fg)(t) = sup u≥0{ f (t +u)−g(u)} (11)

( f∅g)(t) = inf u≥0{ f (t +u)−g(u)} (12)

∧ обозначает оператор минимума;

inf – точная нижняя граница;

sup – точная верхняя граница.

По существу эти равенства характеризуют исходящие потоки и пропускную способность. Эти равенства были адоптированы из теории связи. Для работы с этими равенствами можно просто использовать инструментарий Matlab.

Эта же теория позволяет вычислить задержку вызванную компонентами реального времени, а так же размер буфера необходимого для временного хранения входящих/исходящих событий.