ИЗВЕСТИЯ РАН. ТЕОРИЯ И СИСТЕМЫ УПРАВЛЕНИЯ, 2013, № 6, с. 87-96
СИСТЕМНЫЙ АНАЛИЗ И ИССЛЕДОВАНИЕ ОПЕРАЦИЙ
УДК 517.977.5
АЛГОРИТМ ПОСТРОЕНИЯ ОДНОПРИБОРНЫХ РАСПИСАНИЙ, ОСНОВАННЫЙ НА СХЕМЕ МУРАВЬИНЫХ КОЛОНИЙ
© 2013 г. В. А. Костенко, А. В. Плакунов
Москва, МГУ
Поступила в редакцию 29.04.13 г., после доработки 26.06.13 г.
Приведена математическая постановка задачи построения расписания обменов по каналу с централизованным управлением. Данная задача возникает при проектировании информационно-управляющих систем реального времени. Проведен анализ возможных подходов к построению алгоритмов, основанных на схеме муравьиных колоний, и приведены результаты экспериментального сравнения предложенного алгоритма с жадными алгоритмами.
DOI: 10.7868/S0002338813060085
Введение. В бортовых системах реального времени широко используется архитектура, основанная на каналах с централизованным управлением. Примерами каналов с централизованным управлением являются MIL STD-1553B (МКИО ГОСТ Р52070-2003) [1], STANAG 3910 [2], FC-AE-1553 [3].
Канал обеспечивает обмен данными между устройствами, присоединенными к каналу (далее — оконечные устройства). Обмен представляет собой последовательность передач прикладных и служебных данных между оконечными устройствами. Время начала каждого обмена определяет расписание, которое строят заранее и которое не меняется в ходе функционирования бортовой системы. Расписание исполняется контроллером канала, который является одним из оконечных устройств. Только контроллер канала может инициировать обмен данными; другие оконечные устройства выполняют команды, отданные контроллером (схема ведущий—подчиненный).
Задача построения расписания обменов по каналу с централизованным управлением относится к классу задач построения одноприборных расписаний без прерываний и известна в теории расписаний как задача о выборе максимального числа совместимых заявок, которая является ^Р-трудной. В отличие от задач о выборе максимального числа совместимых заявок, рассматриваемых в теории расписаний, в задаче построения обменов по каналу с централизованным управлением накладываются дополнительные ограничения на корректность расписания, которые обусловлены особенностями программных и аппаратных средств бортовой системы [4—6].
Основной проблемой при использовании алгоритмов, основанных на жадных стратегиях и стратегиях ограниченного перебора, является их настройка на решение частных задач (наложены ограничения на возможные значения входных данных) [7, 8]. Это связано с проблемой формирования ограничений на исходные данные таким образом, чтобы "четко" выделить частную задачу, для которой алгоритм будет гарантировано находить решение с приемлемой точностью и сложностью. В большинстве случаев возможно получение лишь статистических оценок точности и сложности алгоритма. Муравьиные алгоритмы [9, 10] позволяют автоматически настраиваться на пример задачи (заданы конкретные значения исходных данных) путем дополнительной разметки исходных данных, которая используется для построения решения на каждой итерации алгоритма и уточняется по мере увеличения числа итераций. Другими словами, при использовании муравьиных алгоритмов не возникает проблема "четкого" выделения частной задачи.
Алгоритмы, основанные на использовании схемы муравьиных колоний, были успешно применимы для решения таких комбинаторных задач, как квадратичная задача о назначениях [11], задача упаковки в контейнеры [12], задачи построения расписаний [13—15]. В данной работе предлагается алгоритм, основанный на использовании схемы муравьиных колоний, для решения задачи построения расписания обменов по каналу с централизованным управлением.
В первом разделе данной работы рассматривается задача построения расписания обменов по каналу с централизованным управлением, во втором разделе приведена общая схема муравьиных алгоритмов и сформулированы задачи, которые надо решить при построении муравьиных
КС КС
КС КС
OC
СД
СД
СД
ОС
J vn /
Следующее сообщение
—; КС
Следующее сообщение
ОС
СД
СД
СД
КС
f
Рис. 1. Схемы передачи данных от оконечного устройства: а — другому оконечному устройству, б — нескольким оконечным устройствам
t
t
t
1
1
a
t
t
2
алгоритмов для решения задач построения расписаний. В третьем разделе приведено решение этих задач для алгоритма построения расписания обменов по каналу с централизованным управлением, в четвертом разделе приведены результаты исследования свойств предложенного алгоритма.
1. Задача построения расписания обменов. Система состоит из единственного канала обмена (шины) и ограниченного набора оконечных устройств, подключенных к этому каналу, которые являются источниками/приемниками информации, передаваемой по шине. Одно из оконечных устройств назначается контроллером шины, который управляет обменом информации и осуществляет контроль состояния других оконечных устройств в соответствии со статическим расписанием. Эти оконечные устройства лишь выполняют адресованные им команды контроллера. Обмен информацией осуществляется асинхронно путем поочередной передачи информации по принципу "команда—ответ". Информация передается в виде сообщений, которые могут состоять из командных слов, слов данных и ответных слов.
Рассмотрим пример работы шины в соответствии со стандартом MIL STD [1]. Стандарт допускает основные и групповые форматы сообщений. Форматы основных сообщений используются для передачи информации одному из оконечных устройств и предусматривают выдачу им ответного слова. Форматы групповых сообщений применяются для передачи информации одновременно нескольким оконечным устройствам без выдачи ими ответных слов. Последняя группа форматов обеспечивает понижение загрузки шины, но при этом снижается надежность. Если требуется подтверждение факта приема оконечным устройством группового сообщения, то контроллер в этом случае (используя формат основного сообщения) может послать оконечному устройству команды "передать ответное слово" или "передать последнюю команду", и факт приема группового сообщения может быть установлен контроллером путем анализа в ответном слове признака "принято групповое сообщение". Каждый формат определяет количество и порядок следования командных слов, ответных слов и слов данных. Ниже приведены примеры форматов одиночного (а) и группового (б) сообщений (рис. 1). Здесь КС — командное слово, ОС — ответное слово, СД — слово данных, t1, t2 — паузы.
Контроллер должен без паузы передать команду обмена данными с адресом оконечного устройства А на прием данных и команду обмена данными с адресом оконечного устройства Б на передачу данных. Оконечное устройство Б после установления факта достоверности принятой команды должно передать без пауз ответное слово и указанное в команде количество слов данных. Оконечное устройство А после установления факта достоверности адресованной ему информации должно передать ответное слово.
Контроллер должен передать без паузы групповую команду обмена данными на прием данных и команду обмена данными с адресом одного оконечного устройства на передачу данных. Это оконечное устройство после установления факта достоверности принятого командного слова должно передать без пауз ответное слово и указанное в команде количество слов данных.
В качестве исходных данных для задачи построения расписания обменов задается множество периодических сообщений SM = {Mt = (th r)}, где i = 1, n, ti — время передачи сообщения, r j — частота передачи сообщения. Период передачи сообщения обозначим за Ti = 1/r. Для каждого сообщения формируется множество соответствующих ему работ J' = {j = (tj, Sj, fj)}, где j = 1, nt, П = [rsd/t ' — количество экземпляров сообщения, которые надо передать в интервале планирования, rscI — длительность интервала планирования, Sj = (j - 1) • xt; fj = j • т — соответственно левая и правая границы директивного интервала сообщения j. Для некоторых сообщений могут
s1 f1 s2 /2 s3 /3
Ф1 - Ф1 - Ф1
г - -
L L - -- — ... t
0 Ф2 T¡ Ф2 2т, ^2 3х,
Рис. 2. Директивные интервалы работ
быть заданы левый и правый фазовые сдвиги, обозначаемые ф1 и ф2 соответственно, которые сужают директивный интервал сообщения, вычисляемый в зависимости от номера сообщения и периода его передачи (рис. 2). Множество работ определяется как объединение множества работ соответствующих заданным сообщениям
n
J=и
i = 1
Шина может рассматриваться как одноприборное устройство, обслуживающее исходно задан-
Í ч N ■
ный набор работ J = {j} ,'=х, которые должны выполняться без прерываний. Для каждой работы заданы tj > 0 — время выполнения, [sj, f j) — директивный интервал, и верно условие f - Sj > tj. Расписание представляет собой упорядоченное по критерию момента старта работы множество
H = {jk, s*>N=1, j е J, где к — порядковый номер j-й работы в расписании, Nk — количество работ, s * — момент старта j-й работы в расписании H, f* = s* + tj — момент завершения j-й работы. Множество корректных расписаний H* определим набором основных ограничений:
gi: (Vj е H) ^ ((s* > sj) a (f* < f)), g2: (Vje H) ^ (f* - s* = tj),
g3: (V(j,l) е H,j Ф l) ^ (((s* < s*) v (s* > f*)) a ((f* < s*) v (f* > f *))).
Ограничения g1, g2, g3 являются обязательными для одноприборных расписаний без прерываний и соответственно означают:
1) интервал выполнения каждой работы располагается в рамках ее директивного интервала;
2) не допустимы прерывания;
3) интервалы выполнения работ не пересекаются.
Для расписания обменов по каналу с централизованным управлением присутствуют дополнительные к основным ограничения на корректность расписания, которые обусловлены особенностями аппаратных и программных средств конкретной системы реального времени. Для схемы организации обменов с подциклами (интервал планирования разбивается на отрезки равной длины — подциклы, см. рис. 3) возможны следующие дополнительные ограничения g¡:
4) в каждом подцикле может находиться не более одной цепочки работ и работы в цепочке следуют друг за другом без пауз;
5) время выполнения работ не должно пересекать границы подцикла;
6) время начала це
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.