научная статья по теме МИНИМИЗАЦИЯ ДЖИТТЕРА ПРИ ПЛАНИРОВАНИИ ВЫЧИСЛЕНИЙ В СИСТЕМАХ РЕАЛЬНОГО ВРЕМЕНИ Математика

Текст научной статьи на тему «МИНИМИЗАЦИЯ ДЖИТТЕРА ПРИ ПЛАНИРОВАНИИ ВЫЧИСЛЕНИЙ В СИСТЕМАХ РЕАЛЬНОГО ВРЕМЕНИ»

= РАСПРЕДЕЛЕННЫЕ ВСТРОЕННЫЕ СИСТЕМЫ РЕАЛЬНОГО ВРЕМЕНИ =

УДК 65.012.122

МИНИМИЗАЦИЯ ДЖИТТЕРА ПРИ ПЛАНИРОВАНИИ ВЫЧИСЛЕНИЙ В СИСТЕМАХ РЕАЛЬНОГО ВРЕМЕНИ *

© 2014 г. Н.В. Колесов, М.В. Толмачева, П.В. Юхта

ГНЦ РФ ОАО «Концерн «ЦНИИ «Электроприбор» 197046 Санкт-Петербург, ул. Малая Посадская, 30 E-mail: ioukhta@mail.ru Поступила в редакцию 10.05.2013

Предлагаются алгоритмы планирования вычислительного процесса в однопроцессорных системах реального времени. Предполагается, что продолжительность решения задач известна неточно и определяется временным интервалом, что порождает неточность временной привязки (джиттер) решаемых задач.

1. ВВЕДЕНИЕ

В настоящей работе рассматривается проблема планирования в однопроцессорных системах реального времени (СРВ) [1, 4-8], под которой понимается поиск наилучшей с точки зрения заданного критерия упорядоченности для решаемых задач. Планирование вычислений является важным этапом проектирования и применения любых вычислительных систем, однако наибольшие проблемы возникают в широко распространенных на практике СРВ. Правильность функционирования этих систем зависит не только от логической корректности выполняемых вычислений, но и от времени, за которое эти вычисления производятся. Быстродействие СРВ должно быть адекватно скорости протекания наблюдаемых или управляемых с ее участием процессов. Класс СРВ достаточно многообразен. К нему относят различные системы обработки информации, навигации и управления.

Характерными особенностями организации вычислительного процесса в СРВ являются периодичность и, в общем случае, разноприо-ритетность решаемых задач, наличие для них директивных сроков, необходимость обеспечения для интервалов решения задач достаточно точной временной привязки. Заметим, что вы-

* Работа проводилась при поддержке гранта РФФИ 10-08-00035 а

полнению последнего требования препятствует целый ряд факторов и, прежде всего, зависимость длительности решения задач от исходных данных. В результате момент начала любой задачи будет "плавать" из-за неопределенности в длительностях предшествующих ей задач. Для учета этой неопределенности далее будем представлять время решения задачи временным интервалом ej = [ej, ej], j = 1,m, где щ -нижняя, a ej - верхняя границы интервалов, m - число решаемых задач.

Безусловно, по вопросам планирования вычислений в СРВ опубликовано очень много работ, начиная с классической работы [4], и заканчивая монографиями [1, 5-7]. Алгоритмы, предлагаемые в этих работах, используют различные критерии, среди которых, например, минимум максимального отклонения от заданных директивных сроков, минимум энергопотребления и ряд других. При этом проблема планирования с учетом неточности (точности) временной привязки задач до сих пор освещена в литературе весьма ограниченно, хотя на ее существование обращается внимание практически во всех упомянутых выше монографиях. В англоязычной литературе эта проблема обозначается термином "дрожание фазы" (jitter). Как правило, предлагаемые решения связаны с вероятностным подходом, предполагающим знание плотности распределения вероятности для длительностей задач, что на прак-

Рис. 1. Иллюстрация неточности временной привязки задач.

тике обычно не выполняется. Настоящая работа в определенной степени восполняет этот пробел.

2. АЛГОРИТМЫ ОПТИМАЛЬНОГО ПЛАНИРОВАНИЯ ЗАДАЧ

