Курс Алгоритмы оптимизации, основанные на методе проб и ошибок (1121255), страница 5

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 5)

Одним из основных понятийстандарта является понятие раздела: в системе имеется определенный набор разделов, икаждая работа характеризуется номером раздела. Работы из одного раздела могутвыполняться непосредственно одна за другой, без задержек; для перехода из одногораздела в другой необходимо переключение контекста, которое требует определенноговремени.

Все работы внутри окна должны принадлежать одному разделу, таким образом,работы внутри окна могут выполняться непосредственно друг за другом, без временныхзатрат на переключение контекста, которое может производиться только междузакрытием одного окна и открытием следующего. Таким образом, для каждой работызадано время выполнения, номер раздела и директивный временной интервал выполнения.Приведем формальную постановку задачи построения расписания для такихсистем:Пусть задано множество работ:SW={ai=<si,fi,ti,pi>|i[1..n]}, где[si,fi) – директивный интервал;ti – время выполнения работы;pi – номер раздела работы.В дальнейшем будем предполагать, что для i[1..n]:sifi и tifi–si.Кроме того, заданы два параметра:  и , определяющие, соответственно,временные затраты на переключение контекста между окнами и резерв свободноговремени внутри каждого окна.Требуется построить расписание, представляющее собой набор окон:SP={wi=<Si,Fi,SWi>|i[1..m]}, гдеSi – время открытия окна;Fi – время закрытия окна;SWi={aij}SW – множество работ, выполняемых внутри окна.Будем предполагать, что окна упорядочены в порядке возрастания времениоткрытия Si.При этом должны выполняться следующие ограничения:1.

(i,j)[1..m],ij:SWiSWj= – множества работ, размещенных внутри разныхокон, не пересекаются;182. i[1..n],j[1..m],aiSWj:siSj<Fjfi – временной интервал окна лежитвнутри директивных интервалов работ, выполняющихся в окне;3. (i,j)[1..n],k[1..m],ai,ajSWk:pi=pj – разделы работ, размещенных внутриодного окна, совпадают;4. (i,j)[1..m],i<j:SjFi+ – окна не пересекаются и между любыми двумясоседними окнами есть промежуток не короче времени, необходимого напереключение контекста;5.

j  1..m :tai SW ji  2  F j  S j – суммарное время выполнения всех работ изодного окна с учетом резерва времени не больше, чем длина окна.Критериемоптимальностирасписанияявляетсяотношениеколичестваразмещенных работ к общему количеству исходно заданных работ.С материалами данного раздела можно ознакомиться в работах:1.Балаханов В.А., Костенко В.А.

Способы сведения задачи построения статико-динамическогооднопроцессорного расписания для систем реального времени к задаче нахождения на графемаршрута // Программные системы и инструменты. Тематический сборник № 8, М.: Изд-вофакультета ВМиК МГУ, 2007. – С.148-156.2.Балаханов В.А., Кокарев В. Муравьиный алгоритм построения статико-динамических расписаний иисследование его эффективности// Программные системы и инструменты. Тематический сборник №8, М.: Изд-во факультета ВМиК МГУ, 2008.1.4.3. Задача построения расписания обменов по шине с централизованнымуправлением (на примере стандарта MIL-STD 1533В)В данном подразделе приведем пример конкретной бортовой системы и протоколаработы шины.

Описание системы и протокола работы шины ограничим уровнемдетализации необходимым лишь для понимания задачи построения расписаний обменовпо шине с централизованным управлением.Система состоит из единственного канала обмена (шины) и ограниченного набораоконечныхустройств,подключенныхкэтомуканалу,которыеявляютсяисточниками/приемниками информации, передаваемой по шине. Одно из оконечныхустройств назначается контроллером шины, который управляет обменом информации иосуществляет контроль состояния других оконечных устройств в соответствии состатическим расписанием.

Эти оконечные устройства лишь выполняют адресованные имкомандыконтроллера.поочереднойпередачиОбменинформациейинформациипоосуществляетсяпринципуасинхронно"команда-ответ".путемИнформация19передается в виде сообщений, которые могут состоять из командных слов, слов данных иответных слов.Рассмотрим пример работы шины в соответствии со стандартом MIL STD[Государственный стандарт СССР «Интерфейс магистральный последовательный системы электронныхмодулей»ГОСТ26765.52-87.].Стандарт допускает основные и групповые форматысообщений. Форматы основных сообщений используются для передачи информацииодному из оконечных устройств и предусматривают выдачу им ответного слова.

Форматыгрупповыхсообщенийиспользуютсядляпередачиинформацииодновременнонескольким оконечным устройствам без выдачи ими ответных слов. Последняя группаформатов обеспечивает понижение загрузки шины, но при этом снижается надежность.Если требуется подтверждение факта приема оконечным устройством групповогосообщения, то контроллер в этом случае (используя формат основного сообщения) можетпослать оконечному устройству команды “передать ответное слово” или “передатьпоследнюю команду”, и факт приема группового сообщения может быть установленконтроллером путем анализа в ответном слове признака “принято групповое сообщение”.Каждый формат определяет количество и порядок следования командных слов, ответныхслов и слов данных. Ниже приведены примеры форматов одиночного сообщения (рис.1.1.)и группового сообщения (рис.1.2.) (КС – командное слово, ОС – ответное слово, СД –слово данных, t1, t2 – паузы).Основное сообщение (передача данных от оконечного устройства оконечномуустройству).КСКСt1ОССДСД…СДt1ОСt2следующееКСРис.1.1.

