ИЗВЕСТИЯ РАН. ТЕОРИЯ И СИСТЕМЫ УПРАВЛЕНИЯ, 2012, № 5, с. 23-34
КОМПЬЮТЕРНЫЕ МЕТОДЫ
УДК 65.012.122
ПЛАНИРОВАНИЕ ВЫЧИСЛИТЕЛЬНОГО ПРОЦЕССА В РАСПРЕДЕЛЕННЫХ СИСТЕМАХ РЕАЛЬНОГО ВРЕМЕНИ С НЕОПРЕДЕЛЕННЫМИ ВРЕМЕНАМИ РЕШЕНИЯ ЗАДАЧ*
© 2012 г. Н. В. Колесов, М. В. Толмачева, П. В. Юхта
Санкт-Петербург, ГНЦРФ ОАО "Концерн ЦНИИ "Электроприбор" Поступила в редакцию 18.03.11 г., после доработки 27.01.12 г.
Рассматривается подход к планированию вычислительного процесса в распределенных системах реального времени. Предполагается, что продолжительность решения задач известна неточно и определяется временным интервалом. Проблема формулируется как планирование заданий, каждое из которых характеризуется своим приоритетом и состоит из ряда задач (по числу процессоров), исполняемых на разных процессорах и связанных иерархическим отношением предшествования. В основе подхода лежат алгоритмы с низкой вычислительной сложностью для субоптимального планирования равноприоритетных заданий.
Введение. Планирование вычислений является важным этапом проектирования и применения любых вычислительных систем. От качества используемого плана существенно зависят эффективность и корректность работы систем. Однако построение хороших планов — непростая задача, причем наибольшие проблемы возникают в широко распространенных на практике системах реального времени (СРВ) [1—4]. Правильность функционирования этих систем зависит не только от логической корректности выполняемых вычислений, но и от времени, за которое эти вычисления производятся. Быстродействие СРВ должно быть адекватно скорости протекания наблюдаемых или управляемых с ее участием процессов. Класс СРВ достаточно многообразен. К нему относят различные системы навигации, управления и обработки информации.
Под планированием (формированием плана) вычислительного процесса в настоящей работе понимается поиск наилучшей с точки зрения заданного критерия упорядоченности для решаемых задач. При этом будем предполагать, что задачи уже размещены по имеющимся в системе процессорам. Обычно [1] в задачах планирования различают однопроцессорные, многопроцессорные и распределенные системы. Ниже рассматриваются распределенные системы, процессоры которых имеют индивидуальную память для хранения кода программ, обмениваются информацией через каналы обмена, имеют общую шкалу времени. Характерными особенностями организации вычислительного процесса в СРВ являются периодичность и, в общем случае, разноприоритетность решаемых задач, наличие для них директивных сроков, необходимость обеспечения для интервалов решения задач достаточно точной временной привязки. Заметим, что выполнению последнего требования препятствует целый ряд факторов и, прежде всего, зависимость длительности решения задач от исходных данных. В результате момент начала любой задачи будет "плавать" из-за неопределенности в длительностях предшествующих ей задач. Для учета этой неопределенности далее будем представлять время решения задачи временным интервалом ej = [e, Jj ], j = 1, N, где jj — нижняя, а Jj — верхняя границы интервалов, N — число решаемых задач. Такую систему вслед за работой [5] будем называть недетерминированной в противоположность системам с точно известными временами исполнения, которые будем называть детерминированными.
Проблема планирования изучается в рамках двух научных направлений. Первое направление составляет теория расписаний. В основном ее решения применяются при планировании работ, в том числе и на технологических линиях [5—10]. Второе направление — это теория планирования решения задач в вычислительных системах [11—13]. Ниже будут использованы результаты обоих направлений. Наиболее сложными, с нашей точки зрения, в рассматриваемой проблематике являются вопросы планирования в распределенных системах. В литературе (чаще в теории расписаний) эта проблема обычно формулируется либо как проблема job shop (планирования
* Работа выполнена при финансовой поддержке РФФИ (грант № 10—08—00035 а).
0
KO
0
т1, 1 т1, 2
т1, 3
т1, 1
т1, 2 т1, 3
т2, 1 Т2, 2 т2, 3
iT2, 1 т2, 2 т2, 3
т3, 3 т3, 1
т3, 2
т3, 3
т3, 1 т3, 2
T d,
Ey
t
t
2
t
0
d
d
2
3
Рис. 1
набора работ), либо как проблема flow shop (планирования набора потоков). В обоих случаях речь идет о планировании равноприоритетных периодических заданий, т.е. совокупности периодических задач, связанных отношением предшествования (функционально связанных задач) типа "цепочка". Содержание первой проблемы (job shop) состоит в следующем. Необходимо
спланировать решение периодических заданий Tj, j = 1, m, имеющих n(j) задач Tkj, k = 1,n(j). Задана длительность решения каждой задачи ekj (в нашем случае ёк j = [ek , ek j], к = 1, n(j), j = 1, m). Каждая задача решается на своем процессоре. Задача Tk+1j становится готовой к решению после
завершения задачи Tk,j. С каждым заданием тj сопоставлена последовательность Vj, j = 1, m, процессоров, на которых исполняются его задачи. Эту последовательность называют последовательностью посещений. Вторую проблему (flow shop) можно определить как проблему job shop при одинаковой для всех заданий последовательности посещений. Обращаем особое внимание на то, что в обоих случаях речь идет об упорядочивании заданий, состоящих из цепочек задач, т.е. граф предшествования для задач каждого задания имеет один и тот же вид цепочки, а значит, структура системы, выполняющей эти задания, имеет вид конвейера.
На рис. 1 приведен простейший иллюстративный пример, поясняющий исполнение заданий при распределенных вычислениях. Здесь представлен случай, когда на двух процессорах P1 и P2, связанных каналом обмена (КО), исполняются с периодом T три задания: т1, т2, т3. С каждым процессором и каналом обмена на рисунке соотнесена своя временная диаграмма. На диаграммах учтены временные затраты на передачу данных по каналу обмена, хотя в дальнейшем при обсуждении алгоритмов планирования будем считать, что эти затраты включены в длительности исполняемых задач. Из-за этого учета каждое задание т j фактически состоит не из двух, а из трех задач Tij, x2j, , связанных отношением предшествования типа "цепочка". При этом первая и третья задачи каждого из заданий исполняются соответственно на первом и третьем процессорах, а вторая (задача обмена) — каналом обмена. На рисунке отмечены, во-первых, суммарное время ES выполнения всех заданий, которое определяет значение критерия эффективности плана в разд. 2, а, во-вторых, существующие для заданий директивные сроки d1, d2, d3 (вертикальные штриховые линии), которые определяют значение критерия эффективности плана в разд. 3. Видно, что значение ES может превосходить значение периода T. Конечно же, нетрудно представить ситуацию, когда и значения директивных сроков для заданий будут превышать их периоды.
В литературе приводятся решения проблемы flow shop, например, в [7—10], однако все предлагаемые алгоритмы, как правило, характеризуются высокой вычислительной сложностью. Кроме того, в многочисленных публикациях [13, 14] освещаются различные аспекты проблемы планирования при распределенных вычислениях. Среди них — подход, использующий сведение рассматриваемой проблемы к проблеме планирования в однопроцессорной системе путем формирования частных директивных сроков для каждого процессора на основе заданных директив-
ных сроков для распределенных вычислений. Нередко исследуемая проблема ограничивается планированием канала обмена [15, 16] или разработкой тестов планируемости [17, 18], т.е. поиска условий, при проверке которых можно судить о существовании или несуществовании искомого плана. В целом приходится констатировать отсутствие в настоящее время эффективных и достаточно простых в вычислительном плане методов для планирования вычислительного процесса в распределенных системах реального времени. Кроме того, анализ особенностей ряда распределенных систем реального времени показывает, что модель распределенных вычислений будет более адекватной, если предположить, что граф предшествования для задач планируемых заданий имеет вид не цепочки, а иерархии. Причина такого вывода обычно — использование при обработке информации в системах реального времени процедуры комплексирования, когда при формировании значения некоторого параметра используется информация от многих датчиков. Ясно, что с учетом такого уточнения рассматриваемая проблема планирования приобретает более общий характер. Для этой обобщенной постановки авторами настоящей статьи в работах [19, 20] были предложены решения, которые далее коротко излагаются в виде их интервальных аналогов.
Характерной особенностью ряда известных алгоритмов планирования в системах реального времени является то, что, как правило, анализу сразу подвергается общее множество разнопри-оритетных планируемых заданий. Идея рассматриваемого подхода в определенном смысле противоположна. В нем предлагается предварительно разбить множество планируемых заданий на группы (потоки), объединяющие равноприоритетные задания, затем осуществить планирование в соответствии с заданным критерием внутри потоков и далее, воспользовавшись вытесняющим ЯМ8-алгоритмом [1], произвести объединение полученных частных однопоточных планов в общий многопоточный план.
Укажем на некоторые дополнительные предположения, которые положены в основу предлагаемых решений и привнесены из практики построения систем реального времени. Прежде всего, допустим, что все планируемые задания независимы. В противном случае их нельзя было бы произвольно переставлять в поисках наилучшей упорядоченности. Кроме того, будем считать, что передача и прием данных между задачами одного задания, выполняемыми на смежных процессорах, осуществляется без дополнительных задержек по их готовности. Если же реально такие задержки существуют, например, из-за использования канала обмена с централизованным управлением, то будем считать, что они учтены в длительностях решения задач. Наконец, будем предполагать, что в рассматриваемых системах есть определенная свобода при выборе периодов исполнения задач. Это позволяет с разноприоритетными задачами соотноси
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.