Одним из вариантов постановки проблемы планирования является оптимизация плана но минимуму некоторого функционала от средней неточности временной привязки задач. Некоторые из приводимых далее алгоритмов с математической точки зрения представляют собой проекцию на данную проблему известных алгоритмов планирования при минимизации среднего времени прохождения работ (пребывания работ в системе) [2|. Это позволяет далее придерживаться в отношении таких алгоритмов краткого стиля изложения, отсылая желающих ознакомиться с доказательствами приводимых утверждений, например, к выше упомянутой литературе [2].

Будем говорить, что j-•&я задача привязана к моменту времени с точностью 5?, если время начала решения этой задачи лежит в интервале [tj — 5?, + 5? ]. Причины неточной временной привязки моментов начала решения задач могут быть различны. Одна из причин заключается в зависимости длительности решения задач от значений текущих исходных данных. При этом время решения ^ой задачи может быть охарактеризовано временным интервалом ё? = [е?, ё?] j = 1,т. Неопределенность времени выполнения задачи определим величиной А? = 2 (ё? — е?). Задача, стоящая первой в цикле обработки (рис. 1), имеет точную временную привязку (51 = 0) в рамках данной постановки проблемы. Однако уже привязка второй задачи характеризуется погрешностью 52, равной неопределенности времени выполнения первой

задачи 52 = А1 = 0, привязка третьей задачи характеризуется погрешностью 5з, равной сумме неопределенностей времени выполнения первой и второй задач 5з = А1+А2 = 0, и т.д. Можно назвать и другие причины, порождающие погрешность временной привязки. Среди них, в частности, прерывания, апериодические задачи и изменения в составе решаемых задач.

Формулируя математическую постановку задачи, положим, что последствия всех причин неточной привязки пересчитаны в априори известную неопределенность времени выполнения. Далее характеристики задачи, размещаемой на ьй позиции в плане, будем сопровождать нижним индексом в квадратных скобках. Так, например, для неопределенности длительности ьй по порядку задачи будем иметь - А^.

Утверждение 1. Минимальное значение средней неточности временной привязки при планировании независимых задач достигается в плане, для которого выполняется

А[г] < А[2] < ... А[т].

Утверждение 2. Минимальное значение суммарной взвешенной неточности временной при-

Ет г

и?о? при планировании независимых задач достигается в плане, для которого выполняется

А

[1]

А

[2]

<

и[1] и[2]

<

<

А

[т]

и[т]

3. ПЛАНИРОВАНИЕ ВЫЧИСЛИТЕЛЬНЫХ ЗАДАЧ ПРИ ЗАДАННЫХ ДИРЕКТИВНЫХ СРОКАХ

Проблема, рассматриваемая в данном разделе, является более сложной, поскольку оптимизация по критерию минимума средней неточности временной привязки должна осуществляться

при ограничениях, определяемых директивными сроками для задач. Чтобы чрезмерно не усложнять алгоритм планирования, откажемся от поиска оптимального плана и ограничимся некоторым допустимым рациональным решением. Причем в качестве основы алгоритма, как и в предыдущем случае, будем использовать сортировку задач по значению неопределенности их длительности. Предварительно определим основные понятия и рассмотрим утверждения, которые послужат теоретическим обоснованием для предлагаемого алгоритма.

Определение 1. Допустимая (недопустимая) парная перестановка - это преобразование плана, при котором две задачи исходного плана меняются местами, не нарушая директивные сроки всех планируемых задач (нарушая директивные сроки некоторых планируемых задач).

Определение 2. Парную перестановку будем называть соседней, если местами меняются соседние задачи.

Утверждение 3. Оптимальный допустимый план всегда достижим из любого исходного допустимого плана посредством допустимых соседних парных перестановок задач.

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

по п1

Пусть последовательность п содержит в задач. Тогда последней задачей начальной последовательности целевого плана будет т^^] = тр. В исходном плане эта задача тр будет располагаться на более ранней позиции, иначе она вошла бы в завершающую последовательность п, которая в результате стала бы другой. Совершим в исходном плане перестановку вперед задачи тр до завершающей последовательности п. В результате получаем план п'0 = п'0 , п' где п' = трп, а п'0 - получена из по путем исключения тр. Полученный план п0 является допустимым, а совершенная пе-

рестановка соответственно допустимой, посколь-

тр

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

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

Утверждение 4- Любая парная перестановка, упорядочивающая переставляемые задачи по критерию неопределенности длительности уменьшает среднюю неточность временной привязки задач формируемого плана.

Доказательство. Предположим, что в результате перестановки вперед задача с 1-ой позиции меняется местами с задачей, расположенной на (I + Л,)-ой позиции. Причем Д^ > Дг+ь,.

Запишем выражение для средней неточности привязки задач

т т 3-1

*=1V = -ЕЕ Дк.

т

3=2

т

3=2 к=1

Приводя подобные слагаемые, получаем.

1 т

Е = т Е(т - 3 + 1)Дз-1.

3=2

Рис. 2. Иллюстрация вытесняющего КМБ-планирован

Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.

Показать целиком