Пример формата одиночного сообщения.Контроллер должен без паузы передать команду обмена данными с адресомоконечного устройства А на прием данных и команду обмена данными с адресомоконечного устройства Б на передачу данных. Оконечное устройство Б послеустановления факта достоверности принятой команды должно передать без пауз ответноеслово и указанное в команде количество слов данных. Оконечное устройство А послеустановления факта достоверности адресованной ему информации должно передатьответное слово.20Групповое сообщение (рис.1.2.) (передача данных от оконечного устройстваоконечным устройствам).КСКСt1ОССДСД…СДt2следующееКСРис.1.2.

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

Задача построениястатических одноприборных расписаний без прерываний в общем виде может бытьсформулирована следующим образом.Дано: Множество работ, которые должны выполняться на системе J   jNjj1 . Для каждойработы заданы t j  0 - время выполнения, [ s j , f j ) - директивный интервал выполнения ивыполняется условие f j  s j  t j ; Дополнительные ограничения g i ( H , x )  0, i  4  N g на корректность расписания H ,которыеобусловленытехнологическимиособенностямишиныисистемногопрограммного обеспечения; Вектор значений технологических требований x  ( x1...x N x ) .Расписание выполнения работ, которое представляет собой упорядоченное (покритерию время начала выполнения работы) множество H   j k , s *j k H1 , j  J , Здесь k Nпорядковый номер j-ой работы в расписании, s j - время начала выполнения j-ой работы врасписании H , f j  s j  t j - время завершения выполнения j-ой работы. Множествокорректных расписаний H'*(т.е. множество S в задаче (1.1.)) определим наборомограничений:: (j  H )   fg1 : (j  H )  ( s j  s j )  ( f j  f j )g2j s j  t jg 3 : (( j , l )  H , j  l )  (( s j  sl )  ( s j  f l ))  (( f j  sl )  ( f j  f l ))21Ограничения g1,g2,g3 являются обязательными для одноприборных расписаний безпрерываний и соответственно означают:1) интервал выполнения каждой работы располагается в рамках её директивногоинтервала;2) не допустимы прерывания;3) интервалы выполнения работ не пересекаются.Задача:max HH H *'известна в теории расписаний как задача о выборе максимального числа совместимыхзаявок и является NP–трудной.

Однако есть частные задачи этой задачи, которыеявляются полиномиально разрешимыми. Например, для частной задачи:max HH H *' j: t j  f j  s jизвестен оптимальный жадный алгоритм сложности O(n·log n) [Кормен Т., Лейзерсон Ч., РивестР. Алгоритмы: построение и анализ. М.: МЦНМО, 2000.].В задаче построения статических расписаний обменов по шине с централизованнымуправлением присутствуют дополнительные ограничения:max HH H *'g i ( H , x )  0, i  4..N g ,Ограниченияg i ( H , x )  0, i  4  N gопределяются особенностями аппаратных ипрограммных средств конкретной вычислительной системы реального времени. Приведемограничения типичные для авиационных и навигационных систем для двух схеморганизации обменов: с подциклами и без подциклов.В качестве исходных данных задается множество периодических сообщенийSM  { M i  ti , ri | i  [1 ..n ]} , где ti – время передачи сообщения, ri – частота передачисообщения.

Период передачи сообщения обозначим заформируетсяJi { j  t j , s j , fмножествоj | j  [1 .. n i ]} ,i соответствующихгдеr n i   scl i –1ri. Для каждого сообщенияемуработколичествоэкземпляровсообщения, которые надо передать в интервале планирования, rscl – длительностьинтервала планирования, s j  ( j  1 )   i ;f j  j  i – соответственно левая и правая22границы директивного интервала сообщения j. Для некоторых сообщений могутбытьзаданыфазовыесдвиги,которыесужаютдирективныйинтервалсообщения, определяемый номером сообщения и периодом его передачи(рис.1.3.)Множестворабот определяется как объединение множества работсоответствующих заданным сообщениям J nJi.i 1s1f1s2φ1s3f2φ1f3φ1...0φ2Tφ22*Tφ23*TРис.

1.3. Директивные интервалы работДля схемы с подциклами (рис.1.4.) (интервал планирования разбивается на отрезкиравной длины - подциклы), возможны следующие дополнительные ограничения (gi):4) в каждом подцикле может находиться не более 1 цепочки работ и работы вцепочке следуют друг за другом без пауз;5) время выполнения работ не должно пересекать границы подцикла;6) время начала цепочки работ относительно начала соответствующего подцикла недолжно быть меньше заданного значения;7) в конце подцикла должен быть зарезервирован интервал времени, длительностькоторого не меньше, чем заданная доля длительности подцикла;8) число работ в цепочке не должно превышать заданного значения;9) сдвиг работы «вправо» по временной оси на время, не превышающее значениеравное заданному проценту от интервала «время начала выполнения работыминус время начала цепочки» не должен приводить к нарушению директивноговремени завершения работы или требования к минимальному резерву времени вконце подцикла.23подциклподциклчисло работ в цепочкецепочка работрезерв времени вначале подцикларезерв для сдвигарасписаниярезерв времени вконце подциклаРис.

Характеристики

Список файлов лекций